Cross-validation pitfalls and nested CV: Exercises

Before we start, one picture fixes all our vocabulary. Look at it whenever a symbol feels unfamiliar.

Figure — Cross-validation pitfalls and nested CV

You run 5-fold CV over $α \in {0.01, 0.1, 1, 10}$ , pick the $α$ with the lowest CV error, and report that lowest error as your model's accuracy. Name the single bias this introduces, and state its sign (too high or too low error?).

Recall Solution 1.1

What we did: we took the minimum over 4 CV scores and reported it. The bias: optimistic bias (a.k.a. selection bias). Because we minimise over several noisy scores, we tend to pick the $α$ that got lucky on these particular folds. Sign: the reported error is too low (accuracy too high). The minimum of several random variables sits below their average. So $\hat{E}_{standard} \leq E [Loss]$ .

Exercise 1.2 (L1)

In nested CV, which loop's score do you report as the final performance number: inner or outer?

Recall Solution 1.2

The outer loop's averaged error. The inner loop exists only to pick $λ$ ; its scores are contaminated by the selection above and must never be reported as performance.

Level 2 — Application

Exercise 2.1 (L2)

You have 100 samples and choose 5 outer folds. How many samples are in each outer test set, and how many in each outer training set?

Recall Solution 2.1

With $K_{outer} = 5$ : each test fold holds $100/5 = 20$ samples; the training set is the rest, $100 - 20 = 80$ samples.

Exercise 2.2 (L2)

Continuing: inside each 80-sample outer-training set you run 4 inner folds. How many samples train the model on each inner iteration, and how many are the inner validation set?

Recall Solution 2.2

With $K_{inner} = 4$ on 80 samples: inner validation $= 80/4 = 20$ samples; inner training $= 80 - 20 = 60$ samples.

Exercise 2.3 (L2)

You try 6 values of $α$ , use 5 outer and 4 inner folds. How many model fits does the full nested procedure require (count the inner-tuning fits only, ignore the final refit)?

Recall Solution 2.3

For one outer fold: each $α$ is evaluated by inner CV = $4$ fits, over $6$ values $= 24$ fits. Across $5$ outer folds: $24 \times 5 = 120$ inner fits. What this shows: nested CV cost is $K_{outer} \times K_{inner} \times m$ where $m$ is the number of $λ$ values — here $5 \times 4 \times 6 = 120$ .

Level 3 — Analysis

Exercise 3.1 (L3)

Five outer folds produce these test errors: $0.31, 0.19, 0.25, 0.21, 0.27$ Compute the nested CV error estimate.

Recall Solution 3.1

$\hat{E}_{nested} = \frac{0.31 + 0.19 + 0.25 + 0.21 + 0.27}{5} = \frac{1.23}{5} = 0.246$ Why average, not minimum: each error came from a different, independent tuning run, so averaging estimates the performance of the whole pipeline. Taking the minimum would re-introduce exactly the selection bias we escaped.

Exercise 3.2 (L3)

In Cawley & Talbot's synthetic study (100 samples, 1000 features), standard CV with feature-selection-outside reported 91% accuracy while nested CV reported 73%. Compute the accuracy gap, and explain in one sentence why 1000 features on 100 samples inflates the gap.

Recall Solution 3.2

Gap $= 91% - 73% = 18$ percentage points. Why so large: with 1000 features but only 100 samples, some features correlate with $y$ by pure chance; selecting them on the full data lets the model fit noise that the standard-CV validation folds shared, so its 91% is measuring memorised noise, not generalisation. This is a 2.6.16-Data-leakage instance.

Exercise 3.3 (L3)

Given standard CV error $\hat{E}_{standard} = 0.20$ and nested CV error $\hat{E}_{nested} = 0.246$ , compute the optimism (bias magnitude) and state which number you would put in a paper.

Recall Solution 3.3

Optimism $= \hat{E}_{nested} - \hat{E}_{standard} = 0.246 - 0.20 = 0.046$ . Standard CV understated the error by about $0.046$ (≈ 4.6 loss units too optimistic). Report: the nested number, $0.246$ , because it is the unbiased estimate of the deployed pipeline.

Level 4 — Synthesis

Exercise 4.1 (L4)

Write the correct ordering of steps for a pipeline that (a) normalises features, (b) selects top-10 features by correlation, (c) tunes $α$ , (d) estimates performance. State clearly what must sit inside the outer loop and what may sit outside.

Recall Solution 4.1

Everything data-dependent sits inside the outer loop. For each outer fold $i$ :

Split → outer-train (80 samples) and outer-test (20 samples).
Fit the normaliser's mean/std on outer-train only; apply that same transform to outer-test.
Select top-10 features by correlation using outer-train only.
Run inner CV on outer-train to tune $α$ (the normaliser + selector are re-fit inside each inner fold too, ideally).
Refit the final model on all 80 outer-train samples with the chosen $α$ , evaluate on the untouched 20.

Outside the loop: nothing that looks at data. Only fixed choices (which model family, the grid of $α$ values, $K$ ) live outside. Related: 2.6.16-Data-leakage explains why steps 2 and 3 leak if done on the full dataset.

Exercise 4.2 (L4)

A colleague ran nested CV, found the best $α$ was $0.1$ in fold 1 with inner score $0.20$ , and reported $0.20$ . Diagnose the error and give the correct two-part output: (i) the performance number, (ii) the $α$ to deploy.

Recall Solution 4.2

Diagnosis: they cherry-picked one fold's inner score. Inner scores are optimistic (they are the minimum over the $α$ grid) and come from a single fold — doubly biased. (i) Performance: the outer average across all folds (e.g. $0.246$ ), not $0.20$ . (ii) Deploy $α$ : refit on all data using the $α$ chosen most often across outer folds (or re-run one plain inner CV on the full data purely to pick $α$ ). The deploy- $α$ decision and the performance number are answered by different loops.

Level 5 — Mastery

Exercise 5.1 (L5)

Suppose each of $m$ hyperparameter configurations has a CV score that is an independent draw from a distribution with mean $μ = 0.30$ and standard deviation $σ = 0.05$ . Using the known approximation for the expected minimum of $m$ i.i.d. draws, $E [min] \approx μ - σ 2 ln m$ , compute the expected optimistic bias when $m = 4$ configs are searched. Report the biased score and the bias magnitude.

Recall Solution 5.1

With $m = 4$ : $2 ln 4 = 2 \times 1.38629 = 2.77259 = 1.66511$ . Bias magnitude $= σ 2 ln m = 0.05 \times 1.66511 = 0.08326$ . Expected biased (minimum) score $= 0.30 - 0.08326 = 0.21674$ . Interpretation: searching just 4 configs already drags the reported error ~0.083 below the true mean — that gap is exactly what nested CV recovers.

Exercise 5.2 (L5)

Using the same formula, show the bias grows with $m$ : compute the bias for $m = 4$ and $m = 64$ and give their ratio.

Recall Solution 5.2

$m = 4$ : bias $= 0.05 2 ln 4 = 0.05 \times 1.66511 = 0.08326$ . $m = 64$ : $ln 64 = 4.15888$ , $2 \times 4.15888 = 8.31777 = 2.88405$ , bias $= 0.05 \times 2.88405 = 0.14420$ . Ratio $= 0.14420/0.08326 = 1.732$ (which equals $ln 64/ ln 4 = 3$ ). Lesson: searching $16 \times$ more configs multiplies the optimism by $3 \approx 1.73$ — more tuning ⇒ more inflation ⇒ more need for nested CV.

Exercise 5.3 (L5)

Connect to 2.7.3-Bias-variance-tradeoff: on a small dataset the per-fold CV scores have larger variance $σ$ . Using $bias = σ 2 ln m$ , if halving the dataset doubles $σ$ from $0.05$ to $0.10$ (with $m = 4$ fixed), what happens to the optimistic bias?

Recall Solution 5.3

Bias scales linearly in $σ$ . Doubling $σ$ doubles the bias: new bias $= 0.10 \times 1.66511 = 0.16651$ , exactly $2 \times$ the old $0.08326$ . Lesson: small datasets suffer the worst optimism — which is precisely where people most want to skip nested CV to save data, and precisely where they must not.

Recall Master mnemonic

"Inner picks, Outer scores, and the Outer never peeks." ::: Inner loop chooses $λ$ ; outer loop reports the number; the outer test fold is untouched by any choice.

Exercises — Cross-validation pitfalls and nested CV

Level 1 — Recognition

Exercise 1.1 (L1)