Strong Convexity And Parameter Error Bounds

Why Curvature Matters for Parameter Error

A small prediction error does not always imply that a fitted model has parameters close to a particular target. Different parameter values can produce exactly the same predictions, especially when predictors are redundant. Strong convexity rules out this ambiguity locally or globally by requiring the risk to rise at a definite rate in every parameter direction. It therefore turns a guarantee about risk into a quantitative guarantee about parameter distance.

Let $\Theta$ be a convex subset of $\mathbb{R}^d$, equipped with the Euclidean norm $\|\cdot\|$. Write $R(\theta)$ for the population risk at parameter $\theta$. In this tutorial, the relevant curvature is curvature of the population risk itself; a finite-sample risk bound can be used afterward if it controls the population excess risk.

Definition: A differentiable function $R:\Theta\to\mathbb{R}$ is $\mu$-strongly convex, for $\mu>0$, if for all $\theta,\theta'\in\Theta$, $$ R(\theta')\ge R(\theta)+\nabla R(\theta)^\top(\theta'-\theta)+\frac{\mu}{2}\|\theta'-\theta\|^2. $$ The constant $\mu$ is a lower bound on curvature in every parameter direction. Ordinary convexity is the same inequality with the final, strictly positive quadratic term omitted.

For a twice differentiable risk on an open convex set, the Hessian condition $\nabla^2R(\theta)\succeq\mu I$ throughout the set is sufficient for $\mu$-strong convexity. Here the matrix inequality means $v^\top\nabla^2R(\theta)v\ge\mu\|v\|^2$ for every vector $v$. The lower bound must hold in all directions: curvature in only some directions does not yield a Euclidean parameter-distance guarantee.

Excess Risk Controls Distance

The basic transfer follows by applying strong convexity at a risk minimizer. For a constrained parameter space, a minimizer need not have zero gradient. The condition needed is instead that it satisfies the first-order variational inequality $\nabla R(\theta^*)^\top(\theta-\theta^*)\ge 0$ for every $\theta\in\Theta$. This holds, for example, when $R$ is differentiable and convex, $\Theta$ is convex, and $\theta^*$ minimizes $R$ over $\Theta$.

Theorem: Suppose $R$ is $\mu$-strongly convex on a convex set $\Theta$, and $\theta^*\in\Theta$ is a minimizer satisfying $\nabla R(\theta^*)^\top(\theta-\theta^*)\ge 0$ for all $\theta\in\Theta$. Then every $\theta\in\Theta$ obeys $$ \|\theta-\theta^*\|^2\le \frac{2}{\mu}\bigl(R(\theta)-R(\theta^*)\bigr). $$

Proof. Use the definition of strong convexity with its first argument equal to $\theta^*$ and its second argument equal to $\theta$: $$ R(\theta)\ge R(\theta^*)+\nabla R(\theta^*)^\top(\theta-\theta^*)+\frac{\mu}{2}\|\theta-\theta^*\|^2. $$ The variational inequality makes the inner-product term nonnegative. Subtracting $R(\theta^*)$ and multiplying by $2/\mu$ gives the claimed inequality. $\square$

In particular, if an estimate $\hat\theta$ has population excess risk at most $\delta$, then its parameter error satisfies $\|\hat\theta-\theta^*\|\le\sqrt{2\delta/\mu}$. If that risk guarantee holds on an event, the distance guarantee holds on the same event. Strong curvature is what changes the scale: the distance is bounded by the square root of excess risk divided by curvature.

Worked Example: An Anisotropic Quadratic Risk

Let $\Theta=\mathbb{R}^2$, $\theta^*=(0,0)$, and define $R(\theta)=\theta_1^2+4\theta_2^2$. Its Hessian is the diagonal matrix with entries $2$ and $8$, so $R$ is $2$-strongly convex. Suppose a candidate $\theta=(0.3,0.1)$ is known to have this risk.

Direct calculation gives $R(\theta)=0.3^2+4(0.1)^2=0.09+0.04=0.13$, while $\|\theta-\theta^*\|^2=0.3^2+0.1^2=0.10$. The theorem gives $\|\theta-\theta^*\|^2\le(2/2)(0.13)=0.13$, or distance at most $\sqrt{0.13}\approx0.361$. The actual distance is $\sqrt{0.10}\approx0.316$, consistent with the bound. The bound uses the weakest curvature, even though the risk rises faster in the second coordinate.

A Gradient-Based Parameter Bound

Sometimes the population-risk gradient at a candidate is easier to control than its excess risk. Strong convexity then gives another route to parameter error. The result below is stated for an unconstrained minimizer in the interior, so the gradient at the minimizer is zero.

Theorem: Let $R$ be differentiable and $\mu$-strongly convex on an open convex set containing $\theta$ and an interior minimizer $\theta^*$. Then $$ \|\theta-\theta^*\|\le \frac{\|\nabla R(\theta)\|}{\mu}. $$

Proof. Apply strong convexity first with arguments $(\theta,\theta^*)$, then with arguments $(\theta^*,\theta)$, and add the two inequalities. Rearranging yields $$ \bigl(\nabla R(\theta)-\nabla R(\theta^*)\bigr)^\top(\theta-\theta^*)\ge \mu\|\theta-\theta^*\|^2. $$ Because $\theta^*$ is an interior differentiable minimizer, $\nabla R(\theta^*)=0$. The Cauchy–Schwarz inequality therefore gives $\|\nabla R(\theta)\|\,\|\theta-\theta^*\|\ge\mu\|\theta-\theta^*\|^2$. If $\theta=\theta^*$, the result holds immediately; otherwise divide by the positive distance to obtain the bound. $\square$

This is a population statement: it concerns $\nabla R$, not automatically the gradient of a sample risk. To use a sample-gradient calculation, one needs a separate argument controlling how that gradient relates to the population gradient.

Worked Example: Squared-Error Risk for a Mean

Suppose $Y$ has mean $3$ and finite variance $4$, and consider $R(\theta)=E[(Y-\theta)^2]$. Expanding around the mean gives $R(\theta)=4+(\theta-3)^2$: the cross term vanishes because $E[Y-3]=0$. Thus $\theta^*=3$, $R(\theta^*)=4$, and the second derivative is $2$, so $\mu=2$.

At the candidate $\theta=2.6$, the excess risk is $R(2.6)-R(3)=(2.6-3)^2=0.16$, and the actual parameter error is $|2.6-3|=0.4$. The excess-risk theorem gives $|\theta-\theta^*|\le\sqrt{2(0.16)/2}=0.4$, exactly. Also, $\nabla R(\theta)=2(\theta-3)=-0.8$; the gradient theorem gives $|\theta-\theta^*|\le0.8/2=0.4$.

Prediction Risk Can Be Flat in Parameter Directions

Consider linear prediction $x\mapsto x^\top\theta$ with half squared-error population risk $R(\theta)=\frac12E[(Y-X^\top\theta)^2]$, where $E[Y^2]$ and $E[\|X\|^2]$ are finite. Its quadratic curvature matrix is $E[XX^\top]$. If this matrix has a zero eigenvalue, there is a nonzero direction $v$ with $X^\top v=0$ almost surely. Moving the parameter by any multiple of $v$ then leaves predictions and risk unchanged. Risk can still control prediction error, but it cannot control the full parameter distance in that direction.

Worked Example: Perfect Prediction With an Unidentified Parameter

Let $X=(Z,0)^\top$, where $P(Z=1)=P(Z=-1)=1/2$, and set $Y=3Z$. For $\theta=(\theta_1,\theta_2)$, the prediction is $X^\top\theta=Z\theta_1$, so $$ R(\theta)=\frac12E[(Y-X^\top\theta)^2] =\frac12E[Z^2(3-\theta_1)^2] =\frac12(3-\theta_1)^2. $$

The minimum risk is zero, attained by every $\theta=(3,t)$ with $t\in\mathbb{R}$. In particular, $(3,100)$ has zero excess risk but distance $100$ from the chosen minimizer $(3,0)$. No finite bound on that distance can follow from excess risk alone. In contrast, the prediction error relative to $(3,0)$ is $X^\top((3,100)-(3,0))=0$ almost surely. The issue is not poor prediction; the second parameter is not identified by the distribution of $X$.

For this regression model, if $E[XX^\top]$ is positive definite with smallest eigenvalue $\lambda_{\min}>0$, the risk is $\lambda_{\min}$-strongly convex in $\theta$. If the matrix is only positive semidefinite, the corresponding quadratic form controls error in the directions with positive curvature but not necessarily the Euclidean norm of the full parameter difference. Thus a prediction guarantee and a parameter guarantee answer different questions.

Common Pitfall and Practical Interpretation

Wrong reasoning: “The risk is convex and the estimate has nearly minimal risk, so its parameters must be close to the optimal parameters.” Convexity alone does not justify this conclusion; a convex risk may be completely flat along a direction. Correction: a Euclidean parameter-distance bound requires a positive curvature lower bound in every relevant direction, together with a risk or gradient guarantee to which the bound can be applied.

Even when strong convexity holds, the constant matters. A small $\mu$ yields a weak distance bound for the same excess risk. If curvature is available only on a restricted subspace, a parameter guarantee can be stated on that subspace, but it must not be presented as a guarantee for the entire parameter vector. In applications, it is therefore important to state both the norm and the parameter region on which the curvature assumption holds.

Key takeaway: Strong convexity of population risk supplies the missing link between risk and parameter distance: excess risk at most $\delta$ implies distance at most $\sqrt{2\delta/\mu}$. Without curvature in a direction, risk control alone cannot identify movement in that direction, even when predictions are unchanged.

Check Your Understanding

Use the definitions and bounds above to answer each question.

If a population risk is $4$-strongly convex and a candidate has excess risk at most $0.08$, what upper bound follows for its parameter distance from the minimizer?
Why does the excess-risk proof require a first-order condition at a constrained minimizer?
For a differentiable $3$-strongly convex risk with an interior minimizer, what parameter-distance bound follows if the gradient norm at a candidate is $0.6$?
In the linear-prediction example, which parameter direction is unidentifiable, and why does that not prevent accurate prediction?
What additional curvature property is needed to convert population excess risk into a Euclidean bound on the full parameter vector?