自适应步长梯度法实现快速收敛，理论证明优于传统方法。
Gradient Methods with Online Scaling Part I. Theoretical Foundations
- 用在线学习动态调整步长，基于收敛反馈优化迭代过程。
- 在光滑凸问题上实现全局收敛与局部超线性收敛，复杂度更优。
- 解释了机器学习中超梯度下降的实证成功，适用于优化新手。
本文建立了在线缩放梯度法（OSGM）的理论基础，该框架利用在线学习自适应调整步长，并可证明加速一阶优化方法。OSGM通过一个基于收敛度量的反馈函数量化步长有效性，并借助在线学习算法动态调节步长。由此产生的实例在渐近意义下收敛速度不低于最优步长。对于光滑凸问题，OSGM提供理想收敛保证：1）轨迹依赖的全局收敛；2）光滑强凸问题上改进的复杂度结果；3）局部超线性收敛。值得注意的是，OSGM构成一类新的具非渐近超线性收敛的一阶方法，与著名拟牛顿法并列。最后，它解释了机器学习优化中流行的超梯度下降启发式方法的实证成功。
原文摘要 · Abstract (English)
This paper establishes the theoretical foundations of the online scaled gradient methods (OSGM), a framework that utilizes online learning to adapt stepsizes and provably accelerate first-order methods. OSGM quantifies the effectiveness of a stepsize by a feedback function motivated from a convergence measure and uses the feedback to adjust the stepsize through an online learning algorithm. Consequently, instantiations of OSGM achieve convergence rates that are asymptotically no worse than the optimal stepsize. OSGM yields desirable convergence guarantees on smooth convex problems, including 1) trajectory-dependent global convergence on smooth convex objectives; 2) an improved complexity result on smooth strongly convex problems, and 3) local superlinear convergence. Notably, OSGM constitutes a new family of first-order methods with non-asymptotic superlinear convergence, joining the celebrated quasi-Newton methods. Finally, OSGM explains the empirical success of the popular hypergradient-descent heuristic in optimization for machine learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。