Cross-Validation

Definition

Cross-validation (CV) is a resampling strategy for estimating the risk (expected prediction error) of an estimator, and hence for model or algorithm selection: the data are repeatedly split into a training part (used to fit) and a validation part (used to score), and the validation errors are averaged. Its appeal is simplicity and near-universality — it applies to almost any estimator and loss (Arlot-Celisse 2010).

Key Ideas

• From validation to cross-validation. The hold-out uses a single train/validation split; CV averages over many splits to reduce the variance of the risk estimate.
• The main variants.
  • Leave-one-out (LOO): train on $n-1$ points, validate on the one left out, over all $n$ choices.
  • Leave-$p$-out (LPO): exhaustive — average over all $\binom{n}{p}$ splits that hold out $p$ points (LOO is $p=1$).
  • $V$-fold CV (VFCV): partition into $V$ folds, each serving once as validation — the standard computational compromise ($V=5,10$).
  • Monte-Carlo / repeated random splits. Related risk estimators include GCV and bootstrap.
• The bias factor $\kappa=n/n_t$. CV estimates the risk of a model trained on $n_t<n$ points, so it is (usually upward) biased for the risk at sample size $n$. Unbiased-risk procedures have $\kappa\approx 1$ ($n_t\approx n$, as in LOO); deliberately biased ones take $\kappa>1$.
• Estimation vs identification. Two distinct goals: estimation/efficiency (pick the model with smallest risk — asymptotic optimality/oracle) versus identification/consistency (recover the true model). They call for different CV tunings — the CV analogue of the AIC-efficient vs BIC-consistent divide.
• Bias–variance of the CV estimate. Variance decreases as the number of splits $B$ grows (training size fixed) and is larger when $n_t$ is close to $n$; for $V$-fold and LPO (where $B$ is tied to $n_t$) the variance is strongly framework-dependent.

How It Works

Choose the split scheme to match the goal and the signal-to-noise ratio (SNR). Arlot & Celisse's guidelines: for estimation with high SNR, minimize bias — take $n_t\approx n$ (LOO-like); for estimation with low SNR, keep a small upward bias ($n_t\approx\kappa n$, $\kappa\in(0,1)$); for identification, use a large bias ($n_t\ll n$), which also promotes model-selection consistency. Then reduce the estimator's variance by increasing the number of splits within the computational budget. Closed-form shortcuts (e.g. the LOO/GCV formulas for linear smoothers) avoid literally refitting.

Why It Matters

• Assumption-light model selection. CV needs no explicit noise model or degrees-of-freedom accounting, so it works where information criteria are hard to derive — the practical default for tuning penalties, bandwidths, and hyperparameters.
• Bridge to information criteria. LOO-CV is asymptotically equivalent to AIC-type unbiased risk estimation; on the Bayesian side, Bayesian LOO-CV is the target that WAIC approximates, and PSIS-LOO (Vehtari-Gelman-Gabry 2017) computes efficiently.
• Framework-specific care. Naive CV breaks under dependence: time series and other dependent data need block/modified schemes because train and validation sets are not independent; the survey also treats large model collections, outlier robustness, and density estimation.

Open Questions

• Precise variance of $V$-fold / LPO estimators is known in only a few frameworks; the minimal-variance scheme is strongly problem-dependent.
• Valid CV under dependence (time series, spatial) — how much data-splitting structure is needed to restore reliable risk estimates.
• Reconciling the estimation-optimal and identification-consistent tunings when the goal is mixed.

Related

• Model Comparison
• Widely Applicable Information Criterion
• Vehtari-Gelman-Gabry (2017) Practical Bayesian Model Evaluation Using LOO-CV and WAIC
• Conformal Prediction
• Arlot-Celisse (2010) A Survey of Cross-Validation Procedures for Model Selection
• Sylvain Arlot
• Alain Celisse
• Generalized Additive Model
• Classification and Regression Trees (CART)