证明了梯度下降仅靠步长调度无法达到最优收敛速度
A lower bound for stepsize-based acceleration of gradient descent
- 设计新下界证明步长调度的极限能力
- 得出收敛率下界为Ω(T^{-1.9319})
- 适合研究优化算法理论边界的研究者
近期工作表明，对于光滑凸优化问题，仅通过精心设计的步长调度，普通梯度下降（GD）即可从经典的 $O(T^{-1})$ 收敛率提升至 $Oig(T^{- ext{log}_2(1+ ext{√}2)}ig)$，无需动量等额外修改。然而，此前对这类方法的下界了解甚少，仅知一般一阶方法的 $Ω(T^{-2})$ 基线。本文提出一个新下界 $Ω(T^{-1.9319})$，针对预设非负步长调度的梯度下降最后迭代点收敛率。该结果严格表明：仅靠步长调度无法使普通 GD 达到最优 $O(T^{-2})$ 收敛率。证明由 GPT-5.6 Sol Pro 在作者指导下完成。
原文摘要 · Abstract (English)
Recent work has shown that, for smooth convex optimization, plain gradient descent can be accelerated from its textbook convergence rate of $O(T^{-1})$ (where $T$ denotes the number of iterations) to $O\big(T^{-\log_2(1+\sqrt{2})}\big)$ using carefully designed stepsize schedules alone, without resorting to momentum or other algorithmic modifications. Despite this progress, however, little was known about lower bounds for such methods beyond the classical $Ω(T^{-2})$ benchmark for general first-order methods. In this work, we present a new lower bound of $Ω(T^{-1.9319})$ for the last-iterate convergence rate of gradient descent with predetermined nonnegative stepsize schedules. This result provides rigorous evidence that stepsize schedules alone cannot accelerate plain GD to the optimal $O(T^{-2})$ convergence rate. The proof was developed by GPT-5.6 Sol Pro under the authors' guidance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。