A second order regret bound for NormalHedge

Abstract

We consider the problem of prediction with expert advice for ``easy'' sequences. We show that a variant of NormalHedge enjoys a second-order $\hat{I}\mu$-quantile regret bound of $O\left(\sqrt{V_T\log (V_T/\hat{I}\mu )}\right)$ 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.