PreprintCC BY 4.0arXiv
Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex Case
Abstract
We study gradient descent with predetermined nonnegative stepsizes on smooth strongly convex functions. Let psil=log2(1+√2) and κ be the condition number. We prove the iteration lower bound Ω(κ1/psil−o(1)log1/δ) for both relative squared distance and relative function error, uniformly over 0<δ<1 and sufficiently large κ. This matches the polynomial exponent of κ for the Silver stepsize schedule established in [Altschuler and Parrilo, 2025].
Related
- Silver Rate Is (Almost) Optimal for Gradient Descent
- ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization
- Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization
- Optimal Recursive Composition and Dyadic Phase Laws for Gradient Descent with Predetermined Stepsizes
- Compute-Optimal Pretrain--Fine-tune in Ridge Gradient Descent
BibTeX
@misc{liu2026silver,
title = {{Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex Case}},
author = {Kaizhao Liu and Yuhan Ye},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26873},
eprint = {2609.26873},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26873},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex Case
AU - Kaizhao Liu
AU - Yuhan Ye
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.26873
UR - https://arxiv.org/abs/2609.26873
AB - We study gradient descent with predetermined nonnegative stepsizes on smooth strongly convex functions. Let p_sil=log_2(1+√2) and κ be the condition number. We prove the iteration lower bound Ω(κ^1/p_sil−o(1)log1/δ) for both relative squared distance and relative function error, uniformly over 0<δ<1 and sufficiently large κ. This matches the polynomial exponent of κ for the Silver stepsize schedule established in [Altschuler and Parrilo, 2025].
ER -