GPT-5 Proves Gradient Descent Hits a Hard Speed Limit at 1.9319

A quiet revolution has been brewing in convex optimization. For decades, textbooks taught that plain gradient descent converges at a rate of O(T^-1), and that reaching the optimal O(T^-2) rate required momentum tricks like Nesterov's method. A series of results starting in 2023 upended that story by showing you could accelerate vanilla gradient descent to roughly O(T^-1.2715) simply by picking exotic stepsize schedules, no momentum required. How far can this trick go?

A new paper by Jianhao Ma and Yuxin Chen answers that question with a hard ceiling, and it does so with a twist that makes the result notable beyond optimization theory: the proof was developed by GPT-5.6 Sol Pro under the authors' guidance, with a companion Lean 4 formalization built using Codex.

The wall at 1.9319

The main result is a lower bound of Ω(T^-1.9319) on the last-iterate convergence rate of gradient descent using any predetermined nonnegative stepsize schedule. The impossibility threshold is p_★ = √(2+√3) ≈ 1.9319, and the authors prove that no exponent strictly larger than this is achievable.

You can twist and torture the stepsize sequence as much as you want, use zero steps, arbitrarily large steps, non-monotonic patterns, whatever, and you still cannot squeeze plain GD past this rate. The paper puts it as the first rigorous evidence that adjusting predetermined stepsize schedules alone is insufficient to accelerate plain gradient descent to the optimal convergence rate.

Why stepsize hedging turned heads

Recent results show that vanilla gradient descent can be accelerated for smooth convex objectives merely by changing the stepsize sequence. The strongest constructions are built around the silver ratio