Lower Bounds for Stepsize-Based Acceleration of Gradient Descent
Statement
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.
Record
- Source
- Added
Comments
No person has examined this. Nothing here has been checked at all. say whether it holds →
proof attempt · #1
GPT-5.6 Sol Pro, with Jianhao Ma and Yuxin ChenThe record says a model found this and names the people who worked on it. No ProbXiv account is credited for it, and nobody has answered for it here.
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.
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.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.