A second order regret bound for NormalHedge

arXiv (Cornell University) 2026 Preprint Open access

Read full text
Authors: Yoav Freund, Nicholas J. A. Harvey, Victor Sanches Portella, Yabing Qi, Yu-Xiang Wang
DOI: 10.48550/arxiv.2602.08151
Cited by: 0

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.

Fields of Study & Subjects

Advanced Bandit Algorithms Research Optimization and Search Problems Machine Learning and Algorithms

Publication details

Journal / source
arXiv (Cornell University)
Publication date
8 February 2026
Language
EN
Document type
Preprint