Parameter-Free Online Learning via Model Selection

Dylan J. Foster, Satyen Kale, Mehryar Mohri, Karthik Sridharan

Introduction

In machine learning, choosing the right model complexity is a classic Goldilocks problem: a model that is too simple suffers from high approximation error, while a model that is too complex will overfit or learn too slowly. In standard batch learning, we can rely on cross-validation to find the sweet spot. However, in online learning—where data arrives sequentially and predictions must be made on the fly—model selection becomes significantly more challenging.

This paper introduces a powerful meta-algorithm framework, MULTISCALEFTPL, designed to solve this "model selection" problem in online learning. It allows algorithms to automatically adapt to the best hypothesis class or parameter scale without prior knowledge, achieving "oracle inequalities" previously restricted to much narrower settings.

The Challenge of Scale

The core technical hurdle in online model selection is dealing with different "scales." Standard aggregation methods, such as the Multiplicative Weights algorithm, struggle when combining models of vastly different complexities.

For instance, if an algorithm is trying to learn a vector $w$ without knowing whether its norm is 1 or 1,000,000, standard approaches will yield a regret bound that scales with the largest possible norm (1,000,000)—even if the true best vector was small. The goal of parameter-free online learning is to ensure the regret scales only with the actual best model's complexity, ignoring the noise of larger, unnecessary scales.

The Solution: MULTISCALEFTPL

To overcome this, the authors propose a unified meta-algorithm based on Multi-Scale Follow-The-Perturbed-Leader (MULTISCALEFTPL). The framework relies on a few key technical innovations:

  • Multi-Scale Expert Advice: Unlike standard expert algorithms that assume all experts incur losses in a uniform range (e.g., $[0, 1]$), MULTISCALEFTPL accommodates experts where each expert $i$ operates within its own specific loss range $[-c_i, c_i]$.
  • Random Playout: The algorithm employs a "perturbation" strategy. In each round, it simulates future losses using random sign vectors (Rademacher variables) to determine which expert to follow. This tailored "Follow the Perturbed Leader" approach is crucial for handling multiple scales simultaneously without letting large-scale experts drown out the signal of small-scale ones.
  • Oracle Inequalities: The framework guarantees "oracle inequalities." This means the algorithm's total loss is competitive with the best model class $k$, plus a penalty term that scales strictly with the complexity of that specific class $k$, rather than the worst-case complexity across all classes.

Key Theoretical Breakthroughs

As a theoretical machine learning paper, the results are proven mathematically through rigorous regret analysis rather than empirical datasets. The insights push the boundaries of online learning in several ways:

  • Beyond Hilbert Spaces: Previous parameter-free online learning results were largely confined to highly structured Hilbert spaces (like standard Euclidean space). This framework successfully generalizes to arbitrary uniformly convex Banach spaces (including $\ell_p$ norms), offering much greater flexibility for high-dimensional data.
  • A Unified Framework: The authors demonstrate that this single meta-algorithm can solve a wide variety of problems. It provides the first computationally efficient parameter-free algorithms for Banach spaces, algorithms that can compete with the best $\ell_p$ norm simultaneously for all $p \in [1+\delta, 2]$, and efficient rank-adaptive algorithms for Online PCA and Matrix Multiplicative Weights.

Limitations and Future Directions

While the framework is highly general, the authors note a few limitations and areas for future work:

  • Computational Complexity: Although the algorithms run in polynomial time, the meta-algorithm requires solving a linear program or min-max optimization at each step. Achieving faster, specialized versions with $O(n)$ running time per iteration remains an open challenge.
  • Known Lipschitz Constants: The current framework assumes the Lipschitz constant (the "slope") of the loss functions is known. Extending this to handle unknown constants—reaching the true "Pareto frontier" of regret—is a key next step.
  • Curvature: Current bounds achieve standard $O(\sqrt{n})$ regret for general convex losses. Exploiting "curved" losses (like strongly convex or exp-concave functions) to achieve much faster $O(\log n)$ regret using multi-scale ideas is a promising avenue for future research.

Summary updated

Abstract

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.
BibTeX
@inproceedings{foster2017parameter,
  author = {Dylan J. Foster and Satyen Kale and Mehryar Mohri and Karthik Sridharan},
  title = {{Parameter-Free Online Learning via Model Selection}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=B1ZWcvbdbB},
}
Figure