提出改进的NormalHedge算法，对简单序列预测实现更优的后悔界。
A second order regret bound for NormalHedge
- 基于随机微分方程的连续时间启发，设计新算法。
- 在$V_T > \log N$时，后悔界为$O\big(\sqrt{V_T \log(V_T/ε)}\big)$。
- 适合关注在线学习中次线性后悔界的研究者。
我们研究了针对“简单”序列的专家建议预测问题。研究表明，NormalHedge的一个变体在$V_T > \log N$条件下，可达到第二阶$ε$-分位数后悔界$O\big(\sqrt{V_T \log(V_T/ε)}\big)$，其中$V_T$是瞬时每专家后悔值在算法确定的自然分布下的累积二阶矩。该算法受连续时间极限（基于随机微分方程）启发，离散时间分析采用自协调性技术。
原文摘要 · Abstract (English)
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\big(\sqrt{V_T \log(V_T/ε)}\big) $ 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。