Regularization Bias And Comparator Approximation

Why the Comparator Changes

A regularized estimator is often described as an estimate of the best predictor in a model, with the penalty acting only to control variability. That description can conceal a systematic change: even with unlimited data, a nonzero penalty can move the optimizer away from the best predictor under the target risk. This population displacement is regularization bias. It is distinct from approximation error, which arises because the candidate model cannot represent the target, and from random estimation error, which arises because the empirical objective depends on a sample.

To keep these effects separate, compare three objects: the target risk minimizer, the best unpenalized predictor in a chosen model, and the best penalized predictor in that model. The last is the natural population comparator for a penalized empirical estimator. A risk bound against only the unpenalized comparator may miss the fact that the regularizer has deliberately changed the target of estimation.

Definition: Let $P$ be the distribution of an observation $Z$, let $\ell_f(Z)$ be the loss of predictor $f$, and define its population risk by $R(f)=E[\ell_f(Z)]$. For a candidate model $\mathcal M$, an unpenalized population comparator is $f_{\mathcal M}^*\in\arg\min_{f\in\mathcal M}R(f)$. Given a nonnegative penalty $J$ and tuning value $\lambda\geq 0$, a regularized population comparator is $f_{\mathcal M,\lambda}\in\arg\min_{f\in\mathcal M}\{R(f)+\lambda J(f)\}$. A target risk minimizer $f^*$ minimizes $R$ over a stated target class containing $\mathcal M$.

Assume the minimizers used below exist. When $f^*$ belongs to the target class and $\mathcal M$ is a subset of it, the approximation error $R(f_{\mathcal M}^*)-R(f^*)$ is nonnegative. The regularization bias in risk, $R(f_{\mathcal M,\lambda})-R(f_{\mathcal M}^*)$, is also nonnegative because $f_{\mathcal M}^*$ minimizes risk over $\mathcal M$. The regularized comparator need not have greater penalized objective and need not be closer to $f_{\mathcal M}^*$ in every metric; its defining trade-off concerns $R+\lambda J$.

Identity: For any estimator $\hat f$, the following is an exact algebraic decomposition: $$ R(\hat f)-R(f^*)= \underbrace{R(f_{\mathcal M}^*)-R(f^*)}_{\text{approximation}} +\underbrace{R(f_{\mathcal M,\lambda})-R(f_{\mathcal M}^*)}_{\text{regularization bias}} +\underbrace{R(\hat f)-R(f_{\mathcal M,\lambda})}_{\text{estimation contribution}}. $$ The last term is signed: a particular sample can make $\hat f$ have lower risk than the comparator. The name “estimation contribution” identifies its source, not a guarantee that it is nonnegative.

How Penalization Moves a Population Optimum

Curvature makes the displacement caused by a smooth penalty quantifiable. Write a predictor using a parameter $\theta$ in a convex set $\Theta$, and let $R(\theta)$ denote its population risk. The next result gives a bound on the parameter displacement; smoothness of the risk then converts that displacement into a risk-bias bound.

Theorem: Suppose $\Theta\subseteq\mathbb R^d$ is convex, $R$ is differentiable and $\mu$-strongly convex on $\Theta$ for some $\mu>0$, and $J$ is convex and differentiable on $\Theta$. Suppose $\theta_0$ and $\theta_\lambda$ are interior minimizers of $R$ and $R+\lambda J$, respectively, for $\lambda\geq0$. Then $$ \|\theta_\lambda-\theta_0\| \leq \frac{\lambda}{\mu}\|\nabla J(\theta_0)\|. $$ If, in addition, $\nabla R$ is $L$-Lipschitz on $\Theta$, then $$ 0\leq R(\theta_\lambda)-R(\theta_0) \leq \frac{L\lambda^2}{2\mu^2}\|\nabla J(\theta_0)\|^2. $$

Proof. Interior optimality gives $\nabla R(\theta_0)=0$ and $\nabla R(\theta_\lambda)+\lambda\nabla J(\theta_\lambda)=0$. Let $d=\theta_\lambda-\theta_0$. Strong convexity implies strong monotonicity of the gradient: $\langle\nabla R(\theta_\lambda)-\nabla R(\theta_0),d\rangle\geq\mu\|d\|^2$. Convexity and differentiability of $J$ imply monotonicity of its gradient, so $\langle\nabla J(\theta_\lambda)-\nabla J(\theta_0),d\rangle\geq0$. Substitute the optimality equations and add the nonnegative penalty-gradient term to obtain $$ \mu\|d\|^2 \leq -\lambda\langle\nabla J(\theta_\lambda),d\rangle \leq -\lambda\langle\nabla J(\theta_0),d\rangle \leq \lambda\|\nabla J(\theta_0)\|\,\|d\|. $$ If $d=0$, the displacement bound holds immediately; otherwise divide by $\mu\|d\|$. For the risk bound, $L$-Lipschitz continuity of $\nabla R$ gives the descent inequality $R(\theta_\lambda)\leq R(\theta_0)+\langle\nabla R(\theta_0),d\rangle+(L/2)\|d\|^2$. The gradient term is zero. Also $R(\theta_\lambda)\geq R(\theta_0)$ because $\theta_0$ minimizes $R$. Applying the displacement bound proves the stated upper bound. $\square$

This result is a local sensitivity statement about a specified population objective and penalty. It does not say that every regularizer causes bias of order $\lambda^2$ in risk: the stated smoothness, curvature, interior optimality, and differentiability assumptions matter. In particular, a nonsmooth penalty such as an absolute-value penalty is better understood directly through its optimizer, as in the lasso example below.

Worked Example: Scalar Ridge Shrinkage

Let the parameter be $\theta\in\mathbb R$, let the population risk be $R(\theta)=\tfrac12(\theta-3)^2$, and use the ridge penalty $J(\theta)=\tfrac12\theta^2$ with $\lambda=1$. The unpenalized optimum solves $R'(\theta)=\theta-3=0$, so $\theta_0=3$. The penalized objective has derivative $$ \frac{d}{d\theta}\{R(\theta)+J(\theta)\}=(\theta-3)+\theta=2\theta-3. $$ Thus $\theta_\lambda=3/2$. The induced displacement is $3/2-3=-3/2$, and the excess population risk is $$ R(3/2)-R(3)=\frac12(3/2-3)^2=\frac98. $$ The penalty has moved the population comparator toward zero, even before any sampling variation is considered. The theorem’s bound is exact here: $\mu=L=1$, $\nabla J(3)=3$, and its upper bound is $\tfrac12(1)^2(3)^2=9/2$, which is valid but not tight.

Regularization Bias Is Not Always Smooth Shrinkage

The penalty can change not just the magnitude of a coefficient but whether it is retained at all. The scalar lasso objective illustrates the thresholding effect. Its absolute-value penalty is nondifferentiable at zero, so its minimizer is found using the subgradient condition rather than the differentiable perturbation theorem.

Worked Example: Scalar Lasso Thresholding

Let $R(\theta)=\tfrac12(\theta-0.4)^2$ and $J(\theta)=|\theta|$, with $\lambda=0.5$. Without the penalty, $\theta_0=0.4$. For $\theta>0$, the derivative of the penalized objective is $\theta-0.4+0.5=\theta+0.1$, which has no positive root. For $\theta<0$, it is $\theta-0.4-0.5=\theta-0.9$, which has no negative root. At zero, the subgradient of $|\theta|$ is the interval $[-1,1]$. The optimality condition at zero is $0\in -0.4+0.5[-1,1]$, and this holds because $0.4/0.5=0.8\in[-1,1]$. Convexity therefore makes the unique penalized minimizer $\theta_\lambda=0$. Its regularization bias in risk is $$ R(0)-R(0.4)=\frac12(0-0.4)^2=0.08. $$ The coefficient is eliminated by the penalty, not by sampling noise. A different sample can affect the empirical estimate, but it does not change the population calculation just made.

Separating Approximation, Bias, and Random Estimation

The exact decomposition becomes especially informative when each component can be calculated separately. Consider squared-error prediction in two coordinates. The target is $\beta=(2,1)$, the target predictor is $\beta$, and the candidate model only permits predictors $u=(\theta,0)$. Define the risk by $R(u)=\tfrac12\|u-\beta\|^2$. Let the data yield $Y=(2+\varepsilon_1,1+\varepsilon_2)$, where each error has mean zero and $\operatorname{Var}(\varepsilon_1)=0.09$. Use the empirical criterion $\tfrac12\|u-Y\|^2+\tfrac{\lambda}{2}\theta^2$ with $\lambda=0.5$. Only the first noise coordinate affects the fitted parameter, so no assumption about the variance of $\varepsilon_2$ is needed for the calculation.

Worked Example: Three Contributions in a Noisy Restricted Model

The target predictor has risk $R(\beta)=0$. Within the candidate model, the unpenalized population comparator is $u_{\mathcal M}^*=(2,0)$, because minimizing $\tfrac12\{(\theta-2)^2+1\}$ gives $\theta=2$. Its risk is $R(u_{\mathcal M}^*)=\tfrac12$, so the approximation error is $1/2$; the second coordinate cannot be represented in the model.

The regularized population objective is $\tfrac12\{(\theta-2)^2+1\}+\tfrac{0.5}{2}\theta^2$. Its derivative is $(\theta-2)+0.5\theta$, which vanishes at $\theta=4/3$. Thus $u_{\mathcal M,\lambda}=(4/3,0)$, and $$ R(u_{\mathcal M,\lambda})-R(u_{\mathcal M}^*) =\frac12\left(\frac43-2\right)^2 =\frac29. $$ This is the regularization bias in risk. It is additional to the $1/2$ approximation error.

The empirical penalized minimizer solves $(\theta-Y_1)+0.5\theta=0$, so $\hat\theta=Y_1/1.5=(2+\varepsilon_1)/1.5$. Its mean is $4/3$, matching the regularized population comparator, and its variance is $0.09/(1.5)^2=0.04$. Consequently, $$ E[R((\hat\theta,0))] =\frac12\left\{E[(\hat\theta-2)^2]+1\right\} =\frac12\left\{\left(\frac43-2\right)^2+0.04+1\right\} =\frac{167}{225}. $$ The random estimation contribution in expected risk, relative to the regularized comparator, is $\tfrac12(0.04)=0.02$. Checking the full decomposition, $$ \frac12+\frac29+0.02 =\frac{225}{450}+\frac{100}{450}+\frac{9}{450} =\frac{334}{450} =\frac{167}{225}. $$ The terms have different causes: the restricted model accounts for $1/2$, population shrinkage accounts for $2/9$, and sample variation accounts for $0.02$ in expectation.

Connecting the Comparator to the Empirical Fit

The decomposition is an identity, but a useful analysis must also control the estimation contribution. Let $P_n\ell_f$ denote the empirical average loss based on $n$ observations, and suppose $\hat f$ minimizes $P_n\ell_f+\lambda J(f)$ over $\mathcal M$. For any $g\in\mathcal M$, empirical optimality gives a deterministic comparison:

Basic comparison: If $P\ell_f=R(f)$ is finite for the predictors under comparison, then $$ R(\hat f)-R(g) \leq (P-P_n)(\ell_{\hat f}-\ell_g)+\lambda\{J(g)-J(\hat f)\}. $$

Derivation. Add and subtract the empirical risks: $R(\hat f)-R(g)=(P-P_n)(\ell_{\hat f}-\ell_g)+P_n(\ell_{\hat f}-\ell_g)$. Because $\hat f$ minimizes the empirical penalized objective, $P_n\ell_{\hat f}+\lambda J(\hat f)\leq P_n\ell_g+\lambda J(g)$, hence $P_n(\ell_{\hat f}-\ell_g)\leq\lambda\{J(g)-J(\hat f)\}$. Combining the two displays proves the comparison. $\square$

Taking $g=f_{\mathcal M,\lambda}$ links the empirical fit directly to the regularized population comparator. The deviation term is random, and the penalty difference reflects the optimization trade-off; bounding them requires assumptions suited to the loss, model, and penalty. The comparison does not erase regularization bias: that contribution remains $R(f_{\mathcal M,\lambda})-R(f_{\mathcal M}^*)$ in the exact risk decomposition. Keeping these pieces distinct helps diagnose a bound that is numerically small because of a favorable penalty while still revealing a substantial displacement from the unpenalized target.

Common Mistake

A common mistake is to say: “The penalty only reduces variance, so the relevant comparator is still the best unpenalized predictor in the model; any difference from it must be estimation error.” This is wrong because the minimizer of $R+\lambda J$ can differ from the minimizer of $R$ even when the population risk is known exactly. The correction is to name both comparators and insert the term $R(f_{\mathcal M,\lambda})-R(f_{\mathcal M}^*)$ explicitly. Then approximation, population-induced regularization bias, and the sample-dependent estimation contribution can be assessed separately rather than attributed to one another.

Key takeaway: A regularizer changes the population comparator as well as the empirical fit. To interpret excess risk, separate the candidate model’s approximation gap, the risk cost of population shrinkage, and the random contribution from estimating the regularized comparator.

Check Your Understanding

Use the definitions and calculations above to answer these questions.

Why can $R(f_{\mathcal M,\lambda})-R(f_{\mathcal M}^*)$ be positive even if there is no sampling variation?
In the strong-convexity theorem, what role does $\|\nabla J(\theta_0)\|$ play in controlling displacement?
For the scalar ridge example, calculate the penalized population minimizer when $\lambda=2$, and state its risk difference from the unpenalized minimizer.
In the noisy two-coordinate example, which contribution would remain if the sample noise variance were zero? Explain why.
Why is the estimation contribution in the exact decomposition not necessarily nonnegative for every realized sample?