A second order regret bound for NormalHedge

A NormalHedge variant achieves second-order ε-quantile regret O(sqrt(V_T log(V_T/ε))) for easy sequences via self-concordance analysis.

Yoav S Freund, Nicholas Harvey, Victor S. Portella, Yabing Qi, Yu-Xiang Wang

Published 2026Atlanta Poster Session 6 · Fri, Dec 11, 4:30 PM–7:30 PM local time · Hall C1arXiv ↗OpenReview ↗

70%

OverallHighly rated

OverallHighly ratedVote to see the scoreThe exact score shows once you've voted, so every vote is your own call. The first half of each home page shelf shows its scores.

Readers

–

Only vote on papers you've read. Sign in with GitHub to vote.

AI panel5/20reviewers recommend it

lenient 1/5

medium 2/10

strict 2/5

AI panel?Vote to see what the 20 AI reviewers said

Panel consensus

A rare self-concordant analysis yields an elegant second-order quantile regret bound for easy sequences, though the missing variance, untested V_T threshold, and absent baselines leave its practical edge unresolved.

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.