AI-Developed Lower Bound for Stepsize-Only Gradient Descent Acceleration

On August 11, 2026, Jianhao Ma and Yuxin Chen reported a lower bound for accelerating plain gradient descent solely through a predetermined schedule of nonnegative stepsizes. For every exponent $p>\sqrt{2+\sqrt{3}}\approx1.9319$, they construct a smooth convex objective on which the last-iterate error after $T$ steps is at least a constant times $T^{-p}$. This rules out attaining the optimal general first-order rate $O(T^{-2})$ through stepsize scheduling alone.

The result applies separately to every prescribed horizon and schedule, allowing zero, arbitrarily large, and arbitrarily ordered stepsizes. Its proof constructs a schedule-dependent hard trajectory, realizes it with a smooth convex function, removes temporal order through two matching bounds, and completes the estimate with a rank-cutoff and Lyapunov argument. The endpoint exponent $\sqrt{2+\sqrt3}$ is not proved, and a substantial gap remains between this impossibility threshold and the best known achievable exponent $\log_2(1+\sqrt2)\approx1.2715$.

The authors state that GPT-5.6 Sol Pro developed the main proof after receiving the research objective and a high-level resisting-oracle strategy, without other nontrivial mathematical ingredients from them. They queried the model repeatedly, then substantially reviewed, verified, and revised the generated argument; GPT-5.6 Sol also assisted with organization and exposition. Codex was used to formalize the theorem in Lean 4, and the public repository reports no sorry, admit, or project-defined axioms, but this formalization comes from the same research pipeline rather than an independent review.