A second order regret bound for NormalHedge

Yoav Freund, Nicholas J. A. Harvey, Victor S. 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 $ε$-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 S. 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},
}

Loading related content...

Figure