cs.LGFeb 8, 2026
SaveA second order regret bound for NormalHedge
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 when , where is the cumulative second moment of the 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.
Figures & tables
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
| Work | Cumulative variance | Regret bound | Adaptive Minimax? |
| Hedge [ Cesa-Bianchi et al., 2007 ] | No | ||
| Hedge [ Cesa-Bianchi et al., 2007 ] | No | ||
| NormalHedge [ Chaudhuri et al., 2009 ] | T | Yes | |
| Squint [ Koolen and van Erven, 2015 ] | Yes | ||
| Ada-Normal-Hedge [ Luo and Schapire, 2015 ] | Yes | ||
| AdaHedge [ De Rooij et al., 2014 ] | Yes |
Table 1: Summary of instance-dependent regret bounds. For those that depends on priors, e.g., Koolen and van Erven [2015] , we choose the prior to be uniform, so as to be comparable to quantile regret bounds. For clarity, we omit multiplicative factors and additive factors. Also, note that in Negrea et al. [2021] is different from the in our Theorem 6 due to different choices of , both are natural for the algorithm under consideration.
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].
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 is known in advance, the minimax cumulative regret over experts is asymptotically . This is achieved by the Multiplicative Weights Update algorithm with a learning rate tuned to , and is known to be tight. If instead the regret bound is required to hold simultaneously at every time , the best known guarantee has been ---a factor of worse---and it has remained unknown whether this factor of is necessary. We show that it is not. We give an algorithm, requiring no knowledge of the horizon, whose cumulative regret satisfies simultaneously for every .
Prediction with Expert Advice under Heavy-Tailed Losses
We study prediction with expert advice over rounds with experts under heavy-tailed losses whose -moment is bounded by for some . In this setting, existing algorithms designed for the case can be suboptimal when , suffering an additional polynomial dependence on . We characterize the minimax pseudo-regret rate as 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.