The exact worst-case asymptotic rate of Nesterov acceleration for strongly convex optimization
Abstract
We study Nesterov's accelerated gradient method with its standard constant parameters for smooth strongly convex optimization. We characterize the exact worst-case asymptotic factor for the squared distance to the minimizer. To this end, we construct candidate worst-case trajectories by combining planar spirals with a common contraction factor that satisfy a self-similarity condition. Each component rotates by a fixed angle at every iteration. The exact factor is the optimal value of a linear optimization problem over probability measures on a fixed disk, with constraints derived from smooth strongly convex interpolation. Every optimal measure has a common contraction factor, which is also the largest factor for which the angular interpolation conditions are feasible. We also show that this worst-case asymptotic rate can be realized by a \emph{single} function in a finite-dimensional space whose iterates attain this factor. A matching upper bound holds uniformly over all functions in the class and all finite dimensions. Consequently, allowing the function, dimension, and initial point to vary with the iteration horizon does not increase the worst-case asymptotic factor. We also show that the exact factor is 1−4/(3√κ)+o(κ−1/2) as κ→∞, where κ=L/μ is the ratio of the gradient Lipschitz constant to the strong convexity parameter.
Related
- ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization
- Synthesis of the Transient Behaviour of Optimization Algorithms for Strongly Convex Objective Functions
- Near-Optimal Acceleration for Smooth ℓp / ℓq Nondual Convex First-Order Oracle Optimization
- Near-Optimal Single-Loop Predictor--Corrector Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization
- Accelerated Proximal Gradient Method for Non-Strongly Convex Time-Varying Optimization
BibTeX
@misc{pokutta2026exact,
title = {{The exact worst-case asymptotic rate of Nesterov acceleration for strongly convex optimization}},
author = {Sebastian Pokutta and Bartolomeo Stellato},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15125},
eprint = {2610.15125},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15125},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The exact worst-case asymptotic rate of Nesterov acceleration for strongly convex optimization
AU - Sebastian Pokutta
AU - Bartolomeo Stellato
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.15125
UR - https://arxiv.org/abs/2610.15125
AB - We study Nesterov's accelerated gradient method with its standard constant parameters for smooth strongly convex optimization. We characterize the exact worst-case asymptotic factor for the squared distance to the minimizer. To this end, we construct candidate worst-case trajectories by combining planar spirals with a common contraction factor that satisfy a self-similarity condition. Each component rotates by a fixed angle at every iteration. The exact factor is the optimal value of a linear optimization problem over probability measures on a fixed disk, with constraints derived from smooth strongly convex interpolation. Every optimal measure has a common contraction factor, which is also the largest factor for which the angular interpolation conditions are feasible. We also show that this worst-case asymptotic rate can be realized by a \emph{single} function in a finite-dimensional space whose iterates attain this factor. A matching upper bound holds uniformly over all functions in the class and all finite dimensions. Consequently, allowing the function, dimension, and initial point to vary with the iteration horizon does not increase the worst-case asymptotic factor. We also show that the exact factor is 1−4/(3√κ)+o(κ^−1/2) as κ→∞, where κ=L/μ is the ratio of the gradient Lipschitz constant to the strong convexity parameter.
ER -