cs.LGFeb 8, 2026

A second order regret bound for NormalHedge

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

Organizations: University of California, San Diego · University of British Columbia · University of S˜ao Paulo

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(VTlog⁡(VT/ε))O(\sqrt{V_T \log(V_T/ε)}) when VT>log⁡NV_T > \log N, where VTV_T is the cumulative second moment of the instantaneous per-expert regret, averaged with respect to a natural distribution qt\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.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant

    Sep 23, 2026Yang Cai, Vineet Gupta, Yanchen Jiang +4Minimax RegretRegret Minimization

  2. Prediction with Expert Advice under Heavy-Tailed Losses

    Oct 10, 2026Yuki Shibukawa, Shinji ItoMinimax RegretHeavy-Tailed Distributions