← All problems

Su–Boyd–Candès gradient-restart convergence problem

Let f:Rn→Rf:\mathbb{R}^n\to\mathbb{R} be differentiable, $$-smooth, and \vmu\vmu-strongly convex for some 0<μ≤L0<\mu\leq L, with minimizer x⋆x^\star. 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 C>0C>0 and c>0c>0 such that the restarted trajectory satisfies f(x(t))−f(x⋆)≤Ce−ctf(x(t))-f(x^\star)\leq C e^{-ct} for all sufficiently large tt (and analogously a geometric convergence bound for the discrete method)?

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

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 1/(πt3)1/(\pi t^3). 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.

Sources

Solutions 0

No solutions have been posted yet.