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 $\Theta(\sqrt{dT})$, and extend it to a setting of an approximate $d$ subspace. For the adversarial model we show an upper bound of $O(d\sqrt{T})$ and a lower bound of $\Omega(\sqrt{dT})$.
Cite
Text
Hazan et al. "Online Learning with Low Rank Experts." Annual Conference on Computational Learning Theory, 2016.Markdown
[Hazan et al. "Online Learning with Low Rank Experts." Annual Conference on Computational Learning Theory, 2016.](https://mlanthology.org/colt/2016/hazan2016colt-online/)BibTeX
@inproceedings{hazan2016colt-online,
title = {{Online Learning with Low Rank Experts}},
author = {Hazan, Elad and Koren, Tomer and Livni, Roi and Mansour, Yishay},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2016},
pages = {1096-1114},
url = {https://mlanthology.org/colt/2016/hazan2016colt-online/}
}