Parameter-free online learning via model selection
This work addresses the challenge of parameter-free online learning for researchers and practitioners, offering a more general and efficient approach compared to previous methods limited to Hilbert spaces, though it builds incrementally on existing concepts.
The paper tackles the problem of model selection in online learning by introducing a generic meta-algorithm framework that achieves oracle inequalities under minimal structural assumptions, resulting in the first computationally efficient parameter-free algorithms for arbitrary Banach spaces and new results for matrix classes and non-linear classes.
We introduce an efficient algorithmic framework for model selection in online learning, also known as parameter-free online learning. Departing from previous work, which has focused on highly structured function classes such as nested balls in Hilbert space, we propose a generic meta-algorithm framework that achieves online model selection oracle inequalities under minimal structural assumptions. We give the first computationally efficient parameter-free algorithms that work in arbitrary Banach spaces under mild smoothness assumptions; previous results applied only to Hilbert spaces. We further derive new oracle inequalities for matrix classes, non-nested convex sets, and $\mathbb{R}^{d}$ with generic regularizers. Finally, we generalize these results by providing oracle inequalities for arbitrary non-linear classes in the online supervised learning model. These results are all derived through a unified meta-algorithm scheme using a novel "multi-scale" algorithm for prediction with expert advice based on random playout, which may be of independent interest.