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.


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).

Related Material