For smooth strongly convex functions with condition number , the ratio of the gradient Lipschitz constant to the strong convexity parameter , Nesterov’s accelerated gradient method (NAG) with its standard constant step size and momentum converges geometrically. We determine its exact worst-case asymptotic factor for the squared distance to the minimizer. The worst cases combine planar spirals that rotate by fixed angles while contracting by a common factor. The exact factor is the largest contraction for which such spirals come from one function in the class. One fixed function in a finite-dimensional space attains it, and a matching upper bound holds for every function, dimension, and initial point.
The worst case at : one function on and the standard initialization . Every step rotates the error by radians and multiplies its squared norm by .
Worst quadratic
0.467544
Exact worst case
0.564423
Gannot’s upper bound
0.565235
Classical upper bound
0.683772
Asymptotic squared-distance factors at ; larger means slower.
1 · Setting
Nesterov’s method and the factor we measure
We work in , in any dimension , with the Euclidean norm. For , let be the differentiable, -strongly convex functions with -Lipschitz gradients, written when the dimension matters. Each has a unique minimizer . Dividing the objective by gives a function in , where is the condition number; this preserves the iterates when the step size becomes . Nesterov’s accelerated gradient method (NAG) with its standard constant parameters is
started from the standard initialization . The points are where gradients are evaluated; the iterates are what we measure. For a fixed function and initial point, the normalized squared error is , and its asymptotic factor is . If , the factor is : larger means slower convergence. All factors on this page refer to the squared distance.
Two worst cases are natural:
where the suprema range over all dimensions , functions , and initial points . The fixed-objective factor is the worst asymptotic decay of one fixed function and initial point. The horizon-dependent factor first takes the worst error at each iteration , allowing a different function, dimension, and initial point for each . Uniform convergence guarantees control it: if for all and , then . Always ; the main theorem shows equality. At , one step reaches the minimizer, so both factors are zero.
For a broader audience: what is a convergence factor?
Gradient methods move toward the minimizer of a function step by step. On strongly convex problems the error shrinks geometrically: after steps, the squared distance to the solution is roughly times its initial value. The factor depends on the condition number , which measures how differently the function curves in different directions; large means an ill-conditioned problem.
Nesterov’s method adds momentum: each step extrapolates along the previous step before taking a gradient step. With the standard tuning, momentum improves the dependence on from roughly to roughly . This page asks for the slowest possible factor over all such problems, and answers it exactly.
Why two worst cases? A convergence guarantee must hold for every problem, and the worst problem after 10 steps may differ from the worst problem after 1000 steps; allows this. asks how slowly one fixed problem can converge forever. The paper shows that the two coincide and that a single function is as slow as the worst case allows.
2 · Background
Quadratics and the classical guarantee
The quadratic belongs to . On it, the method becomes the linear recurrence , whose characteristic polynomial has the double root . Its asymptotic squared-distance factor is
At : the squared distance on the worst quadratic, from , and the decay rate of the classical guarantee. The curves are exact formulas; the vertical axis is logarithmic. The worst case over all of decays somewhere in the shaded range of slopes.For a broader audience: why quadratics?
On a quadratic function, every step of the method is a fixed linear map, so its behavior is governed by eigenvalues. Many analyses, and much intuition, are built on quadratics. The double root also explains the shape of the curve: from , the error is times its initial value rather than a pure geometric sequence, so it decays more slowly during the first iterations.
3 · The question
How slowly can the method converge on a nonquadratic objective?
Can a nonquadratic function make the method slower than every quadratic, and by how much? The classical bounds leave a wide gap. Gannot [2022, Proposition 2.13] used frequency-domain inequalities to obtain an analytic upper bound on the squared-distance factor: the smaller positive root of
This bound is remarkably close to the exact factor determined below. For large it behaves like , and the paper shows that this leading term is sharp. The same cubic arises from a subset of the interpolation inequalities explained in Section 4, those between consecutive iterations and the minimizer. Keeping only these inequalities enlarges the set of feasible factors, so its largest feasible factor is an upper bound on the exact one.
Known bounds on the worst-case factor at the selected : the worst quadratic is a lower bound; Gannot’s and the classical bounds are upper bounds.For a broader audience: what does a frequency-domain bound do?
Integral quadratic constraints and frequency-domain inequalities treat an optimization method as a feedback system, in which the gradient is an unknown but constrained nonlinearity. Checking one inequality at every frequency certifies that the iterates decay at least at a given rate. Such analyses give upper bounds; on their own, they do not produce a function that attains the rate.
4 · Result
The answer: rotating spirals and interpolation
Theorem (exact asymptotic rate). For every , the two worst-case asymptotic factors satisfy
Here , defined below, is the largest contraction factor for which rotating spirals come from one function in . The factor is attained by a single function in a finite-dimensional space and an initial point, both independent of the iteration count. Moreover, .
Which data come from one function?
Prescribed query points, gradients, and values are interpolated by if some has and for every index . This holds if and only if every ordered pair satisfies
[Taylor, Hendrickx & Glineur, 2017]. We call these the interpolation inequalities; one is active when it holds with equality. With , , and , they become cyclic monotonicity of the pairs : for every cycle of indices ,
[Rockafellar, 1970]. Function values no longer appear; a function satisfying these conditions supplies them.
Spirals
Identify with and let : multiplication by rotates by and multiplies squared norms by . With , the choice
makes the NAG recurrence exact: the query points are , the gradients , and the iterates ; any positive multiple works equally well. Such a trajectory is self-similar: from iteration one onward, every step applies the same rotation and contraction, . Several components with a common , different angles, and weights summing to one occupy orthogonal planes; their angles and weights form a probability measure on .
Feasibility and the exact factor
For such trajectories, all interpolation inequalities reduce to two per iteration index. For one spiral, write , and let be its average over the components. The inequalities hold if and only if there is a scalar with
Here is a free parameter: the value at the first sample of the convex function given by cyclic monotonicity, whose values at later samples can be chosen as . The exact factor is the largest for which some satisfies these conditions; such trajectories are called feasible. Equivalently, is the optimal value of a linear optimization problem over probability measures on a disk of contraction factors and angles, and every optimal measure lies on one circle, that is, uses one common contraction factor.
Matching lower and upper bounds
Lower bound. If , an optimal measure with finitely many angles exists. One additional coordinate, zero from iteration two onward, enforces , and one function in a finite-dimensional space produces the whole trajectory; hence . Otherwise the quadratic attains the factor.
Upper bound. For , the conditions fail, and a finite nonnegative combination of cyclic monotonicity inequalities certifies the failure. These inequalities hold along every run of the method on every function in the class. Summing them, a finite induction gives , with depending only on and , for every function, dimension, and initial point; hence .
For a broader audience: why spirals?
Momentum makes the iterates overshoot, so in two dimensions they can circle around the minimizer instead of approaching it directly. A worst-case function bends its gradients just enough to keep the iterates rotating, while remaining convex with bounded curvature. Whether such a function exists is a purely geometric test on the sequence of points and gradients, called interpolation. The exact worst case is the slowest spiral, or combination of spirals, that passes the test.
5 · Example
At , the worst case is one planar spiral
At , an optimal angular measure is concentrated at a single angle, so the worst case lies in the plane. The exact factor and the corresponding complex multiplier are
One function with minimizer at the origin makes the method produce and for . Each step rotates the error by radians, and for every . The interpolation inequalities are active for the ordered pairs and , , and every inequality comparing the initial query point with a later query point is strict. The matching upper bound uses the inequalities for the cycle . Interval and exact integer arithmetic verify the algebraic solution.
Iterates (green) and query points (blue) from (gold).The exact worst case decays as ; the dotted line with Gannot’s factor is almost indistinguishable from it. The worst quadratic decays faster asymptotically, although its double root makes it slower during the first iterations.
Why is the largest feasible factor. For the planar spiral with angle , each iteration index gives a lower bound on , the function value at the first query point (later values are ), from the interpolation inequality for the pair , and an upper bound from the pair . A spiral is feasible only if every lower bound lies below every upper bound. The dashed lines are the bounds from the two pairs with the minimizer, and . As increases, the bound from meets the bound from at . Bounds are computed in this browser; the status uses rigorous interval arithmetic.For a broader audience: reading these figures
The spiral shows the actual worst-case run of the method on a two-dimensional function: every step turns by the same angle and shrinks the distance by the same factor. The decay plot compares this run with the slowest quadratic. The last figure shows the test that limits how slowly a spiral can contract: past , no single function can produce the spiral.
6 · Example
At , two spirals are needed
At , . There is an optimal angular measure supported on two angles, and , and every optimal measure has exactly these two angles in its support; neither angle alone is feasible at this factor. The exact self-similar trajectory spans four real dimensions. One additional coordinate, zero from iteration two onward, enforces , so one fixed function in attains the factor.
Drag, or focus the figure and use the arrow keys, to rotate.
A three-dimensional projection of the four-dimensional trajectory: with , for the two planes with coordinates and . With the contraction removed, that is, after dividing by , the two rotations at different speeds wind around a torus; at true scale, the trajectory shrinks by per step. Projection can change lengths and apparent intersections; the additional start coordinate is not shown.For a broader audience: why more dimensions?
One spiral turns at a single speed. At , the slowest feasible behavior needs two rotations at different speeds happening at once, in separate planes. Neither rotation alone can be produced by a single function at this contraction factor, but together they can.
7 · Rates
The exact factor across condition numbers
Over the condition numbers evaluated in the paper, , the largest difference between Gannot’s upper bound and the numerically evaluated exact factor is , less than of Gannot’s bound. Both behave like , and the paper proves
so the leading constant in Gannot’s bound is sharp. The factor for the distance is . The same exact factor also governs the function gap and the squared gradient norm .
Top: the exact factor (circles) with the worst quadratic, Gannot’s bound (triangles), and the classical bound. Bottom left: , which tends to for the exact factor and for Gannot’s bound, and to for the worst quadratic; it equals for the classical bound. Bottom right: Gannot’s bound minus the exact factor. Values at , , and (filled) are exact; the others are numerical evaluations of the rate formula reported in the paper. Hover or focus a point for its value.The exact factor at the selected (a numerical evaluation except at and ), between the worst quadratic and Gannot’s bound. The lower panel magnifies the interval between the exact factor and Gannot’s bound.For a broader audience: how large is the difference?
At , the squared distance on the worst function shrinks by per step, against on the worst quadratic. Started the same way, after 100 steps the squared distance on the worst function is about times larger than on the worst quadratic. For very ill-conditioned problems, the worst case needs about times as many iterations as the worst quadratic to reach the same accuracy.
8 · Computation
Computing the exact factor for a given
Once is fixed, the conditions of Section 4 on the angular measure and the scalar are linear in and , and is the largest factor for which they can be satisfied. Computing it for a given therefore means locating the largest for which a linear feasibility problem has a solution. The worst-case search in the explorer does this in three steps.
Test one factor. The measure is restricted to a finite grid of angles and the conditions to the first values of (at : 1041 angles and ). A linear program maximizes the smallest slack of these inequalities; the factor passes if this margin is nonnegative. The solution also gives the angles and weights of the spirals.
Bisect. The worst quadratic factor always passes, and Gannot’s bound is an upper bound. Twenty bisection steps between them, a finer grid around the angles found, and 25 further steps give an estimate.
Certify. A finite grid with finitely many inequalities is not automatically an upper or lower bound. Slightly below the estimate, the spirals returned by the linear program are checked against every interpolation inequality in exact interval arithmetic, with analytic bounds for all later iteration indices and the standard initialization; this certifies a lower bound. Gannot’s bound certifies the upper bound.
The worst-case search at , run by this page’s engine. Dots: angles of the spirals chosen by the linear program at each tested factor , with area proportional to their weights; shaded: factors for which no weights pass. Ticks on the axis: the 45 factors tested by the bisection (filled: passed). Left: from the worst quadratic to Gannot’s bound. Right: magnified near the end, where one spiral splits into two. Rings: the exact angles and at . The estimate lies below the exact . Hover or focus a point for its value.
At and , the paper determines the exact factor with exact arithmetic. At , the inequalities of the cycle combine into a polynomial of total degree 19 in and that must be nonpositive. At , its graph touches zero at the optimal angle,
and is the unique solution in a rational box of half-width , certified by interval arithmetic. Just above , an exact factorization and a derivative bound show that is positive at every angle, so this cycle fails for every spiral; this gives the matching upper bound.
For a broader audience: how can a worst case be computed?
For each candidate rate, a linear program decides whether some combination of rotating spirals with that rate can come from one smooth, strongly convex function. Rates that pass and rates that fail are separated by the exact worst-case rate, and halving the interval between them pins it down to many digits, much like guessing a number by halves. Because the program only sees finitely many angles and inequalities, its answer is an estimate; a separate exact check of every inequality turns the spirals it finds into a guaranteed lower bound. Try it for any in the explorer below.
9 · Explorer
Explore any condition number
Choose to compute a worst-case trajectory in this browser, or set and to test one rotating, contracting trajectory. Each certificate checks every interpolation inequality: between all iterations, with the minimizer, and with the initial point of the standard initialization.
○
Checking the example…
Computing rigorous bounds for the spiral, all later iterations, and the standard initialization.
Searching…
Certified attained factor…
Numerical estimate of …
Certified upper bound…
Certified width ≤…
Condition number
Strong convexity 1 and gradient Lipschitz constant ; any decimal in .
Exact at κ = 1, 10, and 100. For other κ, the search returns a certified trajectory and Gannot’s certified upper bound.
Check one spiral
Lengths shrink by per step; larger means slower decay.
Radians per step. The number fields accept exact decimals.
Exact rational preset geometry. The q and θ fields are approximate displays.
Standard tuningThe manual check tests one planar spiral with the standard initialization in the plane. The search can combine spirals in orthogonal planes and add the start coordinate of the paper’s construction.
A spiral toward the minimizer
Checking
Drag or use arrow keys to rotate
Iterates Initial point Query points
The drawing uses floating-point coordinates. Only the certificate determines feasibility.
How the 3D projection works
The curve is a linear projection of one trajectory. Every rotation plane contributes at the same iteration. Projection can change lengths, angles, and apparent intersections; the certificate applies to the full trajectory.
With two planes, write the coordinates of the self-similar trajectory as . The projection is
The projection angle changes which direction in four dimensions is hidden. Camera rotation changes the viewing direction within the projected space.
Current projection matrix, before camera rotation. Columns follow the full-coordinate CSV; entries are approximate.
Squared contraction…
Rotation per step…
Momentum …
Normalized squared distance, all coordinates
Interpolation and initialization
Interpolation
Checking
Both orientations of every pair of iterations, all indices, and the minimizer.
Standard initialization
Checking
The initial query point enforces .
Objective
One fixed function
One function produces every iteration. Optimality is a separate certificate.
Feasible function values
The iterates fix the query points and gradients. Choose ; later values are , and the initial query point has its own value .
Checking…
The certified interval is a sufficient inner interval, with a rigorous bound for every iteration index beyond the explicitly checked ones.
Changes the chosen value while keeping the geometry. The exact preset uses its original rational value at 50%. An exact value entered below overrides this slider.
Limiting inequalities
Each iteration index gives a lower and an upper bound on ; their intersection must be nonempty.
Ordered pair
Bound on F
Value, approximate
Checking…
These pairs define the interval. A strictly feasible spiral has positive slack, so they need not hold with equality.
Checking the initial query point…
Advanced controls and exact inputs
Decimal inputs are exact rationals. Cosines, sines, and square roots are enclosed rigorously. Changing a geometric control leaves the exact preset and starts a new check.
A failed choice does not rule out other values.
The value at .
More indices can close a slowly decaying remainder. Later indices are always covered by an analytic bound.
Why one certificate covers infinitely many iterations
The method fixes the gradients. For and , set for , , and . The query points and gradients make the recurrence exact. They do not, by themselves, come from one function.
Interpolation decides. Every ordered pair of samples, including the minimizer, whose point, gradient, and value are all zero, must satisfy the interpolation inequality. With , the pair gives a lower bound on and the pair an upper bound.
Only index differences matter. Rotation preserves inner products and multiplication by scales squared norms by , so the inequality for is times the one for .
An analytic bound covers large indices. With , the minimizer gives . For , both bounds at index differ from these limits by at most . Checking the first indices explicitly and subtracting this bound from both margins proves every later inequality.
One function for all samples. Cyclic monotonicity of the countably many pairs gives one convex function by Rockafellar’s theorem [Rockafellar, 1970], and reversing the change of variables gives one function in . For several components, the samples are orthogonal sums with a common , so the same argument applies.
The standard initialization
Continued backward, the self-similar trajectory would have , while the method starts from . The initial point with gradient is consistent with the first step and the next query point. The manual check certifies it in the plane: it finds an interval of values at the initial query point that satisfies every inequality with the later queries and the minimizer, again with analytic bounds for all later indices. Then from .
When this planar start fails, the search uses the construction from the paper. One additional coordinate runs the method on for and for , with , from . Its iterates are and for . Every inequality between its initial query and a later query has slack . The spiral is scaled by with , where bounds the spiral’s own inequalities at its initial query. The added coordinate does not change the asymptotic factor.
What “worst case” means here
For a fixed , the worst case is one function and initial point with the slowest asymptotic decay of the squared distance; it is not a trajectory maximizing the error at one particular iteration. At and , the page shows the paper’s exact lower and matching global upper certificates, computed offline and embedded unchanged; for , the standard initialization is certified in this browser. At , one step reaches the minimizer.
For other , a refined angular linear program on a finite grid estimates numerically and returns angles and weights. The returned parameters, slightly below the estimate, must then pass the rigorous all-index check and the standard initialization; the attained factor is a certified lower bound. Gannot’s Proposition 2.13 supplies a certified upper bound, so the exact factor lies between the two. The search is limited to and at most twelve rotating components; if no improved trajectory is certified, the explicit quadratic baseline is shown instead, labeled accordingly.
Inspect the rigorous certificate
Exact inputs, rigorous enclosures, finite margins, analytic remainders, and the engine’s SHA-256 hash.
Waiting for a result…
The JSON records the complete input, the engine version, and its SHA-256 hash, so the same decision can be recomputed in this page. Enclosures are decimal balls that include their rounding radius; exact interval endpoints are also given as rational numbers.
10 · Evidence
What is proved, certified, and computed
Proved in the paper. The exact-rate theorem, the large- expansion, and the examples at and , with computer-assisted algebraic certificates for the examples.
Certified in this browser. Every certificate in the explorer: all interpolation inequalities of a trajectory, with explicit checks for the first iteration indices and analytic bounds for all later ones, and the standard initialization. Decisions use exact dyadic interval arithmetic with outward rounding at 256 bits.
Embedded, computed offline. The exact and lower and global upper certificates, replayed by the paper’s verifiers; their output is embedded with its source hashes.
Numerical. The rate curve away from and the explorer’s estimate of , which use finite angular grids, finitely many inequalities, and floating point.
The interactive checker is not Lean verified. All computations run in this page; the only network requests load the KaTeX math renderer and its fonts from jsDelivr.
References
O. Gannot. A frequency-domain analysis of inexact gradient methods. Mathematical Programming 194:975–1016, 2022. arXiv:1912.13494v2, Proposition 2.13.
L. Lessard, B. Recht, and A. Packard. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization 26(1):57–95, 2016.
Y. Nesterov. Lectures on Convex Optimization, 2nd ed. Springer, 2018.
R. T. Rockafellar. Convex Analysis. Princeton University Press, 1970.
A. B. Taylor, J. M. Hendrickx, and F. Glineur. Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Mathematical Programming 161:307–345, 2017.