Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex Case
We study gradient descent with predetermined nonnegative stepsizes on smooth strongly convex functions. Let $p_{\mathrm{sil}}=\log_2(1+\sqrt2)$ and $κ$ be the condition number. We prove the iteration lower bound $Ω\left(κ^{\frac{1}{p_{\mathrm{sil}}}-o(1)}\log\frac1δ\right)$ 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].
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.26873
curl -X POST /api/v1/records/arxiv/2609.26873/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.26873/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'