Linear regression with limited observation

Elad Hazan, Tomer Koren

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

Abstract

We consider the most common variants of linear regression, including Ridge, Lasso and Support-vector regression, in a setting where the learner is allowed to observe only a fixed number of attributes of each example at training time. We present simple and efficient algorithms for these problems: for Lasso and Ridge regression they need the same total number of attributes (up to constants) as do full-information algorithms, for reaching a certain accuracy. For Support-vector regression, we require exponentially less attributes compared to the state of the art. By that, we resolve an open problem recently posed by Cesa-Bianchi et al. (2010). Experiments show the theoretical bounds to be justified by superior performance compared to the state of the art.

Original languageEnglish (US)
Title of host publicationProceedings of the 29th International Conference on Machine Learning, ICML 2012
Pages807-814
Number of pages8
StatePublished - Oct 10 2012
Externally publishedYes
Event29th International Conference on Machine Learning, ICML 2012 - Edinburgh, United Kingdom
Duration: Jun 26 2012Jul 1 2012

Publication series

NameProceedings of the 29th International Conference on Machine Learning, ICML 2012
Volume1

Other

Other29th International Conference on Machine Learning, ICML 2012
CountryUnited Kingdom
CityEdinburgh
Period6/26/127/1/12

All Science Journal Classification (ASJC) codes

  • Human-Computer Interaction
  • Education

Fingerprint Dive into the research topics of 'Linear regression with limited observation'. Together they form a unique fingerprint.

  • Cite this

    Hazan, E., & Koren, T. (2012). Linear regression with limited observation. In Proceedings of the 29th International Conference on Machine Learning, ICML 2012 (pp. 807-814). (Proceedings of the 29th International Conference on Machine Learning, ICML 2012; Vol. 1).