LOO & Generalized Cross-Validation - The Statistics Notebook

Leave-one-out evaluates one excluded observation at a time. In least squares, a leverage correction recovers those predictions from a single fit. Generalized cross-validation replaces individual leverages with their average.

Leave-One-Out Cross-Validation¶

With $k=n$ , each fold contains one observation:

\widehat{\operatorname{Err}}_{\mathrm{LOO}} =\frac1n\sum_{i=1}^nL(Y_i,\widehat f^{(-i)}(X_i)).

(1)

A direct implementation fits $n$ models on $n-1$ observations each. For a fixed algorithm under iid sampling, its expected score is $\operatorname{Err}_{n-1}$ . This is often close to $\operatorname{Err}_n$ when the learning curve changes slowly; it is not exactly unbiased for the full-data model’s error.

The OLS Shortcut¶

Let $X$ be a full-rank $n\times p$ fixed design, with rows $x_i^\top$ . Set

H=X(X^\top X)^{-1}X^\top,\qquad \widehat Y=HY,\qquad e_i=Y_i-\widehat Y_i,\qquad h_{ii}=H_{ii}.

(2)

If deleting observation $i$ leaves a full-rank design, then $h_{ii}<1$ and

\boxed{Y_i-\widehat f^{(-i)}(X_i)=\frac{e_i}{1-h_{ii}}.}

(3)

Consequently, for squared loss,

\boxed{\widehat{\operatorname{Err}}_{\mathrm{LOO}} =\frac1n\sum_i\left(\frac{e_i}{1-h_{ii}}\right)^2.}

(4)

The numerator uses ordinary full-fit residuals; the denominator corrects for using the observation in its own fit. $h_{ii}$ is leverage, determined by the design. High leverage can amplify a small residual, but leverage alone is not a complete measure of influence.

Scope of the Formula¶

The identity is exact for the specified OLS refits, and for certain penalized least-squares smoothers with the appropriate fixed penalty convention. Merely writing $\widehat Y=HY$ for an arbitrary full-data linear map is not sufficient: the rule after deletion must have the required relationship to the full fit.

It also does not automatically reproduce a pipeline that repeats feature selection, changes the basis, or retunes a penalty after each deletion. If $h_{ii}=1$ , the displayed OLS shortcut is undefined and the deleted design loses rank.

Worked Leverage Example¶

Use $x=(-1,0,1)$ and $y=(1,0,1)$ , fitting an intercept and slope. The fitted line is constant at $2/3$ :

e=(1/3,-2/3,1/3),\qquad h=(5/6,1/3,5/6).

(10)

Observation	Training residual $e_i$	$1-h_{ii}$	LOO residual
$x=-1$	$1/3$	$1/6$	2
$x=0$	$-2/3$	$2/3$	-1
$x=1$	$1/3$	$1/6$	2

The training MSE is $2/9\approx0.2222$ , but

\widehat{\operatorname{Err}}_{\mathrm{LOO}}=(4+1+4)/3=3.

(11)

Deleting an endpoint leaves a line fitted through the other two points. Predicting the excluded endpoint is extrapolation, which explains the large LOO errors despite modest training residuals.

Generalized Cross-Validation¶

LOO: individual correction

GCV: average correction

\operatorname{LOO}=\frac1n\sum_i\left(\frac{e_i}{1-h_{ii}}\right)^2.

(12)

Uses each observation’s leverage. Exact for the specified OLS deleted fits.

Replace each $h_{ii}$ in the LOO correction by the average leverage

\bar h=\frac1n\sum_i h_{ii}=\frac{\operatorname{tr}(H)}n.

(14)

The GCV score is

\boxed{\operatorname{GCV} =\frac1n\sum_i\left(\frac{e_i}{1-\operatorname{tr}(H)/n}\right)^2 =\frac{\operatorname{RSS}/n}{[1-\operatorname{df}/n]^2}.}

(15)

For OLS, $\operatorname{df}=p$ . Compute the trace without forming the full $n\times n$ hat matrix. The same idea applies to regularized smoothers with noninteger effective degrees of freedom.

LOO	GCV
Corrects each residual using its own leverage.	Uses a common average-leverage correction.
Exact OLS deleted-fit score when the conditions hold.	Approximation to LOO, not literal leave-one-out refitting.
Can be dominated by individual high-leverage cases.	Removes individual leverage denominators, but may hide their effect.

For the three-point example, $\operatorname{df}=2$ and

\operatorname{GCV}=\frac{2/9}{(1-2/3)^2}=2,

(16)

which differs from LOO’s value of 3. If all leverages are equal, the two formulas agree. When df approaches $n$ , the GCV denominator becomes small; at df $=n$ the score is undefined.

A Subtle Point: Estimating the Error of This Fit¶

In correctly specified fixed-design Gaussian OLS, $\widehat\beta$ is independent of $e=(I-H)Y$ . The LOO score with fixed leverages is a function of $e$ , while the fitted coefficients depend on the projected component $HY$ .

This explains an important distinction: an error score need not track how fortunate or unfortunate this particular coefficient estimate was. Estimating average performance across training samples is different from closely predicting the conditional error of one realized fit.