Online learning with low rank experts

Elad Hazan; Tomer Koren; Roi Livni; Yishay Mansour

Online learning with low rank experts

Elad Hazan, Tomer Koren, Roi Livni, Yishay Mansour

Research output: Contribution to journal › Conference article › peer-review

Abstract

We consider the problem of prediction with expert advice when the losses of the experts have low-dimensional structure: they are restricted to an unknown d-dimensional subspace. We devise algorithms with regret bounds that are independent of the number of experts and depend only on the rank d. For the stochastic model we show a tight bound of Θp√ dTq, and extend it to a setting of an approximate d subspace. For the adversarial model we show an upper bound of Opd√ Tq and a lower bound of Ωp√ dTq.

Original language	English (US)
Pages (from-to)	1096-1114
Number of pages	19
Journal	Journal of Machine Learning Research
Volume	49
Issue number	June
State	Published - Jun 6 2016
Event	29th Conference on Learning Theory, COLT 2016 - New York, United States Duration: Jun 23 2016 → Jun 26 2016

All Science Journal Classification (ASJC) codes

Control and Systems Engineering
Software
Statistics and Probability
Artificial Intelligence

Cite this

@article{f9a05c541a3f499e9c9bdeb0832a363a,

title = "Online learning with low rank experts",

abstract = "We consider the problem of prediction with expert advice when the losses of the experts have low-dimensional structure: they are restricted to an unknown d-dimensional subspace. We devise algorithms with regret bounds that are independent of the number of experts and depend only on the rank d. For the stochastic model we show a tight bound of Θp√ dTq, and extend it to a setting of an approximate d subspace. For the adversarial model we show an upper bound of Opd√ Tq and a lower bound of Ωp√ dTq.",

author = "Elad Hazan and Tomer Koren and Roi Livni and Yishay Mansour",

note = "Publisher Copyright: {\textcopyright} 2016 E. Hazan, T. Koren, R. Livni & Y. Mansour.; 29th Conference on Learning Theory, COLT 2016 ; Conference date: 23-06-2016 Through 26-06-2016",

year = "2016",

month = jun,

day = "6",

language = "English (US)",

volume = "49",

pages = "1096--1114",

journal = "Journal of Machine Learning Research",

issn = "1532-4435",

publisher = "Microtome Publishing",

number = "June",

}

TY - JOUR

T1 - Online learning with low rank experts

AU - Hazan, Elad

AU - Koren, Tomer

AU - Livni, Roi

AU - Mansour, Yishay

PY - 2016/6/6

Y1 - 2016/6/6

N2 - We consider the problem of prediction with expert advice when the losses of the experts have low-dimensional structure: they are restricted to an unknown d-dimensional subspace. We devise algorithms with regret bounds that are independent of the number of experts and depend only on the rank d. For the stochastic model we show a tight bound of Θp√ dTq, and extend it to a setting of an approximate d subspace. For the adversarial model we show an upper bound of Opd√ Tq and a lower bound of Ωp√ dTq.

AB - We consider the problem of prediction with expert advice when the losses of the experts have low-dimensional structure: they are restricted to an unknown d-dimensional subspace. We devise algorithms with regret bounds that are independent of the number of experts and depend only on the rank d. For the stochastic model we show a tight bound of Θp√ dTq, and extend it to a setting of an approximate d subspace. For the adversarial model we show an upper bound of Opd√ Tq and a lower bound of Ωp√ dTq.

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

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

M3 - Conference article

AN - SCOPUS:85046997401

SN - 1532-4435

VL - 49

SP - 1096

EP - 1114

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

IS - June

T2 - 29th Conference on Learning Theory, COLT 2016

Y2 - 23 June 2016 through 26 June 2016

ER -

Online learning with low rank experts

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this