Classification with low rank and missing data

Elad Hazan; Roi Livni; Yishay Mansour

Classification with low rank and missing data

Elad Hazan, Roi Livni, Yishay Mansour

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

Access to Document

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

Cite this

@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",

}

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. 32nd International Conference on Machine Learning, ICML 2015, vol. 1, International Machine Learning Society (IMLS), pp. 257-266, 32nd International Conference on Machine Learning, ICML 2015, Lile, France, 7/6/15.

Classification with low rank and missing data. / Hazan, Elad; Livni, Roi; Mansour, Yishay.

32nd International Conference on Machine Learning, ICML 2015. ed. / David Blei; Francis Bach. International Machine Learning Society (IMLS), 2015. p. 257-266 (32nd International Conference on Machine Learning, ICML 2015; Vol. 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Classification with low rank and missing data

AU - Hazan, Elad

AU - Livni, Roi

AU - Mansour, Yishay

PY - 2015/1/1

Y1 - 2015/1/1

N2 - 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.

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.

UR - http://www.scopus.com/inward/record.url?scp=84969506331&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84969506331&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84969506331

T3 - 32nd International Conference on Machine Learning, ICML 2015

SP - 257

EP - 266

BT - 32nd International Conference on Machine Learning, ICML 2015

A2 - Blei, David

A2 - Bach, Francis

PB - International Machine Learning Society (IMLS)

T2 - 32nd International Conference on Machine Learning, ICML 2015

Y2 - 6 July 2015 through 11 July 2015

ER -