TY - JOUR
T1 - Online learning with low rank experts
AU - Hazan, Elad
AU - Koren, Tomer
AU - Livni, Roi
AU - Mansour, Yishay
N1 - Funding Information:
Elad Hazan acknowledges support from the National Science Foundation grant IIS-1523815. Roi Livni is a recipient of the Google Europe Fellowship in Learning Theory, and this research is supported in part by this Google Fellowship. Yishay Mansour is supported in part by the Israeli Centers of Research Excellence (I-CORE) program, (Center No. 4/11), by a grant from the Israel Science Foundation (ISF), by a grant from United States-Israel Binational Science Foundation (BSF) and by a grant from the Len Blavatnik and the Blavatnik Family Foundation. The research leading to these results has received funding from the European Union’s Seventh Framework Programme (FP7/2007-2013) under grant agreement n˝ 336078 ERC-SUBLRN.
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 -