The heavy-ball method with a constant step size and a constant momentum parameter accelerates gradient descent on quadratics, but no choice of the two parameters does so on the class of smooth strongly convex functions. We determine how much faster than gradient descent it can be made on this class. Writing the best worst-case rate over all tunings as 1−c(κ)/κ, where κ is the condition number, we prove that c(κ) tends to 8 in every dimension of two or more. The lower bound on the rate holds for every tuning, because a tuning that is faster than 1−8/κ on quadratics follows a slowly decaying spiral on some function of two variables. The matching upper bound comes from an explicit tuning, with nearly the momentum of Polyak's tuning and a step size about κ/8 times smaller, and from a Lyapunov function whose positivity is verified in exact arithmetic. Optimally tuned heavy-ball is therefore asymptotically four times faster than gradient descent on this class.
Figures & tables
Figure 1: A spiral of Lemma 2 at κ=100 , for the tuning γL=2.5 , β=0.736 . (a) The iterates turn by 2π/7 per step and contract by r=1−8/κ=0.92 . The gradients are the iterates scaled and rotated by a fixed nonzero angle, which no quadratic produces. The orange arrows are the gradient steps −γ∇f(xt) . (b) On this function heavy-ball converges at the rate 0.92 , although on every quadratic of the class it converges at the rate ρQ=0.858 or faster.
Claim
What is checked
Range
Method
Script
Lemma 1
the two Schur–Cohn identities
all parameters
symbolic
verify_lowerbound
Lemma 2
reduction ( 9 ), formulas ( 7 ), identity for Φ
all parameters
symbolic
verify_lowerbound
at r=1 , Φ gives the region of Goujaud et al. [11, Thm. 3.5]
all parameters
symbolic
verify_lowerbound , verify_symbolic
Lemma 4
corner identities ( 11 ) and ( 12 ), u2 -coefficient
all parameters
symbolic
verify_lowerbound
8 end polynomials and 4 concavity coefficients have no root
y∈[0,7/11]
Sturm
verify_lowerbound
(independent) F1,F2>0 on the box
[0,1]×[0,2/5]
interval, 76 boxes
verify_lowerbound
Table 1: Computer-assisted steps. “Range” is the exact parameter range on which the check holds. The scripts are in code/ .
lower bounds on c (tunings)
upper bounds on c (functions)
exact
best on Q
log-spirals
root-of-unity
κ
Theorem B
( Appendix C )
(num.)
(num.)
spirals (num.)
Theorem A
102
–
5.032
5.034
5.37
5.44
8
400
4.800
6.173
6.175
–
6.50
8
103
5.976
6.734
6.736
6.98
6.99
8
104
7.360
7.548
7.549
–
7.66
8
Table 2: Bounds on c(κ)=κ(1−ρ⋆(κ)) for d≥2 . Lower bounds on c come from tunings, and upper bounds from functions that slow every tuning down. Lower bounds are rounded down and upper bounds up. The columns marked “num.” are floating point.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
κ
r
β
γL
∥P∥
λmin(G)
M
400
0.988
0.778544
1.0176
1.44
5.6⋅10−4
78
103
0.994024
0.862348
0.791643
1.57
2.3⋅10−4
127
104
0.999264
0.958558
0.299817
3.51
2.4⋅10−5
559
106
0.999992
0.995984
0.031807
31.6
2.5⋅10−7
1.6⋅104
Appendix
Table 3: The tuning and the constant of Theorem B at sample values of κ , rounded, with M rounded up.
κ
c
β
γL
P22
P23
P33
100
125629
312500000203195907
31250004958407
106368289
−25000082409
25000040071
400
10006173
125⋅109101480295257
123070937500000133279034566039
106521519
−500000146987
500004403
1000
5003367
1012878213437313
496633000000000387381978567129
500000351169
−500000139493
25000014499
104
2501887
1012960020029523
24981130000000074017896690099
200000349997
−20000051973
20000393
Appendix
Table 4: Exact certificates at fixed κ ( results/optimal/fixed_kappa.json ).
interval and σ
σ−γμ
γL−σ
[0,1] , σ=β
1+s1−3s
1+s3−s
[−δ/β,0] , σ=1+3β
(1+s)24(1−s)
(1+s)24s(1−s)
[−1,−δ/β] , σ=β−δ(1+β)(β−2δ)
(1+s)2(1−6s+s2)2(1−10s+2s3−s4)
(1+s)2(1−6s+s2)2(1−2s+10s3−s4)
order of the points
1−δ/β=(1−s)21−6s+s2
δ/β=(1−s)24s
Appendix
Table 5: The slope conditions of Theorem D , with σ the scaled secant γ⋅ secant and s=κ−1/2 . All entries are positive on (0,1/10] .
Script
Checks or produces
verify_lowerbound.py
all checks for Theorem A and Corollary 2 in Table 1 and the floating-point tests, writes results/optimal/lowerbound.json and ends with ALL OK
verify_rou_analytic.py
the constants of the proof of Lemma 5
verify_achievability.py 1/20
Proposition 1 for κ≥400 , writes results/optimal/achievability.json ; with --range it checks the range of Section 6.5 , and with --table it computes Table 3
verify_pv_membership.py
the tuning ( 4 ) lies in the region Q of Pasechniuk-Vilensky [22] ( Remark 2 )
fixed_kappa_certificates.py
Appendix C , writes results/optimal/fixed_kappa.json
ghadimi_corner.py
Section 9.3
Appendix
Table 6: Scripts in code/ and what they check or produce.
Optimization convergence analysis studies whether and how quickly iterative algorithms approach solutions, and which assumptions ensure reliable progress.
Despite having an asymptotically optimal rate of convergence on convex quadratics, the acceleration of Polyak's heavy-ball method and a characterization of its dynamics within more general settings have remained long standing open problems. Recently, the work of Goujaud et al. [Math. Program. (2025)] made progress regarding acceleration in the context of smooth, strongly convex minimization: for a small enough inverse condition number, either the method does not accelerate on quadratics, or there exists a smooth strongly convex function such that heavy-ball cycles over the roots of unity. The constructed functions have two variables, thus leaving the question of acceleration over univariate functions open. In this work, we use a Fourier-based analysis to i) provide a proof for the non-acceleration of the heavy-ball method over the class of univariate smooth strongly convex functions. We also ii) provide a strict enlargement of the previous root-of-unity cycling region, with insights regarding the "fractional" sets of Goujaud et al. [arXiv:2502.19916], and iii) give a higher dimensional cycling instance which is not covered by root-of-unity cycling.
Konstantinos Fotopoulos, Michael Helcig, Karl Deck +1
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(T−log2(1+2)) 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 Ω(T−2) benchmark for general first-order methods. In this work, we present a new lower bound of Ω(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.
Jianhao Ma, Yuxin Chen
Department of Industrial Engineering, Tsinghua University · Department of Statistics and Data Science, Wharton School, University of Pennsylvania
Gradient descent (GD) is one of the most fundamental algorithms in optimization. Yet even for smooth convex objectives, the optimal rate among predetermined nonnegative stepsize schedules has remained unresolved. Altschuler and Parrilo [Mathematical Programming, 2025] showed that their recursive silver stepsize schedule achieves an O(n−psil) rate, where psil=log2(1+2)≈1.2716, improving upon the classical O(n−1) rate of constant-step GD. Although the optimality of psil has been well supported by numerical evidence for small n, a matching lower bound has remained missing. In this paper, we prove an Ω(n−psil−o(1)) lower bound for GD, showing that psil is the optimal convergence exponent. Additionally, we prove an anytime lower bound that matches the exponent 2psil/(1+psil)≈1.1195 of the known upper bound [Zhang, Lee, Du, and Chen, COLT 2025]. Building on the approaches of [Ma and Chen, 2026; Jung, Cho, and Yun, 2026], we select specific iterations as checkpoints at which the GD trajectory explores a new coordinate, and we couple these coordinates using a chain of local functions. Our main technical contribution is a local hard function that bends the GD trajectory between successive checkpoints, resulting in a sharpened lower bound. For each prescribed stepsize schedule, we maximize this bound over admissible checkpoint sets. A recursive analysis of this maximum then yields a lower bound matching the silver exponent for every such schedule.