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 language | English (US) |
|---|---|
| Title of host publication | 32nd International Conference on Machine Learning, ICML 2015 |
| Editors | David Blei, Francis Bach |
| Publisher | International Machine Learning Society (IMLS) |
| Pages | 257-266 |
| Number of pages | 10 |
| ISBN (Electronic) | 9781510810587 |
| State | Published - Jan 1 2015 |
| Event | 32nd International Conference on Machine Learning, ICML 2015 - Lile, France Duration: Jul 6 2015 → Jul 11 2015 |
Publication series
| Name | 32nd International Conference on Machine Learning, ICML 2015 |
|---|---|
| Volume | 1 |
Other
| Other | 32nd International Conference on Machine Learning, ICML 2015 |
|---|---|
| Country | France |
| City | Lile |
| Period | 7/6/15 → 7/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).