新下界证明：梯度下降在任意时间设置下无法达到银级调度速率
研究将非任意时间与任意时间设置的梯度下降下界分别改进至 Ω(n^{-1.6342}) 与 Ω(n^{-1.2408})，并揭示两种设置间的严格分离。
AI解读：这篇论文回答了一个基础问题：在光滑凸优化中，仅靠预设步长，梯度下降最快能有多快？经典的Nemirovsky-Yudin下界是 Ω(n^{-2})，但作者证明，如果算法必须在任何提前停止的时刻都保持良好表现（即“任意时间”设置），收敛速度会被限制在 Ω(n^{-1.2408})，比非任意时间下界 Ω(n^{-1.6342}) 更差。这意味着，工程师若需要随时可用的中间结果，就不能指望达到理论上最优的银级调度速率O(n^{-log₂(1+√2)})——这原本是针对预先确定迭代次数设计的。对于设计优化算法的人来说，这提示在任意时间场景下需选择不同的步长策略，但无需恐慌：这只是理论边界，实际性能仍取决于具体问题。值得注意的是，结果对负步长同样成立，这拓宽了适用性。
一项新的理论研究表明，在光滑凸优化中，使用预设步长的梯度下降（GD）的收敛速率下界可被显著收紧。论文由Yuhan Ye和Kaizhao Liu撰写，于 2026 年 9 月 2 日首次提交至arXiv（第二版于 9 月 3 日更新），证明非任意时间（non-anytime）设置下的下界为 Ω(n^{-1.6342})，任意时间（anytime）设置下的下界为 Ω(n^{-1.2408})。这些结果分别改进了Ma和Chen（2026）的 Ω(n^{-1.932}) 非任意时间下界，以及Tsai等人（2026）的 Ω(n^{-4/3}) 任意时间下界。
核心结果与改进
论文超越了Nemirovsky和Yudin（1983）提出的经典一阶oracle下界 Ω(n^{-2})。非任意时间下界 Ω(n^{-1.6342}) 表示，当预先确定迭代次数n时，梯度下降的最坏情况收敛速率不可能快于该值。任意时间下界 Ω(n^{-1.2408}) 则适用于算法必须在任何迭代步数下都表现良好的场景。
- 非任意时间下界：Ω(n^{-1.6342})，改进自Ma和Chen的 Ω(n^{-1.932})。
- 任意时间下界：Ω(n^{-1.2408})，改进自Tsai等人的 Ω(n^{-4/3})。
- 两个下界在步长可为负值时依然成立。
任意时间设置的限制
研究进一步表明，在任意时间设置下，由Altschuler和Parrilo（2025）及Grimmer等人（2025）提出的非任意时间银级调度（silver schedules）速率O(n^{-log₂(1+√2)}) 无法实现。这建立了两种设置之间严格的分离：非任意时间下可实现更快的理论速率，而任意时间下则不可能达到。
- 银级调度速率O(n^{-log₂(1+√2)}) 仅适用于非任意时间设置。
- 任意时间设置的下界 Ω(n^{-1.2408}) 排除了达到该速率的可能性。