Online Learning with Low Rank Experts
This work addresses a fundamental challenge in online learning for scenarios with many experts but structured losses, offering improved efficiency for applications like recommendation systems or portfolio management.
The paper tackles the problem of prediction with expert advice when expert losses lie in a low-dimensional subspace, achieving regret bounds independent of the number of experts and dependent only on the rank d, with tight bounds like Θ(√(dT)) in stochastic settings and O(d√T) in adversarial settings.
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 $Θ(\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 $Ω(\sqrt{dT})$.