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.