@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",
year = "2015",
month = jan,
day = "1",
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",
note = "32nd International Conference on Machine Learning, ICML 2015 ; Conference date: 06-07-2015 Through 11-07-2015",
}