Lower Bounds for Stepsize-Based Acceleration of Gradient Descent
Carefully designed stepsize schedules alone accelerate plain gradient descent beyond its textbook O(1/T) rate, without momentum. Whether they can reach the optimal O(T^-2) was open. A lower bound of Omega(T^-1.9319) for last-iterate convergence under predetermined nonnegative stepsize schedules says they cannot.
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Convex optimization
- Posed by
- Raised by the silver-stepsize line of work following Altschuler and Parrilo
- Year posed
- 2023
- Years open
- 3y
- Solved
- 2026-08-11
- Model
- GPT-5.6 Sol Pro
- Vendor
- OpenAI
- Collaborators
- Jianhao Ma, Yuxin Chen
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 10 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Recorded as partial: the bound is Omega(T^-1.9319) against an achievable O(T^-1.2716), so it rules out reaching the optimal rate without pinning down the true one.
What the AI did
The abstract closes with it: "The proof was developed by GPT-5.6 Sol Pro under the authors' guidance." The authors added material to make the proof correct and readable, and separately used Codex to formalize the proof in Lean 4.
Verification
A preprint days old. A Lean 4 formalization by Codex is linked from the paper, but it is the same pipeline that produced the proof, so it is not independent confirmation.
Source
- PaperarXiv