PreprintCC BY 4.0arXiv
Silver Rate Is (Almost) Optimal for Gradient Descent
Abstract
We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Writing psil=log2(1+√2), we prove an Ω(n−psil−O(√(loglog n/log n))) non-anytime lower bound. In the anytime setting, every infinite schedule has infinitely many horizons with error Ω(n−2psil/(1+psil)−O(√(loglog n/log n))). 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.
Related
- Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex Case
- A Rate Transfer Method: Convergence Rates in Stochastic Gradient Descent via Stochastic Calculus
- Convergence rate of stochastic gradient descent under Łojasiewicz type condition and polynomially controlled noise
- The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives
- Last-Iterate Convergence Rate of Normalized Gradient Descent under Hölder Smoothness
BibTeX
@misc{ye2026silver,
title = {{Silver Rate Is (Almost) Optimal for Gradient Descent}},
author = {Yuhan Ye and Kaizhao Liu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09152},
eprint = {2609.09152},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09152},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Silver Rate Is (Almost) Optimal for Gradient Descent
AU - Yuhan Ye
AU - Kaizhao Liu
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.09152
UR - https://arxiv.org/abs/2609.09152
AB - We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Writing p_sil=log_2(1+√2), we prove an Ω(n^−p_sil−O(√(loglog n/log n))) non-anytime lower bound. In the anytime setting, every infinite schedule has infinitely many horizons with error Ω(n^−2p_sil/(1+p_sil)−O(√(loglog n/log n))). 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.
ER -