Foundations — Cross-validation pitfalls and nested CV

This page assumes you have seen nothing but the word "data". We build every symbol the parent note (2.6.15) throws at you, one brick at a time. We introduce each symbol only in its own numbered section below — so by the time the parent hits its scary formulas, you will already know every letter in them.

1. What is a dataset? The symbol $D$

The picture: a rectangle of rows. Each row is one example. We call the number of rows $n$ (the count of cards) and the number of input columns $p$ (the number of measurements per card).

Why the topic needs it: everything — splitting, training, scoring — is an operation on this pile. If you don't picture $D$ as physical cards you can move into separate piles, none of the later steps make sense.

2. Splitting into folds — the symbols $K$, fold $k$, and ${\mathcal{D}}_{-k}$

You cannot test a student on the exact questions they practised. So we hide some cards.

Two more symbols fall straight out of the picture:

Why this notation? The parent writes $f_{\lambda ,{\mathcal{D}}_{-k}}$. Read it now in plain English: "the model, using knob-setting $\lambda$, trained on all cards except fold $k$." Every subscript is earned.

This idea is developed fully in 2.6.2-K-fold-cross-validation — treat that as the prerequisite chapter.

3. A model and its knobs — the symbols $f$ and $\lambda$

The picture: a box with dials on the outside ($\lambda$, set by you) and gears on the inside (weights, learned from ${\mathcal{D}}_{-k}$).

Why the topic needs it: the whole disaster in the parent note is about choosing $\lambda$. You cannot talk about choosing a knob before you have a symbol for the knob. Knob-choosing strategies live in 2.6.12-Hyperparameter-tuning-strategies.

4. Measuring wrongness — the symbol $\text{Loss}$

The picture: show the model each card in $\mathcal{D}$, compare its guess to the true back-of-card answer, and average the per-card mistakes.

Why not just "accuracy"? Loss is the general word — it could be mean squared error, mis-classification rate, anything. The topic uses "Loss" so the same formulas cover regression and classification without rewriting them.

5. Averaging the folds — the symbol $\sum$ and the CV score

Now we can read the parent's first formula. It only needs one new symbol.

Read the whole line aloud now, symbol by symbol: "The cross-validation score $\text{CV}(\lambda )$ of knob-setting $\lambda$ is the average, over every fold $k$, of how wrong the model — trained on all-but-$k$, tested on fold $k$ — turns out to be." Nothing here is mysterious anymore.

Why average? One fold could be lucky or unlucky. Averaging over $K$ folds smooths out that luck, giving a steadier estimate. This is the 2.7.3-Bias-variance-tradeoff tension in miniature: more folds = steadier average but more work.

6. Choosing the best knob — the symbols $m$, $\arg \min$ and ${\lambda }^{\ast }$

You compute $\text{CV}(\lambda )$ for several candidate settings and want the winner.

The picture: a bar chart, one bar per candidate $\lambda$ (so $m$ bars), heights = CV scores. $\min$ points at the height of the shortest bar; $\arg \min$ points at the label under it. The little star ${\lambda }^{\ast }$ just means "the chosen, best one".

7. Averages over unseen data — the symbol $\mathbb{E}$

The parent writes $\mathbb{E}[\text{Loss}(f_{{\lambda }^{\ast }},D_{\text{new}})]$. One last symbol.

Why the topic needs it: "generalization" means how you do on new data on average — exactly $\mathbb{E}[\text{Loss on }{D}_{\text{new}}]$. The complaint "$\text{CV}({\lambda }^{\ast })$ is a biased estimate of $\mathbb{E}[\dots ]$" now reads plainly: your reported number does not match the true long-run average — it sits below it.

8. Two loops — inner vs outer

Everything above was one loop over folds. Nested CV wraps a second loop around it.

Now the formal symbols for those two loops:

With these, the parent's nested formula reads plainly: run the inner search on ${\mathcal{D}}_{\text{train}}^{(i)}$ to get ${\lambda }^{\ast (i)}$, score it on the untouched ${\mathcal{D}}_{\text{test}}^{(i)}$, then average those scores over all $K_{\text{outer}}$ rounds.

Prerequisite map

The diagram below feeds top to bottom: raw ideas at the top, the topic's punchline (nested CV) at the bottom. In words, the chain is: $D$ (a pile of cards) → split into folds → "train on ${\mathcal{D}}_{-k}$, test on ${\mathcal{D}}_k$"; separately, a model $f$ with knobs $\lambda$ produces a Loss; folds + Loss combine into the $\text{CV}$ score; taking $\arg \min$ picks ${\lambda }^{\ast }$ but sneaks in negative bias; comparing that against the true $\mathbb{E}$ over new data exposes the bias; and the cure is nested CV's two loops (outer judges, inner chooses).

Equipment checklist

Test yourself — reveal only after answering aloud.