Curvature and Parameter Error in ERM

From Risk Accuracy to Parameter Accuracy

An empirical risk minimizer is often judged by its population excess risk: how much larger its population risk is than the smallest risk available in the model. But risk is not distance. Two parameter values can have very similar risks while being far apart if the risk surface is flat between them. To turn a risk guarantee into a parameter guarantee, we need a condition that says the population risk rises at least quadratically as we move away from its minimizer.

This condition is called quadratic growth. Its constant measures the strength of the curvature relevant to parameter recovery. Once it is available, a bound on excess risk immediately gives a bound on the distance between an ERM estimate and the population-risk minimizer.

Definition: Let $\Theta\subseteq\mathbb{R}^p$, let $R:\Theta\to\mathbb{R}$ be the population risk, and suppose $\theta^*\in\Theta$ minimizes $R$. The risk satisfies quadratic growth at $\theta^*$ with constant $\kappa>0$ if $$ R(\theta)-R(\theta^*)\geq \kappa\|\theta-\theta^*\|_2^2 \quad\text{for every }\theta\in\Theta. $$

The constant $\kappa$ is a lower bound on how quickly risk increases with squared Euclidean distance. In the common convention of $\mu$-strong convexity, the corresponding quadratic term is $(\mu/2)\|\theta-\theta^*\|_2^2$, so $\kappa=\mu/2$. The factor of two matters when converting a risk bound into a distance bound.

The Basic Conversion

The conversion requires no assumptions about how an estimator was obtained. It applies to any parameter value whose excess risk is controlled, including an empirical risk minimizer or an approximate empirical risk minimizer.

Theorem (Excess-risk to parameter-error conversion): Suppose quadratic growth holds at $\theta^*$ with constant $\kappa>0$. For any $\hat{\theta}\in\Theta$, if $$ R(\hat{\theta})-R(\theta^*)\leq r $$ for some $r\geq 0$, then $$ \|\hat{\theta}-\theta^*\|_2\leq \sqrt{\frac{r}{\kappa}}. $$

Proof. Apply the quadratic-growth inequality to $\hat{\theta}$, then use the assumed excess-risk bound:

\kappa\|\hat{\theta}-\theta^*\|_2^2 \leq R(\hat{\theta})-R(\theta^*) \leq r.

Because $\kappa>0$, division by $\kappa$ and taking nonnegative square roots gives the stated result. $\square$

The same argument transfers probability guarantees without changing their probability level. If, for example, an analysis establishes $P\{R(\hat{\theta})-R(\theta^*)\leq r_n\}\geq 1-\delta$, then quadratic growth gives $P\{\|\hat{\theta}-\theta^*\|_2\leq\sqrt{r_n/\kappa}\}\geq 1-\delta$. Likewise, when $\kappa$ is fixed and positive, an excess-risk rate of $O_p(a_n)$ yields a parameter-distance rate of $O_p(\sqrt{a_n})$. This is a square-root conversion, not a claim that the two rates are the same.

Worked Example: A Squared-Error Risk With Known Curvature

Let $X$ take values $-1$ and $1$ with equal probability, and let $Y=2X+\varepsilon$, where $E[\varepsilon\mid X]=0$ and $E[\varepsilon^2]=1$. Consider the scalar parameter $\theta\in\mathbb{R}$ and loss $(Y-\theta X)^2$. Find the population risk, its minimizer, and the parameter bound implied by an excess-risk bound of $0.01$.

Write $Y-\theta X=\varepsilon+(2-\theta)X$. On squaring and taking expectations, the cross term vanishes because $E[\varepsilon X]=E[X E(\varepsilon\mid X)]=0$, and $X^2=1$. Therefore

R(\theta)=E[(Y-\theta X)^2] =E[\varepsilon^2]+(2-\theta)^2E[X^2] =1+(2-\theta)^2.

The risk is minimized at $\theta^*=2$, with $R(\theta^*)=1$. Hence the excess risk is exactly $R(\theta)-R(\theta^*)=(\theta-2)^2$, so quadratic growth holds with $\kappa=1$. If an estimate has excess risk at most $0.01$, the conversion gives

|\hat{\theta}-2|\leq \sqrt{\frac{0.01}{1}}=0.1.

For a direct check, $\theta=2.08$ has excess risk $(0.08)^2=0.0064$, which is below $0.01$, and its parameter error is $0.08$, below the guaranteed bound $0.1$.

When Curvature Guarantees Quadratic Growth

A useful way to verify quadratic growth is to bound the Hessian of the risk from below. The following result is stated on a convex parameter set so the line segment from the minimizer to any other parameter remains inside the region where the curvature condition applies.

Theorem (Hessian lower bound implies quadratic growth): Let $\Theta\subseteq\mathbb{R}^p$ be convex, and let $R$ be twice continuously differentiable on an open set containing $\Theta$. Suppose $\theta^*\in\Theta$ minimizes $R$ over $\Theta$, and for some $\mu>0$, $$ v^\mathsf{T}\nabla^2R(\theta)v\geq \mu\|v\|_2^2 \quad \text{for every }\theta\in\Theta,\ v\in\mathbb{R}^p. $$ Then $R$ has quadratic growth at $\theta^*$ with constant $\mu/2$, and consequently $$ R(\theta)-R(\theta^*)\geq \frac{\mu}{2}\|\theta-\theta^*\|_2^2 \quad\text{for every }\theta\in\Theta. $$

Proof. Fix $\theta\in\Theta$, put $u=\theta-\theta^*$, and define $g(t)=R(\theta^*+tu)$ for $0\leq t\leq1$. Convexity of $\Theta$ ensures that this whole line segment lies in $\Theta$. The chain rule gives

g'(0)=\nabla R(\theta^*)^\mathsf{T}u, \qquad g''(t)=u^\mathsf{T}\nabla^2R(\theta^*+tu)u \geq \mu\|u\|_2^2.

Since $\theta^*$ is a minimizer over the convex set, the one-sided derivative along every feasible segment is nonnegative: $g'(0)\geq0$. Twice applying the fundamental theorem of calculus yields

g(1)-g(0) =g'(0)+\int_0^1(1-t)g''(t)\,dt \geq 0+\mu\|u\|_2^2\int_0^1(1-t)\,dt =\frac{\mu}{2}\|u\|_2^2.

Substituting $g(1)=R(\theta)$, $g(0)=R(\theta^*)$, and $u=\theta-\theta^*$ proves the claim. $\square$

Worked Example: A Strongly Convex Quartic Risk

Consider the scalar risk $R(\theta)=C+0.05(\theta-\log 4)^2+2.18(\theta-\log 4)^4$, where $C$ is any constant. Verify a curvature bound, then use it to bound the distance from $\theta=1.5$ to the minimizer. Use an upper-rounded excess risk so the numerical bound is valid.

Set $d=\theta-\log 4$. Differentiating gives $R'(\theta)=0.1d+8.72d^3$, which is zero at $d=0$. Since $R(\theta)-C=0.05d^2+2.18d^4\geq0$, the minimizer is $\theta^*=\log 4$. The second derivative is

R''(\theta)=0.1+26.16d^2\geq0.1.

Thus the Hessian result applies with $\mu=0.1$, or equivalently quadratic-growth constant $\kappa=0.05$. At $\theta=1.5$, the signed quantity is $d=1.5-\log 4\approx0.1137056389$, so the distance is $|d|\approx0.1137056389$. Its exact excess risk is

r=0.05(1.5-\log 4)^2+2.18(1.5-\log 4)^4 \approx 0.0010108538.

The decimal $0.00101085$ would round this value down and therefore would not be a valid upper bound. Use the conservative upper-rounded value $r=0.00101086$. The conversion then gives

|1.5-\log 4| \leq \sqrt{\frac{0.00101086}{0.05}} =\sqrt{\frac{2(0.00101086)}{0.1}} \approx 0.1422.

The actual distance, about $0.1137$, is below this valid bound. The inequality need not be tight: the global curvature lower bound uses the smallest Hessian value, attained at $d=0$, whereas the Hessian is larger away from the minimizer.

Worked Example: Directional Curvature in Two Dimensions

Let $\theta=(\theta_1,\theta_2)\in\mathbb{R}^2$, let $\theta^*=(1,-1)$, and define $R(\theta)=3+\frac12[2(\theta_1-1)^2+8(\theta_2+1)^2]$. For $\hat{\theta}=(1.1,-1.2)$, calculate the excess risk, the actual distance, and the curvature-based bound.

The Hessian is the diagonal matrix with entries $2$ and $8$, so $v^\mathsf{T}\nabla^2R\,v=2v_1^2+8v_2^2\geq2(v_1^2+v_2^2)$. We may take $\mu=2$, hence $\kappa=1$. The parameter difference is $(0.1,-0.2)$, with squared Euclidean norm $0.1^2+(-0.2)^2=0.05$. Direct substitution gives

R(\hat{\theta})-R(\theta^*) =\frac12\{2(0.1)^2+8(-0.2)^2\} =\frac12(0.02+0.32) =0.17.

The actual distance is $\sqrt{0.05}\approx0.2236$. Applying the conversion to the computed excess risk gives $\|\hat{\theta}-\theta^*\|_2\leq\sqrt{0.17/1}\approx0.4123$, which is valid but looser than the actual distance. The direction of the error matters: this estimate has a substantial component in the more-curved second coordinate, while the global bound uses the smaller curvature $2$ in every direction.

Using Curvature With an ERM Guarantee

Suppose an ERM analysis provides an event on which the estimate’s population excess risk is at most $r_n$. The curvature argument is then a separate, deterministic step: on that same event, the parameter error is at most $\sqrt{r_n/\kappa}$. The ERM analysis supplies the risk guarantee; quadratic growth supplies the parameter interpretation. This separation is useful because the statistical bound and the geometric condition can be checked independently.

Curvature also controls how informative a risk bound is. For fixed excess risk $r$, increasing $\kappa$ decreases the permitted parameter distance. If $\kappa$ is very small, even a small risk gap can allow substantial parameter error. If no positive quadratic-growth constant is available, the conversion theorem gives no finite distance guarantee from excess risk alone.

Common Mistake

Using a rounded-down risk gap as an upper bound. If the conversion assumes excess risk is at most $r$, replacing the actual gap by a decimal rounded down may invalidate that premise. Keep the exact expression, or round the numerical value upward before applying the square root.
Dropping the factor of two. Under $\mu$-strong convexity, the lower bound is $(\mu/2)\|\theta-\theta^*\|_2^2$, not $\mu\|\theta-\theta^*\|_2^2$. Thus the distance bound is $\sqrt{2r/\mu}$.
Assuming a small risk gap always means a close parameter. That conclusion needs a positive quadratic-growth constant. A flat risk surface can have distant parameters with nearly equal risk.

Key takeaway: If population risk grows at least as $\kappa$ times squared distance from its minimizer, every excess-risk bound $r$ implies parameter error at most $\sqrt{r/\kappa}$. A uniform Hessian lower bound of $\mu$ is one sufficient condition, with $\kappa=\mu/2$.

Check Your Understanding

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

If quadratic growth holds with $\kappa=0.2$ and an estimate has excess risk at most $0.008$, what parameter-distance bound follows?
Why does a Hessian lower bound of $\mu$ yield a quadratic-growth constant of $\mu/2$, rather than $\mu$?
Suppose an excess-risk bound holds with probability at least $1-\delta$. What probability guarantee follows for the parameter-distance bound?
In the two-dimensional example, why is the curvature-based distance bound larger than the actual distance?
Why can a decimal rounded down fail to justify an excess-risk conversion, even if the final distance bound appears reasonable?