Cross-Validation

Cross-Validation

Cross-validation estimates a model’s out-of-sample prediction error by repeatedly splitting the data into a training set used to fit the model and a validation set used to score it, then averaging the validation errors. The motivation is direct: the in-sample error of a fitted model is biased downward because the model has already seen the training data; only error on data the model has not seen estimates how it will perform on new observations. Cross-validation is the standard tool for choosing tuning parameters (the ridge penalty $\lambda$, the polynomial degree $d$, the depth of a tree), comparing competing models, and reporting an honest estimate of expected predictive accuracy.

The dominant scheme is $k$-fold cross-validation: partition the $n$ observations randomly into $k$ disjoint folds of roughly equal size, then for each fold $i=1,\dots ,k$ train the model on the other $k-1$ folds and evaluate it on fold $i$. The cross-validated error is
${\text{CV}}_{(k)}=\frac{1}{n}{\sum }_{i=1}^{n}L\left(y_i,{\hat{f}}^{(-\kappa (i))}({\mathbf{x}}_i)\right),$
where $\kappa (i)$ is the fold containing observation $i$ and ${\hat{f}}^{(-\kappa (i))}$ is the model fit on data excluding that fold. Common loss functions are squared error for regression and 0-1 loss for classification. Standard choices of $k$ are 5 or 10; both are good compromises between computational cost and statistical reliability.

The two boundary cases of $k$-fold are useful to know. Leave-one-out (LOO, $k=n$) trains on all observations except one, repeats $n$ times, and gives an almost-unbiased but high-variance estimate of test error; for OLS regression it has the closed-form PRESS statistic ${\text{CV}}_{(n)}=(1/n){\sum }_i((y_i-{\hat{y}}_i)/(1-h_{ii}){)}^2$ where $h_{ii}$ is the leverage. Single train-test split ($k=2$, sometimes called the holdout method) is the cheapest scheme but uses only half the data for training and gives a noisy estimate; it is appropriate only when $n$ is large enough that variance is not a concern.

Cross-Validate the Whole Pipeline $\mathbf{y}$, every transformation, every variable selection, every hyperparameter tuning, happens inside the cross-validation loop. Selecting the top $k$ predictors based on correlation with $\mathbf{y}$ on the full dataset and then doing $k$-fold on the reduced set is a textbook way to get hopelessly optimistic CV scores. The validation fold must be invisible to every choice the model makes, including pre-processing choices.

Cross-validation works only if every step that touches

Intuition

The training error of a fitted model is not a reliable estimate of how it will perform on new data: a flexible model can drive training error to zero by memorizing the noise, even when its predictions on new observations are useless. The right quantity to estimate is the expected prediction error on a fresh sample drawn from the same distribution, but computing that directly requires data the model has not seen. Cross-validation manufactures such data by hiding part of the existing dataset from the fitting procedure, scoring the resulting model on the hidden part, and averaging across many such hide-and-score rounds.

The trade-off is that any single train-test split is wasteful (it discards a portion of the data when fitting) and noisy (the validation error depends on which observations happened to land in the test fold). Multiple folds reduce the noise by averaging, and rotating which fold is held out lets every observation contribute to both training and validation across the full procedure. Five-fold and ten-fold are the standard sweet spots: small enough that each training set is most of the data (so the bias is small), large enough that the variance is acceptable, and computationally cheap (only $k$ model fits instead of $n$ for LOO). The conceptual insight is that cross-validation is not a different estimator than holdout, just a smoothed and de-randomized version of it.

Properties

(K-Fold Procedure) Partition into $k$ folds, train on $k-1$, validate on one, rotate, average.

The procedure is mechanical but worth stating cleanly. Randomly assign each of the $n$ observations to one of $k$ folds of approximately equal size $n/k$. For each fold $i$ from 1 to $k$: fit the model using all data except fold $i$, then evaluate the prediction error on fold $i$. After all $k$ rounds, average the per-fold errors:
${\text{CV}}_{(k)}=\frac{1}{k}{\sum }_{i=1}^k{L}_i,L_i=\frac{1}{|F_i|}{\sum }_{j\in F_i}L(y_j,{\hat{f}}^{(-i)}({\mathbf{x}}_j)).$
Most implementations also report the standard error across folds, $\text{SE}(\text{CV})=\text{sd}(L_1,\dots ,L_k)/\sqrt{k}$, which gives a sense of the uncertainty in the CV estimate. For hyperparameter selection it is common to apply the one-standard-error rule: among models whose CV error is within one SE of the minimum, pick the simplest. This produces more parsimonious choices than minimizing CV error directly, with little loss in predictive accuracy.

(Leave-One-Out) The $k=n$ extreme has small bias but large variance.

Setting $k=n$ leaves a single observation out at a time, so each training set has $n-1$ observations: nearly the full dataset. The bias of LOOCV as an estimator of expected test error is therefore very small, but the variance can be large because the $n$ models are fit on nearly identical training sets, and their errors are highly correlated. For squared-error loss in OLS regression there is a beautiful closed form, the PRESS statistic:
${\text{CV}}_{(n)}=\frac{1}{n}{\sum }_{i=1}^n{\left(\frac{y_i-{\hat{y}}_i}{1-h_{ii}}\right)}^2,$
where $h_{ii}$ is the diagonal of the hat matrix $\mathbf{H}=\mathbf{X}({\mathbf{X}}^{\top }\mathbf{X}{)}^{-1}{\mathbf{X}}^{\top }$. So leave-one-out CV for OLS comes for free from a single fit. For other models LOOCV requires $n$ fits, which is expensive when $n$ is large. The high-variance issue is real enough that 5- or 10-fold are usually preferred even when LOO is computationally feasible.

(Train-Test Split) The cheapest scheme; honest if $n$ is large enough.

Splitting the data once into a training set (typically 70–80%) and a held-out test set (20–30%) is the cheapest validation scheme. The model is fit only once, and the test-set error gives a single estimate of out-of-sample performance. The cost is variance: the estimate depends on which observations happened to land in the test set, and with small $n$ this dependence dominates. When $n$ is in the hundreds, prefer $k$-fold; when $n$ is in the millions, a single split is fine, and additionally a train-validation-test three-way split is standard: train models on the training set, choose hyperparameters on the validation set, and report the final error on the test set, which has been touched by no choice the analyst made.

(Bias-Variance of CV) Different $k$ trade bias for variance.

Smaller $k$ (more data held out per fold) means the training sets are smaller and the fitted models are weaker than the model trained on all $n$ observations, so CV error overestimates the true test error: this is bias. Larger $k$ (less data held out per fold) reduces this bias because each training set is closer in size to the full dataset, but the per-fold errors become more correlated, increasing variance. LOOCV ($k=n$) is the low-bias, high-variance extreme; 2-fold is the high-bias, low-variance extreme. The empirical recommendation that 5-fold and 10-fold are the right defaults reflects this trade-off: they are biased only slightly upward (the training set is 80–90% of the full data, plenty for most models) and have manageable variance (averaging over 5–10 partly-correlated folds smooths the noise).

(Stratified K-Fold) Preserve class balance in classification.

For classification problems with imbalanced classes, vanilla random folds can produce a fold with no examples of a rare class, breaking the model fit. Stratified $k$-fold assigns observations to folds while preserving the class proportions in each fold, which is the right default for any classification problem and the explicit default in scikit-learn’s StratifiedKFold. The same principle applies to any structured target: time bins, geographic regions, or grouping variables should be respected in the fold assignment, not crossed by it.

(Repeated K-Fold) Run the procedure several times with different random partitions.

A single $k$-fold partition is one of many possible ways to split $n$ observations into $k$ folds; the resulting CV score depends on the random seed. Repeated $k$-fold runs the whole procedure $R$ times with different random partitions and averages the results, reducing the variance of the estimate at $R$-fold computational cost. For $R\ge 10$ and $k=10$ the standard error is usually small enough that further repetition adds nothing useful. This is most worth doing when comparing closely-tied models or when reporting CV scores with confidence intervals.

(Nested CV for Honest Hyperparameter Tuning) Two loops, not one.

The trap is using the same $k$-fold both to tune $\lambda$ (or any hyperparameter) and to estimate test error: the hyperparameter has been optimized on the held-out folds, so the resulting error estimate is biased downward. The honest fix is nested cross-validation: an outer CV loop estimates test error, and an inner CV loop (run separately on each outer training fold) selects hyperparameters. The outer fold is then completely untouched by the hyperparameter choice. Nested CV with $k_{\text{outer}}=5,k_{\text{inner}}=5$ requires 25 model fits per hyperparameter value tested, which is expensive but is the right method when reporting an unbiased estimate of generalization error matters.

(Cross-Validation Fails on Dependent Data) Random folds break temporal or spatial dependence.

The mechanical splitting in $k$-fold assumes observations are exchangeable. For time series this is false: shuffling observations across time mixes future data into the training set and produces wildly optimistic CV scores. For spatial data, randomly chosen test points are surrounded by training points in space, making prediction artificially easy. The right substitutes are rolling-origin (or expanding-window) CV for time series and spatial block CV for spatial data, both of which respect the dependence structure by ensuring training and validation sets are well-separated in the relevant axis.

Examples

Choosing the ridge penalty

Fit a ridge regression on $n=200$ observations, $p=50$ predictors, and select $\lambda$ from a grid $\{10^{-3},10^{-2},\dots ,10^3\}$ using 10-fold CV.

Procedure $\lambda$: split the 200 observations into 10 folds; for each fold, fit ridge on the other 9 folds and record squared prediction error on the held-out fold; average across folds to get $\text{CV}(\lambda )$. Plot $\text{CV}(\lambda )$ versus ${\log }_{10}\lambda$. The plot is typically U-shaped: large $\lambda$ over-shrinks (high bias), small $\lambda$ overfits (high variance), and the minimum sits at the sweet spot. Pick $\hat{\lambda }$ at the minimum, or apply the one-standard-error rule and pick the largest $\lambda$ within one SE of the minimum (a slightly more conservative choice that often generalizes better). Refit ridge with $\hat{\lambda }$ on all 200 observations to get the final model. Scikit-learn's RidgeCV does the entire procedure in one call.

For each candidate

Comparing polynomial degrees

Fit polynomials of degree $d\in \{1,2,\dots ,15\}$ to a dataset of $n=100$ observations, and select the best degree by 5-fold CV.

What the CV curve shows $d$ because higher-degree polynomials can fit the training data more closely. The CV error has a U shape: low degrees underfit (training and CV both poor), high degrees overfit (training error tiny, CV error large), and a middle degree minimizes CV. The exact minimum depends on the noise level and the smoothness of the true function. The CV curve also has a noticeable variance band (one SE per degree); using the one-standard-error rule selects the smallest degree within one SE of the minimum, giving a more conservative model that often generalizes as well or better than the CV-minimum choice.

The training error decreases monotonically with

Why touching the validation fold is fatal

An analyst with $n=1000$ patients and $p=10,000$ gene measurements first selects the 100 genes most correlated with the outcome, then runs 10-fold CV on a logistic regression of the outcome against those 100 genes, reporting CV accuracy of 95%.

What's wrong full dataset, including observations that later become the validation fold. The selected genes are guaranteed to look predictive in every fold because they were picked using all the data; the CV procedure is no longer evaluating an honest predictive pipeline, only the final logistic regression on a hand-picked set of "good" predictors. Honest CV requires putting the gene-selection step itself inside the CV loop: for each fold, refit the gene selection on the training data only, then refit the logistic regression on those genes, then evaluate on the held-out fold. Done correctly the CV accuracy in this kind of $p\gg n$ setup typically drops to chance, exposing that the selected gene panel was an artifact of multiple comparisons rather than real biological signal.

The gene-selection step used the

See Also

• 1.5. Regularization: cross-validation is the standard tool for choosing the regularization strength $\lambda$.
• 1.2a. Multiple Linear Regression: the leverage values $h_{ii}$ used in the PRESS shortcut for LOO.
• 1.4. Nonlinear Regression: the same CV machinery applies, with refits required at each fold.
• 2.4.5 Time-Series Cross-Validation: the time-series-correct variant that uses rolling-origin splits instead of random folds.
• 3.8.1 Bayesian Linear Regression: the Bayesian alternative to CV-based hyperparameter selection (marginal likelihood / evidence).