# A second order regret bound for NormalHedge

arXiv: https://arxiv.org/abs/2602.08151 · HTML: https://mlsanity.com/paper/2602.08151/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2026.

## Built on by (most cited first, 4 of 4)

- [Adaptive Bayes exactly tracks information over intrinsic time](https://mlsanity.com/paper/2607.08789/) (2026)
- [Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant](https://mlsanity.com/paper/2609.27206/) (2026)
- [A Short Note on a Variant of the Squint Algorithm](https://mlsanity.com/paper/2603.03409/) (2026)
- [When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation](https://mlsanity.com/paper/2605.13242/) (2026)

## Abstract (arXiv)

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 Obig(√VT log(VT/ε)big)  when VT > log N, where VT 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.