On the Nonoccurrence of Gradient Restart in Nesterov Accelerated Gradient Method
Abstract
Gradient restarting often improves the practical performance of accelerated gradient methods for unconstrained convex optimization problems, but a general theoretical guarantee of such improvement remains unclear. In this paper, we construct smooth, strongly convex objectives with Lipschitz-continuous gradients and corresponding initial points for which gradient restart never occurs, both for Nesterov's accelerated gradient method and for its ordinary differential equation model. From these examples, we conclude that strong convexity and smoothness alone do not guarantee that gradient restart improves the convergence behavior of the accelerated method or its continuous-time model. In particular, for the continuous-time example, the objective gap is asymptotic to 1/(πt3). We therefore obtain a negative answer to the open problem raised by Su, Boyd, and Cand{è}s [\textit{J. Mach. Learn. Res.}, 2016, 17(153), 1--43] of whether gradient restart guarantees linear convergence of the continuous dynamics for smooth strongly convex objectives.
Related
- Convergence Analysis of Nesterov's Accelerated Gradient Descent under Relaxed Assumptions
- Improved Gradient Descent Lower Bounds Beyond Nesterov
- Restart and Adaptive Acceleration in Stochastic Gradient Methods
- A Riemannian Inertial Adaptive Gradient Method with Momentum Restart
- Accelerated Safe Gradient Flow
BibTeX
@misc{bao2026nonoccurrence,
title = {{On the Nonoccurrence of Gradient Restart in Nesterov Accelerated Gradient Method}},
author = {Chenglong Bao and Liang Chen and Jiahong Li and Defeng Sun},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26546},
eprint = {2610.26546},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26546},
}
RIS
TY - UNPB
TI - On the Nonoccurrence of Gradient Restart in Nesterov Accelerated Gradient Method
AU - Chenglong Bao
AU - Liang Chen
AU - Jiahong Li
AU - Defeng Sun
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.26546
UR - https://arxiv.org/abs/2610.26546
AB - Gradient restarting often improves the practical performance of accelerated gradient methods for unconstrained convex optimization problems, but a general theoretical guarantee of such improvement remains unclear. In this paper, we construct smooth, strongly convex objectives with Lipschitz-continuous gradients and corresponding initial points for which gradient restart never occurs, both for Nesterov's accelerated gradient method and for its ordinary differential equation model. From these examples, we conclude that strong convexity and smoothness alone do not guarantee that gradient restart improves the convergence behavior of the accelerated method or its continuous-time model. In particular, for the continuous-time example, the objective gap is asymptotic to 1/(πt^3). We therefore obtain a negative answer to the open problem raised by Su, Boyd, and Cand{è}s [\textit{J. Mach. Learn. Res.}, 2016, 17(153), 1--43] of whether gradient restart guarantees linear convergence of the continuous dynamics for smooth strongly convex objectives.
ER -