acceptodds
Under review as a conference paper at ICLR 2027

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 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 as , where is the ratio of the gradient Lipschitz constant to the strong convexity parameter.

Primary area:
optimization
Keywords:
acceleration, first-order methods, dynamical systems

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_UQnwOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors prove the exact worst case asymptotic rate 1−4/(3κ)+o(1/κ)1-4/(3\sqrt{\kappa}) + o(1/\sqrt{\kappa}) of accelerated gradient method (AGD) for smooth strongly convex optimization problem with the condition number κ\kappa. The argument can be summarized as follows:

  • The authors consider interpolation conditions for smooth and strongly convex functions based on the Legendre transform. The main difference from Taylor et al. (2017) is that they eliminate function values using Rockafellar's cyclic monotonicity interpolation conditions for proper closed convex functions.

  • The authors consider 2m2m-dimensional trajectories of the AGD, where each 2-dimensional block corresponds to a complex geometric sequence of the form ztt∈N0\\{ z^t \\}_{t \in \mathbb{N}_0}, where z∈Cz \in \mathbb{C}. For these trajectories they provide simplified (equivalent to Rockafellar's) interpolation conditions (10) in terms of finitely supported probability measures ν\nu over phases of z∈Cz \in \mathbb{C} (Lemma 3.1).

  • Finding the worst convergence rate (maximal element in Q(s)\mathcal{Q}(s)) over such trajectories can be formulated as finding the largest amplitude ∣z∣|z| such that interpolation conditions (10) hold for some measure ν\nu. The authors also provide a lifted version of this problem over probability distributions μ\mu on a complex disc in (12). Propositon 3.2 shows that the optimal measure μ\mu is supported on a circle, which allows to recover the angular measure ν\nu and proves equivalence between (12) and maximal value in Q(s)\mathcal{Q}(s).

  • Theorem 4.1 shows that the worst-case rate over considered geometric trajectories matches the true worst-case rates in (2) and (3). The main result for the exact worst-case asymptotic rate is proved in Corollary 4.3: the upper bound uses the interpolation conditions (10), and the lower bound is proved by providing a certain feasible measure in (12).

Critical strengths

The main strengths are interesting theoretical insights:

  • Interesting utilization of the interpolation conditions for closed and convex functions that do not use objective function values. Most existing papers (e.g. Taylor et al. (2017)) use simpler conditions with function values.

  • Interesting connection of the worst-case asymptotic convergence rates with the linear optimization problems over probability measures.

Critical weaknesses

The main weakness is significance: the main result for the worst-case asymptotic rate only shows an optimality of the universal constant factor 4/34/3. Moreover, slight modifications of AGD already achieve exact optimal rates [a]. It would be interesting to see if the theoretical developments from this paper could be used to establish genuinly new results beyond improvement of constants.

[a] Taylor, Adrien, and Yoel Drori. "An optimal gradient method for smooth strongly convex minimization." Mathematical Programming 199.1 (2023): 557-594.

Questions for authors

n/a

1 comment
AuthorsOpenReview ↗

Exact characterization beyond the large-condition-number constant

Thank you for the review and the connection to Taylor and Drori. We agree that the paper should explain its significance more clearly.

The sharp constant 4/34/3 is just one consequence of our results. Theorem 4.1 gives (a) an exact characterization of the asymptotic factor for every fixed κ>1\kappa>1, (b) equality of the fixed-objective and horizon-dependent factors, and (c) attainment by one finite-dimensional objective with standard initialization. Corollary 4.3 then extracts the large-κ\kappa expansion.

The fixed-objective statement also distinguishes the result from an improvement of an upper-bound constant. It shows that the slower behavior can persist on one objective throughout an infinite run. At κ=10\kappa=10, the quadratic factor is approximately 0.46754450.4675445, Gannot's upper bound is approximately 0.56523520.5652352, and our exact factor is approximately 0.56442330.5644233. The upper-bound improvement is small, but the matching construction proves that nearly all the gap above the quadratic benchmark is unavoidable for standard NAG.

Quantitative comparison with ITEM. We agree that modifying the algorithm improves its guarantee. Taylor and Drori's Information-Theoretic Exact Method attains the oracle-complexity lower bound for distance to the optimizer. Their Sections 2.2–2.3 give the exact asymptotic squared-distance factor (1−1/κ)2(1-1/\sqrt{\kappa})^2 for the output sequence zNz_N. Comparing this with standard NAG's iterates xtx_t, our theorem quantifies the gap:

\qquad q_{\rm NAG}=1-\frac{4}{3\sqrt{\kappa}}+o(\kappa^{-1/2}).$$ Both methods use one gradient evaluation per iteration. At fixed $\kappa$, the leading worst-case iteration counts for relative squared-distance tolerance $\varepsilon\downarrow0$ are $\log(1/\varepsilon)/[-\log q]$. Their ratio, NAG divided by ITEM, is therefore $\log q_{\rm ITEM}/\log q_{\rm NAG}$. This ratio is approximately $1.33$ at $\kappa=10$ and tends to $3/2$ as $\kappa\to\infty$. Thus, in this high-accuracy asymptotic comparison, standard NAG requires about 33% more gradient evaluations at $\kappa=10$, rising to 50% more as $\kappa$ grows. These are asymptotic comparisons, not finite-iteration or runtime claims. ITEM establishes what an optimally designed method can guarantee. Our result identifies the exact penalty for using standard NAG and constructs one fixed objective exhibiting its slower behavior. **Consequences beyond the leading constant.** Corollary 4.4 gives the same exact factor for function gap and squared gradient norm. At $\kappa=100$, the optimal measure in our characterization requires two rotation angles, and the construction combines two planar spirals. Remark 4.2 gives a condition number at which the exact factor is not expressible by radicals over the rationals. The two-angle example rules out a single rotating mode within our characterization. The radical obstruction explains why a general formula by radicals is unavailable. The proof constructs one finite-dimensional objective attaining the factor and bounds every trajectory. Finite support and standard initialization are essential to this argument. To extend it to other stationary methods, one must establish the analytic bounds and nonzero limiting function needed for finite support, stability of the rescaled recurrence, and compatibility with standard initialization. In the uploaded revision, we have emphasized exactness for every fixed condition number, added the Taylor–Drori reference and the distinction between algorithm design and analysis, and expanded the proof sketch. The exact-rate theorem, metric corollary, two-angle example, and radical obstruction were already established in the submission.
Reviewer_it9mOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper characterizes the exact worst-case asymptotic convergence factor of Nesterov’s accelerated gradient method with its standard constant stepsize and momentum on smooth, strongly convex objectives. It distinguishes between the asymptotic factor obtained on a fixed objective with a fixed initialization and the factor obtained when the objective and dimension may depend on the iteration horizon. The main result establishes that these factors coincide and equal the optimal value of an infinite-dimensional linear program over probability measures on a disk.

The analysis combines interpolation conditions with contracting, rotating trajectories. It establishes a common contraction factor for optimal measures and the existence of a finitely supported optimal angular measure, constructs a realizing objective with standard initialization, and derives a matching uniform upper bound using integral quadratic constraints (IQCs).

Critical strengths
  1. The paper develops a technically substantial analysis combining interpolation, structured trajectories, and upper-bound certificates to obtain an exact asymptotic characterization.

  2. The matching lower bound is attained by a single fixed objective in finite dimension, with standard initialization. This establishes persistent worst-case behavior and goes beyond constructing separate worst-case examples for individual finite horizons.

Critical weaknesses
  1. The methodological novelty relative to existing interpolation, performance-estimation, and IQC approaches needs sharper articulation. The presentation should more clearly distinguish established ingredients from new proof techniques and explain why existing results do not already yield the claimed characterization. In particular, the obstacles to realizing the sharp asymptotic factor on one fixed finite-dimensional objective should be highlighted alongside the arguments that overcome them.

  2. The demonstrated scope is restricted to Nesterov’s method with its prescribed parameter choice. The paper provides limited discussion of which parts of the analysis depend critically on this recurrence and which might extend to other momentum parameters or related methods.

Questions for authors
  1. How does the lower bound strengthen existing results for quadratic objectives and finite-horizon worst-case examples? Which new proof ingredients are essential to obtaining a sharp bound attained by one fixed objective, and what prevents existing interpolation or IQC results from establishing the same conclusion?

  2. Which steps of the proof rely specifically on the standard Nesterov parameters? Could the measure formulation, finite-support argument, and matching upper-bound construction extend to other parameter choices or to heavy-ball? Please identify the main obstacles rather than assuming that the extension is immediate.

  3. Does the characterization suggest principles for algorithm design, such as selecting momentum parameters or understanding mechanisms responsible for slow convergence?

4 comments
AuthorsOpenReview ↗

Why the trajectory optimization gives the exact worst-case rate of NAG

Thank you for the careful review. For standard NAG at each fixed κ>1\kappa>1, we prove that searching over contracting, rotating trajectories gives the exact asymptotic squared-distance factor over all 11-strongly convex objectives with κ\kappa-Lipschitz gradients, not just a lower bound from special examples. One fixed finite-dimensional objective attains it from standard initialization. Allowing the objective and dimension to vary with the horizon does not worsen the factor.

We use established interpolation results (Taylor–Hendrickx–Glineur) and cyclic monotonicity (Rockafellar) to test whether prescribed points, gradients, and function values come from one objective in the class. Finite-horizon performance estimation (PEP) permits the worst-case objective and dimension to vary with the horizon. To establish our result, we must construct one fixed finite-dimensional objective attaining the asymptotic factor and prove a matching bound for arbitrary trajectories.

Why the search is exact. The optimization distributes probability weight over components with different per-step contraction factors and rotation angles, and maximizes the mean squared contraction factor. Write q⋆q_\star for its optimum at fixed κ\kappa. Proposition 3.2 shows that optimal components share one decay factor: a shift-and-reweight identity preserves feasibility and improves the objective by a variance term unless their decay factors agree. The submitted proof then has three further steps.

  1. Bound arbitrary trajectories. For q⋆<q<1q_\star<q<1, no mixture with that factor is feasible. Separation gives a finite nonnegative combination of cycle inequalities, obtained by summing interpolation inequalities around closed sequences of query points. These inequalities hold for any objective in the class. The combination supplies an integral quadratic constraint (IQC) for rescaled NAG. After verifying the strict-IQC theorem's hypotheses (Megretski–Rantzer; discrete form in Zhang–Seiler–Carrasco, Theorem 3), we obtain square summability: the rescaled sequences have a finite sum of squared norms. A further estimate gives ∥xt−x⋆∥2≤bqt∥x0−x⋆∥2\|x_t-x_\star\|^2\le bq^t\|x_0-x_\star\|^2, with bb depending only on κ,q\kappa,q. Taking ttth roots, then t→∞t\to\infty and q↓q⋆q\downarrow q_\star, gives the uniform asymptotic bound.
  2. Keep the construction finite-dimensional. A distribution could still require infinitely many angles. When the optimum exceeds the quadratic factor, we normalize separating combinations and prove uniform bounds on a common complex strip containing the angle interval. Montel's theorem gives an analytic limit that is nonzero by normalization. The limit is nonpositive on the angle interval, whereas feasibility makes its average under an optimal measure nonnegative. The measure must therefore be supported on its zeros. Only finitely many zeros lie on the compact angle interval inside the strip, so finitely many components suffice. The quadratic endpoint is realized directly.
  3. Enforce standard initialization. To obtain x−1=x0x_{-1}=x_0, we scale the target trajectory and add a scalar quadratic coordinate. This supplies slack in the interpolation inequalities involving the initial query point and decays faster than the target. One objective then realizes the entire prescribed trajectory with the same asymptotic factor. This device is sufficient, not always necessary: the κ=10\kappa=10 example initializes directly in two dimensions.

At κ=10\kappa=10, the fixed nonquadratic example and worst quadratic have factors approximately 0.56442330.5644233 and 0.46754450.4675445, respectively. Gannot's upper bound, approximately 0.56523520.5652352, is not tight here. The construction shows that slower convergence on a nonquadratic objective persists throughout an infinite run.

What depends on NAG. The interpolation conditions are method-independent; the query–gradient relation is not. Separating off the strong-convexity quadratic represents standard NAG as a linear filter driven by the remaining gradient. Its double pole at 1−1/κ1-1/\sqrt{\kappa} moves inside the unit circle under rescaling by q−t/2q^{-t/2} when q>(1−1/κ)2q>(1-1/\sqrt{\kappa})^2. Other parameters or methods require analytic bounds and a normalization ensuring a nonzero limiting function, along with initialization and uniform upper bounds. Stability also needs checking: heavy-ball with parameters optimal for quadratics can approach a limit cycle from standard initialization at κ=25\kappa=25 (Lessard–Recht–Packard, 2016, Section 4.6).

Implications for design. Rotating nonquadratic examples expose slow behavior missed by quadratic tests. They give lower bounds for testing candidate momentum parameters; certifying optimal tuning still requires matching upper bounds and comparison across choices.

The roadmap describes the original submission. The uploaded revision replaces Montel with derivative bounds and Rolle's theorem, and the strict-IQC theorem with finite sums and induction. The results are unchanged.

I would like to thank the authors for bringing additional clarification, especially for identifying which parts of the proof depend on the algorithm.

To make this distinction more concrete, could the authors also demonstrate or argue whether that dependence is essential by changing only the momentum slightly? For instance, if we keep the step size (1/\kappa) fixed, which parts of the proof remain valid under a sufficiently small perturbation of (\beta_0), and which would require a new argument ?

AuthorsOpenReview ↗

What survives a small momentum perturbation

Thank you for this concrete test. In response, we checked small momentum perturbations with step size 1/κ1/\kappa fixed. The cycle formulation, upper bounds with a fixed rate margin, and standard-initialization argument survive. Proving the exact perturbed optimum and its attainment requires further work.

What changes algebraically. Fix κ 1\kappa\>1 and write β0=(κ−1)/(κ+1)\beta_0=(\sqrt\kappa-1)/(\sqrt\kappa+1). With momentum β\beta, the polynomial governing the recurrence is

Dβ(z)=z2−(1−1/κ)(1+β)z+(1−1/κ)β.D_\beta(z)=z^2-(1-1/\kappa)(1+\beta)z+(1-1/\kappa)\beta.

At β0\beta_0, it equals (z−(1−1/κ))2(z-(1-1/\sqrt\kappa))^2. Perturbations split this repeated root, but the interpolation and cyclic-monotonicity arguments remain valid using the updated recurrence.

The upper bound survives with any fixed rate margin. Let q⋆q_\star denote the exact squared-distance factor at β0\beta_0. For every fixed q⋆<q<1q_\star<q<1, there exist ε 0\varepsilon\>0 and B<∞B<\infty such that, whenever ∥β−β0∥<ε\|\beta-\beta_0\|<\varepsilon,

∥xt−x⋆∥2≤Bqt∥x0−x⋆∥2\\\|x_t-x_\star\\\|^2\le Bq^t\\\|x_0-x_\star\\\|^2

uniformly over f∈F1,κf\in\mathcal F_{1,\kappa}, finite dimensions, standard initializations, and t≥0t\ge0. The finite cycle combination in Appendix C.3 has a strict margin over the compact set of angles, which persists by continuity in β\beta. The roots of DβD_\beta also remain inside ∥z∥=q\|z\|=\sqrt q, since (1−1/κ)2≤q⋆<q(1-1/\sqrt\kappa)^2\le q_\star<q. Thus the inverse of the rescaled recurrence still has absolutely summable coefficients, and the finite-sum and induction argument applies with modified constants. The perturbation interval can shrink as q↓q⋆q\downarrow q_\star; this does not assert an unchanged exact rate.

Standard initialization survives explicitly. In Lemma C.3, use curvature a=κ/(1+β)a=\kappa/(1+\beta) on the positive side and κ\kappa on the negative side. For 0<β<κ−10<\beta<\kappa-1, an interval containing β0\beta_0, we have 1<a<κ1<a<\kappa. The auxiliary coordinate still vanishes after two steps, and the initial interpolation inequalities retain strictly positive slack. This attaches standard initialization to a feasible finite-dimensional contracting geometric trajectory.

What remains to establish exactness. One must identify the new optimum and prove attainment. In particular, the finite-support argument in Appendix C.1 requires checking that the limiting separating function at that optimum is not identically zero. The standard-parameter rate formulas and active modes cannot simply be reused.

I would like to thank the authors for their detailed responses. I will raise my score to 3.

Reviewer_m8MfOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the exact worst-case asymptotic convergence rate of Nesterov's accelerated gradient method with standard constant parameters for smooth strongly convex objectives. The authors characterize the exact worst-case asymptotic factor for the squared distance and establish matching upper and lower bounds, with the lower bound attained by a single fixed finite-dimensional objective. In particular, they show that the leading constant 4/34/3 in Gannot's previously known upper bound is sharp.

Critical strengths
  • To the best of this reviewer's understanding, characterizing the exact worst-case asymptotic factor of standard NAG is a new and meaningful theoretical contribution.
  • The fact that the worst-case factor is attained by a single fixed objective rather than by objectives depending on the iteration horizon seems nontrivial and interesting.
  • This reviewer finds the techniques used to characterize the worst-case asymptotic factor interesting.
Critical weaknesses

This reviewer did not identify any critical weaknesses in the paper. As a relatively minor point, since the authors discuss the behavior of the smooth convex version of NAG under different parameter choices in the last paragraph of the Related Work section, this reviewer thinks it would be worth mentioning [1] and some of its follow-up work.

[1] W. Su, S. Boyd, and E. J. Candès, "A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights," Neural Information Processing Systems, 2014.

Questions for authors

To the best of this reviewer's understanding, cyclic monotonicity has been used in previous studies of worst-case convergence analysis. Could the authors clarify what the main technical bottlenecks were in extending this approach to characterize the exact worst-case asymptotic factor of NAG, and what novel arguments were required to overcome them?

2 comments
AuthorsOpenReview ↗

Technical bottlenecks beyond cyclic monotonicity

Thank you for the review and the suggested reference. We agree that cyclic monotonicity (Rockafellar) is an established tool and is not itself the claimed novelty. In the uploaded revision, we have added Su, Boyd, and Candès (NIPS 2014) to Related Work. We have also explained the discrete and continuous Lyapunov connection of Sanz-Serna and Zygalakis (2021), already cited in the submission.

Interpolating a finite trajectory or constructing a periodic orbit does not settle the question here. We need an infinite contracting trajectory satisfying every pairwise interpolation inequality on one fixed finite-dimensional objective, with standard initialization. Its factor must also bound every trajectory. The submitted proof requires four further steps.

A common contraction factor. A feasible disk measure can combine different radii. Proposition 3.2 uses the cycle-shift identity to reweight by squared radius while preserving feasibility. The objective increases by a variance term unless the radii coincide. This proves common-radius support for optimal measures.

One finite-dimensional objective for an infinite run. Countably many interpolation constraints must hold simultaneously. Finite-dimensional representations for individual finite subsets do not by themselves give one finite-dimensional representation satisfying them all. When the optimum exceeds the quadratic factor, our finite-support argument starts with weighted combinations of cycle inequalities that rule out larger candidate factors. Uniform analytic bounds let us apply Montel's theorem to the associated separating functions; normalization keeps the limit nonzero. The limit is nonpositive on the angle interval, but feasibility makes its average under an optimal measure nonnegative. That measure must therefore be supported on the limit's zeros, of which there are finitely many on the compact angle interval inside its domain of analyticity. Cyclic monotonicity then realizes the entire prescribed trajectory on one objective. The quadratic endpoint has a separate direct realization.

Standard initialization. A rotating trajectory need not satisfy x−1=x0x_{-1}=x_0. We use an auxiliary scalar coordinate to give a simple, uniform initialization argument. It supplies interpolation slack and decays faster than the target trajectory, preserving the factor. This is a construction device, not a claim that an extra dimension is necessary; the κ=10\kappa=10 example starts directly in two dimensions.

A bound for every trajectory. A feasible spiral family supplies lower bounds only. Above its optimum, a finite strict separator supplies a combination of cycle inequalities. We turn this combination into an integral quadratic constraint (IQC) multiplier and verify the strict-IQC theorem's hypotheses for the rescaled NAG recurrence (Megretski–Rantzer; discrete form in Zhang–Seiler–Carrasco, Theorem 3). The theorem establishes square summability: the rescaled sequences have a finite sum of squared norms. A further estimate gives a constant bb independent of the objective and dimension. This yields the matching upper bound on arbitrary NAG trajectories.

These steps establish both attainment by one fixed objective and equality with the horizon-dependent factor. Neither follows from cyclic monotonicity alone or from constructing separate finite-horizon worst-case instances.

Subsequent simplifications. Since submission, we have replaced the Montel argument with explicit derivative bounds, Taylor expansions, and Rolle's theorem. The added initialization coordinate now becomes zero after two steps, and finite sums and induction give the upper bound without invoking the strict-IQC theorem. An explicit finite cycle also shortens the interpolation reduction. These simplify the same result. The uploaded revision includes an expanded proof sketch explaining the bottlenecks summarized above.

Thank you for your detailed response.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.