@inproceedings{df42055384ff4cbd849407461f90aa62,
title = "Classification with low rank and missing data",
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.",
author = "Elad Hazan and Roi Livni and Yishay Mansour",
note = "Funding Information: EH: This research was supported in part by the European Research Council project SUBLRN and the Israel Science Foundation grant 810/11. RL is a recipient of the Google Europe Fellowship in Learning Theory, and this research is supported in part by this Google Fellowship. YM: This research was supported in part by The Israeli Centers of Research Excellence (I-CORE) program, (Center No. 4/11), by a grant from the Israel Science Foundation, by a grant from United States-Israel Binational Science Foundation (BSF).; 32nd International Conference on Machine Learning, ICML 2015 ; Conference date: 06-07-2015 Through 11-07-2015",
year = "2015",
language = "English (US)",
series = "32nd International Conference on Machine Learning, ICML 2015",
publisher = "International Machine Learning Society (IMLS)",
pages = "257--266",
editor = "David Blei and Francis Bach",
booktitle = "32nd International Conference on Machine Learning, ICML 2015",
}