Classification with low rank and missing data

Elad Hazan, Roi Livni, Yishay Mansour

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

15 Scopus citations

Abstract

We consider classification and regression tasks where we have missing data and assume that the (clean) data resides in a low rank subspace. Finding a hidden subspace is known to be computationally hard. Nevertheless, using a non-proper formulation we give an efficient agnostic algorithm that classifies as good as the best linear classifier coupled with the best low-dimensional subspace in which the data resides. A direct implication is that our algorithm can linearly (and non-linearly through kernels) classify provably as well as the best classifier that has access to the full data.

Original languageEnglish (US)
Title of host publication32nd International Conference on Machine Learning, ICML 2015
EditorsDavid Blei, Francis Bach
PublisherInternational Machine Learning Society (IMLS)
Pages257-266
Number of pages10
ISBN (Electronic)9781510810587
StatePublished - Jan 1 2015
Event32nd International Conference on Machine Learning, ICML 2015 - Lile, France
Duration: Jul 6 2015Jul 11 2015

Publication series

Name32nd International Conference on Machine Learning, ICML 2015
Volume1

Other

Other32nd International Conference on Machine Learning, ICML 2015
CountryFrance
CityLile
Period7/6/157/11/15

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Human-Computer Interaction

Fingerprint Dive into the research topics of 'Classification with low rank and missing data'. Together they form a unique fingerprint.

  • Cite this

    Hazan, E., Livni, R., & Mansour, Y. (2015). Classification with low rank and missing data. In D. Blei, & F. Bach (Eds.), 32nd International Conference on Machine Learning, ICML 2015 (pp. 257-266). (32nd International Conference on Machine Learning, ICML 2015; Vol. 1). International Machine Learning Society (IMLS).