Improved Gradient Descent Lower Bounds Beyond Nesterov
Yuhan Ye, Kaizhao Liu
math.OC, cs.LG, stat.ML
2026-09-03
MIT把光滑凸优化里预定步长梯度下降的非随时下界从Ω(n^{-1.932})收到Ω(n^{-1.634})，随时下界到Ω(n^{-1.241})，随时算法因此达不到silver约n^{-1.272}的速率。
梯度下降只改步长、不加动量，能不能快过教科书上的O(n^{-1})？近几年的答案是能。silver schedule用偶尔的长步和递归结构，把有限步数（非随时）的目标函数间隙做到O(n^{-log₂(1+√2)})，指数大约1.2716。随时版本要求同一条无限步长序列在每一个停机时刻都成立，目前最好是O(n^{-1.119})。
一阶方法整体的下界仍是Nemirovsky–Yudin的Ω(n^{-2})，Nesterov加速能对上这个指数。预定步长GD更窄：它看不到历史梯度，只按事先写好的步长走。Ω(n^{-2})对它当然成立，却太松，几乎说不清「只改步长」还能走多远。Ma和Chen把非随时下界推到Ω(n^{-1.932})，Tsai再收到Ω(n^{-√3})≈Ω(n^{-1.732})，随时一侧Tsai等人给出Ω(n^{-4/3})。两端之间仍有空隙。
硬函数沿用Ma–Chen：按给定步长序列挑出若干长步（hk>1），构造一条与这些长步对齐的Huber型障碍，得到只依赖步长序列的乘积下界。先前工作把相邻长步之间的耦合压成一个总量或调和平均。这篇留下每一对相邻因子，逐项估计。
问题被收成一条序列不等式。选q个最大的步长超额，把间隔累积和超额分别归一化成(xi)和(ωi)，再用带惩罚λ的Γλ吃掉xi。剩下的是相邻权重上Γλ的求和。Γλ对称、联合凸、逐坐标递减且严格子模，于是可以用匹配拆分、大化和弱超优关系，把求和换成一维积分J(α,λ)。找到一组使J<0的参数，就得到Ω(n^{-(1+α)})下界。
数值上取α=0.6342、λ=0.4506，积分给出J<-0.00005。非随时下界因此是Ω(n^{-1.6342})。随时情形借用Tsai等人的有限到随时转移：只在「当前步长是迄今最大」的地平线调用同一套估计，指数变成2(1+α)/(2+α)≈1.2408。
| 设定 | 此前下界 | 本篇下界 | 已知上界 |
| 非随时（有限地平线） | Ω(n^{-1.932}) / Ω(n^{-1.732}) | Ω(n^{-1.6342}) | O(n^{-1.2716})（silver） |
| 随时（无限序列） | Ω(n^{-4/3})≈Ω(n^{-1.333}) | Ω(n^{-1.2408}) | O(n^{-1.119}) |
因为1.2716>1.2408，silver在非随时能达到的指数，随时算法达不到。这是这篇最硬的分离结论。
训练里日常用的GD/SGD往往带动量。这篇回答更窄也更干净的问题：不准改迭代形式，只允许事先排好步长，光滑凸问题上的极限在哪。没人会拿silver schedule去训大模型，但凸求解器和「长步+递归步长」这条近年很热的线，现在有了一张更紧的地图。非随时还能往1.27挤；随时已经被卡在1.24以下，和silver的1.27之间有严格缝隙。
这是下界改进，没有给出更快的算法。
作者承认，现有乘积下界加上「只挑q个最大超额」这一步估得已经比较满，靠同一套引理很难再贴上silver的1.2716。要对齐silver的递归结构，可能需要带层次尺度的新硬函数。随时一侧的2(1+α)/(2+α)来自末端步估计，耦合多个地平线或多步界能不能给出更强随时下界，仍是开放问题。
指数1.6342和1.2408来自数值积分刚好让J变负，不是闭式最优。附录写了参数搜索，换一套更精的数值方法，非随时指数还可能再往下挤一点。全文分析的是确定光滑凸、全梯度、预定步长；随机、非凸、自适应步长都不在范围内。
作者披露非随时证明曾用ChatGPT-5.6辅助起草，随后人工重写并负责正确性。