Improved Gradient Descent Lower Bounds Beyond Nesterov

Yuhan Ye; Kaizhao Liu

Source-linked AI summary

Improved Gradient Descent Lower Bounds Beyond Nesterov

Yuhan Ye, Kaizhao Liu

arXiv:2609.02855v2Sep 2, 2026math.OCcs.LGstat.ML

TL;DR

The paper studies how far gradient descent can be accelerated using predetermined stepsizes in smooth convex optimization, where stronger lower bounds are needed beyond classical guarantees. It refines a hard-function product analysis by preserving consecutive long-step interactions, proving improved non-anytime and anytime lower bounds that remain valid with negative stepsizes. The anytime result also rules out the non-anytime silver rate and separates the two settings.

Problem
The paper asks how far GD can be accelerated by predetermined stepsizes in smooth convex optimization, amid gaps between known lower and upper bounds.
Method
The paper refines a hard-function product lower bound by retaining every factor coupling consecutive selected long steps and analyzing the resulting sequence inequalities.
Results
The paper proves Ω(n^-1.6342) and Ω(n^-1.2408) lower bounds in the non-anytime and anytime settings, respectively, including schedules with negative stepsizes.
Takeaways & Limitations
The anytime lower bound shows that the non-anytime silver rate is unattainable for a single schedule at every stopping time, establishing a strict separation.
Takeaways & Limitations
Gaps remain between the lower and upper bounds, and the current use of Lemmas 2.1–2.2 may not suffice to close them.

Abstract

from arXiv · show

We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Going beyond the classical $Ω(n^{-2})$ first-order oracle lower bound of Nemirovsky and Yudin (1983), we prove an $Ω(n^{-1.6342})$ non-anytime lower bound and an $Ω(n^{-1.2408})$ anytime lower bound. These improve the recent $Ω(n^{-1.932})$ non-anytime lower bound of Ma and Chen (2026) and the $Ω(n^{-4/3})$ anytime lower bound of Tsai et al. (2026), respectively. Both results continue to hold when the stepsizes may be negative. Our anytime lower bound also shows that the $O(n^{-\log_2(1+\sqrt{2})})$ rate of non-anytime silver schedules (Altschuler and Parrilo, 2025; Grimmer et al., 2025) is unattainable in the anytime setting. This establishes a strict separation between the two settings.

1 Introduction

The paper asks how much predetermined-stepsize gradient descent can be accelerated in smooth convex optimization, beyond its classical O(n^-1) rate. It improves lower bounds in both finite-horizon and anytime settings, establishes a strict separation between them, and covers negative stepsizes.

1 Introduction: Predetermined stepsizes define the studied GD class, with schedules fixed in advance for either a chosen horizon or all horizons.The non-anytime schedule is designed for a fixed n, whereas one infinite schedule is reused at every stopping time.
1 Introduction: The classical Ω(n^-2) first-order lower bound applies to GD, while prior results left gaps between GD lower and upper bounds.Silver schedules achieved faster finite-horizon rates, and anytime constructions also accelerated GD, motivating stronger lower bounds.
1.1 Contribution: The paper improves the non-anytime lower bound to Ω(n^-1.6342) and the anytime lower bound to Ω(n^-1.2408).These results narrow the gaps between known lower and upper bounds in both settings.
1.1 Contribution: The anytime lower bound shows that the non-anytime silver rate is unattainable at every stopping time, establishing a strict separation between the settings.The distinction concerns finite-horizon schedules versus a single infinite schedule used for every horizon.
1.1 Contribution: Both lower bounds remain valid when negative stepsizes are allowed, resolving an open question from prior lower-bound results.Earlier cited lower bounds covered only nonnegative schedules.

2 Technique overview

The proof starts from a schedule-adapted hard-function product lower bound and refines it by retaining interactions between consecutive long steps. Sequence inequalities, majorization, matching arguments, and numerical parameter selection yield the improved non-anytime exponent, which is extended to arbitrary schedules and the anytime setting.

2 Technique overview: The hard-function construction reduces GD’s lower bound to a product involving selected long steps and the stepsize accumulations between them.Each Si records the accumulation between consecutive selected long steps.
2 Technique overview: The main technical refinement retains every factor coupling consecutive selected long steps instead of summarizing all excesses with one aggregate quantity.This differs from earlier bounds based on a single summary or the harmonic mean of long-step excesses.
2 Technique overview: The product bound is reduced to a sequence inequality, with a cutoff selecting the largest excesses and normalization imposing tail conditions on rearranged weights.The reduction chooses the cutoff from the schedule and ensures the normalized variables have total mass below q.
2 Technique overview: Consecutive-pair sums are controlled through matching, symmetry, convexity, majorization, submodularity, and comparison with a one-dimensional integral.These steps replace unknown weights by an explicit comparison sequence and identify the maximizing matching.

3 Proof of the Non-Anytime Lower Bound

The proof reduces the non-anytime GD lower-bound problem to inequalities over selected long-step excesses, then controls consecutive-pair contributions through matching, majorization, and regularity properties.

3.1 Reduction to a sequence inequality: The proof decomposes each stepsize into a base min{h_k,1} and an excess max{h_k−1,0}, then orders positive excesses decreasingly.The base accumulation is bounded by n+1, and D_s excludes the excesses from the s longest steps.
3.1 Reduction to a sequence inequality: The q=1 case directly yields R_n(H) ≥ 1/[4(n+1)^(α+1)] through separate bounds depending on the largest excess a_1.The proof handles a_1≤D_1 and a_1>D_1 separately before combining the cases.
3.1 Reduction to a sequence inequality: For q≥2, the reduction selects the q largest positive excesses and normalizes the associated quantities into sequences x_i and weights ω_i.The selected indices are ordered chronologically, while the positive excesses are summarized in decreasing order for the sequence inequality.
3.3 Properties of Γ_λ: The function Γ_λ is shown to have a unique smooth optimizer and to be symmetric, jointly convex, and coordinatewise decreasing.These properties support later majorization and matching arguments.
3.4 Upper bounding ∑q−1: Consecutive pairs are split into odd and even matchings; symmetry, convexity, and coordinatewise decrease permit majorization and selection of a maximizing matching.The resulting sum is then compared with a Riemann integral, while a Lipschitz extension controls endpoint behavior.

4 Anytime Lower Bound

The anytime proof strengthens the lower bound by enforcing consistency across all horizon prefixes of one infinite schedule. It combines a truncated sequence inequality with an anytime transfer argument and verifies a parameter choice numerically.

4 Anytime Lower Bound: In the anytime setting, one infinite schedule h=(h_k)_{k≥1} is fixed in advance, and its prefix H_n=(h_1,...,h_n) is used at horizon n.Unlike the finite-horizon setting, schedules at different horizons must be consistent.
4 Anytime Lower Bound: The proof combines the preceding term-by-term estimate with the anytime transfer argument of [TFZH26].The initial proof treats nonnegative infinite schedules, with an extension to arbitrary schedules stated afterward.
4 Anytime Lower Bound: The anytime problem is reduced to a truncated sequence inequality whose constraints leave the ℓ largest weights unconstrained.For ℓ>1, the product estimate has exponent qJ(α,λ)+O_{α,λ}(ℓ+1).
4 Anytime Lower Bound: For α=0.6342 and λ=0.4506, numerical integration gives J(0.6342,0.4506)<−0.00005, implying that no nonnegative infinite schedule achieves o(n^−1.2408).The argument uses 2(1+0.6342)/(2+0.6342)=1.240756...<1.2408 and is extended to arbitrary stepsize schedules.

5 Concluding Remarks

The paper strengthens GD lower bounds with predetermined stepsizes in both non-anytime and anytime settings, while negative stepsizes remain covered. Important gaps to corresponding upper bounds remain open, partly because the current hard-function and transfer arguments may be insufficient.

The proofs refine the hard-function product lower bound by analyzing consecutive-pair factors term by term.
Ω(n^-1.6342) improves the non-anytime lower bound from Ω(n^-1.7321).
Ω(n^-1.2408) improves the anytime lower bound from Ω(n^-4/3) through finite-to-anytime transfer.
Both lower bounds continue to hold when negative stepsizes are allowed.
Closing the gaps to corresponding upper bounds remains a significant open problem.
The current Lemma 2.1-to-Lemma 2.2 route may not suffice to match the silver-schedule upper bound.

AI Disclosure

The authors used ChatGPT-5.6 Sol during development of both the non-anytime improvement and the anytime extension, then reviewed and rewrote the resulting work. They retain full responsibility for correctness and originality.

ChatGPT-5.6 Sol helped develop the non-anytime proof over multiple rounds.
The authors subsequently checked the calculation and reorganized and rewrote the presentation.
ChatGPT-5.6 Sol also helped develop the anytime extension proof.
The authors take full responsibility for the correctness and originality of all content.

A Hard-Function Construction

The hard-function construction combines Huber-style affine behavior with fresh orthogonal directions so selected long steps switch gradient blocks without repeatedly exploiting one direction. A Moreau-envelope realization makes the construction globally smooth and convex, while the analysis reduces the lower bound to scalar inequalities and optimization.

For nonnegative schedules with h_k ≤ 1, the Huber construction gives R_n(H) ≥ 1/(2n+1), so improving the n^-1 scale requires steps strictly larger than 1.
Fresh orthogonal directions prevent selected long steps from repeatedly exploiting the same one-dimensional overshoot.
The Huber function supplies constant-gradient affine regions, while new coordinate axes keep successive long-step effects separate.
The construction divides the schedule into transition blocks and a terminal block, with each selected long step moving between coordinate-axis anchors.
A Moreau envelope of a support function realizes the prescribed gradient pattern as a globally convex function with a 1-Lipschitz gradient.
The hard function retains a quadratic region and affine outer pieces, with gradients represented through projections onto a convex set.
The lower-bound proofs reduce to finding the smallest α for which J(α,λ) ≤ 0, optimizing over λ.
J(α,·) is strictly convex with a unique minimizer in (1/4,1/2), while its minimized form is continuous and strictly decreasing in α.

C Proofs for the Anytime Lower Bound

This appendix proves the two lemmas underlying the anytime lower bound.

The appendix proves Lemmas 4.1 and 4.2.

C.1 Proof and Intuition of Lemma 4.1

The proof strengthens the finite-to-anytime transfer by combining one-dimensional lower bounds with refined control of positive stepsize excesses. These bounds yield a contradiction for schedules that would otherwise achieve an overly fast anytime rate.

Part II: The anytime transfer: The transfer begins with lower bounds relating R_n(H_n) to the total stepsize and controlling terminal steps exceeding one.Convex quadratics provide the total-sum control, while an asymmetric Huber loss supplies the terminal-step bound.
Part I: Constructing tail bounds: The proof partitions positive excesses into decreasing order and establishes two tail inequalities whenever R_n(H)D_m ≤ c_0.These inequalities compare adjacent D_m values and control D_m itself, allowing the remaining excesses to be summed.
Part I: Constructing tail bounds: The first tail bound follows by selecting the largest excesses, applying the comparison inequality, and ruling out excessively large normalized weights.A contradiction results when the selected excesses exceed the threshold β_αD_s/s.
Part I: Constructing tail bounds: The second tail bound proves that F_m = D_ms^α remains comparable to F_r, using the first inequality and the assumed implication between the tail conditions.The constants depend only on α, and the argument concludes with bounds on D_r and r.
Part II: The anytime transfer: Applying the tail bounds to a sufficiently large prefix controls both head and tail excesses, forcing a total-stepsize estimate that contradicts R_n(H_n)(1+2h_1:n) ≥ 1.The contradiction completes the anytime transfer for nonnegative schedules.

C.2 Proof of Lemma 4.2

Lemma 4.2 replaces discrete matching sums with integral estimates under tail constraints. Its proof removes unconstrained weights, identifies maximizing matchings, and bounds the resulting Riemann-sum error.

Step 1. Eliminate the x_i’s: The proof first eliminates the x_i variables using the Lipschitz estimate for Γ_λ(W_α(u), W_α(v)).This reduces the comparison to expressions involving the ordered weights and the function W_α(t) = αt^-1-α.
Step 2. Set aside the ℓ unconstrained largest weights: The ℓ largest normalized weights are unconstrained by the tail conditions and are removed from the odd and even matchings.At most 2ℓ matching terms are deleted.
Step 3. Identify the maximizing matching and compare it with the integral: After ordering the remaining weights, convexity, symmetry, and coordinatewise decrease identify the relevant matching comparison.The odd and even matchings are then compared with a corresponding Riemann integral.
Step 3. Identify the maximizing matching and compare it with the integral: The shifted Riemann-sum estimate bounds discretization error in terms of the matching imbalance d and the number of terms.Separate cases handle d ≥ q/4 and d < q/4.
Step 3. Identify the maximizing matching and compare it with the integral: Applying the estimate to both matchings and restoring deleted terms proves the target bound (30).The deleted contributions are controlled because every remaining weight is at least α.

D Extension to Possibly Negative Stepsize Schedules

The negative-stepsize extension replaces a signed schedule by a nonnegative schedule based on running maxima of cumulative steps. A trajectory comparison on the same hard function transfers the lower bounds unchanged.

Extension to possibly negative stepsize schedules: A signed schedule is converted into a nonnegative schedule that advances only when the signed cumulative stepsize reaches a new maximum.The associated schedule is defined from partial sums P_k and running maxima M_k.
Extension to possibly negative stepsize schedules: For selected long steps, the associated nonnegative schedule preserves the lower-bound expressions used for R_n.This establishes the required transfer for the hard instance corresponding to the finite-schedule bound.
Extension to possibly negative stepsize schedules: The proof compares the signed and associated trajectories block by block and shows that they meet at each block boundary.The comparison uses the displacement d_k between cumulative sums and running maxima.
Extension to possibly negative stepsize schedules: Both trajectories use the same hard function, initial point, and minimizer, while the associated trajectory attains at least the signed schedule’s normalized gap.Taking the supremum over admissible functions and initial points transfers the lower bound to the signed schedule.
Extension to possibly negative stepsize schedules: The same replacement argument completes both the non-anytime and anytime lower bounds for arbitrary real-valued schedules.The subsequent proofs remain unchanged after all quantities are recomputed from the associated nonnegative schedule.