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

Software
Control and Systems Engineering
Statistics and Probability
Artificial Intelligence

Fingerprint Dive into the research topics of 'Online learning with low rank experts'. Together they form a unique fingerprint.

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

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

note = "29th Conference on Learning Theory, COLT 2016 ; Conference date: 23-06-2016 Through 26-06-2016",

}

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

VL - 49

SP - 1096

EP - 1114

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

SN - 1532-4435

IS - June

T2 - 29th Conference on Learning Theory, COLT 2016

Y2 - 23 June 2016 through 26 June 2016

ER -