Improved Gradient Descent Lower Bounds Beyond Nesterov
We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Going beyond the classical $Ω(n^{-2})$ first-order oracle lower bound of Nemirovsky and Yudin (1983), we prove an $Ω(n^{-1.6342})$ non-anytime lower bound and an $Ω(n^{-1.2408})$ anytime lower bound. These improve the recent $Ω(n^{-1.932})$ non-anytime lower bound of Ma and Chen (2026) and the $Ω(n^{-4/3})$ anytime lower bound of Tsai et al. (2026), respectively. Both results continue to hold when the stepsizes may be negative. Our anytime lower bound also shows that the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.02855
curl -X POST /api/v1/records/arxiv/2609.02855/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.02855/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'