# Proof of LOOCV formula

From An Introduction to Statistical Learning by James et al., the leave-one-out cross-validation (LOOCV) estimate is defined by $$\text{CV}_{(n)} = \dfrac{1}{n}\sum\limits_{i=1}^{n}\text{MSE}_i$$ where $\text{MSE}_i = (y_i-\hat{y}_i)^2$.

Without proof, equation (5.2) states that for a least-squares or polynomial regression (whether this applies to regression on just one variable is unknown to me), $$\text{CV}_{(n)} = \dfrac{1}{n}\sum\limits_{i=1}^{n}\left(\dfrac{y_i - \hat{y}_i}{1-h_i}\right)^2$$ where "$\hat{y}_i$ is the $i$th fitted value from the original least squares fit (no idea what this means, by the way, does it mean from using all of the points in the data set?) and $h_i$ is the leverage" which is defined by $$h_i = \dfrac{1}{n}+\dfrac{(x_i - \bar{x})^2}{\sum\limits_{j=1}^{n}(x_j - \bar{x})^2}\text{.}$$

How does one prove this?

My attempt: one could start by noticing that $$\hat{y}_i = \beta_0 + \sum\limits_{i=1}^{k}\beta_k X_k + \text{some polynomial terms of degree }\geq 2$$ but apart from this (and if I recall, that formula for $h_i$ is only true for simple linear regression...), I'm not sure how to proceed from here.

• Either your equations seem to use $i$ for more than one thing or I'm highly confused. Either way additional clarity would be good. – Glen_b Aug 1 '15 at 7:36
• @Glen_b I just learned about LOOCV yesterday, so I might not understand some things correctly. From what I understand, you have a set of data points, say $\mathcal{X} = \{(x_i, y_i): i \in \mathbb{Z}^+\}$. With LOOCV, you have for each fixed (positive integer) $k$ some validation set $\mathcal{V}_k = \{(x_k, y_k)\}$ and a test set $\mathcal{T}_k = \mathcal{X}\setminus \mathcal{V}_k$ used to generate a fitted model for each $k$. So say, for example, we fit our model using simple linear regression with three data points, $\mathcal{X} = \{(0, 1), (1, 2), (2,3)\}$. We would have (to be continued) – Clarinetist Aug 1 '15 at 16:19
• @Glen_b $\mathcal{V}_1 = \{(0, 1)\}$ and $\mathcal{T}_1 = \{(1, 2), (2, 3)\}$. Using the points in $\mathcal{T}_1$, we can find that using a simple linear regression, we get the model $\hat{y}_i = X + 1$. Then we compute the $\text{MSE}$ using $\mathcal{V}_1$ as the validation set and get $y_1 = 1$ (just using the point given) and $\hat{y}_1^{(1)} = 0 + 1 = 1$, giving $\text{MSE}_1 = 0$. Okay, maybe using the superscript wasn't the best idea - I will change this in the original post. – Clarinetist Aug 1 '15 at 16:24
• here are some lecture notes on the derivation pages.iu.edu/~dajmcdon/teaching/2014spring/s682/lectures/… – Xavier Bourret Sicotte Sep 12 '18 at 7:29

I'll show the result for any multiple linear regression, whether the regressors are polynomials of $X_t$ or not. In fact, it shows a little more than what you asked, because it shows that each LOOCV residual is identical to the corresponding leverage-weighted residual from the full regression, not just that you can obtain the LOOCV error as in (5.2) (there could be other ways in which the averages agree, even if not each term in the average is the same).

Let me take the liberty to use slightly adapted notation.

We first show that \begin{align*} \hat\beta-\hat\beta_{(t)}&=\left(\frac{\hat u_t}{1-h_t}\right)(X'X)^{-1}X_t', \quad\quad \textrm{(A)} \end{align*} where $\hat\beta$ is the estimate using all data and $\hat\beta_{(t)}$ the estimate when leaving out $X_{(t)}$, observation $t$. Let $X_t$ be defined as a row vector such that $\hat y_t=X_t\hat\beta$. $\hat u_t$ are the residuals.

The proof uses the following matrix algebraic result.

Let $A$ be a nonsingular matrix, $b$ a vector and $\lambda$ a scalar. If \begin{align*} \lambda&\neq -\frac{1}{b'A^{-1}b} \end{align*}Then \begin{align*} (A+\lambda bb')^{-1}&=A^{-1}-\left(\frac{\lambda}{1+\lambda b'A^{-1}b}\right)A^{-1}bb'A^{-1}\quad\quad \textrm{(B) }\end{align*}

The proof of (B) follows immediately from verifying \begin{align*} \left\{A^{-1}-\left(\frac{\lambda}{1+\lambda b'A^{-1}b}\right)A^{-1}bb'A^{-1}\right\}(A+\lambda bb')=I. \end{align*}

The following result is helpful to prove (A)

Proof of (C): By (B) we have, using $\sum_{t=1}^TX_t'X_t=X'X$, \begin{align*} (X_{(t)}'X_{(t)})^{-1}&=(X'X-X_t'X_t)^{-1}\\ &=(X'X)^{-1}+\frac{(X'X)^{-1}X_t'X_t(X'X)^{-1}}{1-X_t(X'X)^{-1}X_t'}. \end{align*} So we find \begin{align*} (X_{(t)}'X_{(t)})^{-1}X_t'&=(X'X)^{-1}X_t'+(X'X)^{-1}X_t'\left(\frac{X_t(X'X)^{-1}X_t'}{1-X_t(X'X)^{-1}X_t'}\right)\\ &=\left(\frac{1}{1-h_t}\right)(X'X)^{-1}X_t'. \end{align*}
Now, note $h_t=X_t(X'X)^{-1}X_t'$. Multiply through in (A) by $X_t$, add $y_t$ on both sides and rearrange to get, with $\hat u_{(t)}$ the residuals resulting from using $\hat\beta_{(t)}$ ($y_t-X_t\hat\beta_{(t)}$), $$\hat u_{(t)}=\hat u_t+\left(\frac{\hat u_t}{1-h_t}\right)h_t$$ or $$\hat u_{(t)}=\frac{\hat u_t(1-h_t)+\hat u_th_t}{1-h_t}=\frac{\hat u_t}{1-h_t}$$
• The definition for $X_{(t)}$ is missing in your answer. I assume this is a matrix $X$ with row $X_t$ removed. – mpiktas Aug 4 '15 at 8:48
• Also mentioning the fact that $X'X=\sum_{t=1}^T X_t'X_t$ would be helpful too. – mpiktas Aug 4 '15 at 8:50
• When you start the proof of (C) you write $(X_{(t)}'X_{(t)})^{-1}=(X'X-X_t'X_t)^{-1}$. That is a nice trick, but I doubt that casual reader is aware of it. – mpiktas Aug 4 '15 at 12:22