Cross-validation

Remarks

The case $K = n$, with one observation per fold, is leave-one-out cross-validation. To choose a tuning parameter, one computes $\mathrm{CV}$ for each candidate value and keeps a value with the smallest $\mathrm{CV}$. Example: for least squares with $\ell(y, \hat y) = (y - \hat y)^2$, leave-one-out has a closed form. It equals $\frac{1}{n} \sum_i \big((y_i - \hat y_i)/(1 - h_{ii})\big)^2$, where $\hat y_i$ is the full fit and $h_{ii}$ the $i$-th diagonal entry of the hat matrix. Non-example: the training error $\frac{1}{n} \sum_i \ell(y_i, \hat f(x_i))$ with $\hat f$ fitted on all data is not cross-validation. Each $y_i$ is predicted by a function that used it, so the error is biased downwards.