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
| CREATOR | Yoav Freund, Nicholas J. A. Harvey, Victor S. Portella, Yabing Qi, Yu-Xiang Wang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 147 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-08151