Optimism & Model Complexity

A covariance penalty estimates how much fitting to the observed responses reduces training error. The resulting degrees of freedom measure how strongly predictions respond to those responses.

Fresh Responses at the Same Inputs¶

For this page, condition on the design matrix $X$ . Let $\mu_i=m(X_i)$ and assume

E[Y\mid X]=\mu,\qquad \operatorname{Cov}(Y\mid X)=\sigma^2I_n.

(1)

Let $Y_i^0$ be an independent new response generated at the same input $X_i$ . With $\widehat Y_i=\widehat f_T(X_i)$ , define

\operatorname{Err}_{\mathrm{in}}(T)=\frac1n\sum_i E[(Y_i^0-\widehat Y_i)^2\mid T],\qquad \operatorname{err}_{\mathrm{train}}(T)=\frac1n\sum_i(Y_i-\widehat Y_i)^2.

(2)

“In-sample” here refers to the input locations, not reuse of the observed responses for scoring. This differs from random-input generalization error, which also averages over a new $X_0$ .

The realized optimism is

\operatorname{op}(T)=\operatorname{Err}_{\mathrm{in}}(T)-\operatorname{err}_{\mathrm{train}}(T).

(3)

Averaging over response vectors $Y$ at the fixed design gives the exact squared-error identity

\boxed{\omega(X)=E_{Y\mid X}[\operatorname{op}(T)] =\frac2n\sum_i\operatorname{Cov}(Y_i,\widehat Y_i\mid X).}

(4)

A model that closely follows each response tends to have a positive covariance penalty. This is why training error typically underestimates fresh-response error on average. Nonnegativity is not a theorem for every arbitrary prediction rule, and the identity above is not an exact correction for all random-input prediction problems.

Effective Degrees of Freedom¶

Define

\boxed{\operatorname{df}(A;X)=\frac1{\sigma^2}\sum_i\operatorname{Cov}(Y_i,\widehat Y_i\mid X).}

(7)

Then

\boxed{E[\operatorname{Err}_{\mathrm{in}}\mid X] =E[\operatorname{err}_{\mathrm{train}}\mid X]+\frac{2\sigma^2}{n}\operatorname{df}(A;X).}

(8)

Degrees of freedom measure adaptivity to the observed responses. They need not be an integer or equal a count of displayed coefficients.

Linear Smoothers¶

If $\widehat Y=HY$ and $H$ depends on $X$ and fixed tuning choices but not on $Y$ , then

\operatorname{Cov}(Y_i,\widehat Y_i\mid X) =\sum_jH_{ij}\operatorname{Cov}(Y_i,Y_j\mid X)=\sigma^2H_{ii},

(9)

so

\boxed{\operatorname{df}=\operatorname{tr}(H).}

(10)

Ordinary Least Squares¶

For a full-column-rank $n\times p$ design,

\widehat\beta=(X^\top X)^{-1}X^\top Y,\qquad H=X(X^\top X)^{-1}X^\top.

(11)

The hat matrix is a symmetric projection: $H^\top=H$ , $H^2=H$ . Its eigenvalues are 0 or 1, and

\operatorname{df}=\operatorname{tr}(H)=\operatorname{rank}(H)=p.

(12)

Equivalently, cyclicity of trace gives $\operatorname{tr}[(X^\top X)^{-1}X^\top X]=p$ . With an intercept and $d$ independent predictor columns, $p=d+1$ . If columns are dependent, the projection has df $\operatorname{rank}(X)$ and the displayed inverse must be replaced by an appropriate generalized inverse.

Quantity	OLS value	Role
Fitted-model df	$p$	Complexity of the fitted mean.
Residual df	$n-p$	Denominator in the usual unbiased error-variance estimate.
Expected optimism	$2\sigma^2p/n$	Training-to-fresh-response error correction.

Covariance Penalties & Mallows’ $C_p$ ¶

The general idea is to minimize

\operatorname{err}_{\mathrm{train}}+\frac2n\sum_i\widehat{\operatorname{Cov}}(Y_i,\widehat Y_i\mid X).

(13)

For OLS with fixed candidate models, a prediction-error-scale version of Mallows’ criterion is:

\widehat R_{C_p}=\frac{\operatorname{RSS}}n+\frac{2\widehat\sigma^2p}{n}.

(14)

A common dimensionless convention is

C_p=\frac{\operatorname{RSS}}{\widehat\sigma^2}-n+2p, \qquad \widehat R_{C_p}=\frac{\widehat\sigma^2}{n}(C_p+n).

(15)

These conventions rank candidates identically when they use the same observations and the same variance estimate. A common estimate is the residual mean square from an adequately specified larger model, provided it has residual degrees of freedom. A misspecified larger model can contaminate this estimate.

Worked Comparison: Is the Improved Fit Worth the Complexity?

Suppose $n=100$ and a common $\widehat\sigma^2=4$ .

Model	$p$ , including intercept	RSS	Training MSE	Penalty	Corrected score
A	2	380	3.80	0.16	3.96
B	6	360	3.60	0.48	4.08

B fits better in-sample, but A has the lower estimated fresh-response error. The extra four coefficients must reduce RSS by more than

2\widehat\sigma^2(6-2)=32

(16)

to compensate for the penalty. Here the reduction is only 20.

Akaike Information Criterion¶

Mallows’ criterion

AIC

\widehat R_{C_p}=\frac{\operatorname{RSS}}n+\frac{2\widehat\sigma^2p}{n}.

(17)

A squared-error correction using a common variance estimate across candidate models.

For a likelihood fitted by maximum likelihood, the conventional total-scale criterion is

\boxed{\operatorname{AIC}=-2\ell(\widehat\theta)+2q,}

(19)

where $q$ counts estimated likelihood parameters. An equivalent per-observation scaling is $\operatorname{AIC}/n$ . Smaller values are preferred among comparable likelihoods fitted to the same response data. The usual AIC penalty is an asymptotic likelihood-based correction under regularity conditions.

Connection with $C_p$ ¶

For Gaussian regression with known common variance $\sigma^2$ , $q=p$ and

\frac{\operatorname{AIC}}n =\log(2\pi\sigma^2)+\frac{\operatorname{RSS}}{n\sigma^2}+\frac{2p}{n}.

(20)

Apart from a common additive constant, this is $\widehat R_{C_p}/\sigma^2$ when the variance in that score is $\sigma^2$ . Thus the criteria have the same ranking in this setting.

With unknown variance estimated separately by Gaussian maximum likelihood, $\widehat\sigma^2_{\mathrm{MLE}}=\operatorname{RSS}/n$ and $q=p+1$ , giving

\operatorname{AIC}=n\log(\operatorname{RSS}/n)+2(p+1)+\text{constant}.

(21)

This is not literally the same formula as the common-variance $C_p$ score. Keep the scaling, variance treatment, and parameter count explicit when comparing formulas.

Covariance penalties are convenient when complexity can be calculated. Cross-validation replaces that calculation with repeated held-out fitting and can be applied to much broader learning procedures.

Fresh Responses at the Same Inputs¶

Effective Degrees of Freedom¶

Linear Smoothers¶

Ordinary Least Squares¶

Covariance Penalties & Mallows’ CpC_pCp​¶

Akaike Information Criterion¶

Connection with CpC_pCp​¶

Covariance Penalties & Mallows’ $C_p$ ¶

Connection with $C_p$ ¶