License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2017.45
URN: urn:nbn:de:0030-drops-81518
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8151/
Go to the corresponding LIPIcs Volume Portal

Juba, Brendan

Conditional Sparse Linear Regression

pdf-format:
LIPIcs-ITCS-2017-45.pdf (0.4 MB)

Abstract

Machine learning and statistics typically focus on building models that capture the vast majority of the data, possibly ignoring a small subset of data as "noise" or "outliers." By contrast, here we consider the problem of jointly identifying a significant (but perhaps small) segment of a population in which there is a highly sparse linear regression fit, together with the coefficients for the linear fit. We contend that such tasks are of interest both because the models themselves may be able to achieve better predictions in such special cases, but also because they may aid our understanding of the data. We give algorithms for such problems under the sup norm, when this unknown segment of the population is described by a k-DNF condition and the regression fit is s-sparse for constant k and s. For the variants of this problem when the regression fit is not so sparse or using expected error, we also give a preliminary algorithm and highlight the question as a challenge for future work.

BibTeX - Entry

@InProceedings{juba:LIPIcs:2017:8151,
  author =	{Brendan Juba},
  title =	{{Conditional Sparse Linear Regression}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{45:1--45:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Christos H. Papadimitriou},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8151},
  URN =		{urn:nbn:de:0030-drops-81518},
  doi =		{10.4230/LIPIcs.ITCS.2017.45},
  annote =	{Keywords: linear regression, conditional regression, conditional distribution search}
}

Keywords: linear regression, conditional regression, conditional distribution search
Collection: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Issue Date: 2017
Date of publication: 28.11.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI