Unbiased Performance Estimation

We've established that nested cross-validation separates model selection from performance evaluation through its two-loop structure. But why does this separation produce unbiased estimates? What is the precise statistical mechanism that eliminates selection bias?

This page provides the rigorous theoretical foundation for nested CV's unbiasedness. Understanding these principles doesn't just verify that nested CV works—it reveals when and why it might fail, how to interpret its outputs correctly, and how to extend it to novel situations.

Before proving unbiasedness, we must be precise about what nested CV estimates. This is often misunderstood, leading to incorrect interpretation.

The estimand (what we're trying to measure):

Nested CV estimates the expected generalization performance of the model selection procedure, not the performance of any specific selected model.

Formally, let:

• $\mathcal{A}$ denote the model selection algorithm (hyperparameter tuning procedure)
• $D$ denote a training dataset of size $n$ drawn from distribution $P$
• $\mathcal{A}(D)$ denote the model selected by $\mathcal{A}$ when trained on $D$
• $R(f, P)$ denote the true risk (expected loss) of model $f$ on distribution $P$

Nested CV estimates:

$$\theta = \mathbb{E}_{D \sim P^n}[R(\mathcal{A}(D), P)]$$

In words: the expected test performance of the model you would get by applying your selection procedure to a random training set of size $n$ from the same distribution.

Why this estimand is the right one:

1. Reproducibility: If a colleague runs your procedure on similar data, what should they expect?
2. Generalization of the process: You're not deploying your validation model; you're deploying a retrained model from the same procedure
3. Decision-making: Should you use this model selection approach or a different one?

Contrast with standard (non-nested) CV:

Standard CV with hyperparameter selection estimates:

$$\hat{\theta}{\text{biased}} = \max{\lambda \in \Lambda} \hat{R}{CV}(\mathcal{A}\lambda(D))$$

This is the best CV score across hyperparameter configurations—which, as we showed, is optimistically biased because the maximum of noisy estimates tends to exceed the true maximum.

We now prove that nested CV provides an unbiased estimate of the expected generalization performance.

Theorem (Unbiasedness of Nested CV):

Let $\hat{\theta}_{NCV}$ be the nested cross-validation estimate. Under the assumption that outer folds are exchangeable (satisfied by random splitting), we have:

$$\mathbb{E}[\hat{\theta}{NCV}] = \mathbb{E}{D \sim P^n}[R(\mathcal{A}(D), P)]$$

where the left expectation is over the randomness in both the dataset and the CV splits.

Proof:

Let the full dataset $D$ be split into $K$ outer folds: $D = D_1 \cup D_2 \cup ... \cup D_K$.

For outer fold $k$:

• Let $D_{-k} = D \setminus D_k$ be the outer training set (all folds except $k$)
• Let $\hat{f}k = \mathcal{A}(D{-k})$ be the model selected by applying procedure $\mathcal{A}$ to the outer training set
• Let $\hat{R}k = \frac{1}{|D_k|} \sum{(x,y) \in D_k} L(\hat{f}_k(x), y)$ be the empirical risk on outer test fold $k$

The nested CV estimate is:

$$\hat{\theta}{NCV} = \frac{1}{K} \sum{k=1}^{K} \hat{R}_k$$

Step 1: Conditional unbiasedness

Conditioned on $D_{-k}$ (and hence on the selected model $\hat{f}_k$), the outer test fold $D_k$ consists of i.i.d. samples from $P$ that were not used in model selection. Therefore:

$$\mathbb{E}[\hat{R}k | D{-k}] = R(\hat{f}k, P) = R(\mathcal{A}(D{-k}), P)$$

This is the key step: because $D_k$ was held out during the entire inner loop, evaluating on $D_k$ gives an unbiased estimate of the selected model's true risk.

Step 2: Marginalizing over training sets

Taking the expectation over $D_{-k}$:

$$\mathbb{E}[\hat{R}k] = \mathbb{E}{D_{-k}}[R(\mathcal{A}(D_{-k}), P)]$$

This equals $\mathbb{E}_{D'}[R(\mathcal{A}(D'), P)]$ where $D'$ is a dataset of size $(K-1)n/K$ drawn from $P$.

Step 3: Averaging over folds

By symmetry (exchangeability of folds):

$$\mathbb{E}[\hat{\theta}{NCV}] = \mathbb{E}\left[\frac{1}{K} \sum{k=1}^{K} \hat{R}k\right] = \frac{1}{K} \sum{k=1}^{K} \mathbb{E}[\hat{R}k] = \mathbb{E}{D'}[R(\mathcal{A}(D'), P)]$$

Step 4: Addressing the sample size discrepancy

Note that $D'$ has size $(K-1)n/K$ rather than $n$. Nested CV technically estimates performance on training sets of size $(K-1)/K$ times the available data. This introduces a small upward bias because smaller training sets generally yield worse models.

For K = 5: Outer training sets are 80% of full data For K = 10: Outer training sets are 90% of full data

This bias is typically small and conservative (you underestimate final performance because your final model uses 100% of data). Many practitioners consider this acceptable.

Conclusion:

Nested CV is unbiased with respect to the performance of the model selection procedure on training sets of size $(K-1)n/K$. It provides a conservative estimate of full-data performance. □

While nested CV is unbiased, its estimates have variance. Understanding variance sources helps interpret results and design better experiments.

Decomposition of variance:

The total variance of the nested CV estimate can be decomposed as:

$$\text{Var}(\hat{\theta}{NCV}) = \text{Var}{between}(outer\ folds) + \text{Var}_{within}(inner\ CV)$$

1. Between-fold variance (outer loop):

Different outer folds yield different selected models and different test sets. This contributes:

$$\text{Var}{between} = \frac{1}{K{outer}^2} \sum_{k=1}^{K_{outer}} \text{Var}(\hat{R}k) + \frac{2}{K{outer}^2} \sum_{k<k'} \text{Cov}(\hat{R}k, \hat{R}{k'})$$

The covariance term arises because outer folds share training data (non-independence). This increases variance compared to independent samples.

2. Within-fold variance (selection uncertainty):

Within each outer fold, the inner CV has variance in which hyperparameters it selects. Sometimes a suboptimal configuration wins due to noise. This adds variance to the outer test score—you're sometimes evaluating a suboptimally selected model.

Factors affecting total variance:

Estimating variance:

The standard error of nested CV is often estimated as:

$$\hat{\text{SE}}(\hat{\theta}{NCV}) = \frac{s}{\sqrt{K{outer}}}$$

where $s$ is the sample standard deviation of outer fold scores. However, this underestimates true variance because it ignores the correlation between folds (they share training data).

Corrected variance estimation:

More accurate variance estimation requires:

• Repeated nested CV with different outer splits
• Bootstrap methods
• Analytic corrections for fold correlation

In practice, reporting the uncorrected standard error with a note about potential underestimation is common.

Let's verify nested CV's unbiasedness empirically through simulation. This also illustrates the magnitude of selection bias that nested CV avoids.

Nested CV has a small conservative bias that's often acceptable in practice.

The source of conservative bias:

In nested CV with K_outer folds:

• Each outer training set contains $(K-1)/K$ of the data
• The final deployed model will train on $100%$ of the data
• Larger training sets generally produce better models

Therefore, nested CV slightly underestimates the performance of the final deployed model because it evaluates models trained on less data than will be available at deployment.

Learning curve perspective:

The relationship between training set size and performance follows a learning curve. For many models:

$$\text{Error}(n) \approx a + \frac{b}{n^\alpha}$$

where $\alpha$ is typically 0.5-1.0. The relative improvement from 80% to 100% of data is:

$$\frac{\text{Error}(0.8n) - \text{Error}(n)}{\text{Error}(n)} = \frac{b/((0.8n)^\alpha) - b/(n^\alpha)}{a + b/n^\alpha}$$

For typical learning curves, this yields 1-5% relative performance difference. A model reported at 85% accuracy by nested CV might achieve 86-87% with full data training.

Why conservative bias is acceptable:

1. Honest: You don't overpromise to stakeholders
2. Safe for decision-making: Underestimating beats overestimating
3. Predictable direction: You know the bias direction
4. Decreases with K: Using K=10 reduces it substantially

Beyond point estimates, nested CV can provide confidence intervals for generalization performance. However, constructing valid intervals requires care.

Naive approach (often used, somewhat problematic):

With K outer fold scores $\hat{R}_1, ..., \hat{R}_K$, the simplest interval is:

$$\hat{\theta}{NCV} \pm t{K-1, \alpha/2} \cdot \frac{s}{\sqrt{K}}$$

where $s$ is the sample standard deviation of outer scores.

Problems with this approach:

1. Non-independence: Outer folds overlap in training data, violating the independence assumption for the t-interval
2. Underestimated width: The correlation inflates true variance beyond $s^2/K$
3. Non-normality: With K=5 folds, normality is questionable

Improved approaches:

Repeated nested CV for better intervals:

The most reliable approach: repeat nested CV with different random splits, then use the distribution of estimates:

from sklearn.model_selection import RepeatedKFold

# Repeat nested CV 10 times with different splits
outer_cv = RepeatedKFold(n_splits=5, n_repeats=10, random_state=42)

# This gives 50 outer fold scores instead of 5
# CI from 50 scores is more reliable (though still correlated)

With R repetitions and K folds, you get R×K scores. The interval is more reliable, though correlation still exists.

Nested CV enables valid statistical comparison of different model families (e.g., SVM vs Random Forest), not just hyperparameter configurations within a family.

The comparison setup:

1. Run nested CV separately for each model family
2. Use the same outer folds for all models (paired comparison)
3. Compare outer fold score distributions

Why same outer folds matter:

Using identical outer splits creates a paired experimental design. The difference $d_k = \hat{R}^{A}_k - \hat{R}^{B}_k$ for fold $k$ removes variance due to fold-specific difficulty. This dramatically increases statistical power.