Classification with Low Rank and Missing Data

Elad Hazan, Roi Livni, Yishay Mansour
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:257-266, 2015.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-hazan15, title = {Classification with Low Rank and Missing Data}, author = {Hazan, Elad and Livni, Roi and Mansour, Yishay}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {257--266}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/hazan15.pdf}, url = {https://proceedings.mlr.press/v37/hazan15.html}, 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.} }
Endnote
%0 Conference Paper %T Classification with Low Rank and Missing Data %A Elad Hazan %A Roi Livni %A Yishay Mansour %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-hazan15 %I PMLR %P 257--266 %U https://proceedings.mlr.press/v37/hazan15.html %V 37 %X 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.
RIS
TY - CPAPER TI - Classification with Low Rank and Missing Data AU - Elad Hazan AU - Roi Livni AU - Yishay Mansour BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-hazan15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 257 EP - 266 L1 - http://proceedings.mlr.press/v37/hazan15.pdf UR - https://proceedings.mlr.press/v37/hazan15.html AB - 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. ER -
APA
Hazan, E., Livni, R. & Mansour, Y.. (2015). Classification with Low Rank and Missing Data. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:257-266 Available from https://proceedings.mlr.press/v37/hazan15.html.

Related Material