Abstract: We introduce a formalism of localization for online learning problems, which, similarly to statistical learning theory, can be used to obtain fast rates. In particular, we introduce local sequential Rademacher complexity and show how it can be used to derive tighter regret bounds. We provide a general framework for algorithms that automatically adapt to the difficulty of the data sequence, bridging the gap between adversarial and stochastic settings.
Introduction
In the realm of machine learning, a significant gap has long existed between statistical learning theory and online learning. Statistical learning typically assumes data is sampled independently and identically distributed (i.i.d.), allowing for the use of "local Rademacher averages." This technique focuses on the complexity of a small neighborhood around the optimal function, leading to "fast rates" of convergence.
Conversely, online learning traditionally prepares for the worst-case scenario, assuming an adversary chooses the data. This robustness often comes at a cost: standard online regret bounds are typically "slow," growing at a rate of $O(\sqrt{T})$. While specific scenarios like strongly convex functions were known to permit faster $O(\log T)$ rates, a unified, abstract theory explaining these speed-ups—and a general method to achieve them when data is not perfectly adversarial—has been missing. This paper addresses this gap by introducing a localized analysis framework for online learning.
The Framework of Relaxations
The authors build their framework on the concept of relaxations. Instead of attempting to solve the full minimax game, which is often computationally intractable, they utilize a sequence of functions that upper-bound the value of the learning game. These relaxations serve as a template for designing practical algorithms.
As shown in Algorithm 1, the Meta-Algorithm (MetAlgo) computes a distribution $q_t$ over the function class $\mathcal{F}$ by minimizing the supremum of the expected loss plus a relaxation term $\text{Rel}_T$. This relaxation term accounts for the future complexity of the game given the history $x_1, \dots, x_{t-1}$ and the current move $x$.
Localization via Blocking
The core innovation of this work is the application of localization to the online setting. This is achieved through a blocking strategy. The total $T$ rounds of learning are divided into blocks. At the beginning of each block, the algorithm identifies a "localized" subset of the function class $\mathcal{F}$. This subset, denoted as $\mathcal{F}_{r}$, contains only those functions that remain plausible candidates for the optimal predictor (Empirical Risk Minimizers) based on the data observed so far.
Algorithm 2 illustrates this process. By playing $k_i$ rounds using the Meta-Algorithm restricted to a localized subset $\mathcal{F}_{r(k_i; x_1, \dots, x_t)}$, the learner effectively "rules out" bad hypotheses. As more data is processed, the set of potentially optimal functions shrinks, simplifying the learning problem in subsequent blocks and enabling faster rates.
Universal Adaptation and Key Results
Building upon these foundations, the authors introduce an adaptive meta-algorithm that does not rely on fixed blocks. Instead, it dynamically monitors the sequence to determine if the adversary's moves are "easier" than the worst-case. If the data sequence exhibits favorable properties (e.g., it is i.i.d. or the loss functions are strongly convex), the algorithm re-localizes more aggressively.
Key Theoretical Findings:
- Strongly Convex Losses: The framework naturally recovers the optimal $O(\frac{\log T}{\lambda})$ regret bound.
- IID Regret Bounds: The authors provide a novel upper bound on regret in terms of classical Rademacher complexity for i.i.d. data, filling a significant gap in existing literature.
- Unified View of Fast Rates: Many disparate "fast rate" results, such as those for Adaptive Gradient Descent or Adaptive Hedge, are shown to be specific instances of this broader localization principle.
Discussion and Future Work
While this framework provides a powerful theoretical template, challenges remain regarding computational complexity. Calculating exact localized sequential Rademacher complexities or optimal relaxations can be difficult for complex function classes. Additionally, while doubling blocks provide a robust default, identifying optimal blocking strategies for specific problem domains is an area for future research.
The authors suggest that this localization principle could be extended to even more general settings, including non-convex optimization and games with more complex structures, potentially revolutionizing how we design adaptive online algorithms.
Summary updated