Stronger Lower Bounds for (Non-)Anytime Acceleration of Gradient Descent
The rate-optimal convergence rate of gradient descent (GD) with a fixed step-size is well known to be $Θ(N^{-1})$ for $L$-Lipschitz smooth convex objectives in the prior art in convex optimization. Surprisingly, several recent works show that we can accelerate vanilla GD by applying a nonconstant, nonadaptive, deterministic step-size schedule. The best-known upper bounds so far in the non-anytime & anytime setups are $O(N^{-1.271})$ [Altschuler and Parrilo, 2025, Grimmer et al., 2023] and $O(N^{-1.119})$ [Zhang et al., 2025], respectively. On the other hand, the best reported lower bounds…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.04032
curl -X POST /api/v1/records/arxiv/2609.04032/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.04032/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'