A lower bound for stepsize-based acceleration of gradient descent
Jianhao Ma, Yuxin Chen
math.OC, cs.LG, stat.ML
2026-08-11
Any predetermined nonnegative stepsize schedule caps GD's last-iterate rate at Ω(T^{-1.93}), short of optimal O(T^{-2}). GPT-5.6 Sol Pro wrote it; Lean 4 checks it.
Gradient descent (GD) on a smooth convex function with the constant stepsize 1/L converges at O(T^{-1}) after T iterations. Going faster has classically meant adding momentum: Nesterov's accelerated method reaches the optimal O(T^{-2}) for convex optimization.
Since 2024 a different line has shown plain GD can be accelerated without touching its update rule, just by designing the stepsize sequence carefully, including occasional "long steps" (η>1/L) that may temporarily increase the objective. The strongest construction so far is the silver-ratio schedule built on ρsil=1+√2, which reaches a last-iterate rate of O(T^{-1.2715}). Altschuler and Parrilo conjecture this 1.2715 is optimal.
The open question: if clever scheduling already lifts plain GD from exponent 1 to 1.2715, can still better schedules push it all the way to the optimal O(T^{-2})? No one could rule this out. The classical first-order lower bound Ω(T^{-2}) holds for every method using T gradient queries, so it cannot separate plain GD from momentum methods. Sharper GD-specific lower bounds either restrict the schedule class or address the "anytime" setting (one infinite schedule that must work uniformly over all stopping times). Whether plain GD with a well-designed predetermined schedule can reach the optimal O(T^{-2}) was entirely open.
Theorem 2.1: let p⋆:=√(2+√3)≈1.9319. For every p∈(p⋆,2) there is a constant cp>0 such that for every T, smoothness L, initial distance R, and every predetermined nonnegative schedule η, there is a smooth convex f in dimension d≤T+1 with a minimizer x⋆ at distance R from x₀ for which GD's last iterate satisfies
f(xT) − f(x⋆) ≥ cp · L · R² · (T+1)^{-p}.
So plain GD with any nonnegative predetermined schedule has worst-case last-iterate rate no better than Ω(T^{-1.9319}), strictly slower than the optimal O(T^{-2}). This is the first rigorous evidence that stepsize scheduling alone cannot drive plain GD to the optimum.
The bound is broad: stepsizes may be zero or arbitrarily large, in any order, with no monotonicity or descent assumption; only nonnegativity and being fixed in advance (knowing T) are required.
The high-level idea is the authors' "resisting oracle": construct an adversarial GD trajectory, then prove it can be realized by an actual smooth convex function. The concrete mathematical construction is GPT-5.6 Sol Pro's, in three stages:
For comparison, the concurrent anytime lower bound of Tsai et al. (2026) rules out o(T^{-4/3}) for a single infinite positive schedule uniform over all stopping times; its exponent (4/3≈1.333) is weaker but its setting is stronger, and the two results do not imply each other.
This is a theory paper; the numbers are the bound and the gap it carves out:
| Quantity | Exponent | Meaning |
| Constant-stepsize GD | 1 | O(T^{-1}), textbook rate |
| Silver schedule (best upper bound) | 1.2715 | log₂(1+√2), conjectured optimal |
| This lower bound | 1.9319 | √(2+√3), proven impossible to beat |
| Nesterov / first-order optimal | 2 | O(T^{-2}), convex ceiling |
The truth lies in [1.2715, 1.9319]. The paper does not prove the silver schedule optimal (that conjecture stays open), but it tightens the range from below: the optimal exponent cannot exceed roughly 1.9319.
For optimization and training theory, the recent "schedule-only acceleration" line has been hot, and this paper draws a hard ceiling over it. Anyone hoping to approach Nesterov-level speed through stepsize engineering alone now knows there is a floor. It also draws a clean line between what plain GD can do and what needs an actual algorithmic change (momentum).
The more striking angle for the AI community is how the proof was produced. The entire main proof was written by GPT-5.6 Sol Pro. The authors gave it only the research objective (prove a GD lower bound strictly slower than 1/T²) and a high-level strategy (build an adversarial trajectory, then show it is realizable); beyond that, they did not provide any nontrivial mathematical ingredient used in the final proof. It took multiple queries and several attempts to get there. The authors then used Codex to formalize the whole proof in Lean 4 (repo: github.com/jianhaoma/gd-lower-bound-lean), so correctness is not a matter of trusting the model; it is machine-checked line by line.
This is a concrete data point of a frontier model making a non-trivial contribution to original mathematical research, with the verification done right. The cold water is easy to throw: this is one proof, in a subfield (convex optimization) whose constructions are relatively combinatorial and geometric, and the humans supplied the objective and the scaffold while the model filled in the construction. It is not "an LLM solved a Millennium Prize problem." But it is genuine research, disclosed honestly and checked properly.