Cross-Validation

Let a dataset be $D = \{(x_i, y_i)\}_{i=1}^N$, drawn i.i.d. from an unknown distribution $P$. A learning algorithm $\mathcal{A}$ maps any training set to a fitted model $\hat{f} = \mathcal{A}(D_{\text{train}})$. We care about the generalization error,

the expected loss on a fresh point not used in training. Training error underestimates this because the model has already seen — and partly memorized — the training points, a gap that widens with model flexibility (this is the Training Error vs Test Error gap).

K-fold cross-validation partitions $D$ into $K$ roughly equal-sized, disjoint subsets (folds) $F_1, \dots, F_K$. For each $k$, train on all data except $F_k$, and evaluate on $F_k$:

where $\hat{f}^{(-k)}$ is the model trained with fold $k$ removed. Every point is used for validation exactly once and for training $K-1$ times. Two special cases matter: Leave-One-Out CV (LOOCV), where $K = N$ (each fold is a single point), and the common practical default $K = 5$ or $K = 10$. Crucially, cross-validation estimates the expected error of the learning procedure — the algorithm plus its hyperparameters, applied to a training set of size roughly $N(K-1)/K$ — not the error of any single fitted model. This distinction matters: the $K$ models $\hat{f}^{(-1)}, \dots, \hat{f}^{(-K)}$ are all slightly different, trained on overlapping but non-identical data, and the final CV score averages over this randomness rather than reporting a property of one specific model.

The procedure has three ingredients: how folds are formed, what is estimated on each fold, and how results are aggregated.

Fold construction. Shuffle the data (unless order matters, as in time series), then split indices into $K$ contiguous groups. Stratified K-fold additionally preserves the class-label proportions within each fold — essential for imbalanced classification, where a naive random split could produce a fold with zero positive examples. Grouped K-fold ensures that all rows sharing a group identifier (e.g., all measurements from the same patient) land in the same fold, preventing information leakage between train and validation. ``` ALGORITHM KFoldCV(D, K, LearningAlgorithm A, Loss L) Input: dataset D of size N, number of folds K, learner A, loss L Output: estimated generalization error, per-fold errors

# 1. Partition into K folds (optionally stratified / grouped) folds <- SplitIntoKFolds(D, K) # list of K index sets, disjoint, union = D errors <- empty list for k in 1..K: D_val <- D[folds[k]] D_train <- D minus D_val f_hat <- A.fit(D_train) # train from scratch on this fold's complement fold_loss <- 0 for (x, y) in D_val: fold_loss <- fold_loss + L(y, f_hat.predict(x)) fold_loss <- fold_loss / |D_val| errors.append(fold_loss) CV_estimate <- mean(errors) CV_stderr <- stddev(errors) / sqrt(K) return CV_estimate, CV_stderr, errors ``` When cross-validation is used for hyperparameter tuning (e.g., choosing regularization strength $\lambda$), the entire K-fold loop is repeated for each candidate value, and the value with the lowest CV estimate is selected: ``` ALGORITHM SelectHyperparameter(D, K, A, Lambdas, L) best_lambda <- None best_score <- +infinity for lambda in Lambdas: A_lambda <- A.withHyperparameter(lambda) score, _, _ <- KFoldCV(D, K, A_lambda, L) if score < best_score: best_score <- score best_lambda <- lambda return best_lambda, best_score ``` A critical subtlety: if this selected `best_score` is reported as the generalization error estimate, it is optimistically biased — the hyperparameter search itself used all the data's validation signal. The honest fix is nested cross-validation: an outer CV loop estimates generalization error, and an inner CV loop (run only on each outer-loop's training portion) selects hyperparameters. ``` ALGORITHM NestedCV(D, K_outer, K_inner, A, Lambdas, L) outer_folds <- SplitIntoKFolds(D, K_outer) outer_scores <- empty list for k in 1..K_outer: D_test <- D[outer_folds[k]] D_devel <- D minus D_test

# inner loop: choose lambda using only D_devel lambda_star, _ <- SelectHyperparameter(D_devel, K_inner, A, Lambdas, L) f_final <- A.withHyperparameter(lambda_star).fit(D_devel) test_loss <- mean( L(y, f_final.predict(x)) for (x,y) in D_test ) outer_scores.append(test_loss) return mean(outer_scores), stddev(outer_scores)/sqrt(K_outer) ```

Time complexity. Let $T(m)$ be the cost of training the learner on $m$ examples, and $P(m)$ the cost of predicting on $m$ points. K-fold CV trains $K$ times, each on $\approx N(K-1)/K$ points, and evaluates on the remaining $N/K$ points:

For learners with roughly linear-in-$m$ training cost, this is $O(K \cdot N)$ overall — a constant-factor overhead of $K$ compared to a single fit. For LOOCV ($K=N$), naively this is $O(N \cdot T(N-1))$, which is prohibitive for expensive models; for a full dataset of size $N=10^5$ and a learner costing $O(m^2)$ to train, LOOCV costs $O(N^3)$, infeasible in practice.

The LOOCV shortcut for linear models. For ordinary least squares and ridge regression, LOOCV admits a closed form avoiding $N$ retrainings. If $H$ is the hat matrix ($\hat{y} = Hy$), the leave-one-out residual satisfies

so the full LOOCV error is computable from a single fit on all $N$ points plus the diagonal of $H$ — $O(N)$ extra work instead of $O(N^2)$ or worse. This identity is a special case of the more general generalized cross-validation (GCV) approximation, which replaces $H_{ii}$ with $\text{tr}(H)/N$ for further speed at slight approximation cost.

Space complexity. $O(N)$ to store the dataset and fold assignments; no asymptotic space overhead beyond one model's footprint at a time if models are trained and discarded sequentially.

Correctness / bias-variance argument. Cross-validation is not an unbiased estimator of the error of the specific model $\hat{f}$ trained on all $N$ points — it estimates the expected error of the procedure trained on $N(K-1)/K$ points. Because learning curves are typically decreasing in training-set size, K-fold CV is pessimistically biased: it slightly overestimates the error of the final model (which will be trained on all $N$ points). This bias shrinks as $K$ grows, vanishing exactly at LOOCV ($K = N$), where each training set has size $N-1$, nearly matching the full-data model. The tradeoff is variance. LOOCV's $N$ training sets overlap in $N-2$ out of $N-1$ points — they are highly correlated with each other — so the $N$ per-point error terms are far from independent, and their average can have high variance across different overall datasets. Moderate $K$ (5 or 10) trades a small increase in bias for a substantial reduction in variance, which is why $K=5,10$ is the standard practical default rather than LOOCV, despite LOOCV's lower bias. Formally, if $\text{Var}(\hat{\text{Err}}_{\text{CV}})$ is decomposed via the covariance structure of overlapping-fold estimators,

the off-diagonal covariance terms grow as folds overlap more in training data (larger $K$), which is exactly the mechanism inflating LOOCV's variance — a fact confirmed empirically across many learners even though a clean general-purpose formula for this variance does not exist in closed form for arbitrary learners.

Consider $N = 10$ points with true relationship $y = 2x + \epsilon$, and we compare two candidate models: Model A (degree-1 polynomial, correctly specified) and Model B (degree-9 polynomial, heavily overfit). We run 5-fold CV ($K=5$, 2 points per fold).

Model A's training error alone would read around $0.90$ (slightly optimistic relative to CV's $0.998$, exactly the pessimistic-bias effect predicted above, since training used only 8 of 10 points per fold). Model B's training error on all 10 points would read essentially zero — a degree-9 polynomial can interpolate 10 points exactly — completely masking its catastrophic generalization failure, which only cross-validation exposes. The large standard error for Model B (3.42) also signals instability: its validation error swings wildly fold to fold (from 3.02 to 22.6), itself a symptom of overfitting, since a model highly sensitive to which 2 points are excluded is a model that has fit noise rather than signal. This is the concrete payoff of the article's key idea: only by rotating the held-out role across all data did the enormous gap between Model A and Model B become visible, and the standard errors reveal how much to trust the reported averages, not just their point values.

Cross-validation emerged from statistics' broader shift toward computationally intensive, resampling-based inference in the 1970s, alongside the bootstrap. Where classical statistics relied on analytic formulas for standard errors, Stone, Geisser, and later Efron argued that repeatedly re-using the same dataset under controlled resampling schemes could substitute for — and often outperform — asymptotic theory, especially for complex, nonlinear models where no clean analytic variance formula exists. Kohavi's 1995 empirical comparison across many datasets and learners became the standard citation for choosing $K=10$ as a practical default, a recommendation that persists in modern machine learning libraries.

Every major machine learning library — scikit-learn's `GridSearchCV`, XGBoost's built-in CV routines, Keras's cross-validation wrappers — implements K-fold and nested CV as the default mechanism for hyperparameter search. In industry, CV underlies A/B-test-adjacent offline model evaluation before a model is ever deployed: recommendation systems tune regularization and embedding dimensions via CV before online experiments confirm the gains. In medicine and genomics, grouped cross-validation (by patient, not by sample) is mandatory to avoid leaking patient-specific signal across folds, a mistake that has invalidated published diagnostic models. Time-series forecasting systems in finance and operations use rolling-origin (walk-forward) cross-validation, a temporal analogue that respects causal ordering. Cross-validation is also the backbone of automated machine learning (AutoML) pipelines, which run thousands of nested CV evaluations to search architecture and hyperparameter spaces, and it feeds directly into the broader theory of Model Selection, where CV-estimated error is compared against information criteria like AIC and BIC.

Ask the tutor: How does nested cross-validation's outer-loop error estimate compare, in bias and cost, to simply reporting the best inner-loop CV score directly?