Cross-Validation and Model Selection

Take a dataset where the labels are pure coin flips, so the best possible error is 50%. Tune a classifier's hyperparameters by cross-validation, pick the configuration with the lowest cross-validated error, and report that error. It will come out well below 50%. Varma and Simon ran exactly this experiment on null data with shrunken centroids and support vector machines, and found the cross-validated error of the tuned classifier was a substantially biased estimate of the true error (Varma & Simon, 2006, Bias in Error Estimation When Using Cross-Validation for Model Selection, BMC Bioinformatics 7:91). Nothing in the arithmetic was wrong. The estimate answered a different question from the one being asked.

The estimator

Split \(n\) observations into \(K\) disjoint folds. Let \(\kappa(i)\) be the fold containing observation \(i\), and \(\hat f^{-k}\) the model trained with fold \(k\) held out. The \(K\)-fold cross-validation estimate of prediction error under loss \(L\) is

Each prediction comes from a model that never saw that point. Each model also trained on only \((K-1)/K\) of the data, 80% for \(K = 5\), so if the learning curve is still rising the estimate is pessimistic for a model trained on everything. Leave-one-out (\(K = n\)) nearly removes that bias; whether it pays for it in variance is argued both ways, because its \(n\) training sets overlap almost completely and their errors are highly correlated.

What it actually estimates

The natural reading is that CV estimates the error of the model you will deploy, trained on this dataset. For ordinary least squares, Bates, Hastie and Tibshirani proved that it does not: cross-validation tracks the average error of models trained on other datasets of the same size from the same population, and is nearly uncorrelated with the error of the specific fit in hand (Bates, Hastie & Tibshirani, 2024, Cross-Validation: What Does It Estimate and How Well Does It Do It?, JASA 119(546), arXiv:2104.00673). CV evaluates the procedure, not the artefact.

Its uncertainty is also harder to quantify than it looks. The \(K\) fold scores share training data, so they are positively correlated, and computing a standard error as if they were independent understates it. Bengio and Grandvalet proved that no unbiased estimator of the variance of \(K\)-fold CV exists that is valid under all distributions (Bengio & Grandvalet, 2004, JMLR 5). Bates and colleagues showed the naive intervals can cover far below nominal and proposed nested CV as a variance estimate that restores coverage.

Selection is a second fitting step

Using CV to choose among \(m\) configurations and reporting the winner's score is a maximum over \(m\) noisy estimates, and the maximum of noisy estimates is biased upward even when every individual estimate is unbiased. With many configurations and a small dataset, that bias can be as large as the real differences between algorithms. Cawley and Talbot framed it as over-fitting the model selection criterion itself, arguing that the variance of the criterion matters as much as its bias (Cawley & Talbot, 2010, On Over-fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation, JMLR 11).

The remedy is to separate selection from assessment. Nested CV runs the whole tuning procedure, inner CV included, inside each outer training fold, and scores the chosen configuration on the outer test fold. The cost is multiplicative: 5 outer folds, 5 inner folds and 50 configurations is \(5 \times 5 \times 50 = 1{,}250\) fits, plus 5 refits of the winners, against 250 for plain tuning. A single untouched test set does the same job more cheaply when data are plentiful.

For choosing rather than reporting, the one-standard-error rule picks the simplest model whose CV error is within one standard error of the best, trading a little estimated accuracy for protection against selecting on noise. Given Bengio and Grandvalet's result, that standard error is itself approximate.

When it breaks

Resampling the wrong unit. Rows from the same patient, user or document split across folds let the model memorise the entity. Folds must be formed at the level at which new data will arrive, which is group \(K\)-fold for repeated entities and forward-chaining splits for time, covered in backtesting and temporal validation.

Preprocessing outside the loop. Scaling, imputation, feature selection or target encoding fitted on the full dataset before splitting leaks test-fold information into training. Selecting the 100 most correlated features from 10,000 on all rows and then cross-validating a classifier on them can show strong accuracy on pure noise. Every data-dependent step belongs inside the fold, as discussed under target leakage.

Small data makes every estimate noisy. With 60 samples, a 5-fold CV accuracy has an uncertainty of several points, and different random fold assignments change the ranking of close models. Repeated CV averages over splits and reduces that particular noise, but it cannot create information or remove the correlation between folds.

Stationarity is assumed. CV estimates error on data drawn like the training data. Deployment under covariate or label shift has a different error, and no resampling of the past measures it.