What does a bound on the curvature buy you?

At the setting (2, 1) on the objective x² + 4y², take one step of size 1/8. The step subtracts (1/8)(4, 8) = (0.5, 1) from the setting, so the move has length √(0.5² + 1²) = 1.12 and lands at (1.5, 0), where the objective falls from 8 to 2.25. Before the step you could have guaranteed a reduction of at least 5, using the gradient alone and one additional number describing the curvature.

The number is the smoothness constant. An objective is smooth with constant L when its gradient cannot change faster than L per unit distance [S:43:39-39]. In verbal terms, the slope is not permitted to jump: displace the setting slightly and the gradient changes slightly, in proportion [S:46:23-23]. When the objective possesses second derivatives, L is the largest curvature, the largest second derivative along any direction; for this example the second derivatives are 2 and 8, so L = 8 [S:46:23-24]. !Along the update $\theta -\eta g$ from $(2,1)$ on $f(x,y)=x^2+4y^2$, with $g=(4,8)$. The loss falls from 8, and the parabola $8-80\eta +320{\eta }^2$ touches it at $\eta =0$ and lies above it. The parabola reaches its minimum at $\eta =1/L=1/8$ with value 3, so the lemma guarantees a fall of at least 5; the actual step lands at $(1.5,0)$ with loss 2.25, a fall of 5.75. The guarantee is a floor, not a prediction. The figure is schematic. Status: schematic.

Smoothness supplies an upper bound on where a displacement can land. At any nearby setting the objective lies below a parabola that touches it at the starting point.

$$f({\theta }^{\prime })\le f(\theta )+\nabla f(\theta {)}^{\top }({\theta }^{\prime }-\theta )+\frac{L}{2}\Vert {\theta }^{\prime }-\theta {\Vert }^2.$$

That line says: the objective at a nearby setting is at most the straight-line prediction plus a curvature penalty that grows with the square of the displacement. The superscript ⊤ turns a column into a row so that the product is an inner product; the double bars denote length; θ' is a nearby setting. [F01]

Choose the displacement vector to be −(1/L)∇f(θ), and write g for ∇f(θ). The linear term then contributes −‖g‖²/L and the penalty contributes ‖g‖²/(2L), because the displacement has length ‖g‖/L. The first two terms therefore supply a reduction of ‖g‖²/L while the penalty consumes half of it. What remains is a floor beneath the decrease.

$$f\left(\theta -\frac{1}{L}\nabla f(\theta )\right)\le f(\theta )-\frac{\Vert \nabla f(\theta ){\Vert }^2}{2L}.$$

That line says: one step of size 1/L lowers the objective by at least the squared gradient divided by twice the curvature. [F02]

The argument is the descent lemma, and it is where every subsequent guarantee originates [S:77:138-138]. It requires no convexity: the inequality concerns one displacement from one point, and it holds whether the objective is a bowl or a mountain range [S:43:40-40].

Worked example: at (2, 1) the gradient is (4, 8), so its squared length is 16 + 64 = 80. With L = 8 the floor is 80/16 = 5. The step of 1/8 lands at (1.5, 0), where the objective is 2.25, so the actual reduction is 8 − 2.25 = 5.75. The floor is satisfied with 0.75 to spare.

The spare reduction is not an error. The parabola is a worst case, and the step happened to be better than the worst case. The floor is a guarantee, not a prediction, and a guarantee that is nearly tight is the useful variety.

The multiplier 1/L is not a convention. It is the bottom of the parabola: the value that minimises the model, obtained by setting the derivative of the right-hand side with respect to the multiplier to zero. That derivative is −‖g‖² + Lη‖g‖², which vanishes at η = 1/L. A smaller multiplier leaves part of the predicted gain unused, and a larger one pays more curvature penalty than it gains in slope. The lemma evaluates the model at its own minimum, which is why the floor has the form it does.

On a quadratic the actual reduction divided by the floor lies between 1 and 2 − m/L, where m is the smallest curvature. Here the ratio is 5.75/5 = 1.15. The ratio is 1 when the gradient lies along the direction of greatest curvature, and it approaches 2 − m/L when the gradient lies along the flattest one; here that limit is 1.75. The floor uses only the length of the gradient, so the spare reduction measures how far the curvature along this direction falls short of the largest one.

Smoothness is a substantive restriction, not a formality. The objective θ⁴ is differentiable — it has a gradient at every point — and convex, and its gradient 4θ³, by the power rule, changes by more than any fixed L over a sufficiently long interval. No finite smoothness constant exists, and the parabola argument fails at large settings. A kinked objective such as the absolute value has no gradient at the corner at all. The bound covers the smooth, finite-curvature case and is silent outside it.

The lid has limits. Many objectives possess corners and no finite L at all, and then the parabola argument says nothing. Even when L exists it may be enormous or unknown, which makes the guaranteed multiplier tiny or unusable. And a floor is one-sided: it reports the least a displacement can achieve, never the most, and it does not claim that the objective is convex or that the displacement leads to a minimum.

The formal statement. A differentiable $f$ is $L$-smooth on a set when $\Vert \nabla f(x)-\nabla f(y)\Vert \le L\Vert x-y\Vert$ for every pair in the set [S:43:39-39]. The descent lemma then holds for any such pair:

$$f(y)\le f(x)+\nabla f(x{)}^{\top }(y-x)+\frac{L}{2}\Vert y-x{\Vert }^2.$$

The display says that the loss stays below the tangent line plus a quadratic penalty set by the curvature bound. The hypotheses are differentiability on the segment from $x$ to $y$ and the Lipschitz bound along that segment. Convexity is not one of them.

The derivation. Write the difference as an integral along the segment:

$$f(y)-f(x)={\int }_0^1\nabla f(x+t(y-x){)}^{\top }(y-x)dt.$$

Subtract the tangent term $\nabla f(x{)}^{\top }(y-x)$ and move it inside the integral. The integrand becomes a difference of two gradients dotted with $y-x$, whose modulus is at most $Lt\Vert y-x{\Vert }^2$ by the Lipschitz bound. Integrating $t$ from zero to one gives $L\Vert y-x{\Vert }^2/2$. Bubeck gives this proof [S:43:40-40], and the only estimate in the middle is Cauchy–Schwarz, followed by the Lipschitz bound.

Now put $y=x-\eta \nabla f(x)$ and write $g$ for the gradient at $x$. The right-hand side becomes $f(x)-\eta \Vert g{\Vert }^2+\frac{L{\eta }^2}{2}\Vert g{\Vert }^2$, so the guaranteed fall is $\eta (1-\frac{L\eta }{2})\Vert g{\Vert }^2$. That expression is positive exactly when $\eta <2/L$ and largest at $\eta =1/L$, where it equals $\Vert g{\Vert }^2/(2L)$. The value $\eta =1/L$ is the bottom of the parabola, and the same algebra explains the stability boundary of section 17.2.

The edge case. The core's statement about ${\theta }^4$ concerns the whole line, and that is where it holds. On any bounded interval a finite constant exists. On $[-a,a]$ the second derivative is at most $12a^2$, so $L=12a^2$ works there, and the lemma holds for every multiplier whose step stays inside the interval [S:46:23-23]. The global statement fails because no single $L$ covers every interval, not because the loss breaks the lemma locally. A run that stays in a bounded region therefore has a finite $L$ even when the global statement says it has none. The practical difficulty is that the bound depends on the region, and the region is what you do not know in advance.

A second edge is the corner. The absolute value has no gradient at zero, so the lemma has nothing to say there. The subgradient method replaces the gradient with any supporting slope and keeps a convergence proof, at a slower rate [S:77:147-147]. The floor is also empty at a stationary point, where the gradient is zero and the promise collapses to $f\le f$.

What the core hid. The core gave the floor at the multiplier $1/L$ and mentioned that a larger multiplier pays a larger penalty. The general factor $\eta (1-L\eta /2)$ makes the trade visible: the gain grows with the multiplier, the penalty grows with its square, and the product has one maximum. The core also hid that the lemma concerns a pair of points, which is exactly why it survives without convexity and why it also applies to a stochastic step.

Original sources. The lemma appears as Lemma 3.4 in Bubeck, with the integral proof [S:43:39-40], and as equation (4.3) in Bottou, Curtis and Nocedal [S:46:23-23]. Both present it as the standard hypothesis for a first-order method. Boyd and Vandenberghe give the same inequality with the constants $m$ and $M$ for the two curvatures, and they warn that the pair is known only in rare cases [S:44:477-477].

An open question. The bound is only as good as $L$, and a training run rarely knows $L$. A value that is too small makes the lemma false, and a value that is too large makes the guaranteed step tiny. The field has not settled how to obtain a usable $L$ for a model with millions of parameters without paying for a line search at every step. Evidence that would settle a proposal: a stated estimator, a proof that the descent lemma still holds with the estimated value, and a measured step count on problems whose true $L$ is known.

A frontier result. Nesterov and Nemirovski built a class of losses whose analysis needs no unknown constant at all. A convex loss is self-concordant when $|f^{\prime \prime \prime }(x)|\le 2f^{\prime \prime }(x{)}^{3/2}$ along every line [S:44:511-512]. The third derivative is bounded by the three-halves power of the second, not by the second itself; that power is what makes the condition survive a change of units, and the factor 2 is a normalisation that a rescaling of the loss can remove. Newton's method on such a loss has a complexity bound that does not depend on any constant you would have to measure [S:44:511-511]. The class is defined by that inequality, so the constant becomes a property of the function rather than a number you must measure on an interval. The price is a narrower class: the logarithmic barriers of interior-point methods belong to it, and a loss with a corner does not.

What to read next. Read Bubeck section 3.2 for the lemma and its one-step consequence [S:43:40-40]. Read Bottou section 4.1 for the stochastic version [S:46:23-24]. Read Boyd and Vandenberghe sections 9.5 and 9.6 for self-concordance [S:44:511-511]. Then read Bach section 5.2.3 for the same inequality written with $\mu$ and $L$ [S:77:136-136].