Improved Gradient Descent Lower Bounds Beyond Nesterov
Yuhan Ye, Kaizhao Liu
math.OC, cs.LG, stat.ML
2026-09-03
MIT tightens predetermined-stepsize GD to Ω(n^{-1.634}) non-anytime and Ω(n^{-1.241}) anytime, ruling out the silver exponent ~1.272 for any single infinite schedule.
Can gradient descent beat the textbook O(n^{-1}) rate if the only degree of freedom is a predetermined stepsize sequence, with no momentum and no extra sequences? Recent constructions say yes. Silver schedules, which mix occasional long steps with a recursive pattern, reach O(n^{-log2(1+√2)}) on the objective gap at finite horizons, an exponent of about 1.2716. An anytime version, one infinite sequence that must work at every stopping time, currently sits at O(n^{-1.119}).
The classical first-order lower bound is still Nemirovsky–Yudin's Ω(n^{-2}), matched by Nesterov acceleration. Predetermined-stepsize GD is a thinner class: it never looks at past gradients. The Ω(n^{-2}) barrier still applies, but it is too loose to say how far stepsizes alone can go. Ma and Chen raised the non-anytime lower bound to Ω(n^{-1.932}); Tsai tightened that to Ω(n^{-√3})≈Ω(n^{-1.732}). On the anytime side, Tsai et al. had Ω(n^{-4/3}). The remaining gaps are the subject of this paper.
The hard-function family is the one from Ma and Chen. Given a stepsize schedule, one selects several long steps (hk>1) and builds a Huber-type obstacle aligned with those steps, producing a product lower bound that depends only on the schedule. Earlier analyses collapsed the coupling between consecutive long steps into a single summary, or into a harmonic mean of excesses. Here every adjacent factor is kept and estimated term by term.
That estimate is reduced to a sequence inequality. The q largest stepsize excesses are selected; interval mass and excesses are normalized into (xi) and (ωi); a penalized function Γλ absorbs the xi variables. What remains is a sum of Γλ on consecutive weights. Γλ is symmetric, jointly convex, coordinatewise decreasing, and strictly submodular, so matching, majorization, and weak supermajorization replace the unknown weights by an explicit comparison sequence and the sum by a one-dimensional integral J(α,λ). Any parameter pair with J<0 yields an Ω(n^{-(1+α)}) bound.
Numerically, α=0.6342 and λ=0.4506 give J<-0.00005, hence Ω(n^{-1.6342}) in the non-anytime case. The anytime argument reuses Tsai et al.'s finite-to-anytime transfer, applying the same estimate at horizons whose last stepsize is the largest seen so far. The exponent becomes 2(1+α)/(2+α)≈1.2408.
| Setting | Prior lower bound | This paper | Known upper bound |
| Non-anytime (fixed horizon) | Ω(n^{-1.932}) / Ω(n^{-1.732}) | Ω(n^{-1.6342}) | O(n^{-1.2716}) (silver) |
| Anytime (one infinite sequence) | Ω(n^{-4/3})≈Ω(n^{-1.333}) | Ω(n^{-1.2408}) | O(n^{-1.119}) |
Because 1.2716>1.2408, the silver exponent that is achievable with a horizon-dependent schedule is impossible for any single infinite schedule. That separation is the sharpest claim in the paper.
Production GD and SGD almost always carry momentum. The question here is narrower: if the iteration is forbidden to change, and only the stepsize table may be written in advance, where does smooth convex optimization stop. Nobody will train a foundation model with a silver schedule. Convex solvers and the recent line of long-step recursive schedules now have a tighter map. Non-anytime rates can still move toward 1.27; anytime rates are stuck below 1.24, strictly short of silver.
This is a lower-bound improvement. It does not produce a faster algorithm.
The authors say the product bound plus the rule of keeping only the q largest excesses already looks tight, so the same lemmas are unlikely to reach silver's 1.2716. Matching the recursive geometry of silver steps may need a hard function with a hierarchy of scales. On the anytime side, the factor 2(1+α)/(2+α) comes from a terminal-step estimate; coupling several horizons, or replacing that estimate by a multi-step bound, is open.
The exponents 1.6342 and 1.2408 are the first numerical pair that makes J negative, not a closed-form optimum. A sharper integrator could still shave the non-anytime exponent. The analysis is deterministic, smooth, convex, full-gradient, predetermined-stepsize GD. Stochastic, nonconvex, and adaptive stepsizes are out of scope.
The authors disclose that ChatGPT-5.6 helped draft the non-anytime proof, which they then rewrote and take responsibility for.