Gradient descent acceleration reaches near best possible speed with silver rate
Silver Rate Is (Almost) Optimal for Gradient Descent Acceleration
Machine Learning
Summary
The paper looks at how fast a basic method called gradient descent can solve smooth convex problems if you pick the stepsizes in advance and keep them nonnegative. The authors show that a specific schedule, known as the silver rate, is almost the best you can do for speeding up convergence. They provide mathematical lower bounds showing no predetermined stepsize method can beat this by much, both when you know how long you'll run (non-anytime) and when you don't (anytime). Their results confirm previous upper bounds and help understand the fastest rates achievable with these methods.
gradient descentstepsize schedulesmooth convex optimizationconvergence ratelower boundanytime algorithmsnon-anytime algorithmssilver ratepolynomial convergence
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.