Abstract
This paper introduces a generic and computationally efficient framework for parameter-free online learning. Traditional online learning algorithms often require prior knowledge of the optimal model's complexity (e.g., the norm of the comparator) to achieve optimal regret. We introduce a novel "multi-scale" expert advice algorithm that enables automatic adaptation to the complexity of the best-performing model without manual tuning. Our framework extends model selection guarantees from restricted Hilbert spaces to arbitrary Banach spaces and a wide range of non-linear learning tasks, achieving general oracle inequalities across diverse settings such as high-dimensional matrices and non-nested hypothesis sets.
Introduction
In the field of online learning, a learner iteratively makes predictions and receives feedback in the form of loss functions. A fundamental challenge in this setting is model selection: determining the appropriate "size" or complexity for the hypothesis set $\mathcal{W}$. For instance, when $\mathcal{W}$ is a ball in a vector space, choosing a radius that is too small leads to high approximation error, while a radius that is too large results in high estimation error (regret).
Historically, achieving an optimal balance—known as an oracle inequality—required the learner to know the norm of the optimal comparator in advance to properly tune the learning rate. While "parameter-free" methods have been developed to address this, they were largely confined to specific structures like nested balls in Hilbert spaces. This work seeks a unified, efficient approach to perform model selection across diverse mathematical settings, including Banach spaces and non-linear function classes.
Problem Formulation
The paper focuses on the standard framework of Online Convex Optimization (OCO). In this protocol, a learner selects a strategy from a convex decision set, and an adversary (Nature) reveals a convex loss function.
The goal is to minimize the cumulative regret, which is the difference between the learner's total loss and the loss of the best fixed strategy in hindsight. The challenge addressed here is doing so when the optimal strategy's norm is unknown.
Methodology
The authors propose a hierarchical meta-algorithmic approach consisting of three primary components:
1. MultiScaleFTPL (Algorithm 3)
This is the core engine of the framework. It is a variation of the "Follow the Perturbed Leader" (FTPL) algorithm designed for scenarios where different "experts" (models) have different loss scales. Standard aggregation algorithms typically scale regret based on the global maximum possible loss. In contrast, MultiScaleFTPL ensures that the regret for each expert scales only with its own specific loss range. This is achieved through a novel "multi-scale" perturbation mechanism based on random playout using Rademacher variables.
2. MultiScaleOCO (Algorithm 4)
This wrapper applies the multi-scale expert logic specifically to OCO. It operates by running multiple sub-algorithms (such as Mirror Descent) on hypothesis sets of increasing size. MultiScaleFTPL is then used to aggregate the predictions of these sub-algorithms, effectively selecting the best scale dynamically.
3. MultiScaleLearning (Algorithm 5)
This is a further generalization intended for online supervised learning with arbitrary non-linear classes. The mathematical foundation involves proving that the "relaxation" (a tool for designing online algorithms) is admissible, ensuring cumulative regret remains bounded even when experts operate at wildly different scales.
Key Insights: Scale-Sensitivity and Geometry
A critical insight of this work is Scale-Sensitive Regret. Standard expert aggregation fails in model selection because it treats all experts as having the same worst-case loss. By making the algorithm scale-sensitive, the learner can compete with a massive model without being penalized by that model's potential losses while it is actually tracking a smaller, more effective one.
Furthermore, the paper moves Beyond Hilbert Spaces. Most prior work relied on the specific geometry of $L_2$ norms. This research demonstrates that as long as a space is uniformly convex (a property of Banach spaces), parameter-free learning is achievable. The use of Random Playout as a Regularizer—specifically drawing sign vectors—acts as a sophisticated regularization technique that adapts naturally to the multi-scale nature of the problem.
Key Results
The framework yields several significant theoretical advancements:
- General Oracle Inequalities: The authors derive the first computationally efficient parameter-free algorithms for arbitrary Banach spaces. For a comparator $w$, the regret scales as $O(\|w\| \sqrt{n \log(\|w\|n)})$.
- Simultaneous $\ell_p$ Norms: The proposed algorithm can satisfy oracle inequalities for many different $\ell_p$ norms at the same time.
- Matrix and PCA Applications: The framework provides new results for Online PCA (adapting to unknown optimal rank $k$) and Matrix Multiplicative Weights (adapting to unknown trace norm).
- Non-linear Classes: Results extend to supervised learning with non-linear classes, with bounds based on Sequential Rademacher Complexity.
Limitations and Future Work
While the proposed algorithms are polynomial-time efficient, they require solving a linear program (LP) at each step, which may introduce computational overhead for a very large number of models. Future work may explore if $O(n)$ experts are strictly necessary.
Additionally, the current bounds are $O(\sqrt{n})$, suitable for general convex losses. Extending this framework to achieve "fast rates" (logarithmic regret) for strongly convex or exp-concave losses is a promising direction. Finally, the current framework assumes the Lipschitz constant of the loss functions is known; adapting to an unknown Lipschitz constant remains an open area for research.
Summary updated