版本更新 · v2arXiv:2602.08151
A second order regret bound for NormalHedge
Yoav Freund, Nicholas J. A. Harvey, Victor S. Portella, Yabing Qi, Yu-Xiang Wang
原文摘要
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.
cs.LG · stat.ML