提出新误差度量，更精准评估在线优化性能。
Small Gradient Norm Regret for Online Convex Optimization
- 用累积梯度平方和定义新误差指标
- 理论证明该指标可比旧指标尖锐数倍
- 适用于优化算法分析与实际验证
本文为平滑损失下的在线凸优化引入一种新的问题相关后悔度量，称为 $G^/star$ 回悔。该度量基于事后决策点处的累积平方梯度范数。我们证明 $G^/star$ 回悔严格优于现有的 $L^/star$（小损失）回悔，并在损失函数在事后决策点附近曲率趋近于零时可显著更优。文中建立了 $G^/star$ 回悔的上下界，并将其拓展至动态回悔与贝叶斯设置。作为副产品，我们改进了插值区域内随机优化算法的收敛性分析。部分实验验证了理论结果。
原文摘要 · Abstract (English)
This paper introduces a new problem-dependent regret measure for online convex optimization with smooth losses. The notion, which we call the $G^\star$ regret, depends on the cumulative squared gradient norm evaluated at the decision in hindsight. We show that the $G^\star$ regret strictly refines the existing $L^\star$ (small loss) regret, and that it can be arbitrarily sharper when the losses have vanishing curvature around the hindsight decision. We establish upper and lower bounds on the $G^\star$ regret and extend our results to dynamic regret and bandit settings. As a byproduct, we refine the existing convergence analysis of stochastic optimization algorithms in the interpolation regime. Some experiments validate our theoretical findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。