提出可随时停止的梯度下降加速方法，收敛速度突破传统极限。
Anytime Acceleration of Gradient Descent
- 设计预设步长策略，无需知道停止时间即可保证任意时刻收敛。
- 非强凸问题下收敛率达 $O(T^{-1.119})$，强凸下为 $\ ext{exp}(-Ω(T/κ^{0.893}))$。
- 解决COLT开放问题，适合关注自适应优化与理论保证的研究者。
本文研究基于步长的梯度下降在任意停止时间下的加速机制。对于光滑（非强凸）优化问题，提出一种预设步长策略，使梯度下降在任意停止时间 $T$ 下均可达到 $O(T^{-1.119})$ 的收敛率，无需提前知晓停止时间。该结果正面回答了COLT开放问题——步长加速能否实现 $o(T^{-1})$ 的任意时间收敛率。进一步将理论扩展至光滑强凸优化，获得 $\ ext{exp}(-Ω(T/κ^{0.893}))$ 的任意时间收敛保证，其中 $κ$ 为条件数。
原文摘要 · Abstract (English)
This work investigates stepsize-based acceleration of gradient descent with {\em anytime} convergence guarantees. For smooth (non-strongly) convex optimization, we propose a stepsize schedule that allows gradient descent to achieve convergence guarantees of $O(T^{-1.119})$ for any stopping time $T$, where the stepsize schedule is predetermined without prior knowledge of the stopping time. This result provides an affirmative answer to a COLT open problem \citep{kornowski2024open} regarding whether stepsize-based acceleration can yield anytime convergence rates of $o(T^{-1})$. We further extend our theory to yield anytime convergence guarantees of $\exp(-Ω(T/κ^{0.893}))$ for smooth and strongly convex optimization, with $κ$ being the condition number.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。