A second order regret bound for NormalHedge

Yoav Freund, Nicholas J. A. Harvey, Victor Sanches Portella, Yabing Qi, Yu-Xiang Wang

Abstract: We consider the problem of prediction with expert advice for "easy" sequences. We show that a variant of NormalHedge enjoys a second-order $\epsilon$-quantile regret bound of $O\big(\sqrt{V_T \log(V_T/\epsilon)}\big) $ when $V_T > \log N$, where $V_T$ is the cumulative second moment of instantaneous per-expert regret averaged with respect to a natural distribution determined by the algorithm. The algorithm is motivated by a continuous time limit using Stochastic Differential Equations. The discrete time analysis uses self-concordance techniques.

Introduction

In the classic framework of prediction with expert advice, a learner aims to minimize regret—the difference between their cumulative loss and the loss of the best expert in a pool of $N$ candidates. While standard algorithms like Hedge provide a robust regret bound of $O(\sqrt{T \log N})$, these bounds are often pessimistic. They depend on the total number of rounds $T$ and the total number of experts $N$, failing to exploit sequences that are "easy" (low variance) or scenarios where a significant fraction of experts perform well.

To address these limitations, researchers have pursued two specific refinements:

  1. Quantile Regret: Competing not just with the single best expert, but with the top $\epsilon$-fraction of experts. This is vital when the expert pool is massive or redundant.
  2. Second-Order (Variance-based) Regret: Achieving bounds that scale with the cumulative variance of the losses ($V_T$) rather than the raw number of rounds $T$.

In 2016, Yoav Freund conjectured that the NormalHedge algorithm could simultaneously achieve both properties. This paper provides a positive answer to that decade-old open problem, overcoming previous impossibility results by refining the measurement of variance and the discretization of continuous-time strategies.

Methodology: From SDEs to Discrete Time

The authors bridge the gap between continuous-time mathematical elegance and discrete-time algorithmic rigor using three primary pillars:

Potential Functions and the Backwards Heat Equation

The algorithm is constructed around a potential function $\phi(y, t)$ designed to remain constant in expectation. By requiring this function to satisfy the backwards heat equation—$\partial_t \phi = -\frac{1}{2} \partial_{yy} \phi$—the authors naturally link the passage of "time" in the algorithm to the accumulation of variance. This constraint ensures that the algorithm's weights are always optimally balanced against the observed volatility of the experts.

Stochastic Differential Equations (SDE) Motivation

The update rules for the learner's weights are derived from the continuous limit of SDEs. In this idealized limit, the learner’s strategy is determined by the gradient of the potential function. This perspective allows the researchers to design an algorithm that is inherently adaptive to the sequence's complexity.

Local Generalized Self-Concordance

To translate the smooth continuous-time theory into a rigorous discrete-time proof, the authors employ a novel "local" version of self-concordance. While standard self-concordance is a staple of interior-point methods in optimization, it is often too restrictive for online learning. By introducing a localized version, the authors successfully bound the "discretization error"—the mathematical penalty incurred when taking finite steps in a system designed for continuous flow.

Key Theoretical Insights

A pivotal discovery in this work is the distinction between two distributions: $p$ and $q$. In most traditional algorithms, such as Exponential Weights, the player's distribution ($p$) and the distribution used to measure variance are identical. However, for NormalHedge, the analysis reveals that variance must be calculated relative to a distribution $q$ derived from the potential's second derivative.

This distinction is the key to bypassing previous impossibility proofs. By decoupling these distributions, the authors demonstrate that the discretization error is manageable for NormalHedge and exactly zero for Exponential Weights. Furthermore, the resulting bounds are iteration-free, meaning they depend entirely on the cumulative variance $V_T$ rather than the number of rounds $T$.

Main Results

The paper's primary contribution is formalized in Theorem 6, which proves the regret bound for the NormalHedge.BH variant:

$$\text{Regret}_\epsilon(T) \le \sqrt{(t_0 + 2V_T)(\log(t_0 + 2V_T) + 2 \log(1/\epsilon))}$$

Here, $V_T$ represents the cumulative second moment of instantaneous regret. This result confirms that NormalHedge possesses the "best of both worlds" property: it adapts to the best $\epsilon$-quantile of experts while simultaneously scaling with the sequence's variance.

To complement this, Theorem 7 provides a lower bound, demonstrating that this result is adaptively optimal up to a multiplicative factor of $\sqrt{\log V_T}$. This confirms that the proposed algorithm is near-optimal for the class of problems it addresses.

Conclusion and Future Work

By resolving the COLT 2016 open problem, this work provides a robust theoretical foundation for adaptive online learning. While a small logarithmic gap remains between the upper and lower bounds, the authors suspect this may be an inherent characteristic of the NormalHedge potential.

Beyond regret bounds, the introduction of "local self-concordance" offers a promising new tool for the broader machine learning community. This technique could potentially be applied to other domains where continuous-time SDEs are used to inspire discrete algorithms, such as stochastic control, financial modeling, and high-dimensional optimization.

Summary updated

Abstract

We consider the problem of prediction with expert advice for ``easy'' sequences. We show that a variant of NormalHedge enjoys a second-order $ε$-quantile regret bound of $O\big(\sqrt{V_T \log(V_T/ε)}\big) $ when $V_T > \log N$, where $V_T$ is the cumulative second moment of instantaneous per-expert regret averaged with respect to a natural distribution determined by the algorithm. The algorithm is motivated by a continuous time limit using Stochastic Differential Equations. The discrete time analysis uses self-concordance techniques.
BibTeX
@misc{freund2026second,
  author = {Yoav Freund and Nicholas J. A. Harvey and Victor Sanches Portella and Yabing Qi and Yu-Xiang Wang},
  title = {{A second order regret bound for NormalHedge}},
  year = {2026},
  eprint = {2602.08151},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.08151},
}
Figure