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

Mar 3, 2026

A Short Note on a Variant of the Squint Algorithm

This short note describes a simple variant of the Squint algorithm of Koolen and Van Erven [2015] for the classic expert problem. Via an equally simple modification of their proof, we prove that this variant ensures a regret bound that resembles the one shown in a recent work by Freund et al. [2026] for a variant of the NormalHedge algorithm [Chaudhuri et al., 2009].
Sep 23, 2026

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

Prediction with expert advice is a fundamental problem in online learning. When the time horizon TT is known in advance, the minimax cumulative regret over nn experts is asymptotically Tln⁡n2\sqrt{\frac{T \ln n}{2}}. This is achieved by the Multiplicative Weights Update algorithm with a learning rate tuned to TT, and is known to be tight. If instead the regret bound is required to hold simultaneously at every time tt, the best known guarantee has been tln⁡n\sqrt{t \ln n}---a factor of 2\sqrt{2} worse---and it has remained unknown whether this factor of 2\sqrt{2} is necessary. We show that it is not. We give an algorithm, requiring no knowledge of the horizon, whose cumulative regret satisfies Rt≤(1+O(ln⁡ln⁡n/ln⁡n))tln⁡n/2R_t \le \bigl(1 + O(\sqrt{\ln \ln n / \ln n})\bigr)\sqrt{t \ln n / 2} simultaneously for every t≥1t \ge 1.
Oct 10, 2026

Prediction with Expert Advice under Heavy-Tailed Losses

We study prediction with expert advice over TT rounds with KK experts under heavy-tailed losses whose (1+ε)(1+ε)-moment is bounded by θ>0θ>0 for some ε∈(0,1]ε\in(0,1]. In this setting, existing algorithms designed for the case ε=1ε=1 can be suboptimal when ε<1ε<1, suffering an additional polynomial dependence on KK. We characterize the minimax pseudo-regret rate as Θ((θT)11+ε(log⁡K)ε1+ε)Θ((θT)^{\frac{1}{1+ε}}(\log K)^{\fracε{1+ε}}) and establish gap-dependent lower bounds in a self-bounded environment. To attain this minimax rate without prior knowledge of either εε or θθ, we propose Adaptive Heavy-Tailed FTRL, which uses robust data-dependent scale adaptation together with truncation. We further develop Adaptive Heavy-Tailed OMD, which likewise requires neither εε nor θθ and achieves near-optimal regret guarantees in both adversarial and self-bounded environments. Finally, when εε and θθ are known, an FTRL algorithm with Shannon-entropy regularization achieves optimal regret guarantees in both environments.