Cross-Validation & Model Selection

Table of Contents

1. Learning Objectives
2. Notation
3. Core Intuition
4. The Generalization Problem
5. Hold-Out Estimation
6. K-Fold Cross-Validation
7. Leave-One-Out Cross-Validation
8. Bias-Variance of CV Estimators
9. Nested Cross-Validation
10. Information Criteria
11. Common Pitfalls
12. Summary
13. Exercises

Learning Objectives

1. Formalize the distinction between model assessment (estimating test error) and model selection (choosing among candidates).
2. Derive the bias of hold-out estimation due to reduced training set size.
3. Prove that LOO-CV is approximately unbiased for test error.
4. Analyze the bias-variance tradeoff in choosing $K$ for $K$-fold CV.
5. Derive AIC as an asymptotic estimate of out-of-sample KL divergence.
6. Explain why nested CV is needed when both selecting and evaluating models.

Notation

• $\hat{R}(f)$ — estimated risk (test error estimate)
• $R(f)$ — true (population) risk
• $\mathcal{D}^{(-k)}$ — training data with fold $k$ removed
• $\hat{f}^{(-k)}$ — model trained on $\mathcal{D}^{(-k)}$
• $n_k$ — size of fold $k$
• $p$ — number of parameters in the model
• $\hat{\ell}$ — maximized log-likelihood

Core Intuition

Training error underestimates test error because the model was fit to the same data. We need an honest estimate of how the model will perform on unseen data. Cross-validation simulates this by repeatedly training on subsets and testing on held-out portions, rotating through all data.

The Generalization Problem

We want to estimate:

where $\hat{f}$ is trained on $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^n$.

The training error $\hat{R}_n(\hat{f}) = \frac{1}{n}\sum_i\ell(\hat{f}(x_i), y_i)$ is optimistically biased:

The gap (called "optimism") depends on model complexity.

Hold-Out Estimation

Split data into training ($n_{\text{train}}$) and validation ($n_{\text{val}}$) sets:

Problem: This estimates the test error of a model trained on $n_{\text{train}} < n$ samples, not the full dataset. The estimate is pessimistically biased (overestimates error) because less training data leads to worse models.

K-Fold Cross-Validation

Partition $\{1, \ldots, n\}$ into $K$ disjoint folds $\mathcal{I}_1, \ldots, \mathcal{I}_K$:

Each model $\hat{f}^{(-k)}$ is trained on $n(1 - 1/K)$ samples.

Key properties:

• $K = n$: Leave-one-out (LOO), nearly unbiased but high variance.
• $K = 5$ or $10$: Standard choices, good bias-variance tradeoff.
• $K = 2$: High bias (training on only $n/2$ samples).

Leave-One-Out Cross-Validation

Theorem. LOO-CV is approximately unbiased for the expected test error of a model trained on $n-1$ samples:

For linear models with squared loss, LOO-CV has a closed-form (no refitting needed):

where $\mathbf{H} = \mathbf{X}(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{X}^T$ is the hat matrix.

Bias-Variance of CV Estimators

Bias: $K$-fold CV trains on $n(1-1/K)$ samples. Since test error decreases with training size, CV overestimates the error of the full-$n$ model. Bias is $\mathcal{O}(1/(nK))$ — smaller for larger $K$.

Variance: LOO has high variance because the $n$ training sets overlap heavily (each pair shares $n-2$ samples), producing highly correlated estimates. $K$-fold with smaller $K$ reduces this correlation.

The tradeoff:

• Large $K$ (e.g., LOO): low bias, high variance.
• Small $K$ (e.g., 5): higher bias, lower variance.
• Empirically, $K = 5$ or $K = 10$ works well.

Nested Cross-Validation

When using CV both to select hyperparameters and assess final performance:

1. Outer loop ($K_{\text{out}}$-fold): splits data into assessment train/test.
2. Inner loop ($K_{\text{in}}$-fold): on the outer training set, selects best hyperparameters.
3. Train final model with selected hyperparameters on outer training set; evaluate on outer test.

This avoids the optimistic bias from evaluating on the same data used for selection.

Information Criteria

Akaike Information Criterion (AIC):

where $\hat{\ell}$ is the maximized log-likelihood and $p$ is the number of parameters.

Derivation. AIC estimates $-2\mathbb{E}[\log p(Y_{\text{new}} \mid \hat{\boldsymbol\theta})]$. Under regularity conditions and large $n$, the optimism (difference between training and test log-likelihood) is approximately $p/n$, giving the $2p$ penalty.

Bayesian Information Criterion (BIC):

BIC penalizes complexity more heavily for large $n$. It approximates the log marginal likelihood $\log p(\mathcal{D} \mid \mathcal{M})$ up to a constant, enabling Bayesian model comparison.

When to use:

• AIC: optimal prediction (minimizes KL divergence to true model).
• BIC: model identification (consistent — selects true model as $n \to \infty$).

Common Pitfalls

Pitfall 1. Data leakage: preprocessing (normalization, feature selection) on the full dataset before CV introduces bias. All transformations must occur inside each fold.

Pitfall 2. Using CV error for model selection and then reporting the same CV error as the test error estimate. This is optimistic; use nested CV.

Pitfall 3. Ignoring stratification for classification. Folds should preserve class proportions to reduce variance (stratified $K$-fold).

Summary

• Hold-out is simple but wastes data and overestimates error.
• $K$-fold CV balances bias (from reduced training size) and variance (from fold correlation).
• LOO-CV is nearly unbiased but high-variance; has closed form for linear models.
• Nested CV separates model selection from assessment.
• AIC/BIC provide asymptotic alternatives that avoid refitting; AIC targets prediction, BIC targets model identification.

Exercises

Exercise 1. Derive the LOO formula for linear regression (equation 7) using the Sherman-Morrison-Woodbury identity.

Exercise 2. Show that for a model with $p$ parameters fit by MLE, the training log-likelihood overestimates the test log-likelihood by approximately $p/n$ (motivating AIC).

Exercise 3. Prove that BIC is consistent: as $n \to \infty$, BIC selects the true model (assuming it's among candidates).

Exercise 4. For $K = 2$ fold CV, compute the bias in estimating test error for a linear model with $d$ features.

Exercise 5. Explain why repeated $K$-fold CV (averaging over multiple random partitions) reduces variance without affecting bias.