Pith. sign in

REVIEW 1 major objections 4 minor 33 references

A lower bound for stepsize-based acceleration of gradient descent

T0 review · 1 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that no predetermined nonnegative stepsize schedule lets gradient descent beat a 1/T^1.9319 worst-case last-iterate rate on smooth convex problems.

desk verdict First lower bound for horizon-dependent stepsize schedules: the math looks consistent on inspection, but the GPT-generated proof and unauditable Lean artifact put the verification burden on the reader. read the letter →

arxiv 2608.10418 v1 pith:MVBITVCR submitted 2026-08-11 math.OC cs.LGstat.ML

Jianhao Ma , Yuxin Chen This is my paper · ORCID
classification math.OCcs.LGstat.ML MSC 90C2590C6065K05
keywords gradientdescentstepsizescheduleslowerboundlast-iterateconvergencesmoothconvexoptimizationsilverMoreauenvelopeacceleration
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves a structural limitation of stepsize-based acceleration: for every exponent $p > p^* = \sqrt{2+\sqrt{3}} \approx 1.9319$, and for every prescribed nonnegative stepsize schedule $\eta$, there exists a smooth convex problem on which gradient descent's last iterate is at least $c_p L R^2 (T+1)^{-p}$ from optimality. In plain terms, no schedule chosen in advance—no matter how long the steps or how they are ordered—can force plain gradient descent to converge faster than $T^{-1.9319}$ in the worst case over $L$-smooth convex functions. The consequence is that stepsize schedules alone cannot close the gap to Nesterov's optimal $O(T^{-2})$ rate without momentum. The paper's construction makes the hard instance explicit in dimension at most $T+1$, and it deliberately allows zero steps, arbitrarily large steps, and non-monotone objective values along the trajectory.

What carries the argument

The carrying object is the Moreau envelope of the support function of a convex hull: for $K=\operatorname{conv}\{0,g_0,\dots,g_m\}$ the paper sets $F(x)=\min_z\{\sigma_K(z)+\tfrac12\|x-z\|^2\}$, whose gradient is exactly the Euclidean projection $\Pi_K(x)$ onto $K$ (Lemma 4.2). The construction chooses orthogonal anchor points and block gradients so that, as long as each squared amplitude obeys $\gamma_i^2\le\chi_i$ from (7), the projection at every visited iterate is the prescribed block gradient; the long-step transitions then move the trajectory from one anchor to the next, and the terminal gap equals $\tfrac{1}{2H_m}\prod_{i=0}^{m-1}\gamma_i^2$ (Theorem 4.1). All schedule-dependence is thereby concentrated in the functional $C_T(h)$ from (20), whose lower bound is derived by ranking excesses, bounding the reciprocal chain value through two matchings (Proposition 5.1), and controlling residual schedule mass with a Lyapunov potential.

What would settle it

Exhibit a single predetermined nonnegative stepsize schedule $\eta$ and prove that, for every $L$-smooth convex $f$ with $\|x_0-x^*\|\le R$, the last-iterate gap is $O(T^{-q})$ for some $q>p^*$ (say $q=1.95$); Theorem 2.1 asserts an $\Omega(T^{-p})$ lower bound for every $p>p^*$, so such a schedule would be a direct counterexample. A more surgical check is to evaluate the functional $C_T(h)$ from (20) for that schedule on a sequence of horizons and show $C_T(h)\ll T^{-p^*}$; since Corollary 4.3 says the worst-case gap equals $C_T(h)/2$, that would falsify the reduction immediately.

Watch

Extended reading notes

Core claim

The central claim is Theorem 2.1: for each $p\in(p^*,2)$ there is a constant $c_p>0$ such that, for every horizon $T$, every $L,R>0$, and every predetermined schedule $\eta=(\eta_0,\dots,\eta_{T-1})$ of nonnegative stepsizes, there is an $L$-smooth convex $f$ in some dimension $d\le T+1$ with a minimizer $x^*$ at distance $R$ from the initialization for which the last-iterate gap satisfies $f(x_T)-f(x^*) \ge c_p L R^2(T+1)^{-p}$. This establishes an $\Omega(T^{-p})$ lower bound for all $p>p^*$, hence rules out any asymptotic last-iterate rate faster than $T^{-p^*}$ for stepsize-only gradient descent. The endpoint $p=p^*$ itself is left open, as is the gap to the known silver-ratio upper bound $O(T^{-\log_2(1+\sqrt2)})$. The paper frames the result as the first rigorous evidence that predetermined stepsize schedules alone cannot accelerate plain GD to the optimal $O(T^{-2})$ rate.

Load-bearing premise

The proof's load-bearing premise is the geometric realization theorem: for every selection of long steps with squared amplitudes satisfying $0<\gamma_i^2\le\chi_i$ in (7), the Moreau envelope's Euclidean projection onto $K$ equals the prescribed block gradient at every visited iterate, including the terminal block and all unhandled combinations of stepsize order; if that projection identity failed at any iterate, the constructed trajectory would not realize the chain value in (20) and the lower bound would not follow.

Editorial extensions

If this is right

  • Every predetermined nonnegative stepsize schedule has a worst-case last-iterate rate no faster than $\Omega(T^{-p})$ for every $p>p^*$, so asymptotically the barrier is $T^{-1.9319}$.
  • Stepsize schedules alone cannot reach the $O(T^{-2})$ rate of Nesterov acceleration; the acceleration seen from silver stepsizes is real but bounded away from optimal.
  • The lower bound applies even when zero steps, arbitrarily large steps, or non-monotone objective values are allowed, and it uses only $T+1$ dimensions.
  • The silver-ratio upper bound $O(T^{-\log_2(1+\sqrt2)})\approx O(T^{-1.2715})$ remains compatible with the lower bound, so the true exponent for stepsize-based acceleration lies somewhere between these two values.
  • Because the schedule may depend on the horizon $T$, the statement is about prescribed-horizon planning, not about single infinite anytime schedules, and it is not a consequence of the anytime lower bound.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The way the threshold $p^*$ emerges from the matching condition $2\theta+2\theta^2<1$ suggests that any improvement toward $T^{-2}$ would need a sharper total-weight estimate for matchings, not merely longer schedules; testing whether the matching lemma can be sharpened is a natural next step.
  • The same Moreau-envelope construction is modular enough to be reused for other deterministic first-order methods whose iterates stay in the span of past gradients, for example extrapolated or averaged iterates; the paper does not claim such bounds, but the block-projection mechanism transfers.
  • A concrete check of the functional $C_T(h)$ from (20) for small horizons by exhaustive search over schedules would test the sharpness of the matching and Lyapunov estimates; if any schedule achieved $C_T(h)\ll T^{-1.932}$ along a sequence, the proof's inequalities would be overestimates and the true exponent could be lower.
  • The bound's invariance to ordering and allowance of arbitrarily large steps suggests that adaptive feedback rules, which observe the function along the way, are the next class to test; the paper explicitly leaves signed and adaptive stepsizes open.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper proves a new worst-case lower bound for plain gradient descent with predetermined nonnegative stepsize schedules on smooth convex functions. The main result, Theorem 2.1, states that for every exponent p > p* = sqrt(2+sqrt(3)) ≈ 1.9319, every horizon T, every L,R > 0, and every predetermined nonnegative schedule, there is a smooth convex instance (in dimension at most T+1) whose last-iterate suboptimality is at least c_p L R^2 (T+1)^{-p}. The proof normalizes to L=R=1, decomposes each step into a capped part and an excess, selects long steps, and constructs a hard instance via the Moreau envelope of the support function of a simplex (Theorem 4.1). A key functional C_T(h) is then bounded below by an order-free matching argument (Proposition 5.1 and Lemma 5.3), followed by a rank-cutoff and Lyapunov mass-growth argument (Section 6). The endpoint p = p* is not reached; the result leaves open the gap between the best known upper exponent log_2(1+sqrt(2)) and the new impossibility threshold.

Significance. If correct, this is a substantial contribution: it is the first rigorous evidence that prescribed nonnegative stepsize schedules alone cannot accelerate plain gradient descent to the optimal O(T^{-2}) rate, and it distinguishes the prescribed-horizon setting from both the anytime lower bound of Tsai et al. and the classical oracle lower bound of Drori. The proof is fully written out and parameter-free, with explicit constructions whose dimension is at most T+1; the threshold p* arises cleanly from the competing requirements 2theta+2theta^2<1 and the Lyapunov exponent. I spot-checked the load-bearing identities—the factor expansions (26), the mass decomposition (24)–(25), the equalization Lemma 5.2, the matching bound (40), the recursions (49)–(53), the drift identity (65), and the bounded-rank prefix bound (B.1)—and found them internally consistent. The projection identity at the heart of Theorem 4.1 is proved for every s in [0,U_i-1] on every block, including empty gaps, zero steps, and unselected long steps inside gaps.

major comments (1)
  1. [Theorem 2.1 / proof of Theorem 2.1 in Section 6.4] The theorem's universal quantifier over every prescribed initial point x0 is not established by the written proof. Corollary 4.3 and the final scaling argument construct a normalized instance with initial point x̄0 = e0 and then only scale it, yielding x0 = R e0 in the basis chosen by the construction. Since the objective is allowed to depend on the prescribed initial point, the missing step is an orthogonal change of variables: choose U in O(d) with U e0 = x0/R and define f(x) = L R^2 F(U^T x/R), x* = 0; then the GD iterates satisfy x_t = R U x̄_t and the same suboptimality bound holds. This is a local repair, but as written the theorem's stated quantifier is not proved.
minor comments (4)
  1. [Section 7 (Disclosure on the use of generative AI)] The claimed Lean 4 formalization is referenced only by a URL, with no commit hash, toolchain version, build instructions, or list of formalized theorem statements. Without these details the formalization claim cannot be independently checked; please pin the artifact and specify exactly which statements (e.g., Theorem 2.1, Theorem 4.1, Proposition 5.1, Proposition 6.1) are formalized.
  2. [Theorem 2.1 and Remark 2.2] The quantifier order in Theorem 2.1 should be clarified: the objective f and minimizer x* are allowed to depend on the prescribed initial point x0 as well as on T, L, R, and the schedule eta; Remark 2.2 currently mentions only the horizon and the schedule.
  3. [Section 5.1, Eq. (26)] The reciprocal-factor expansion (26) is load-bearing and correct, but the derivation would be more readable if the intermediate identity chi_{i-1}^{-1} = U_{i-1}(H_{i-1}+H_i)/(c_i H_i) were shown explicitly before expanding.
  4. [Appendix B.4, Eq. (72)] In the terminal-factor estimate (72), the final inequality 3q D_q <= 3 D_{q0} q0 uses D_q <= D_{q0}(q0+1)/(q+1) together with monotonicity of q(q0+1)/(q+1) in q; a one-sentence justification would prevent reader confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the lower bound is derived from an explicit hard-instance construction with independent matching and Lyapunov arguments, not from fitted constants or self-referential definitions.

full rationale

The paper's central claim, Theorem 2.1, is a parameter-free worst-case lower bound over all predetermined nonnegative stepsize schedules. The derivation is self-contained against external definitions of smooth convex optimization: it constructs a Moreau envelope of the support function of a simplex (Section 4.3), characterizes the projection onto that simplex at every visited iterate (Theorem 4.1), reduces the problem to lower-bounding a geometric functional C_T(h) (Corollary 4.3), and then proves that lower bound using order-free matching inequalities (Proposition 5.1, Lemmas 5.2 and 5.3) and a rank-cutoff/Lyapunov mass-growth argument (Proposition 6.1, Lemmas 6.2–6.5). The constants c_p, rho, Q, K_p, and c_Q depend only on the fixed exponent p, and the threshold p* = sqrt(2+sqrt(3)) follows from the explicit inequalities 2*theta + 2*theta^2 < 1 with theta = 1/(p^2 - 1). No fitted parameter is renamed as a prediction, no quantity is defined in terms of the target lower bound, and no load-bearing uniqueness theorem is imported from a self-citation. The only self-citation in the paper is Zhang et al. (2025), the authors' own anytime acceleration work, and it is mentioned only as related work, not used as a proof input. The disclosure that GPT-5.6 Sol Pro generated the proof, and that the Lean formalization is only referenced by URL, is a legitimate epistemic verification concern, but it is not circularity: the manuscript's mathematical chain is not equivalent to its inputs by construction. The paper should therefore receive a circularity score of 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The proof introduces no data-fitted constants: p is a theorem parameter, and theta, rho, Q, c_p are chosen from inequalities, not from measurements. There are no new physical or mathematical entities beyond the constructed convex functions, which are built from standard support functions and Moreau envelopes. The AI-generation provenance is a verification concern, not a mathematical assumption.

assumptions (3)
  • standard math Standard Euclidean projection, support function, and Moreau envelope identities, including Lemma 4.2 that grad(F) = projection onto K for the Moreau envelope of a support function.
    Used at the start of Section 4.3 to convert a piecewise constant gradient field into a single convex 1-smooth function. The lemma is proved in Appendix A and is a classical convex-analysis fact.
  • domain assumption The theorem is scoped to L-smooth convex functions, predetermined nonnegative stepsize schedules, and the last-iterate objective gap.
    This is the model class in Theorem 2.1. The paper explicitly does not cover adaptive, signed, or anytime schedules, as discussed in Sections 2.1, 3, and 7.
  • standard math Every admissible block-decomposition trajectory is realizable by a Moreau envelope of a convex hull of block gradients, subject to the local criterion 0 < gamma_i^2 <= chi_i.
    This is Theorem 4.1, the geometric core of the proof. It is proved in Section 4.3 via projection comparisons, but the entire lower-bound argument collapses if this construction fails at any iterate.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A lower bound for stepsize-based acceleration of gradient descent." pith.science (2026). https://pith.science/paper/MVBITVCR

@misc{pith2026260810418,
  author       = {Pith},
  title        = {Pith review of: A lower bound for stepsize-based acceleration of gradient descent},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MVBITVCR}},
  note         = {Machine review of arXiv:2608.10418}
}
abstract

Recent work has shown that, for smooth convex optimization, plain gradient descent can be accelerated from its textbook convergence rate of $O(T^{-1})$ (where $T$ denotes the number of iterations) to $O\big(T^{-\log_2(1+\sqrt{2})}\big)$ using carefully designed stepsize schedules alone, without resorting to momentum or other algorithmic modifications. Despite this progress, however, little was known about lower bounds for such methods beyond the classical $\Omega(T^{-2})$ benchmark for general first-order methods. In this work, we present a new lower bound of $\Omega(T^{-1.9319})$ for the last-iterate convergence rate of gradient descent with predetermined nonnegative stepsize schedules. This result provides rigorous evidence that stepsize schedules alone cannot accelerate plain GD to the optimal $O(T^{-2})$ convergence rate. The proof was developed by GPT-5.6 Sol Pro under the authors' guidance.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 25 canonical work pages

  1. [1]

    , title =

    Nesterov, Yurii E. , title =. Soviet Mathematics Doklady , volume =

    work page

  2. [2]

    Foundations and trends in Machine Learning , volume=

    Convex optimization: Algorithms and complexity , author=. Foundations and trends in Machine Learning , volume=. 2015 , publisher=

    2015

  3. [3]

    International Conference on Machine Learning , pages=

    On the iteration complexity of oblivious first-order optimization algorithms , author=. International Conference on Machine Learning , pages=

    work page

  4. [4]

    Mathematical Programming , volume=

    Performance of first-order methods for smooth convex minimization: a novel approach , author=. Mathematical Programming , volume=. 2014 , publisher=

    work page 2014

  5. [5]

    Mathematical Programming , volume=

    Smooth strongly convex interpolation and exact worst-case performance of first-order methods , author=. Mathematical Programming , volume=. 2017 , publisher=

    2017

  6. [6]

    The exact information-based complexity of smooth convex minimization

    The exact information-based complexity of smooth convex minimization , author=. arXiv preprint arXiv:1606.01424 , year=

    work page Pith review arXiv

  7. [7]

    Master's thesis, Université Catholique de Louvain , year=

    Performance estimation of the gradient method with fixed arbitrary step sizes , author=. Master's thesis, Université Catholique de Louvain , year=

    work page

  8. [8]

    Worst-case functions for the gradient method with fixed variable step sizes , author=

    work page

Show all 33 references
  1. [9]

    Mathematical programming , volume=

    Optimized first-order methods for smooth convex minimization , author=. Mathematical programming , volume=. 2016 , publisher=

    2016

  2. [10]

    2017 , publisher=

    First-order methods in optimization , author=. 2017 , publisher=

    2017

  3. [11]

    Mathematical Programming , volume=

    Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods , author=. Mathematical Programming , volume=. 2024 , publisher=

    2024

  4. [12]

    arXiv preprint arXiv:2507.20773 , year=

    Numerical Design of Optimized First-Order Algorithms , author=. arXiv preprint arXiv:2507.20773 , year=

    arXiv

  5. [13]

    arXiv preprint arXiv:2412.04427 , year=

    A proof of the exact convergence rate of gradient descent , author=. arXiv preprint arXiv:2412.04427 , year=

    arXiv

  6. [14]

    Mathematical Programming , pages=

    Exact worst-case convergence rates of gradient descent: a complete analysis for all constant stepsizes over nonconvex and convex functions , author=. Mathematical Programming , pages=. 2026 , publisher=

    2026

  7. [15]

    Optimization Letters , volume=

    The exact worst-case convergence rate of the gradient method with fixed step lengths for L-smooth functions , author=. Optimization Letters , volume=. 2022 , publisher=

    2022

  8. [16]

    Journal of the ACM , volume=

    Acceleration by stepsize hedging: Multi-step descent and the silver stepsize schedule , author=. Journal of the ACM , volume=. 2025 , publisher=

    2025

  9. [17]

    Mathematical Programming , volume=

    Acceleration by stepsize hedging: Silver Stepsize Schedule for smooth convex optimization , author=. Mathematical Programming , volume=. 2025 , publisher=

    2025

  10. [18]

    SIAM Journal on Optimization , volume=

    Provably faster gradient descent via long steps , author=. SIAM Journal on Optimization , volume=. 2024 , publisher=

    2024

  11. [19]

    , author=

    Accelerated Objective Gap and Gradient Norm Convergence for Gradient Descent via Long Steps. , author=. INFORMS Journal on Optimization , volume=

  12. [20]

    Journal of Mathematics and Physics , volume=

    On Richardson's method for solving linear systems with positive definite matrices , author=. Journal of Mathematics and Physics , volume=. 1953 , publisher=

    1953

  13. [21]

    International Conference on Machine Learning , pages=

    Acceleration via fractal learning rate schedules , author=. International Conference on Machine Learning , pages=

  14. [22]

    arXiv preprint arXiv:2410.12395 , year=

    Accelerated gradient descent by concatenation of stepsize schedules , author=. arXiv preprint arXiv:2410.12395 , year=

  15. [23]

    Mathematics of Operations Research , year=

    Composing optimized stepsize schedules for gradient descent , author=. Mathematics of Operations Research , year=

  16. [24]

    Conference on Learning Theory , pages=

    Accelerating Proximal Gradient Descent via Silver Stepsizes , author=. Conference on Learning Theory , pages=

  17. [25]

    Conference on Learning Theory , pages=

    Large stepsize gradient descent for logistic loss: Non-monotonicity of the loss improves optimization efficiency , author=. Conference on Learning Theory , pages=

  18. [26]

    Mathematics of Operations Research , year=

    On averaging and extrapolation for gradient descent , author=. Mathematics of Operations Research , year=

  19. [27]

    Conference on Learning Theory , pages=

    Open problem: Anytime convergence rate of gradient descent , author=. Conference on Learning Theory , pages=

  20. [28]

    Conference on Learning Theory , pages=

    Anytime Acceleration of Gradient Descent , author=. Conference on Learning Theory , pages=

  21. [29]

    arXiv preprint arXiv:2607.02053 , year=

    Lower Bounds for Anytime Acceleration of Gradient Descent , author=. arXiv preprint arXiv:2607.02053 , year=

    arXiv

  22. [30]

    Journal of machine learning research , volume=

    Adaptive subgradient methods for online learning and stochastic optimization , author=. Journal of machine learning research , volume=

  23. [31]

    International Conference on Machine Learning , pages=

    Adaptive Gradient Descent without Descent , author=. International Conference on Machine Learning , pages=

  24. [32]

    arXiv preprint arXiv:2412.05790 , year=

    Acceleration by random stepsizes: Hedging, equalization, and the arcsine stepsize schedule , author=. arXiv preprint arXiv:2412.05790 , year=

    arXiv

  25. [33]

    arXiv preprint arXiv:2505.01423 , year=

    Negative stepsizes make gradient-descent-ascent converge , author=. arXiv preprint arXiv:2505.01423 , year=

    arXiv

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.