A second order regret bound for NormalHedge

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

Read A second order regret bound for NormalHedge by Yoav Freund, Nicholas J. A. Harvey, Victor S. Portella, Yabing Qi, Yu-Xiang Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-08151.txt.

Description

Prediction with expert advice is easiest when the sequence is easy, yet most regret bounds ignore that easiness. Yoav Freund and four co-authors show a variant of the NormalHedge algorithm enjoys a second-order quantile regret bound. It scales with the square root of cumulative second-moment regret times a log factor, when that variance-like quantity exceeds log of the expert count.

The recipe draws on a continuous-time limit using stochastic differential equations, while the discrete analysis leans on self-concordance methods. Online-learning theorists gain a bound that adapts to easy sequences: when experts' regrets vary little, the guarantee tightens automatically, matching the intuition that predictable problems should cost less to learn.

Catalog record

CREATORYoav Freund, Nicholas J. A. Harvey, Victor S. Portella, Yabing Qi, Yu-Xiang Wang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE147 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-08151

Browse the full library · About the Tower of Babel