# A second order regret bound for NormalHedge

DevFeed: [A second order regret bound for NormalHedge](<https://devfeed.tech/articles/a-second-order-regret-bound-for-normalhedge-132751.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2602.08151>)

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

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Artificial Intelligence](<https://devfeed.tech/topics/ai.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>)

Tags: [advice](<https://devfeed.tech/tags/advice.md>), [algorithm](<https://devfeed.tech/tags/algorithm.md>), [analysis](<https://devfeed.tech/tags/analysis.md>), [continuous](<https://devfeed.tech/tags/continuous.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [distribution](<https://devfeed.tech/tags/distribution.md>), [easy](<https://devfeed.tech/tags/easy.md>), [limit](<https://devfeed.tech/tags/limit.md>), [log](<https://devfeed.tech/tags/log.md>), [machine-learning](<https://devfeed.tech/tags/machine-learning.md>), [prediction](<https://devfeed.tech/tags/prediction.md>), [quantile](<https://devfeed.tech/tags/quantile.md>), [sequences](<https://devfeed.tech/tags/sequences.md>), [stat-ml](<https://devfeed.tech/tags/stat-ml.md>), [time](<https://devfeed.tech/tags/time.md>), [uses](<https://devfeed.tech/tags/uses.md>)

## AI overview

A variant of NormalHedge achieves a second-order ε-quantile regret bound of O(√(V_T log(V_T/ε))) for prediction with expert advice on "easy" sequences, under the stated condition V_T > log N. Here V_T is the cumulative second moment of instantaneous per-expert regret, averaged using a natural distribution q_t determined by the algorithm. The algorithm is motivated by a continuous-time limit involving stochastic differential equations; its discrete-time analysis uses self-concordance techniques.

## Source excerpt

arXiv:2602.08151v2 Announce Type: replace 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(\sqrt{V_T \log(V_T/\epsilon)})$ when $V_T > \log N$, where $V_T$ is the cumulative second moment of the instantaneous per-expert regret, averaged with respect to a natural distribution $\mathbf{q}_t$ 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.