Strong Convexity and Loss Curvature

Why Curvature Matters for a Loss

Convexity rules out certain shapes: as a prediction moves between two values, a convex loss cannot rise above the straight line connecting its endpoint losses. Strong convexity says more. It requires a definite amount of curvature, so that the loss lies below that line by a quadratic amount. This extra information can quantify how much worse a prediction is than a benchmark and, when the benchmark minimizes the loss, how far away the prediction is.

The size of the curvature matters. Multiplying a loss by a positive constant multiplies its strong convexity parameter by the same constant. A stated parameter also depends on the scale of the prediction: curvature over a restricted domain may be bounded below even when it approaches zero over a larger domain.

Definition and Curvature Interpretation

Fix an outcome $y$, and write $f_y(a)=\ell(y,a)$ for the loss at prediction $a$. Let $C$ be a convex subset of $\mathbb{R}^d$, and suppose $f_y$ is finite on $C$. The norm and inner product below are Euclidean.

Definition: For $\lambda>0$, $f_y$ is $\lambda$-strongly convex on $C$ if, for every $u,v\in C$ and $t\in[0,1]$, $$ f_y((1-t)u+tv) \leq (1-t)f_y(u)+tf_y(v)-\frac{\lambda}{2}t(1-t)\|u-v\|^2. $$ The loss $\ell$ is uniformly $\lambda$-strongly convex in its prediction if this inequality holds for every outcome $y$, with the same $\lambda$. If the parameter can vary with $y$, it is not a uniform bound unless those parameters have a positive common lower bound.

Setting $\lambda=0$ gives the usual convexity inequality. For $\lambda>0$, the subtracted term specifies how much below the chord the function must lie. An equivalent characterization is that $a\mapsto f_y(a)-\frac{\lambda}{2}\|a\|^2$ is convex. Indeed, the quadratic identity $$ \|(1-t)u+tv\|^2=(1-t)\|u\|^2+t\|v\|^2-t(1-t)\|u-v\|^2 $$ shows that applying ordinary convexity to this adjusted function gives exactly the definition above, and the same identity gives the converse.

For a twice continuously differentiable function on an open convex domain, curvature can be checked using its Hessian. A matrix inequality $\nabla^2 f_y(a)\succeq\lambda I$ means that $z^\mathsf{T}\nabla^2 f_y(a)z\geq\lambda\|z\|^2$ for every vector $z$. In one dimension this condition is simply $f_y''(a)\geq\lambda$.

Worked Example: Squared Loss Has Constant Curvature

Take the squared loss for a scalar prediction, $f_y(a)=(y-a)^2$, with prediction domain $\mathbb{R}$. Its second derivative with respect to $a$ is $f_y''(a)=2$, regardless of $a$ or $y$. Thus the curvature condition gives $\lambda=2$.

The defining inequality can also be checked exactly. For $u,v\in\mathbb{R}$, $$ (1-t)(y-u)^2+t(y-v)^2-\bigl(y-((1-t)u+tv)\bigr)^2 =t(1-t)(u-v)^2. $$ The right side is $\frac{2}{2}t(1-t)(u-v)^2$, so squared loss is $2$-strongly convex. The equality confirms that its curvature is exactly constant, not merely bounded below by 2.

If instead the loss is defined as $\frac12(y-a)^2$, its second derivative is 1, so its strong convexity parameter is 1. The factor of one half in a loss definition changes the parameter.

From Strong Convexity to a Quadratic Lower Bound

The defining inequality compares a point between two predictions with a weighted average of their losses. When the function is differentiable, it also implies a useful lower bound relative to any reference prediction. The gradient term is essential: it records the local direction in which the loss is changing.

Theorem: Let $C$ be an open convex subset of $\mathbb{R}^d$, and let $f_y$ be differentiable and $\lambda$-strongly convex on $C$. Then for all $u,v\in C$, $$ f_y(v)\geq f_y(u)+\nabla f_y(u)^\mathsf{T}(v-u)+\frac{\lambda}{2}\|v-u\|^2. $$

Proof. Define $g(a)=f_y(a)-\frac{\lambda}{2}\|a\|^2$. By the equivalent characterization above, $g$ is convex. Put $d=v-u$, and consider the one-dimensional convex function $h(s)=g(u+sd)$, for $0\leq s\leq1$. Convexity implies, for $0<s\leq1$, $$ \frac{h(s)-h(0)}{s}\leq h(1)-h(0). $$ As $s$ decreases to zero, differentiability gives $h'(0)=\nabla g(u)^\mathsf{T}d$. Therefore $g(v)\geq g(u)+\nabla g(u)^\mathsf{T}(v-u)$. Substituting $g(a)=f_y(a)-\frac{\lambda}{2}\|a\|^2$ and using $\|v\|^2-\|u\|^2-2u^\mathsf{T}(v-u)=\|v-u\|^2$ gives the stated inequality. $\square$

This result explains the phrase quadratic lower bound on loss differences. Subtracting $f_y(u)$ from both sides gives $$ f_y(v)-f_y(u)\geq\nabla f_y(u)^\mathsf{T}(v-u)+\frac{\lambda}{2}\|v-u\|^2. $$ The loss difference is bounded below by a linear term plus a positive quadratic term. It is not generally bounded below by the quadratic term alone when $u$ is an arbitrary reference point.

Worked Example: A Loss Difference From an Arbitrary Reference

Let $y=3$, use squared loss $f_y(a)=(3-a)^2$, and compare the reference prediction $u=1$ with $v=2$. The loss at the reference is $f_y(1)=4$; at the new prediction it is $f_y(2)=1$. Thus the loss difference is $1-4=-3$.

Here $\lambda=2$, and the derivative is $f_y'(a)=2(a-3)$, so $f_y'(1)=-4$. The theorem's lower bound is $$ f_y(2)-f_y(1)\geq f_y'(1)(2-1)+\frac{2}{2}(2-1)^2=-4+1=-3. $$ The actual difference is $-3$, so equality holds. The quadratic term is positive, but the linear term is negative and larger in magnitude. This is why a quadratic lower bound relative to an arbitrary prediction must include the gradient term.

When the Reference Is a Minimizer

The bound becomes especially informative when the reference prediction $u_*$ minimizes the loss on its domain and is an interior point where the loss is differentiable. At an interior differentiable minimum, $\nabla f_y(u_*)=0$. Substituting this into the theorem yields $$ f_y(v)-f_y(u_*)\geq\frac{\lambda}{2}\|v-u_*\|^2. $$ Thus a prediction with small excess loss must be close to the minimizer: rearranging gives $\|v-u_*\|^2\leq 2\{f_y(v)-f_y(u_*)\}/\lambda$. This conclusion requires the minimum and zero-gradient conditions; it does not follow by dropping the gradient term at an arbitrary reference point.

Worked Example: Excess Loss Controls Distance to the Minimum

For squared loss with outcome $y=2$, $f_y(a)=(2-a)^2$ on $\mathbb{R}$. Its minimum occurs at $u_*=2$, where the derivative $f_y'(2)=0$ and the loss is 0. The strong convexity parameter is 2.

At prediction $v=4$, the loss is $f_y(4)=(2-4)^2=4$, and the squared distance from the minimizer is $(4-2)^2=4$. The minimizer bound gives $$ f_y(4)-f_y(2)\geq\frac{2}{2}(4-2)^2=4. $$ Both sides equal 4. More generally, for any prediction $v$, the loss difference is $(v-2)^2$, exactly the quadratic lower bound in this example.

Checking Curvature on a Restricted Domain

A positive lower curvature bound can depend on restricting predictions to a particular domain. The following example uses binary logistic loss as a function of its scalar score. It illustrates how a second-derivative calculation establishes strong convexity only where the curvature has a positive uniform lower bound.

Worked Example: Logistic Loss on a Bounded Score Range

Let $y\in\{-1,1\}$ and $f_y(a)=\log(1+e^{-ya})$, with $a\in[-2,2]$. Differentiating twice gives $$ f_y''(a)=\frac{e^{ya}}{(1+e^{ya})^2}. $$ For $s=ya$, this curvature is unchanged when $s$ is replaced by $-s$, and it decreases as $|s|$ increases. Since $|s|\leq2$, its minimum on the domain is $$ \lambda=\frac{e^2}{(1+e^2)^2}\approx 0.1050. $$ Thus $f_y''(a)\geq\lambda$ throughout $[-2,2]$, for either outcome, and the loss is uniformly $\lambda$-strongly convex there.

For a numerical check of the quadratic bound, take $y=1$, $u=0$, and $v=1$. Then $f_y(0)=\log 2$, $f_y'(0)=-1/2$, and $f_y(1)=\log(1+e^{-1})\approx0.3133$. The lower bound is $$ f_y(1)\geq\log 2-\frac12+\frac{0.1050}{2}(1-0)^2\approx0.2456, $$ which holds. On the full real line, however, this logistic curvature tends to zero as $|a|$ tends to infinity. It therefore has no positive strong convexity parameter on all of $\mathbb{R}$.

Curvature Criterion and Its Justification

The second-derivative test is a direct link between local curvature and the global strong convexity inequality on a convex domain. The condition must hold everywhere in the domain, not just at one prediction.

Theorem: Let $C$ be an open convex subset of $\mathbb{R}^d$, and let $f_y$ be twice continuously differentiable on $C$. Then $f_y$ is $\lambda$-strongly convex on $C$ if and only if $\nabla^2 f_y(a)\succeq\lambda I$ for every $a\in C$.

Proof. First suppose the Hessian condition holds. Take $u,v\in C$, put $d=v-u$, and define $q(t)=f_y(u+td)$ for $0\leq t\leq1$. Convexity of $C$ ensures the segment is in the domain. By the chain rule, $$ q''(t)=d^\mathsf{T}\nabla^2 f_y(u+td)d\geq\lambda\|d\|^2. $$ Consequently $r(t)=q(t)-\frac{\lambda}{2}t^2\|d\|^2$ has $r''(t)\geq0$, and so is convex. Its convexity inequality between 0 and 1 gives $$ q(t)-\frac{\lambda}{2}t^2\|d\|^2 \leq(1-t)q(0)+t\left(q(1)-\frac{\lambda}{2}\|d\|^2\right). $$ Rearranging yields the strong convexity inequality for $f_y$.

Conversely, suppose $f_y$ is $\lambda$-strongly convex. Fix $a\in C$ and a vector $z$. For sufficiently small $h>0$, both $a-hz$ and $a+hz$ lie in $C$. Applying the definition at their midpoint gives $$ f_y(a+hz)+f_y(a-hz)-2f_y(a)\geq\lambda h^2\|z\|^2. $$ Divide by $h^2$ and let $h$ decrease to zero. Twice differentiability makes the left side converge to $z^\mathsf{T}\nabla^2 f_y(a)z$. Hence $z^\mathsf{T}\nabla^2 f_y(a)z\geq\lambda\|z\|^2$ for every $z$, which is the required Hessian condition. $\square$

Common Pitfalls and Practical Use

The most common error is to write $f_y(v)-f_y(u)\geq\frac{\lambda}{2}\|v-u\|^2$ for every pair of predictions. The correct general inequality contains the gradient at $u$; the stronger version without that term applies when $u$ is a differentiable interior minimizer. Another error is to verify a positive second derivative at just one point and call the loss strongly convex on its entire domain. A uniform lower bound over the domain is needed.

Strong convexity is useful because it turns curvature into a quantitative guarantee: predictions far from an interior minimizer must incur a definite amount of extra loss. When using such a guarantee, check the prediction domain, the loss scaling, whether the parameter is uniform over outcomes, and whether the reference prediction actually has zero gradient.

Check Your Understanding

Use the definition and results above to answer the following questions.

For $\frac12(y-a)^2$, what is the largest strong convexity parameter on $\mathbb{R}$, and how does it compare with the parameter for $(y-a)^2$?
Why does the quadratic lower bound between arbitrary $u$ and $v$ include a gradient term?
What uniform second-derivative condition establishes $\lambda$-strong convexity for a scalar twice differentiable loss?
For logistic loss, why does a bounded prediction domain permit a positive curvature lower bound that fails on the full real line?
Under what conditions can the gradient term be omitted to bound excess loss by a quadratic in the distance from a reference prediction?