Variance Adaptive Online Learning

This direction is merged into another direction: second-order regret bounds. Its last version stays readable and citable here.

Version 1 of 148 papers60 conceptsfrozen 2026-10-04

In the standard framework of online learning, we measure success by regret: the difference between our cumulative loss and the loss of the best fixed strategy in hindsight. For decades, the gold standard for adversarial environments has been a regret bound that scales with the square root of time, $O(\sqrt{T})$. This bound is robust but pessimistic; it assumes the environment is always as difficult as possible.

However, real-world data is rarely purely adversarial. Often, the "experts" we follow are consistent, or the losses we observe are stable. Researchers have developed a more refined lens called second-order regret bounds. Instead of scaling with the total number of steps $T$, these bounds scale with the variance or cumulative variation of the losses. If the environment is "easy" or stable, the algorithm automatically accelerates, achieving much lower regret without needing to know the environment's difficulty in advance.

The Geometry of Stability

Why does variance determine the speed of learning? The intuition lies in the curvature of the algorithms we use. Most online learning algorithms, like Multiplicative Weights or Online Mirror Descent, maintain a "potential function" that tracks the performance of different options.

As Michael Muehlebach demonstrates in Adaptive Decision-Making with Constraints and Dependent Losses, applying a second-order Taylor expansion to these potential functions reveals that the primary driver of regret is a variance-like term. When the predictions of the learner and the best expert are similar, the "effective" loss range shrinks. Nicolò Cesa-Bianchi and Ohad Shamir showed in Bandit Regret Scaling with the Effective Loss Range that if we can anchor our estimates to a local baseline, the learner's penalty is determined by local fluctuations rather than the global range of possible outcomes.

Bridging Stochastic and Adversarial Worlds

A major motivation for second-order bounds is the "best-of-both-worlds" problem. We want algorithms that are robust enough to handle an adversary but efficient enough to exploit a stable, stochastic environment.

Wouter M. Koolen and Tim van Erven have been central to this effort. In Second-order Quantile Methods for Experts and Combinatorial Games, they introduced Squint, an algorithm that integrates over a range of learning rates to adapt to both the variance of the data and the distribution of good experts. This allows the learner to achieve faster convergence in stable settings where variance is low, while maintaining the $O(\sqrt{T})$ safety net for adversarial cases.

Similarly, the MetaGrad algorithm, developed by Koolen, van Erven, and Niels Bohrweg, achieves logarithmic regret for functions even without curvature (like hinge loss) by bounding regret by the variance of the gradients. This mechanism ensures that if the data is empirically stable, the algorithm converges at a "fast rate" typically reserved for much simpler problems.

The Continuous Perspective

The most elegant explanation for why second-order bounds work comes from the transition to continuous time. Lexing Ying argues in A note on continuous-time online learning that regret in adversarial settings is fundamentally linked to quadratic variation—a measure of how much a stochastic process oscillates.

By using tools from stochastic calculus like Ito’s Lemma, researchers can show that the regret bound is not just an arbitrary formula, but a direct consequence of the information constraints on the learner. This connection was further solidified by Yoav Freund and colleagues in A second order regret bound for NormalHedge, which solved a long-standing open problem by using Stochastic Differential Equations (SDEs) to prove that the NormalHedge algorithm can simultaneously achieve quantile-based and variance-based bounds.

Applications and Extensions

The shift toward variance-sensitivity is transforming more complex domains:

By focusing on the second-order statistics of the environment, these researchers have moved online learning from a "worst-case" discipline to one that is truly adaptive, ensuring that the difficulty of the math matches the actual difficulty of the data.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_variance_adaptive_online_learning_737c196b,
  title = {Variance Adaptive Online Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/variance-adaptive-online-learning/rdr_737c196bb794475ea66daef0896c898a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_variance_adaptive_online_learning_737c196b_v1,
  title = {Variance Adaptive Online Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/variance-adaptive-online-learning/rdr_737c196bb794475ea66daef0896c898a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}