Underpenalization And Excessive Model Complexity

Why a Penalty Can Be Too Small

A richer model can usually fit the observed sample at least as well as a simpler one. Some of that improvement may reflect real structure, but some may be the result of fitting random noise. A complexity penalty is intended to make the selector account for the extra freedom used to obtain a lower empirical risk. If the penalty is too small relative to the size and frequency of noise-driven improvements, the selected model can be unnecessarily complex.

Underpenalization is a comparison, not an absolute property of a numerical penalty. The relevant comparison depends on the loss, sample size, candidate models, and the fluctuations of their empirical risks. The central issue is whether the penalty difference between two models is large enough to counter the empirical advantage that a more complex model can obtain by chance.

Definition: Let $\mathcal M$ be a collection of candidate models. For $m\in\mathcal M$, let $R_m$ denote its risk and $\widehat R_m$ its empirical risk, and let $\operatorname{pen}(m)$ be its penalty. A penalized selector chooses a model $$ \hat m\in\arg\min_{m\in\mathcal M}\left\{\widehat R_m+\operatorname{pen}(m)\right\}. $$ A penalty is underpenalizing for a model comparison when its increase for the more complex model is too small to offset the empirical-risk improvement that model can obtain from random fluctuations. This describes a failure of calibration for the comparison; it does not mean that every selected model must be too complex on every sample.

The Selection Inequality

The basic comparison follows directly from the definition of the selector. It makes precise how a noisy empirical advantage can overcome a penalty. Consider two models, a simpler reference model $m_0$ and a more complex model $m_1$. Define their risk difference by $\Delta=R_{m_1}-R_{m_0}$, and define the empirical fluctuation in the risk difference by $(\widehat R_{m_1}-\widehat R_{m_0})-\Delta$.

Proposition: If a penalized selector chooses $m_1$ over $m_0$, then $$ (\widehat R_{m_1}-\widehat R_{m_0})-\Delta \leq -\Delta-\{\operatorname{pen}(m_1)-\operatorname{pen}(m_0)\}. $$ In particular, if $m_1$ has higher risk, so $\Delta>0$, selection of $m_1$ requires a sufficiently negative empirical fluctuation.

Proof. Choosing $m_1$ rather than $m_0$ means its penalized empirical risk is no larger: $$ \widehat R_{m_1}+\operatorname{pen}(m_1) \leq \widehat R_{m_0}+\operatorname{pen}(m_0). $$ Rearranging gives $$ \widehat R_{m_1}-\widehat R_{m_0} \leq -\{\operatorname{pen}(m_1)-\operatorname{pen}(m_0)\}. $$ Subtract $\Delta=R_{m_1}-R_{m_0}$ from both sides to obtain the stated inequality. If $\Delta>0$, the empirical difference must be smaller than its true-risk difference by at least the true risk gap plus the penalty increase. A small penalty increase leaves more room for a chance empirical advantage to trigger selection. $\square$

This inequality does not say that every fluctuation of that size is likely, or that the richer model is always worse. It identifies the event that must occur for a higher-risk model to win. A well-calibrated penalty aims to make such events sufficiently rare across the collection being searched.

Worked Example: A Rich Model Wins on One Noisy Sample

Suppose $n=4$ responses are $y=(1,-1,1,-1)$, and compare a zero predictor with a model that can fit all four responses exactly. Use mean squared empirical risk and penalize the rich model by $\lambda d/n$, where $d=4$ and $\lambda=0.2$. Assume the true signal is zero.

For the zero predictor, the empirical risk is $$ \widehat R_0=\frac{1^2+(-1)^2+1^2+(-1)^2}{4}=1. $$ For the interpolating model, the residuals are all zero, so its empirical risk is $0$. Its penalized criterion is $$ 0+\frac{0.2(4)}{4}=0.2, $$ which is less than the zero model's criterion $1$. The penalized selector therefore chooses the rich model.

On this realized sample the rich predictor's mean squared error relative to the zero signal is $$ \frac{1^2+(-1)^2+1^2+(-1)^2}{4}=1, $$ whereas the zero predictor's error relative to that signal is $0$. This is a concrete instance of fitting noise: the sample fit improves by $1$, but the improvement is not evidence of a nonzero signal. The example shows what can happen on a sample; a probabilistic calculation is needed to describe how often it happens.

How Much Fitting Can Pure Noise Produce?

A linear projection gives an exact calculation of the fitting gains available under a simple noise model. Let $Y=\varepsilon\in\mathbb R^n$, where $\varepsilon\sim N(0,\sigma^2 I_n)$, so the true mean vector is zero. Let $P$ be a fixed orthogonal projection matrix of rank $d$, and fit the vector $PY$. The quantity $\|PY\|^2/n$ is the squared estimation error per observation relative to the zero signal. The result below distinguishes that error from the residual empirical risk.

Result: For a fixed rank-$d$ orthogonal projection $P$, $$ E\!\left[\frac{\|PY\|^2}{n}\right]=\frac{\sigma^2 d}{n}, \qquad E\!\left[\frac{\|(I_n-P)Y\|^2}{n}\right] =\frac{\sigma^2(n-d)}{n}. $$

Proof. An orthogonal projection is symmetric and idempotent: $P^\mathsf{T}=P$ and $P^2=P$. Thus $\|PY\|^2=Y^\mathsf{T}PY$. For any fixed matrix $A$, expansion by entries gives $E[Y^\mathsf{T}AY]=\sum_{i,j} A_{ij}E[Y_iY_j]=\sigma^2\operatorname{tr}(A)$, because the coordinates of $Y$ have covariance matrix $\sigma^2 I_n$. Applying this identity with $A=P$ yields $E[\|PY\|^2]=\sigma^2\operatorname{tr}(P)=\sigma^2 d$, since the trace of a projection equals its rank. Applying it with $A=I_n-P$, which is a projection of rank $n-d$, gives $E[\|(I_n-P)Y\|^2]=\sigma^2(n-d)$. Dividing both equalities by $n$ proves the result. $\square$

Even when the signal is identically zero, fitting $d$ directions removes an expected $\sigma^2d/n$ of empirical residual risk and creates an expected squared estimation error of $\sigma^2d/n$. A low training error alone therefore cannot tell us whether the fitted component captures signal or noise. The danger grows when the procedure can choose among models after seeing which one happens to fit best.

Worked Example: A Small Penalty Selects a Four-Dimensional Noise Fit

Take $n=8$, $\sigma^2=1$, and compare the zero predictor with a fixed rank-$4$ projection model. Choose the model by minimizing empirical mean squared residual plus $\lambda d/n$, using $\lambda=0.1$ for the rank-$4$ model and zero penalty for the zero predictor. The true mean is zero.

Write $Q=\|PY\|^2$. Orthogonal decomposition gives $\|Y\|^2=\|PY\|^2+\|(I_n-P)Y\|^2$, so the empirical residual-risk reduction from using the rank-$4$ model is $Q/8$. Its penalty is $0.1(4)/8=0.4/8$. The richer model is selected exactly when $$ \frac{Q}{8}>\frac{0.4}{8}, \quad\text{or equivalently}\quad Q>0.4. $$

Under the stated Gaussian model, $Q\sim\chi^2_4$. Its survival probability is $P(Q>t)=e^{-t/2}(1+t/2)$ for $t\geq0$. Therefore the probability of selecting the rich model is $$ P(Q>0.4)=e^{-0.2}(1.2)\approx 0.9825. $$ The penalty is positive, but it is small enough that the rank-$4$ fit is selected on almost every sample.

The selected predictor is zero when $Q\leq0.4$, and its squared estimation error per observation is $Q/8$ when $Q>0.4$. The expected error is consequently $$ \frac{1}{8}E[Q\mathbf{1}\{Q>0.4\}]. $$ The $\chi^2_4$ density is $q e^{-q/2}/4$ for $q>0$. With $a=0.2$, direct integration gives $$ E[Q\mathbf{1}\{Q>0.4\}] =\int_{0.4}^{\infty}\frac{q^2}{4}e^{-q/2}\,dq =2e^{-a}(a^2+2a+2) =4e^{-0.2}(1+0.2+0.02) \approx 3.9954. $$ Thus the expected squared estimation error per observation after selection is approximately $3.9954/8=0.4994$. By comparison, the zero predictor has error zero relative to the true mean. This calculation includes the fact that selection occurs only above the threshold; it is not obtained by simply multiplying the fixed-model risk by the selection probability.

Searching Across Many Candidates

The number of candidate models matters as well as their individual dimensions. If many models are tried, one may achieve an unusually large empirical improvement just by chance. A penalty that distinguishes model sizes but assigns the same charge to every model of a given size may fail to account for this search.

Worked Example: Ten One-Dimensional Models Compete With the Null

Suppose there are $n\geq10$ orthonormal design directions and the response is pure Gaussian noise with variance one. Let $Z_j\sim N(0,1)$ be the observed response coordinate in direction $j$, for $j=1,\ldots,10$; the coordinates are independent. Each candidate model fits one direction, and the null model fits none. Fitting direction $j$ reduces empirical mean squared error by $Z_j^2/n$. Give each one-dimensional model penalty $4/n$, and give the null model penalty zero.

The best one-dimensional candidate beats the null whenever $\max_{1\leq j\leq10}Z_j^2/n>4/n$, or $\max_j|Z_j|>2$. For a standard normal variable, $P(|Z_j|\leq2)=2\Phi(2)-1\approx0.9545$. Independence therefore gives $$ P\!\left(\max_{1\leq j\leq10}|Z_j|>2\right) =1-\{2\Phi(2)-1\}^{10} \approx 1-(0.9545)^{10} \approx 0.372. $$ Thus a penalty that is enough to require a two-standard-deviation improvement from any single candidate still allows a noise-only model to beat the null in about 37 percent of samples when ten candidates are searched. The calculation isolates the search effect: there is no signal in any direction, and the winning direction is chosen because its observed noise coordinate is large.

Interpretation and Common Pitfall

Underpenalization does not mean “the most complex model is always selected.” The examples instead show two mechanisms: a rich model can exploit random variation within its own fitting directions, and searching over more candidates creates more opportunities to find an unusually favorable fluctuation. In applications, the empirical-risk improvement may also reflect real signal. The purpose of penalization is to balance these possibilities, not to forbid complexity.

Common mistake: “The richer model has lower empirical risk, so it must predict better; the penalty is only a minor adjustment.” This reasoning treats the observed improvement as if it were all genuine. The correction is to compare the improvement with the noise and search opportunities that produced it. In the Gaussian projection calculation, the richer model reduces training residual even though the true signal is zero. A penalty too small to account for that fitting opportunity can select complexity that increases estimation error.

A second mistake is to judge a penalty only by its value in isolation. A penalty of $0.1$ or $4$ has no universal interpretation: its adequacy depends on the scale of the loss, sample size, and how many candidate models are compared. The relevant quantity is the penalty difference relative to the empirical-risk fluctuations for the selection problem at hand.

Key takeaway: A model can win because it captures signal or because it fits noise. Underpenalization leaves too much room for the second explanation: noisy empirical improvements can overcome the complexity charge and lead to excess model complexity.

Check Your Understanding

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

For two models with $R_{m_1}>R_{m_0}$, what must happen to the empirical risk difference for the penalized selector to choose $m_1$?
Under pure Gaussian noise, what is the expected squared estimation error per observation of a fixed rank-$d$ projection fit?
In the $n=8$, rank-$4$ example, why is the model-selection event $Q>0.4$, rather than $Q/8>0.1$?
Why does searching over ten one-dimensional candidates increase the chance of beating the null compared with checking only one candidate?
Explain why a lower empirical risk does not, by itself, establish that a richer model has lower prediction error.