Cross-validation pitfalls and nested CV

Why standard CV can lie to you

The data leakage trap

WHAT happens: You split data → tune hyperparameters with CV → report the best CV score.

WHY it's wrong: Your hyperparameter search saw the validation folds. The model configuration is now optimized for those specific splits. The CV score is optimistically biased—it's no longer an independent estimate of generalization.

Derivation of the bias: Let's formalize. You have dataset $D$ , split into $K$ folds. For each hyperparameter config $\lambda$ : $\text{CV}(\lambda) = \frac{1}{K}\sum_{k=1}^{K} \text{Loss}(f_{\lambda, \mathcal{D}_{-k}}, \mathcal{D}_k)$ where $f_{\lambda, \mathcal{D}_{-k}}$ is the model trained on all folds except $k$ .

You select: $\lambda^* = \arg\min_{\lambda} \text{CV}(\lambda)$

Now, $\text{CV}(\lambda^*)$ is not an unbiased estimate of $\mathbb{E}[\text{Loss}(f_{\lambda^*}, D_{\text{new}})]$ because:

You searched over $m$ configurations
By chance, some $\lambda$ will perform well on these specific folds
The minimum over $m$ random variables has negative bias (it's always ≤ the mean)

The bias grows with:

More hyperparameters searched ( $m$ ↑)
Smaller dataset (higher variance in CV scores)
More complex models (easier to overfit to validation)

The outer loop never participates in model selection. Each outer fold gets a fresh hyperparameter search.

Deriving the nested CV estimator

Step 1: Outer split For outer fold $i = 1, \ldots, K_{\text{outer}}$ :

Training: $\mathcal{D}_{\text{train}}^{(i)}$ (all data except outer fold $i$ )
Test: $\mathcal{D}_{\text{test}}^{(i)}$ (outer fold $i$ , completely held out)

Step 2: Inner CV on $\mathcal{D}_{\text{train}}^{(i)}$ Within this training set, split into $K_{\text{inner}}$ folds. For each $\lambda$ : $\text{CV}_{\text{inner}}^{(i)}(\lambda) = \frac{1}{K_{\text{inner}}}\sum_{j=1}^{K_{\text{inner}}} \text{Loss}\left(f_{\lambda, \mathcal{D}_{\text{train}}^{(i)} \setminus \text{fold}_j}, \text{fold}_j\right)$

Select: $\lambda^{*(i)} = \arg\min_{\lambda} \text{CV}_{\text{inner}}^{(i)}(\lambda)$

WHY this step? We're mimicking what we'd do in production: tune on available training data. But this tuning is independent for each outer fold.

Step 3: Train final model and evaluate on outer test Train $f_{\lambda^{*(i)}, \mathcal{D}_{\text{train}}^{(i)}}$ using the best hyperparameter from inner CV, then evaluate on $\mathcal{D}_{\text{test}}^{(i)}$ : $\text{Error}^{(i)} = \text{Loss}\left(f_{\lambda^{*(i)}}, \mathcal{D}_{\text{train}}^{(i)}, \mathcal{D}_{\text{test}}^{(i)}\right)$

Step 4: Average across outer folds $\text{Nested CV Error} = \frac{1}{K_{\text{outer}}}\sum_{i=1}^{K_{\text{outer}}} \text{Error}^{(i)}$

WHY this is unbiased: Each $\mathcal{D}_{\text{test}}^{(i)}$ was never seen during hyperparameter tuning. The outer loop estimates performance of the entire pipeline (including hyperparameter search).

Nested CV (unbiased): $\hat{E}_{\text{nested}} = \frac{1}{K_{\text{outer}}}\sum_{i=1}^{K_{\text{outer}}} \left[ \text{Loss}\left(f_{\lambda^{*(i)}, \mathcal{D}_{\text{train}}^{(i)}}, \mathcal{D}_{\text{test}}^{(i)}\right) \right]$ where $\lambda^{*(i)} = \arg\min_{\lambda} \text{CV}_{\text{inner}}^{(i)}(\lambda)$

Outer test sets never touched by hyperparameter search
Averages performance after each independent tuning

Standard CV (5-fold):

For each α:
  - Compute5-fold CV error on all100 samples
Best α = 1.0, CV error = 0.23
Report: "Our model achieves 0.23 error"

WHY wrong: The choice $\alpha=1.0$ was made because it performed best on these 5 folds. By chance, maybe $\alpha=10$ would generalize better, but happened to do poorly on these specific splits.

Nested CV (5 outer, 5 inner):

Outer fold 1 (20 samples held out):
  - Inner 5-fold CV on remaining 80 samples
  - Best α = 0.1, train on 80, test on 20 → error = 0.31
Outer fold 2:
  - Inner CV finds best α = 1.0, error = 0.19
...
Outer fold 5:
  - Best α = 1.0, error = 0.27
  
Average = (0.31 + 0.19 + 0.25 + 0.21 + 0.27)/5 = 0.246
Report: "Our model + tuning procedure achieves ~0.25 error"

WHY this step? Each outer fold's test set was never seen during the inner hyperparameter search for that fold. The average 0.246 is an honest estimate.

Worked example Example 2: Feature selection inside vs outside CV

Biased approach:

1. Select top 10 features by correlation with y (using all data)
2. 10-fold CV on those 10 features
3. Report CV accuracy = 92%

WHY wrong: Feature selection looked at the full dataset, including validation folds. You leaked information.

Derivation of the bias: When you select features on all $n$ samples, then do CV, the features were chosen to maximize correlation with $y$ in those validation samples too.

Let $S(D)$ be your feature selection function. The biased estimator is: $\hat{E}_{\text{biased}} = \text{CV}(f_{S(D)}, D)$

But we want to estimate performance of the pipeline $S \circ f$ on new data: $E_{\text{true}} = \mathbb{E}_{D_{\text{train}}, D_{\text{test}}}[\text{Loss}(f_{S(D_{\text{train}})}, D_{\text{test}})]$

The biased estimator uses $S(D)$ which saw $D_{\text{test}}$ , so $\hat{E}_{\text{biased}} < E_{\text{true}}$ .

Correct nested approach:

Outer fold i:
  - On training 90%, select top 10 features
  - Inner CV to tune model on those features
  - Evaluate on test 10% (which wasn't used for feature selection)

Method	Reported Accuracy
Standard CV (feature selection outside)	91%
Nested CV (feature selection inside)	73%

WHY the huge gap? With 1000 features and 100 samples, many features by chance correlate with $y$ in these specific samples. Standard CV selected features that fit the noise, then validated on the same data those features were chosen for.

Why it feels right: You held out data! You didn't train on it!

Steel-man: You're correct that you didn't train on it. The mistake is subtle—you didn't train on the validation folds, but you made decisions based on them (which hyperparameters to use, which features to keep, when to stop searching). Every decision informed by validation performance makes that validation set less independent.

The fix: Nested CV or a true held-out test set that's never used for any decision-making.

Common mistake Common Pitfall 2: Doing nested CV, then reporting inner CV score

Wrong approach:

Nested CV with outer folds...
"The best hyperparameter was α=0.1 with inner CV score0.20"
Report: 0.20 as final performance

Why it feels right: That's the best score from your tuning, and nested CV found it properly.

Steel-man: You ran nested CV correctly, but then cherry-picked the inner score from one fold. The inner CV score is optimistic for that fold's hyperparameter search.

The fix: Report the outer CV average. The inner scores are for tuning only. If you want to know what hyperparameter to use for production, retrain on all data with the most commonly selected inner $\lambda^*$ , but your performance estimate is the outer average.

Common mistake Common Pitfall 3: Preprocessing outside CV

Wrong:

1. Normalize features using mean/std of entire dataset
2. Run nested CV

Why wrong: Normalization computed statistics from test folds. Data leakage.

Derivation: If $\mu$ and $\sigma$ are computed from all $n$ samples, then for test sample $x_{\text{test}}$ in fold $k$ : $x_{\text{test}}^{\text{normalized}} = \frac{x_{\text{test}} - \mu}{\sigma}$ where $\mu = \frac{1}{n}\sum_{i=1}^{n} x_i$ includes $x_{\text{test}}$ itself. You've used test information to transform the test data.

Correct: Preprocessing must be inside both loops:

For each outer fold:
  For each inner fold:
    - Compute μ, σ on inner training set only
    - Apply to inner validation set
  - Compute μ, σ on outer training set
  - Apply to outer test set

Recall Explain to a 12-year-old

Imagine you're practicing for a spelling bee. You get a list of 100 words to study. You practice by testing yourself: cover up the answer, try to spell it, check if you're right. After a few hours, you find you can spell 90 out of 100 words correctly.

But here's the trick: did you actually learn to spell, or did you just memorize those specific100 words?

To find out, you'd need a fresh list of words you've never seen before. That's what a real test set is.

Now, nested cross-validation is like this: Imagine you don't just practice once—you do five practice sessions, each with a different 80-word subset. For each session, you try different study techniques (flashcards, writing them out, etc.) and pick the best one for that session. Then you test yourself on the 20 words you didn't study in that session. You repeat this five times with different 20-word test groups, and average your scores.

Why? Because each time, those 20 test words were never part of your "which study technique should I use?" decision. You get an honest measure of how well your learning method works, not just how well you memorized.

Picture a three-layer tower:

Top (Test): Pure evaluation floor, locked door, no one goes there until end
Middle (Tune): Workshop floor where you try different tools and see what works
Bottom (Train): Assembly line where models are built with chosen tools

Only the middle floor talks to the top through a one-way mirror—it can't change the test data, just report results.

When to use nested CV

Use nested CV when:

You're tuning hyperparameters (any model selection based on data)
Your dataset is small/medium (<10,000 samples typically)
You need an unbiased performance estimate
You're comparing different model families or pipelines
You're doing feature selection, preprocessing tuning, or any data-driven decision

Skip nested CV when:

You have a massive dataset and can afford true held-out test set (20%+)
You're not doing hyperparameter search (just training one fixed model)
Computational cost is prohibitive and you accept biased estimates (but document this!)

Computational cost: Nested CV is expensive. If outer $K_o = 5$ , inner $K_i = 5$ , and you search $m = 100$ hyperparameters: $\text{Total fits} = K_o \times K_i \times m = 5 \times 5 \times 100 = 2500 \text{ model fits}$

Alternative: Use a single train/validation/test split if you have enough data (e.g., 60/20/20). Tune on validation, report on test. Simpler, but requires larger $n$ .

Connections to other concepts

2.6.1-Train-test-split-and-holdout-method: Nested CV is the principled extension when you need hyperparameter tuning
2.6.2-K-fold-cross-validation: Inner and outer loops both use k-fold
2.6.12-Hyperparameter-tuning-strategies: Grid/random search must be inside inner CV loop
2.6.16-Data-leakage: Nested CV prevents leakage during model selection
2.7.3-Bias-variance-tradeoff: Standard CV has optimistic bias; nested CV reduces it
3.4.5-Early-stopping: If using validation-based early stopping, it must be inner loop

Key takeaways

Standard CV with hyperparameter tuning gives biased (optimistic) estimates
Nested CV separates tuning (inner) from evaluation (outer) to remove bias
Report the outer CV average; inner CV is for selection only
Preprocessing, feature selection, and all data-dependent choices must be inside CV
Cost: $K_{\text{outer}} \times K_{\text{inner}} \times m$ fits, but gives honest estimates

#flashcards/ai-ml

What is the fundamental problem with reporting CV score after hyperparameter tuning? :: The CV score is optimistically biased because hyperparameters were selected to minimize that score on those specific folds—the validation data participated in model selection.

What are the two loops in nested CV and their purposes?

Outer loop: provides independent test sets for unbiased performance estimation. Inner loop: performs hyperparameter tuning on the training portion of each outer fold.

Why is nested CV's estimate unbiased?

Each outer fold's test set was never seen during hyperparameter selection for that fold. The outer average estimates performance of the entire pipeline (tuning + training) on new data.

If you normalize features using mean/std from the full dataset before CV, what's wrong?

Data leakage: normalization parameters computed from test folds, so test data influenced its own preprocessing. Must compute normalization inside each CV fold.

Standard CV with hyperparameter search has what kind of bias?

Negative (optimistic) bias—the minimum over multiple hyperparameter trials is always≤ the true expected error due to selection bias.

In nested CV, which score do you report as your model's performance?

The average error across outer folds. Inner CV scores are for hyperparameter selection only and are optimistically biased.

What's the computational cost of nested CV with

K_o

outer,

K_i

inner folds, and

m

hyperparameters?

K_o \times K_i \times m

model fits (e.g., 5 × 100 = 2500 fits).

When can you skip nested CV?

When you have enough data for a true held-out test set (never used for any decisions), or when you're not doing hyperparameter search.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Nested cross-validation ek bahut important concept hai jab ap machine learning models ki sachi performance janna chahte ho. Socho ki aap ek model train kar rahe ho aur hyperparameters (jaise learning rate, regularization strength) tune kar rahe ho. Agar aap sirf simple cross-validation use karke best hyperparameters choose karte ho, phir wahi CV score report kar dete ho, toh yeh ek problem hai—aapka score optimistically biased hoga, matlab actual performance se zyada acha dikhega.

Kyun? Kyunki aapne jo hyperparameters choose kiye, woh specifically in validation folds ke liye best the. Aapne directly toh nahi train kiya un folds pe, lekin apne decisions unhe dekhke liye. Yeh thoda sa cheating jaisa hai—jaise exam dene se pehle questions dekh liye, phir practice score ko real score bola.

Nested CV isko solve karta hai do loops se: outer loop jo pure performance estimation ke liye hai (yeh test data kabhi tune karne mein nahi ata), aur inner loop jo hyperparameter tuning ke liye hai (har outer fold ke andar fresh tuning hoti hai). End mein aap outer folds ke errors ka average lete ho—yeh tumhari actual generalization ability hai, bina kisi bias ke. Yeh thoda computationally expensive hai (bohot saare model fits), lekin jab dataset chhota ho aur aapko honest estimate chahiye, toh nested CV gold standard hai. Production mein deploy karte waqt, aap final model ko full data pe best hyperparameters se train karte ho, lekin performance estimate outer CV se ata hai.