Convergence under convexity

The objective 0.5(x² + 10y²) at the setting (10, 1) sits 55 above its minimum. With a step of 0.1 the geometric bound is 55 × 0.9ᵗ, which falls below 1 at 39 iterations. The run beats its bound and crosses 1 sooner. A bound that uses only convexity supplies 505 divided by the iteration number, which requires 506 iterations to reach the same location. Both bounds describe the same trajectory, and the geometric one is thirteen times more useful.

The difference is a second assumption. A convex function is one whose graph lies below the straight line between any two of its points. Every tangent — the straight line that touches the graph at one point and matches its slope there — sits beneath the objective. !Gap to the minimum against iteration number for $0.5(x^2+10y^2)$ from $(10,1)$, both axes logarithmic. The convexity bound $505/t$ is a straight line that reaches 1 at $t=505$; the strong-convexity bound $55\times 0.9^t$ falls below 1 at $t=39$. Both bound the same run, and at this accuracy the geometric bound needs thirteen times fewer iterations. The figure is schematic. Status: schematic.

Convexity alone does not give a rate of one over the iteration number. Convexity, L-smoothness and the constant step 1/L together give the next display [S:77:140-140]. With only a Lipschitz bound on the values, the provable rate is the weaker O(log t/√t) [S:77:147-147].

$$f({\theta }_t)-f({\theta }^{\ast })\le \frac{L\Vert {\theta }_0-{\theta }^{\ast }{\Vert }^2}{2t}.$$

That line says: the value gap falls in proportion to one over the iteration number. [F01]

Strong convexity adds a floor beneath the curvature: the objective must bend at least as much as some constant m. With both bounds the gap contracts by a constant factor at every iteration [S:77:138-138].

$$f({\theta }_t)-f({\theta }^{\ast })\le {\left(1-\frac{1}{\kappa }\right)}^t\left[f({\theta }_0)-f({\theta }^{\ast })\right],\kappa =\frac{L}{m}.$$

That line says: the gap is multiplied by the same number below one at every iteration, so it decays geometrically. [F02]

The ratio κ is the condition number, the largest curvature divided by the smallest [S:77:137-137]. It is at least 1, and it measures how stretched the bowl is. A round bowl has κ = 1 and one iteration finishes; a long thin valley has a large κ and the procedure crawls.

The number has a geometric interpretation. The level sets — the sets where the objective keeps one value — of 0.5(x² + 10y²) are ellipses whose axes have ratio √10, approximately 3.16, and the condition number affects precisely that shape [S:77:137-138]. A gradient perpendicular to a long axis points across the valley rather than along it, so the trajectory crosses and re-crosses instead of descending. The two bounds above are two methods of paying for the same geometry: the geometric bound pays κ directly, and the 1/t bound pays it inside the constant.

The condition number is not a property of the objective alone. Change the units of one parameter and the same objective acquires a different κ, because the ratio of curvatures changes with the coordinates [S:77:139-139]. Choosing coordinates that reduce the ratio is the principal idea of preconditioning [S:77:139-140]. A procedure that rescales its own variables can convert a long thin valley into a round bowl without changing the answer it seeks.

The two bounds also differ in their requirements. The 1/t bound needs smoothness and convexity, and no positive m, so it survives when the smallest curvature is zero. The geometric bound needs a positive m, and when m is zero its factor is 1 and the bound says nothing. Strong convexity is an additional promise about the shape of the objective, and it is what purchases the exponent.

One caution concerns what t counts. An iteration is one gradient evaluation, not one unit of total work, so the counts above convert to work by multiplication. A method with fewer iterations can still cost more per iteration, and a comparison between methods must use the product, not the iteration count alone.

Worked example: the objective 0.5(x² + 10y²) has curvatures 1 and 10, so L = 10, m = 1 and κ = 10. The initial gap is 55, and the squared distance from (10, 1) to (0, 0) is 101. The geometric factor is 1 − 1/κ = 0.9, so the bound is 0.9ᵗ × 55, and 0.9³⁹ × 55 is approximately 0.90, a little below 1, while 0.9³⁸ × 55 is 1.004. The convex bound is L‖θ₀ − θ*‖²/(2t) = 10 × 101/(2t) = 505/t, which equals 1 at 505 iterations and falls below it at 506. The first bound requires 39 iterations, the second requires 506, and their ratio is approximately 13.

The arithmetic demonstrates what strong convexity purchases: not a different algorithm, but a different exponent. A constant factor per iteration beats one over the iteration number, and the gap between them grows with the accuracy you demand.

The bounds cost something. They require convexity, and they require both constants, which are known only in rare cases [S:44:477-477]. They bound the value, not the distance to the answer: a long flat valley permits the value to fall while the setting barely moves. And they are counts in advance, so they are crude: the same analysis on a quadratic is an upper bound, not the count the trajectory will take [S:44:481-481].

The formal statement. Let $f$ be convex, differentiable and $L$-smooth, with a minimizer ${\theta }^{\ast }$. Run gradient descent with the constant step $1/L$. Then, for every $t\ge 1$,

$$f({\theta }_t)-f({\theta }^{\ast })\le \frac{L\Vert {\theta }_0-{\theta }^{\ast }{\Vert }^2}{2t}.$$

If in addition $f$ is $m$-strongly convex with $m>0$, then

$$f({\theta }_t)-f({\theta }^{\ast })\le {\left(1-\frac{1}{\kappa }\right)}^t[f({\theta }_0)-f({\theta }^{\ast })],\kappa =\frac{L}{m}.$$

The first display says that the value gap falls like one over the step number. The second says that the gap is multiplied by the same factor below one at every step. Both assume exact arithmetic and the step $1/L$. Neither assumes that you know the constants.

The derivation. The descent lemma gives $f({\theta }_{t+1})\le f({\theta }_t)-\Vert \nabla f({\theta }_t){\Vert }^2/(2L)$. Strong convexity gives $\Vert \nabla f({\theta }_t){\Vert }^2\ge 2m[f({\theta }_t)-f({\theta }^{\ast })]$ [S:77:136-136], so that line becomes

$$f({\theta }_{t+1})-f({\theta }^{\ast })\le \left(1-\frac{m}{L}\right)[f({\theta }_t)-f({\theta }^{\ast })].$$

The display says that one step removes at least the fraction $m/L$ of the gap. Iterating it gives the geometric bound, and that is the complete proof of the second statement. The first statement needs one more move. Convexity gives $f({\theta }_t)-f({\theta }^{\ast })\le \nabla f({\theta }_t{)}^{\top }({\theta }_t-{\theta }^{\ast })$, and the Lyapunov function $V_t=t[f({\theta }_t)-f({\theta }^{\ast })]+\frac{L}{2}\Vert {\theta }_t-{\theta }^{\ast }{\Vert }^2$ decreases along the run [S:77:141-141]. Bach calls that choice mysterious on purpose, because the cancellations are found by trial rather than by a rule [S:77:141-141]. The algebra is omitted here; the reference carries it in full.

The edge case. The core's example has curvatures $1$ and $10$, and it reads the geometric bound as $0.9^t$. That is the bound for the step $1/L$. Bach computes the constant step that is best in the worst case over the whole spectrum, and its factor is slightly smaller [S:77:130-130]. The core's count of $39$ steps is therefore the count for $1/L$, not the best possible count. The difference is a constant factor, not a different exponent.

A sharper edge is the spread of the spectrum. The bound $(1-1/\kappa {)}^t$ is set by the two extreme curvatures and ignores everything between them. When the eigenvalues are spread, Bach reports a strong discrepancy between the bound and the observed behaviour [S:77:131-131]. The bound can therefore overstate the step count badly, and a run that looks slow on paper can arrive sooner.

What the core hid. The core said that the condition number is not a property of the loss alone, because changing units changes it. The formal version: $\kappa$ is the ratio of the largest to the smallest eigenvalue of the Hessian, and a linear change of variables conjugates the Hessian, so the eigenvalues move [S:77:139-139]. Preconditioning is the search for a change that lowers the ratio [S:77:139-140]. The core also hid that the $1/t$ bound needs no positive $m$. That is why it survives on a flat valley where the geometric bound says nothing.

Where the analogy breaks. The valley picture has a floor and walls you can point at. A loss with a million knobs has no picture, and "across the valley" is not a direction you can draw. The bound uses two numbers, the largest and the smallest curvature, so the geometry that matters is the spectrum and not the drawing.

Original sources. Bach proves both bounds, the geometric one for smooth strongly convex losses [S:77:138-138] and the $1/t$ one for smooth convex losses [S:77:140-140]. Boyd and Vandenberghe prove the geometric version with the constants $m$ and $M$, and they give the iteration count as a logarithm of the ratio between the starting gap and the target [S:44:480-481]. Bottou, Curtis and Nocedal prove a stochastic version with a fixed step and a noise floor [S:46:26-26].

An open question. The fast bound needs $m$ and $L$, and the field has not settled how to obtain the fast rate when neither is known. Bach notes that faster first-order methods exist but that they give up adaptivity and lose stability under noise [S:77:139-139]. The two constants are not free parameters either. In a regularised linear model the strong-convexity constant comes from the regulariser, and it shrinks as the table grows [S:77:136-136]. Evidence that would settle a proposal: a method that reaches the $\kappa$ rate on a family of problems without being told $m$ or $L$, with the estimation cost counted and the noise level varied.

A frontier result. Nesterov's modification of gradient descent keeps two iterates and extrapolates between them. For a strongly convex loss it changes the characteristic time from $\kappa$ steps to $\sqrt{\kappa }$ [S:77:143-143]. For a convex loss it changes the value rate from $1/t$ to $1/t^2$ [S:77:143-143]. Bach also reports that these rates are optimal for methods that combine gradients linearly, so the gain is a property of the class and not an accident of one analysis.

What to read next. Read Bach sections 5.2.3 to 5.2.5 for the two proofs and the acceleration [S:77:138-143]. Read Boyd and Vandenberghe section 9.3 for the same argument in the $m$ and $M$ notation [S:44:480-481]. Read Murphy section 8.2.3 for the condition number as a picture [S:63:316-316]. Then read Bottou section 4.2 for the stochastic case [S:46:26-26].