Su–Boyd–Candès gradient-restart convergence problem
Let be differentiable, $$-smooth, and -strongly convex for some , with minimizer . Does gradient restarting in Nesterov's accelerated method, in particular in its continuous-time dynamics, guarantee linear convergence using only these assumptions; that is, do there exist constants and such that the restarted trajectory satisfies for all sufficiently large (and analogously a geometric convergence bound for the discrete method)?
References
- On the Nonoccurrence of Gradient Restart in Nesterov Accelerated Gradient Method — arXiv — Chenglong Bao, Liang Chen, Jiahong Li, Defeng Sun
Source: arXiv
Progress summary
An October 2026 preprint claims a counterexample to the general guarantee, but the result has not been independently checked.
The problem asks whether gradient restarting in Nesterov acceleration is guaranteed to converge linearly using only smoothness and strong convexity. Su, Boyd, and Candès posed the underlying convergence question in 2015.
Known results
- O’Donoghue and Candès, 2012: adaptive restarting achieves optimal linear convergence for quadratic objectives under the stated assumptions.
- Su, Boyd, and Candès, 2015: the acceleration ODE motivates restarting and proves linear convergence for strongly convex objectives in the relevant restarted scheme.
- Roulet and d’Aspremont, 2016: periodic restarting has linear guarantees under a strong-convexity estimate; adaptive restarting remains heuristic there.
- Calatroni et al., 2024: gradient-restarted methods obtain linear convergence in discrete settings and for quadratic continuous-time models, only partially resolving the general question.
October 2026 counterexample
Bao, Chen, Li, and Sun claim that restart can never trigger on constructed examples, while the continuous-time objective gap is asymptotic to . This would disprove a general linear-convergence guarantee based only on smoothness and strong convexity; the preprint is unrefereed and the claim remains unverified.
Current status (as of October 2026): The general guarantee is claimed to be false by an unrefereed counterexample, while positive results remain limited to additional assumptions and special classes.
Solutions 0
No solutions have been posted yet.