A lower bound for stepsize-based acceleration of gradient descent
Jianhao Ma, Yuxin Chen
math.OC, cs.LG, stat.ML
2026-08-11
任取非负预设步长调度,梯度下降末次迭代收敛率都被证不低于 Ω(T^{-1.93}),够不到最优的 O(T^{-2});证明由 GPT-5.6 Sol Pro 给出、并经 Lean 4 形式化。
梯度下降(GD)求光滑凸函数最小值时,常数步长 1/L 下迭代 T 次,误差以 O(T^{-1}) 下降。要更快,教科书做法是加动量(Nesterov 加速法),能把凸优化推到最优的 O(T^{-2})。
2024 年起一条新路线冒出来:不动 GD 的更新公式,只精心设计每一步的步长序列,偶尔插「长步」(η>1/L,可能临时让目标值变差),也能加速。目前最强的是基于银比 ρsil=1+√2 的调度,末次迭代收敛率达到 O(T^{-1.2715})。Altschuler 和 Parrilo 猜想这个 1.2715 就是最优。
问题在于:既然光调步长能把指数从 1 抬到 1.2715,继续设计更聪明的步长调度,能不能一路逼近最优的 O(T^{-2})?此前没人能否定。经典一阶方法下界 Ω(T^{-2}) 对所有用 T 次梯度查询的方法都成立,区分不了「裸 GD」和「带动量的加速法」;更细的下界要么只管一类受限调度,要么管的是 anytime 设定(一条无限长步长序列,要在任意停止时刻都表现好)。所以在这篇论文出现前,「裸 GD 配上好调度能不能冲到最优 O(T^{-2})」是一个完全敞开的口子。
主结论(Theorem 2.1):令 p⋆:=√(2+√3)≈1.9319。对任意 p∈(p⋆,2),存在常数 cp>0,使得对任意迭代数 T、光滑参数 L、初始距离 R,以及任意一条预设的非负步长调度 η,都存在一个维度 d≤T+1 的光滑凸函数 f 和最小值点 x⋆(‖x₀−x⋆‖=R),让 GD 跑完 T 步后,末次迭代误差满足
f(xT) − f(x⋆) ≥ cp · L · R² · (T+1)^{-p}.
即裸 GD 配任意非负预设调度,最坏情况末次迭代率不低于 Ω(T^{-1.9319}),严格慢于最优的 O(T^{-2})。这是头一份严格证据,说明单靠步长调度没法把裸 GD 推到最优。
下界管得很宽:步长可为零、可任意大、顺序任意,不要求单调或下降,只要非负且提前定好(知道总步数 T)。证明的大思路是作者给的「抵抗式 oracle」:先造一条对抗性 GD 轨迹,再证明它能被一个真实的光滑凸函数实现。具体的数学构造由 GPT-5.6 Sol Pro 给出,分三步:
对比:Tsai 等人(2026)的同期 anytime 下界能否定 o(T^{-4/3}),指数(4/3≈1.333)比这篇弱,但设定更强(单一无限正序列、对所有停止时刻一致),两边互不蕴含。
这是理论结果,数字就是下界本身和它卡出的间隙:
| 量 | 指数 | 含义 |
| 常数步长 GD | 1 | O(T^{-1}),教科书率 |
| 银比调度(已知最佳上界) | 1.2715 | log₂(1+√2),被猜想为最优 |
| 论文下界 | 1.9319 | √(2+√3),证明做不到更快 |
| Nesterov 加速 / 一阶最优 | 2 | O(T^{-2}),凸优化上限 |
真相落在 [1.2715, 1.9319] 之间。论文没证明银比就是最优(那个猜想仍开着),但从下方收紧了可能性:最优率不可能高于 1.9319 这个量级。
对优化和训练理论:近两年「光调步长也能加速」这条线很热,这篇给它画了硬天花板。指望靠步长工程一路逼近 Nesterov 级速度的人,现在知道脚下有地板。它也给「裸 GD 能做什么」和「必须改算法(动量)才能做什么」之间划了一道干净的界。
对 AI 圈更抓人的是它的产出来路。整份主证明是 GPT-5.6 Sol Pro 写的:作者只给了它研究目标(证一个严格慢于 1/T² 的 GD 下界)和一个高层策略(先造对抗轨迹、再证它可实现),除此之外没有提供最终证明里用到的任何非平凡数学要素。证明是多次提问、几轮尝试才跑通的。作者随后用 Codex 把整套证明在 Lean 4 里形式化(仓库 github.com/jianhaoma/gd-lower-bound-lean),于是它不只是「信不信 LLM」,而是机器逐行核验过。
这是一份前沿模型在原创数学研究里做出非平凡贡献的实打实样本,而且把该做的验证(形式化)做对了。要泼冷水也容易:这是一篇证明,在一个构造相对组合化、几何化的子领域(凸优化),不是「LLM 解决了千禧难题」;人给了目标和脚手架,模型在脚手架里填构造。但它确实是真研究,披露与核验都到位。