Cross-Validation

Why we need it (motivation first)

In machine learning, the quantity we actually care about is generalization: how well a trained model predicts on new, unseen examples drawn from the same data-generating process. Formally, if (x, y) is a random example and your model predicts ŷ = f(x), then the ideal target is the expected risk (generalization error)

R(f) = 𝔼[L(y, f(x))]

where L(y, ŷ) is a loss function (0–1 loss for classification, squared loss for regression, log loss for probabilistic models, etc.).

But we do not have access to the true distribution of (x, y). We only have a finite dataset D = {(xᵢ, yᵢ)}ᵢ₌₁ᴺ, and we need a procedure to estimate R(f) using D.

A naive idea is to train on all of D and compute the training loss:

(1/N) ∑ᵢ L(yᵢ, f(xᵢ))

This almost always underestimates the true error, because the model has already “seen” those points during fitting. The more flexible the model (higher variance), the worse this optimism can be. That’s the core reason held-out evaluation exists.

The core definition

Cross-validation is a family of resampling-based methods that estimate generalization error by:

1) splitting the dataset into training and validation parts multiple times,

2) training the model on the training part each time,

3) evaluating on the held-out validation part, and

4) aggregating these validation losses into a single estimate.

The most common form is k-fold cross-validation:

• •Partition the dataset indices {1, …, N} into k disjoint subsets (folds) F₁, …, F_k.
• •For each fold j ∈ {1, …, k}:
• •Train a model on all data except Fⱼ.
• •Validate on Fⱼ.
• •Aggregate the k validation scores.

This gives an estimate of how the training procedure (algorithm + hyperparameters + preprocessing choices) performs on new data.

“Held-out” means “not used for training”

The key rule is no information leakage from validation fold into training. In practice this means:

• •Fit preprocessing (scaling, imputation, feature selection, PCA, etc.) using only the training folds.
• •Then apply that fitted transform to the validation fold.

You can think of each fold as a tiny “future” dataset that the model hasn’t been allowed to learn from.

Where CV sits in the bias–variance story

You already know the bias–variance tradeoff. Cross-validation is a tool to measure the net effect:

• •Complex models may have low training error but high validation error (overfitting / high variance).
• •Simple models may have high training and validation error (underfitting / high bias).

By comparing validation performance across model complexities or hyperparameters, CV helps you pick a good balance.

What CV is and isn’t

CV is not (primarily) a way to “get more data.” The training sets in different folds overlap heavily. What CV does do is reduce dependence on a single arbitrary train/validation split by averaging performance across multiple splits.

A useful mental model:

• •A single holdout split gives one noisy estimate.
• •k-fold CV gives k correlated but different estimates and averages them, typically reducing variance of the estimate.

Notation we’ll use

• •N: dataset size
• •k: number of folds
• •Fⱼ: the index set of fold j
• •D_trainⱼ: all examples not in Fⱼ
• •D_valⱼ: all examples in Fⱼ
• •f̂ⱼ: model trained on D_trainⱼ
• •L(y, ŷ): loss

Per-fold validation loss (average over that fold):

ℓⱼ = (1/|Fⱼ|) ∑_{i ∈ Fⱼ} L(yᵢ, f̂ⱼ(xᵢ))

Cross-validated estimate (simple average):

CV_k = (1/k) ∑_{j=1}^k ℓⱼ

If folds are unequal size, a common alternative is a size-weighted average:

CV_k = (1/N) ∑_{j=1}^k ∑_{i ∈ Fⱼ} L(yᵢ, f̂ⱼ(xᵢ))

Both mean “average validation loss over all held-out predictions,” just aggregated slightly differently.

Quick comparison of common evaluation strategies

The rest of this lesson focuses on k-fold CV and LOOCV, plus practical issues that matter in real ML pipelines.

Why k-fold works as a compromise

You want two conflicting things:

1) Large training set (to reduce bias of the trained model; many algorithms improve with more data).

2) Independent evaluation (to avoid optimistic bias in measured performance).

k-fold CV compromises by training on a fraction (k−1)/k of the data and validating on 1/k, repeated k times so every example gets to be held out once.

As k increases:

• •Training sets get larger (good for bias).
• •Validation sets get smaller (bad for evaluation noise per fold).
• •Total compute increases roughly linearly with k.

This creates a practical sweet spot, often k = 5 or k = 10.

The algorithm, step-by-step

Given dataset D with N examples and a fixed learning procedure A (algorithm + hyperparameters + preprocessing):

1) Partition indices into k folds

Choose a partition {F₁, …, F_k} such that:

• •Fₐ ∩ F_b = ∅ for a ≠ b
• •∪ⱼ Fⱼ = {1, …, N}

Typically |Fⱼ| ≈ N/k.

2) Loop over folds

For each j = 1…k:

• •Training indices Tⱼ = {1, …, N} \ Fⱼ
• •Fit model f̂ⱼ = A(D[Tⱼ])
• •Compute validation loss on fold j:

ℓⱼ = (1/|Fⱼ|) ∑_{i ∈ Fⱼ} L(yᵢ, f̂ⱼ(xᵢ))

3) Aggregate

Report CV_k = (1/k) ∑ⱼ ℓⱼ (or a weighted average).

What exactly is being estimated?

Cross-validation estimates the performance of the training procedure when trained on about (k−1)/k of the available data.

That distinction matters:

• •If you later retrain on all N points, the final model may perform slightly better than CV suggests (because it had more training data).
• •Still, CV is usually a good proxy for comparing choices (hyperparameters, model classes) because those comparisons tend to preserve ordering.

K-fold vs repeated random splits

Another family of methods is repeated random subsampling (“Monte Carlo CV”): repeatedly sample a random train/validation split.

k-fold has a nice property: each sample is used exactly once for validation, which tends to be sample-efficient.

Stratification (especially for classification)

If you have class imbalance, random folding can accidentally create folds with very different class proportions. This can make validation scores unstable or misleading.

Stratified k-fold chooses folds so that the class proportions in each fold approximate the overall distribution.

This is not just a convenience; it protects you from evaluating on an unrepresentative validation fold.

Time series and grouped data: when standard k-fold is wrong

The “i.i.d. examples” assumption (independent and identically distributed) underlies the idea that any subset is a valid proxy for the future. But many datasets violate this:

1) Time series / temporal drift

If data is ordered in time, random folds leak future information into training.

Use a forward-chaining or blocked CV:

• •Train on past
• •Validate on future

2) Grouped observations (e.g., multiple rows per patient/user/device)

If the same person appears in both train and validation folds, leakage occurs through identity-specific patterns.

Use group k-fold:

• •All samples from the same group must appear in the same fold.

These variants preserve the core CV principle: validation must simulate the real deployment scenario.

Choosing k: practical guidance

A common, defensible approach in practice:

• •Start with k = 5 for iteration speed.
• •Move to k = 10 if you need more stable estimates and can afford compute.

From losses to model selection

Suppose you have hyperparameter λ (like regularization strength). For each λ, you can compute:

CV_k(λ) = (1/k) ∑_{j=1}^k ℓⱼ(λ)

Then choose:

λ* = argmin_λ CV_k(λ)

This is the central use of CV in ML: selecting among alternatives using held-out evaluation repeatedly.

Reporting variability: mean and uncertainty

Per-fold losses {ℓⱼ} vary because each fold is a different sample of held-out points.

You’ll often see:

• •mean CV score: μ = (1/k) ∑ⱼ ℓⱼ
• •sample standard deviation:

s = √( (1/(k−1)) ∑_{j=1}^k (ℓⱼ − μ)² )

A rough standard error estimate is s/√k. Be cautious: fold scores are not independent in a strict statistical sense (training sets overlap), but these summaries are still useful for sanity checks and comparisons.

A note on vector notation in models

Many models learn parameter vectors w (and bias b). Even though cross-validation is model-agnostic, it’s helpful to remember that in each fold you learn a different parameter vector:

ŵ₁, ŵ₂, …, ŵ_k

The variability across these learned parameters is one concrete manifestation of variance in the bias–variance tradeoff.

Leave-One-Out Cross-Validation (LOOCV)

LOOCV is k-fold CV with k = N:

• •Each fold contains exactly 1 example.
• •Each training set contains N−1 examples.

Per-fold loss is simply:

ℓᵢ = L(yᵢ, f̂_{−i}(xᵢ))

where f̂_{−i} means “trained on all data except point i.”

LOOCV estimate:

CV_LOO = (1/N) ∑_{i=1}^N L(yᵢ, f̂_{−i}(xᵢ))

Why LOOCV is tempting

• •Training sets are almost the full dataset, so the trained model is close to what you’d train on all data.
• •You use every point for validation exactly once.

Why LOOCV can be a bad idea

1) Compute cost

You train N models. If N is 100,000 this is impossible for many algorithms.

2) Potentially higher variance of the estimate

Each validation fold is a single point. That makes each ℓᵢ extremely noisy.

The average can still be noisy in practice, especially with heavy-tailed losses.

3) Highly correlated training sets

LOOCV training sets differ by only one point. This can make the estimate behave oddly and makes standard error formulas less trustworthy.

For many modern ML tasks, 5- or 10-fold is preferred.

Aggregation: turning k numbers into one estimate

After running CV, you have per-fold losses ℓ₁ … ℓ_k. The aggregation step looks simple (“just average”), but there are subtleties:

1) Averaging losses vs averaging metrics

• •For losses like squared error or log loss, averaging is straightforward.
• •For some metrics (like F1, AUC), you must decide whether to:
• •compute the metric per fold then average, or
• •collect all out-of-fold predictions and compute one global metric.

These can differ because metrics are non-linear.

A robust pattern:

• •For metrics that can be computed on pooled predictions (e.g., AUC), compute out-of-fold predictions for every point, then compute the metric once.
• •For metrics that decompose per example (e.g., log loss), fold-averaging and pooled averaging match when weighted properly.

2) Weighted vs unweighted averaging

If folds have equal size, unweighted mean is fine.

If fold sizes differ, prefer a size-weighted mean:

CV_k = (1/N) ∑_{j=1}^k ∑_{i ∈ Fⱼ} L(yᵢ, f̂ⱼ(xᵢ))

This ensures each example contributes equally, not each fold.

3) Choosing the loss L(y, ŷ)

The loss should match what you care about.

• •Regression: L = (y − ŷ)², |y − ŷ|, Huber
• •Classification: log loss, hinge loss, 0–1 loss

Important: if you use probabilistic models (like logistic regression), log loss evaluates probability calibration, not just accuracy.

Cross-validation as an estimator (and what it estimates)

Let A be the learning algorithm (including your preprocessing and hyperparameter settings). When you run k-fold CV, you produce an estimator of risk:

R̂_CV = CV_k

This estimator has:

• •Bias: because training sets are smaller than N.
• •Variance: because folds differ.

As k increases:

• •Bias tends to decrease (training sets closer to full N).
• •Variance can increase or decrease depending on the setting, but small validation folds often increase noise.

This is one reason k = 5 or 10 is popular: it tends to deliver stable comparisons without extreme compute.

Cross-validation for comparing models: paired structure

A key benefit of CV is that comparisons are often paired: you evaluate multiple models on the same folds.

Suppose model A and model B yield fold losses {ℓⱼᴬ} and {ℓⱼᴮ}. Consider differences dⱼ = ℓⱼᴬ − ℓⱼᴮ. Then:

d̄ = (1/k) ∑_{j=1}^k dⱼ

If d̄ < 0, A is better on average. Because each dⱼ compares A vs B on the same validation fold, some sources of noise cancel out.

Nested cross-validation (conceptual preview)

When you tune hyperparameters using CV, you are “using the validation data to choose.” This can lead to an optimistic bias if you then report the same CV score as final performance.

Nested CV addresses this by adding an outer CV loop for evaluation and an inner CV loop for tuning.

We’ll revisit this in the application section, but keep the principle in mind:

• •CV for selection is not automatically CV for unbiased performance reporting.

A helpful way to think about CV outputs

Cross-validation produces two useful artifacts:

1) A scalar estimate (mean validation loss).

2) A set of out-of-fold predictions (each point predicted by a model that did not train on it).

Those out-of-fold predictions are extremely valuable for:

• •stacking/ensembling
• •error analysis without leakage
• •calibration checks

Even though the node focus is evaluation, this dual viewpoint helps you use CV effectively.

The standard workflow: train/validation/test with CV

In many projects you want:

• •a way to select hyperparameters (needs validation)
• •a way to report final performance (needs a final untouched test set)

A common workflow:

1) Split data into train+validation and test (test untouched).

2) On train+validation, run k-fold CV to choose hyperparameters.

3) Retrain the chosen model on all train+validation.

4) Evaluate once on test.

This keeps the test set as an honest proxy for future data.

When nested CV matters

If you do not have enough data to comfortably hold out a test set, you might use nested CV.

Outer loop (evaluation):

• •Split into k_outer folds.
• •For each outer fold:
• •treat that fold as outer validation/test
• •tune hyperparameters using inner CV on the remaining data
• •train best model on outer-train
• •evaluate on outer-holdout

Then aggregate outer-fold scores.

Why before how:

• •Hyperparameter tuning is a form of learning from validation data.
• •If you tune and evaluate on the same folds, you can overfit the validation procedure.
• •Nested CV reduces that optimism.

CV and maximum likelihood (connection to prerequisites)

You know MLE: choose parameters θ to maximize likelihood on training data.

θ̂ = argmax_θ ∑ᵢ log p(yᵢ | xᵢ, θ)

This is “fit.” Cross-validation answers a different question:

• •If we fit θ̂ on one subset, how good is p(y | x, θ̂) on a held-out subset?

In probabilistic models, a natural CV loss is negative log-likelihood:

L(y, ŷ) = −log p(y | x, θ̂)

Then CV estimates the expected out-of-sample negative log-likelihood, aligning evaluation with MLE’s objective.

Preprocessing and leakage: the pipeline rule

Many evaluation bugs come from doing preprocessing on the full dataset before CV.

Example: standardization

• •Wrong: compute global mean μ and std σ on all N points, then run CV.
• •Right: for each fold j:
• •compute μⱼ, σⱼ on training folds only
• •transform training and validation using μⱼ, σⱼ

Why it matters:

• •Even “unsupervised” transforms can leak information about the validation distribution into training.
• •Leakage can make performance look better than it will be in production.

Practical solution: use an explicit pipeline object (conceptually):

transform = FitTransform(D_trainⱼ)

model = FitModel(transform(D_trainⱼ))

validate on transform(D_valⱼ)

CV for model comparison and selection criteria

Cross-validation is often used to compare:

• •linear vs non-linear models
• •different regularization strengths
• •feature sets
• •training objectives

But you must align the metric with the decision.

Cross-validation in small data vs big data regimes

• •Small data: CV is extremely valuable; single holdout is too noisy.
• •Big data: you might use a single validation set because estimates stabilize with large N, and compute is the bottleneck.

Still, even in big data, CV can be useful for:

• •comparing close contenders
• •diagnosing variance
• •robustly evaluating across slices (e.g., geographic regions)

Practical heuristics that prevent wasted effort

1) Use the same folds across experiments

This creates paired comparisons and reduces noise.

2) Track fold-by-fold results

A mean score can hide instability. If one fold collapses, investigate why (distribution shift, leakage, rare class missing).

3) Do not over-tune

If you try hundreds of hyperparameter configurations, you can overfit the CV estimate itself. Consider:

• •nested CV
• •a final holdout test
• •limiting search space or using Bayesian optimization with care

Interpreting CV outcomes

Suppose model A has mean CV error 0.120 and model B has 0.118. Is B better?

You should look at:

• •magnitude of difference vs variability across folds
• •whether the improvement is consistent (most folds better) or driven by one fold
• •whether the metric matches your product goal

CV gives evidence, not certainty.

Where this node connects next

Cross-validation is foundational for:

• •hyperparameter optimization
• •regularization selection
• •ensembling (stacking uses out-of-fold predictions)
• •model evaluation best practices (nested CV, leakage prevention)

You now have the machinery to evaluate models on held-out data in a principled, repeatable way—and to avoid the most common traps.