Worst-case rates of gradient descent with predetermined step sizes

For smooth convex minimization, how fast can the last iterate of gradient descent converge when nonnegative step sizes are prescribed in advance? The schedule may depend on the horizon but not adapt to the objective.

Why it matters and what counts as progress

Why it matters: Lower bounds determine whether step-size schedules alone can match accelerated first-order rates.

What counts as progress: A lower bound for every prescribed schedule separating it from O(T⁻²), or a schedule with a stronger uniform guarantee in L, initial radius and horizon.

How the problem developed

11 Aug 2026 · Lower bound [1]
Jianhao Ma and Yuxin Chen, with GPT-5.6 Sol Pro under their guidance Reported an Ω(T⁻¹·⁹³¹⁹) last-iterate lower bound for gradient descent on smooth convex objectives with predetermined nonnegative step sizes.

AI contribution

A lower bound for stepsize-based acceleration of gradient descent

Jianhao Ma, Yuxin Chen

For every p between sqrt(2+sqrt(3)) and 2, every horizon T and every predetermined nonnegative gradient-descent stepsize schedule, Ma and Chen construct a smooth convex problem in dimension at most T+1 with last-iterate error at least c_p L R²/(T+1)^p.

AI involvementAI-led

ImportanceNotable

Technical verificationFormal (Lean 4 + human)

Human understandingFull