Gradient descent acceleration approaches optimal rate with silver stepsizes
Silver Rate Is (Almost) Optimal for Gradient Descent Acceleration
Machine Learning
Summary
This paper studies how stepsizes chosen in advance can speed up the process of gradient descent, a common method to find the best solution in smooth convex problems. The authors prove mathematical limits on how fast this method can converge with predetermined nonnegative stepsizes. Their results show that the so-called silver stepsize schedule nearly achieves the fastest possible convergence rate, both in fixed-time and anytime settings. This means the silver schedule sets a strong benchmark for accelerating gradient descent with predetermined stepsizes.
What this means in practice
- •For machine learning engineers: Optimize tuning of predetermined stepsizes in training algorithms for faster convergence under smooth convex objectives.
- •For data scientists: Design gradient descent procedures that approach optimal convergence rates in convex smooth optimization tasks common in analytics.
A theory result. No direct application yet.
Authors
Yuhan Ye, Kaizhao Liu
Abstract
We study how far gradient descent (GD) can be accelerated by predetermined nonnegative stepsizes in smooth convex optimization. Writing $p_{\mathrm{sil}}=\log_2(1+\sqrt{2})$, we prove an $Ω\left(n^{-p_{\mathrm{sil}}-O(\sqrt{\log\log n/\log n})}\right)$ non-anytime lower bound. In the anytime setting, every infinite nonnegative schedule has infinitely many horizons with error $Ω\left(n^{-\frac{2p_{\mathrm{sil}}}{1+p_{\mathrm{sil}}}-O(\sqrt{\log\log n/\log n})}\right)$. Together with the silver-schedule upper bound [Altschuler and Parrilo, 2025] and the anytime upper bound [Zhang et al., 2025], our results determine the optimal polynomial convergence exponents in both settings.