Dimension Penalties In Nested Linear Regression

Why Model Dimension Has a Cost

In nested linear regression, a larger predictor space can represent more patterns in the mean response. But least squares also uses the observed noise when estimating its coefficients. Even if the larger space contains no additional signal, its fitted values can follow random fluctuations in the data. A dimension penalty accounts for this fitting cost.

With known noise variance, the penalty has a precise form under a fixed-design, homoskedastic model: adding one fitted dimension contributes $2\sigma^2$ to the residual sum of squares criterion, or $2\sigma^2/n$ when the criterion is mean squared error. The derivation below identifies the assumptions behind this formula and the risk comparison it supports.

Setup and Definitions

Let $Y\in\mathbb R^n$ be the vector of responses at fixed design points. Assume $Y=\mu+\varepsilon$, where $\mu\in\mathbb R^n$ is the vector of true conditional means and the noise satisfies $E[\varepsilon]=0$ and $\operatorname{Cov}(\varepsilon)=\sigma^2 I_n$, with known $\sigma^2>0$. For the risk calculations, a new response vector $Y^*=\mu+\varepsilon^*$ has noise with the same mean and covariance and is independent of $Y$.

Let $V_1\subseteq V_2\subseteq\cdots$ be fixed linear subspaces of $\mathbb R^n$, representing nested linear predictor spaces. Write $P_m$ for the orthogonal projection onto $V_m$, and $d_m=\dim(V_m)$ for its dimension. Least squares in model $m$ gives the fitted vector $\hat\mu_m=P_mY$. The squared norm $\|v\|^2$ is $v^\mathsf{T}v$.

Definition: The approximation error in model $m$ is $A_m=\|(I_n-P_m)\mu\|^2$. The mean-prediction risk is $R_m^{\mathrm{mean}}=E[\|\hat\mu_m-\mu\|^2]$. The fresh-response prediction risk is $R_m^{\mathrm{resp}}=E[\|\hat\mu_m-Y^*\|^2]$. Both risks average over the training noise, and the second also averages over the independent test noise.

The mean vector $\mu$ need not belong to any candidate space: the calculation allows misspecification. The subspaces and their projections must be fixed independently of the observed responses. The expectation identities below need zero-mean noise with covariance $\sigma^2 I_n$, but not Gaussian noise. Gaussianity is useful for distributional and tail calculations, not for these identities.

Deriving the Fixed-Model Penalty

For a fixed model, the residual sum of squares is $\|Y-P_mY\|^2$. Its expectation has two parts: approximation error and noise left in the orthogonal complement of the model. In contrast, prediction risk includes noise accumulated in the fitted directions. The difference between the two is the source of the dimension penalty.

Theorem: Under the fixed-design assumptions above, for each fixed $m$, $$ \begin{aligned} E[\|Y-P_mY\|^2] &= A_m+\sigma^2(n-d_m),\\ R_m^{\mathrm{mean}} &= A_m+\sigma^2d_m,\\ R_m^{\mathrm{resp}} &= A_m+\sigma^2(n+d_m). \end{aligned} $$ Consequently, the penalized training sum of squares $$ \|Y-P_mY\|^2+2\sigma^2d_m $$ is unbiased for $R_m^{\mathrm{resp}}$. Dividing by $n$, the corresponding penalty is $2\sigma^2d_m/n$.

Proof. Since $P_m$ is an orthogonal projection, $I_n-P_m$ is also an orthogonal projection and has rank $n-d_m$. The residual vector is $(I_n-P_m)Y=(I_n-P_m)\mu+(I_n-P_m)\varepsilon$. The first term is fixed, and the second has mean zero, so the cross-product has expectation zero. For any fixed matrix $B$, $E[\varepsilon^\mathsf{T}B\varepsilon]=\operatorname{tr}(B\operatorname{Cov}(\varepsilon))$. Therefore, $$ E[\|Y-P_mY\|^2] =A_m+\sigma^2\operatorname{tr}(I_n-P_m) =A_m+\sigma^2(n-d_m). $$

For mean-prediction risk, write $\hat\mu_m-\mu=-(I_n-P_m)\mu+P_m\varepsilon$. The fixed and mean-zero terms again have zero expected cross-product. Since $\operatorname{tr}(P_m)=d_m$, $$ R_m^{\mathrm{mean}}=A_m+\sigma^2\operatorname{tr}(P_m)=A_m+\sigma^2d_m. $$ Finally, $Y^*=\mu+\varepsilon^*$ and $\varepsilon^*$ is independent of the training noise. Thus the cross-product between $\hat\mu_m-\mu$ and $\varepsilon^*$ has expectation zero, while $E[\|\varepsilon^*\|^2]=n\sigma^2$. It follows that $R_m^{\mathrm{resp}}=R_m^{\mathrm{mean}}+n\sigma^2=A_m+\sigma^2(n+d_m)$. Adding $2\sigma^2d_m$ to the expected training sum of squares gives $A_m+\sigma^2(n+d_m)$, as claimed. $\square$

A second useful form makes the risk comparison across models explicit. Define $$ C_p(m)=\frac{\|Y-P_mY\|^2}{\sigma^2}-n+2d_m. $$ This is the usual Mallows $C_p$ criterion when the variance is known. By the first two identities in the theorem, $$ E[C_p(m)]=\frac{A_m}{\sigma^2}+d_m =\frac{R_m^{\mathrm{mean}}}{\sigma^2}. $$ Thus, for every fixed candidate model, $C_p(m)$ estimates its mean-prediction risk divided by $\sigma^2$. The subtracted $n$ is constant across models and does not affect which model minimizes the criterion.

Worked Calculations

Worked Example: Comparing Three Nested Dimensions

Suppose $n=4$, $\sigma^2=4$, and three nested spaces have dimensions $1,2,3$. In an orthonormal basis aligned with these spaces, let the coordinates of $\mu$ be $(1,2,2,1)$. The approximation errors are therefore $A_1=2^2+2^2+1^2=9$, $A_2=2^2+1^2=5$, and $A_3=1^2=1$.

For model 1, the expected residual sum of squares is $9+4(4-1)=21$. The unnormalized penalty is $2(4)(1)=8$, so the expected penalized score is $21+8=29$. Its fresh-response risk is $9+4(4+1)=29$.

For model 2, the expected residual sum of squares is $5+4(4-2)=13$, and the penalty is $2(4)(2)=16$. The expected penalized score is $13+16=29$, equal to its fresh-response risk $5+4(4+2)=29$.

For model 3, the expected residual sum of squares is $1+4(4-3)=5$, and the penalty is $2(4)(3)=24$. The expected penalized score is $5+24=29$, again equal to the fresh-response risk $1+4(4+3)=29$. Dividing by $n=4$, each expected score and risk is $29/4=7.25$. In this example, every added signal coordinate has squared size $4$, exactly the noise variance, so each increase in approximation accuracy is balanced by an increase in estimation variance.

Worked Example: The Increment for One Added Dimension

Suppose a nested model adds one orthogonal direction to a smaller space. Let the squared coefficient of $\mu$ in that direction be $a^2=6$, let $\sigma^2=4$, and let $n=10$. The approximation error decreases by $6$, while the mean-prediction variance increases by $4$. The mean-prediction risk therefore decreases by $6-4=2$.

The expected training residual sum of squares changes by $-a^2-\sigma^2=-6-4=-10$: the residual loses the signal in that direction and one noise degree of freedom. The normalized penalty increases by $2\sigma^2/n=8/10=0.8$. Thus the expected penalized mean squared error changes by $(-10+8)/10=-0.2$, which agrees with the change in fresh-response risk per observation, $(-6+4)/10=-0.2$.

More generally, adding one orthogonal dimension changes mean-prediction risk by $\sigma^2-a^2$. Its expected penalized score has the same change. The penalty does not automatically favor larger models: it balances the reduction in approximation error against the variance cost.

What the Comparison Guarantees

The fixed-model identity gives a direct comparison of expected scores: for any two fixed candidate models, the difference in their expected penalized scores equals the difference in their fresh-response risks. It therefore identifies the risk-optimal candidate if one compares the expectations of the scores. In practice, the criterion is computed from one data set, and its minimizing model depends on the same noise used to fit the predictors. Those are different comparisons.

Important qualification: Unbiasedness holds model by model when the model is fixed in advance. It does not say that the criterion evaluated at a data-selected model is an unbiased estimate of that selected model’s risk. A risk guarantee for a data-dependent choice requires additional control of the search over models; the dimension penalty alone is not, without such conditions, a universal finite-sample oracle guarantee.

Worked Example: Selection Can Change the Risk Comparison

Let $n=1$, $Y=\varepsilon\sim N(0,1)$, and compare $V_0=\{0\}$ with $V_1=\mathbb R$. Here $\mu=0$, $\sigma^2=1$, and the two fixed-model criteria on the fresh-response scale are $S_0=Y^2$ and $S_1=2$. Their expectations are $1$ and $2$, respectively, matching their fixed-model fresh-response risks.

If we select the model with the smaller criterion, we choose $V_1$ exactly when $Y^2>2$. The selected criterion is $\min(Y^2,2)$, whose expectation is $$ E[\min(Y^2,2)] =E[Y^2\mathbf{1}\{|Y|\leq\sqrt{2}\}]+2P(|Y|>\sqrt{2}) =1-2\sqrt{2}\,\phi(\sqrt{2}) \approx 0.585, $$ where $\phi$ is the standard normal density. The selected fresh-response risk is different: if $V_0$ is selected it is $1$, and if $V_1$ is selected the fitted value is $Y$, giving conditional test risk $1+Y^2$. Hence the selected risk is $$ 1+E[Y^2\mathbf{1}\{|Y|>\sqrt{2}\}] =1+2\bigl(\sqrt{2}\,\phi(\sqrt{2})+1-\Phi(\sqrt{2})\bigr) \approx 1.572. $$ Thus the fixed-model risk identity does not transfer to the selected model simply by substituting the minimizing index.

Assumptions and Common Pitfall

The factor $2\sigma^2d_m$ depends on the model being a fixed linear least-squares projection and on the noise covariance being $\sigma^2 I_n$. If errors are correlated or have unequal variances, the trace contributions from the projection and residual operators need not equal $\sigma^2d_m$ and $\sigma^2(n-d_m)$. If the design or candidate spaces are chosen using the responses, the fixed-projection calculation also no longer applies as stated. The variance must be known for this version of the criterion; replacing it with an estimate requires a separate calibration.

Pitfall: treating the penalty as $ \sigma^2d_m$. That quantity is the increase in mean-prediction variance for $d_m$ fitted directions. But training residual error also decreases as noise directions are fitted. The total training-to-test optimism is $2\sigma^2d_m$, which is why the residual criterion needs twice the variance cost.
Pitfall: assuming fixed-model unbiasedness proves selected-model unbiasedness. The example above shows that minimizing noisy criteria changes their expectations. Model search must be accounted for separately if the goal is a risk guarantee after selection.
Pitfall: penalizing dimension without specifying the scale. For a sum of squares the penalty is $2\sigma^2d_m$; for mean squared error it is $2\sigma^2d_m/n$. Mixing these scales gives an incorrect comparison.

Key takeaway: Under fixed design, isotropic noise with known variance, and a fixed least-squares projection, adding $d_m$ fitted dimensions calls for a training-error penalty of $2\sigma^2d_m$. This yields an exact expected risk comparison for each fixed model; it does not by itself settle the risk of a data-selected model.

Check Your Understanding

Use the fixed-design assumptions and distinguish carefully between a fixed model and a selected model.

For a model of dimension $d_m$, what are the expected residual sum of squares and mean-prediction risk?
Why does the normalized mean-squared-error penalty equal $2\sigma^2d_m/n$, rather than $\sigma^2d_m/n$?
Does the fixed-model risk identity require Gaussian noise? Which noise conditions does its expectation calculation use?
What does Mallows’ $C_p$ estimate in this setup, up to a scale factor?
Why does unbiasedness for every fixed candidate model not imply unbiasedness after minimizing the criterion over the candidates?