The Optimal Rate Constant of Heavy-Ball Momentum on Smooth Strongly Convex Functions
Abstract
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 , where is the condition number, we prove that tends to in every dimension of two or more. The lower bound on the rate holds for every tuning, because a tuning that is faster than 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 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
| 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 , 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 ), -coefficient | all parameters | symbolic | verify_lowerbound |
| 8 end polynomials and 4 concavity coefficients have no root | Sturm | verify_lowerbound | ||
| (independent) on the box | interval, 76 boxes | verify_lowerbound |
| lower bounds on (tunings) | upper bounds on (functions) | |||||
| exact | best on | log-spirals | root-of-unity | |||
| Theorem B | ( Appendix C ) | (num.) | (num.) | spirals (num.) | Theorem A | |
| – | 5.032 | 5.034 | 5.37 | 5.44 | 8 | |
| 4.800 | 6.173 | 6.175 | – | 6.50 | 8 | |
| 5.976 | 6.734 | 6.736 | 6.98 | 6.99 | 8 | |
| 7.360 | 7.548 | 7.549 | – | 7.66 | 8 | |
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
| interval and | ||
|---|---|---|
| , | ||
| , | ||
| , | ||
| order of the points |
| 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 , 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 of Pasechniuk-Vilensky [22] ( Remark 2 ) |
| fixed_kappa_certificates.py | Appendix C , writes results/optimal/fixed_kappa.json |
| ghadimi_corner.py | Section 9.3 |
Optimization Convergence Analysis
Optimization convergence analysis studies whether and how quickly iterative algorithms approach solutions, and which assumptions ensure reliable progress.
See all 78 papers