arXiv:2602.08151 · v2

A second order regret bound for NormalHedge

首次提交 2026-02-09 06:57

版本更新 2026-11-12 03:35

雷达观测 2026-11-13 14:16

摘要

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

作者备注：53 pages, 3 figures. Camera-ready version for NeurIPS 2026 without the conference checklist