Online Learning with Many Experts
This addresses scalability issues in online learning for applications with many experts, such as low-rank models, but is incremental as it builds on prior work like Hazan et al. (2016).
The paper tackles the problem of prediction with expert advice when the number of experts is extremely large or infinite, achieving a tight regret bound of ̃O(εT + N + √(NT)) where N is the empirical ε-covering number.
We study the problem of prediction with expert advice when the number of experts in question may be extremely large or even infinite. We devise an algorithm that obtains a tight regret bound of $\widetilde{O}(εT + N + \sqrt{NT})$, where $N$ is the empirical $ε$-covering number of the sequence of loss functions generated by the environment. In addition, we present a hedging procedure that allows us to find the optimal $ε$ in hindsight. Finally, we discuss a few interesting applications of our algorithm. We show how our algorithm is applicable in the approximately low rank experts model of Hazan et al. (2016), and discuss the case of experts with bounded variation, in which there is a surprisingly large gap between the regret bounds obtained in the statistical and online settings.