A lower bound for stepsize-based acceleration of gradient descent

This paper establishes a new lower bound on the convergence rate of plain gradient descent (GD) when the stepsize schedule is predetermined and nonnegative, showing that such schedules alone cannot achieve the optimal O(T-2) rate for smooth convex optimization.

Main result (Theorem 2.1): For every p > p* = sqrt 2+ sqrt 3 about 1.9319, there exists a constant c p > 0 such that for every horizon T, every L, R > 0, and every predetermined nonnegative stepsize schedule eta = (eta 0,, eta T-1), there exists a dimension d T+1 and a smooth convex function f with grad f(x) - grad f(y) Lx-y, a minimizer x* with x 0 - x* = R, such that GD's last iterate satisfies:

[

f(x T) - f(x*) c p L R squared (T+1)-p.

]

This holds for arbitrary nonnegative stepsizes (including zero or arbitrarily large), arbitrary ordering, and no descent or monotonicity assumptions.

Context: Recent work (Altschuler and Parrilo 2025b; Grimmer et al. 2025b) showed that plain GD can be accelerated from the textbook O(T-1) rate to O(T- 2(1+ sqrt 2)) = O(T-1.2715...) using carefully designed stepsize schedules with occasional long steps, without momentum. The classical (T-2) lower bound applies to all first-order methods, not specifically to GD. This paper provides the first rigorous evidence that predetermined stepsize schedules alone cannot reach the optimal O(T-2) rate.

Proof strategy (Section 2.2):

1. Normalize L = R = 1, decompose each stepsize h t = L eta t into capped part h t,1 and excess y t = (h t-1)+. Define base mass B = 1 + sum t h t,1 and r = number of long steps (h t > 1).

2. Construct an explicit hard instance using a Moreau envelope of a support function over a convex hull of block gradients. The construction selects m long steps, partitions the schedule into blocks, and defines orthogonal anchors X i = lambda i e i with lambda i+1 squared = chi i lambda i squared, where chi i are transition factors. The hard instance is F(x) = z [sigma K(z) + 1 over 2x-z 2] with K = conv0, g 0,, g m. The key property (Lemma 4.2) is that grad F(x) = K(x), the Euclidean projection onto K. The construction yields final gap:

[

F(x T) - F(0) = 1 over 2H m product i=0 m-1 chi i.

]

3. Define the key functional C T(h) = 0 m r 0 t 1< <t m<T 1 over H m product i=0 m-1 chi i. Corollary 4.3 shows this is attained by a valid instance.

4. Remove temporal order dependence using two matchings (Section 5). Rank the excesses a 1 a r > 0, define residual mass D q = B + sum s=q+1 r a s. For each 2 q r, select the q largest excesses, restore chronological order, and bound the reciprocal chain value via a path with two matchings (odd/even edges). This gives:

[

C T(h) q over 2D q(q-1)M q,

]

where M q is the product of two matching values. A total-weight estimate (Lemma 5.3) bounds the geometric mean per edge mu q = M q 1/q in terms of zeta q = D q over q squared sum s=1 q 1 over a s.

5. Final cutoff argument (Section 6): Fix p in (p*, 2), set = 1/(p 2-1). Since p > p*, we have 2 + 2 squared < 1, so choose rho in (0,1) with 2 + 2 squared < rho < 1. For large ranks q Q, if zeta q then mu q rho-q/(2D q).

• If mu q rho, then zeta q > and 0 < nu q <-1, where nu q = q a q / D q.

6. Lyapunov analysis (Lemma 6.3, 6.4): Define potential L q = nu q(zeta q -) over(nu q + p + 1). The exact recursion zeta q+1 = q squared zeta q over(q+1)(q+1+ nu q+1) + 1 over(q+1) nu q+1 drives zeta q toward 1/(nu(nu+2)). Telescoping the drift gives D k k p-1 K p B r p-1 along intervals where the second alternative persists.

7. Combining cases yields Proposition 6.1: C T(h) c p / (B(r+1) p-1). Since B T+1 and r+1 T+1, this gives C T(h) 2c p (T+1)-p.

8. Restore scaling via Lemma 6.6: f(x) = LR squared F(x/R) gives f in F 0,L(R d), x 0 - x* = R, and f(x T) - f(x*) = LR 2(F(T) - F(0)).

Threshold exponent: The matching estimate requires 2 + 2 squared sqrt 2+ sqrt 3 = p*. At p = p*, the interval (2 + 2 squared, 1) collapses, so the theorem does not establish the endpoint (T-p*).

Key technical lemmas:

• Lemma 4.2: For compact convex K with 0 in K, the Moreau envelope F(x) = z[sigma K(z) + 1 over 2x-z 2] satisfies grad F(x) = K(x), F(x) = 1 over 2x squared - 1 over 2 dist(x,K) squared, and is convex with 1-Lipschitz gradient.

• Lemma 5.2: Product inequality under mass constraint sum u i D.

• Lemma 5.3: Matching product bound P psi(W,k) 1/k over 2k + squared over 8k squared, where is total vertex weight.

• Lemma 6.2: Exact adjacent-rank recursions: D q-1/D q = 1 + nu q/q, zeta q+1 = q 2 zeta q over(q+1)(q+1+ nu q+1) + 1 over(q+1) nu q+1.

• Lemma 6.3: One-step Lyapunov drift estimate L n - L n-1 p-1-nu n over n + C p over n squared.

• Lemma 6.4: Growth bound D k k p-1 K p B r p-1 when mu q rho for all q in k+1,,r.

• Lemma 6.5: Bounded-rank prefix bound C T(h) c Q / D q 0 for 0 q 0 Q,r.

• Lemma B.1: For 0 q 0 r, at least one of the prefix chains (empty, tau 1, tau 1, tau 2,, tau 1,, tau q 0) has value at least 1/(4D q 0 q 0 8 q 0-1).

Comparison with anytime lower bounds: The concurrent result of Tsai et al. (2026) rules out o(T-4/3) for any single infinite sequence of strictly positive stepsizes that must work uniformly over all stopping times. Theorem 2.1 allows a different predetermined schedule for each horizon, so the anytime bound does not imply this result.

Open problems (Section 7):

• Determining the optimal convergence exponent (gap between upper bound T-1.2715 and lower bound T-1.9319).

• Lower bounds for the best iterate 0 t T f(x t) - f(x*).

• Lower bounds for strongly convex problems.

• Allowing negative or adaptive stepsizes.

Disclosure: The main proof was developed by GPT-5.6 Sol Pro under the authors' guidance, with the authors providing the research objective and a high-level resisting-oracle strategy. The proof was not produced in a single interaction; multiple queries were made. The authors spent substantial effort reviewing, verifying, and revising the material, and used Codex to formalize the proof in Lean 4.

Based on this paper, here are the specific improvements I can make to AI systems, and what the improved system can do:

1. Adaptive Stepsize Scheduling with Provable Worst-Case Guarantees

• Improvement: Integrate the lower-bound theorem (Theorem 2.1) into the optimizer's decision loop. The system can now detect when a predetermined, nonnegative stepsize schedule is fundamentally incapable of achieving better than O(T-1.9319) on smooth convex objectives, and automatically switch to a different algorithmic family (e.g., accelerated gradient with momentum, or adaptive/feedback-based stepsizes) when the horizon T is large.

• What it can do: An AI system can now certify its own convergence rate before execution. Given a target accuracy epsilon and a horizon T, it can check whether the required rate O(T-2) is attainable; if not, it will reject the plain GD with fixed schedule configuration and propose an alternative (e.g., Nesterov acceleration) with a formal guarantee, preventing silent underperformance.

2. Hard-Instance Generation for Robustness Testing

• Improvement: Use the explicit construction (Moreau envelope of a support function over block gradients, Lemma 4.2) to generate adversarial smooth convex functions that are worst-case for any predetermined nonnegative stepsize schedule. The system can synthesize these instances on-the-fly for arbitrary T, L, R, and schedule.

• What it can do: An AI system can now stress-test any new optimization algorithm (including learned or neural-network-based step-size policies) against provably hard instances. It can automatically generate a benchmark suite that exposes the exact worst-case exponent p for a given schedule, enabling empirical verification of theoretical claims and preventing overfitting to easy problems.

3. Horizon-Aware Schedule Design with Cutoff Thresholds

• Improvement: Incorporate the threshold exponent p* = sqrt 2+ sqrt 3 about 1.9319 into the schedule optimizer. The system can now classify any candidate schedule by its effective exponent using the functional C T(h) and the Lyapunov drift analysis (Lemmas 6.3–6.4). It can prune schedules that fall below the threshold and search only among those that could theoretically approach O(T-2).

• What it can do: An AI system can now perform a provably guided hyperparameter search over stepsize schedules. Instead of random or grid search, it can compute the matching-based bound C T(h) for candidate schedules, discard those with p < p*, and focus computational effort on schedules with the best theoretical ceiling—reducing search time by orders of magnitude while maintaining worst-case guarantees.

4. Anytime vs. Fixed-Horizon Trade-off Detection

• Improvement: Leverage the distinction between the anytime lower bound (o(T-4/3)) and the fixed-horizon lower bound (T-1.9319) to build a meta-controller. The system can decide whether to use a single infinite sequence (for streaming/online settings) or a horizon-specific schedule (for batch settings) based on the task's stopping-time flexibility.

• What it can do: An AI system can now automatically choose the optimal algorithmic regime: if the user can commit to a fixed horizon, it can use a schedule that exploits the higher T-1.9319 bound; if the stopping time is unknown or adaptive, it will switch to a conservative anytime-safe schedule. This prevents catastrophic failure when the horizon is misestimated.

5. Formal Verification of Convergence Claims

• Improvement: Use the Lean 4 formalization (mentioned in the disclosure) to build a certified optimizer. The system can now verify, at runtime, that its chosen stepsize schedule satisfies the necessary conditions for the lower bound (e.g., checking the mass B, long-step count r, and the matching product M q) and reject any schedule that violates the structural constraints.

• What it can do: An AI system can now produce machine-checkable certificates for its convergence claims. For any given schedule, it can output a formal proof that the worst-case gap is at least c p L R squared (T+1)-p for some p, or explicitly state that the schedule is outside the theorem's scope—eliminating false confidence in unverified heuristics.

6. Automatic Exponent Optimization via the Dichotomy

• Improvement: Implement the cutoff argument (Section 6) as an internal optimizer. The system can iteratively adjust the stepsize schedule to push the effective exponent p toward p*, using the dichotomy: if mu q < rho, increase the mass D q or adjust excesses to raise the bound; if mu q rho, use the Lyapunov recursion to find the optimal nu q that minimizes the drift.

• What it can do: An AI system can now perform closed-loop schedule design that provably approaches the lower-bound exponent. It can output a schedule with a certified worst-case rate, and if the user demands better than T-1.9319, it will immediately flag this as impossible for plain GD and recommend a different algorithm—saving time and resources.

7. Safe Fallback for Degenerate Schedules

• Improvement: Use Lemma B.1 (bounded-rank prefix bound) to build a safety net. The system can detect when a schedule has too few long steps or too little mass (e.g., r small or B small) and automatically fall back to a provably safe schedule (e.g., constant stepsize) that guarantees at least O(T-1).

• What it can do: An AI system can now guarantee a minimum performance floor even for poorly designed schedules. It can monitor the schedule's structural parameters in real time and trigger a fallback before the optimization diverges, ensuring that no run ever performs worse than the textbook rate, regardless of user error or adversarial initialization.

8. Cross-Method Comparison and Recommendation

• Improvement: Embed the lower-bound result as a speed limit in a meta-learning system. The system can compare the theoretical ceiling of plain GD (with any predetermined schedule) against alternatives (momentum, adaptive methods, or negative stepsizes) and recommend the best method for a given problem class, using the paper's open problems as a guide (e.g., strongly convex cases remain open, so the system will flag those as requiring empirical caution).

• What it can do: An AI system can now provide a principled recommendation: For this smooth convex problem with horizon T, plain GD cannot beat T-1.9319, but Nesterov acceleration achieves T-2; therefore, use Nesterov. This prevents the common mistake of over-tuning GD's schedule when a different algorithm is fundamentally superior.