Online Learning with Low Rank Experts

Elad Hazan, Tomer Koren, Roi Livni, Yishay Mansour
29th Annual Conference on Learning Theory, PMLR 49:1096-1114, 2016.

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 Θ(\sqrtdT), and extend it to a setting of an approximate d subspace. For the adversarial model we show an upper bound of O(d\sqrtT) and a lower bound of Ω(\sqrtdT).

Cite this Paper

BibTeX
@InProceedings{pmlr-v49-hazan16, title = {Online Learning with Low Rank Experts}, author = {Hazan, Elad and Koren, Tomer and Livni, Roi and Mansour, Yishay}, booktitle = {29th Annual Conference on Learning Theory}, pages = {1096--1114}, year = {2016}, editor = {Feldman, Vitaly and Rakhlin, Alexander and Shamir, Ohad}, volume = {49}, series = {Proceedings of Machine Learning Research}, address = {Columbia University, New York, New York, USA}, month = {23--26 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v49/hazan16.pdf}, url = {https://proceedings.mlr.press/v49/hazan16.html}, 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 Θ(\sqrtdT), and extend it to a setting of an approximate d subspace. For the adversarial model we show an upper bound of O(d\sqrtT) and a lower bound of Ω(\sqrtdT). } }
Endnote
%0 Conference Paper %T Online Learning with Low Rank Experts %A Elad Hazan %A Tomer Koren %A Roi Livni %A Yishay Mansour %B 29th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2016 %E Vitaly Feldman %E Alexander Rakhlin %E Ohad Shamir %F pmlr-v49-hazan16 %I PMLR %P 1096--1114 %U https://proceedings.mlr.press/v49/hazan16.html %V 49 %X 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 Θ(\sqrtdT), and extend it to a setting of an approximate d subspace. For the adversarial model we show an upper bound of O(d\sqrtT) and a lower bound of Ω(\sqrtdT).
RIS
TY - CPAPER TI - Online Learning with Low Rank Experts AU - Elad Hazan AU - Tomer Koren AU - Roi Livni AU - Yishay Mansour BT - 29th Annual Conference on Learning Theory DA - 2016/06/06 ED - Vitaly Feldman ED - Alexander Rakhlin ED - Ohad Shamir ID - pmlr-v49-hazan16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 49 SP - 1096 EP - 1114 L1 - http://proceedings.mlr.press/v49/hazan16.pdf UR - https://proceedings.mlr.press/v49/hazan16.html 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 Θ(\sqrtdT), and extend it to a setting of an approximate d subspace. For the adversarial model we show an upper bound of O(d\sqrtT) and a lower bound of Ω(\sqrtdT). ER -
APA
Hazan, E., Koren, T., Livni, R. & Mansour, Y.. (2016). Online Learning with Low Rank Experts. 29th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 49:1096-1114 Available from https://proceedings.mlr.press/v49/hazan16.html.

Related Material