Silver Rate Is (Almost) Optimal for Gradient Descent Acceleration
New optimization theory paper proves near-optimal lower bounds for gradient descent with predetermined stepsizes, confirming silver-schedule optimality.
The paper studies the limits of accelerating gradient descent using predetermined nonnegative stepsizes in smooth convex optimization, with the key constant p_sil = log2(1 + sqrt(2)). It proves a non-anytime lower bound of Omega(n^(-p_sil - O(sqrt(log log n / log n)))) on the error achievable by any such stepsize schedule. In the anytime setting, it shows every infinite nonnegative schedule must incur error Omega(n^(-2*p_sil/(1+p_sil) - O(sqrt(log log n / log n)))) at infinitely many horizons. Combined with the silver-schedule upper bound of Altschuler and Parrilo (2025) and the anytime upper bound of Zhang et al. (2025), these results determine the optimal polynomial convergence exponents in both settings.
- Proves a near-optimal non-anytime lower bound for gradient descent with predetermined nonnegative stepsizes in smooth convex optimization.
- Identifies p_sil = log2(1 + sqrt(2)) as the constant governing optimal gradient descent acceleration rates.
- Shows every infinite nonnegative schedule incurs Omega(n^(-2*p_sil/(1+p_sil))) error at infinitely many anytime horizons.
- Results match the Altschuler-Parrilo silver-schedule and Zhang et al. anytime upper bounds, settling optimal convergence exponents.
- Tags
- accelerationconvergence-ratesconvex-optimizationgradient-descentlower-boundsmachine-learning-theoryoptimization-theory
- Organizations
- arXiv
From the original article
1 min read at arxiv.orgWe 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.
By Yuhan Ye · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.