Nested Cross-Validation and the Optimism of Tuned Scores

Tuning selects the configuration that scores best on a validation set. Reporting that best score as the performance of the selected model is the same error as reporting the maximum of a set of noisy estimates as if it were an unbiased estimate of the winner. The bias is not a small-sample artifact; it persists as the sample grows if the number of configurations grows with it, and the standard repair is to nest the selection inside an outer loop that never sees the configuration choice.

Where the optimism enters

Take a grid of $m$ configurations and a validation set of $n$ rows. Each configuration’s validation score is its true risk plus noise of standard deviation $\sigma \approx \sqrt{p(1-p)/n}$ for a 0/1 loss. Selecting the minimum and reporting it gives an estimate biased low by roughly the expected gap between the minimum and the mean, which grows like $\sigma\sqrt{2\ln m}$ for approximately Gaussian noise. With $n = 1000$, $p = 0.2$, and $m = 100$, that is about $0.0126 \times 3.03 \approx 0.038$: nearly four points of error attributed to the model rather than to the search.

The bias has two sources and they behave differently. Selection bias comes from picking the maximum of noisy estimates and does not shrink with more data if $m$ is held fixed, though it shrinks as $1/\sqrt{n}$. Overfitting bias comes from the winning configuration being tuned to the particular validation rows; it shrinks with more validation data but persists if the configuration space is large enough that some configuration fits the noise. Cawley and Talbot’s argument is that the second effect is the dangerous one, because it does not vanish as fast as intuition suggests when the model family is flexible.

A single cross-validation loop with tuning inside it produces a score for the winning configuration, and that score is computed on the same folds used to choose it. Every fold contributed to the choice, so every fold’s score is contaminated. Averaging contaminated scores does not clean them; the average inherits the bias, diluted only by the fact that each fold’s score was computed on rows excluded from that fold’s fit but not from the selection.

The two loops

Nested cross-validation splits the data into $k$ outer folds. For each outer fold, the held-out portion is untouched. The remaining $k-1$ portions form the inner data, which is split again into $j$ inner folds; the grid is evaluated on the inner folds, the best configuration is chosen, a model is fitted on the whole inner set with that configuration, and scored once on the outer held-out portion. The result is $k$ scores, each produced by a complete selection-and-fit procedure that never saw the corresponding outer rows.

The estimate is of the procedure, not of a configuration. Each outer fold may select a different configuration, and that variation is part of what is being estimated: the number reports how well “tune on data of this size and fit” performs on unseen data, which is exactly the quantity relevant to a workflow that will be rerun on new data. If all folds select the same configuration, the estimate is also a reasonable estimate for that configuration, but that is an observation about the folds rather than a guarantee.

The final model is a separate fit. After the nested loop reports a score, the usual practice is to select a configuration on all the data, using an inner cross-validation, and fit once. The nested score does not describe that final model exactly, because the final model is trained on more rows than any outer fold’s model. The discrepancy is the training-size bias discussed in Stratified k-Fold Cross-Validation and the Variance of the Estimate, and it is small when the outer folds already use most of the data.

from itertools import product
import numpy as np

def nested_cv(X, y, make_model, grid, k=5, j=4):
    """Return per-outer-fold scores of the full select-and-fit procedure."""
    outer = np.array_split(np.arange(len(y)), k)
    scores = []
    for i in range(k):
        test = outer[i]
        train = np.concatenate([outer[t] for t in range(k) if t != i])
        best, best_err = None, np.inf
        for params in product(*grid.values()):
            cfg = dict(zip(grid.keys(), params))
            inner = np.array_split(train, j)
            err = 0.0
            for m in range(j):
                itest = inner[m]
                itrain = np.concatenate([inner[t] for t in range(j) if t != m])
                model = make_model(**cfg).fit(X[itrain], y[itrain])
                err += np.mean(model.predict(X[itest]) != y[itest]) * len(itest)
            if err / len(train) < best_err:      # inner error decides the configuration
                best, best_err = cfg, err / len(train)
        model = make_model(**best).fit(X[train], y[train])
        scores.append(np.mean(model.predict(X[test]) != y[test]))
    return np.array(scores)

The inner error is averaged over the inner folds with weights equal to fold sizes, so an uneven inner partition does not bias the comparison toward the smallest fold. The outer score is computed once per fold, on rows that took no part in either the inner fit or the inner selection.

The selection rule inside the inner loop

The inner loop returns more than a winner. Each configuration has an inner score, and the spread of those scores carries information that a bare argmin discards. The one-standard-error rule uses it: among all configurations whose inner score is within one standard error of the best, choose the simplest. The rule trades a small amount of measured performance for a configuration that is less likely to be fitted to the inner noise, and its justification is that configurations within one standard error are statistically indistinguishable on data of that size.

Implementing it requires a standard error for the inner score, which the inner fold scores provide as a rough spread with the same dependence caveats as the outer loop. The rule is therefore approximate, and it is still preferable to a bare argmin when the configuration space contains a complexity axis, because the argmin on a noisy criterion drifts toward the most flexible configuration at the boundary of the grid. That drift is a real selection effect and it shows up as a nested score that is worse than the inner scores predicted.

A second decision is what to do when the outer folds disagree about the winner. Disagreement is evidence that the inner criterion is not stable at this sample size, and the nested estimate already incorporates it: each outer fold scored its own choice, so the average covers the disagreement. For the final model, the usual resolution is to select on all data with the same inner procedure and accept that the selected configuration may match none of the outer folds’ choices. Reporting the distribution of selected configurations across outer folds is more informative than reporting the final winner alone.

The cost, and how to spend less of it

The naive cost is $k \times j \times m$ fits plus $k$ final fits. With $k = 5$, $j = 5$, and a grid of 50 configurations, that is 1,250 fits. For a model that takes an hour to fit, the procedure is not feasible, and the practical responses are all approximations with their own bias.

The first is to reduce the inner work: use a smaller inner fold count, a coarser grid, or a random search over the grid, since random search covers a high-dimensional space more efficiently than a full grid when only a few dimensions matter. The second is to accept a single inner split rather than an inner cross-validation, which halves the work per configuration at the cost of a noisier selection. The third is to reuse the outer scores for the selection as well, which is exactly the contamination the nesting exists to avoid, so it is not an approximation but a different, biased procedure.

A cheaper structure is to fix the configuration by an independent tuning run on a separate dataset, then run a plain cross-validation on the evaluation data with that configuration fixed. That is valid when a separate tuning set genuinely exists, and it is a different claim: the estimate then covers the configuration as given, not the selection procedure.

Reporting both loops without conflating them

The two numbers that come out of the procedure are the nested estimate and the final configuration’s inner score. They are estimates of different quantities, and a table that lists them under adjacent headings invites the reader to treat the larger as the model’s performance. The nested estimate covers the procedure; the inner score covers one configuration on the data it was selected from and is therefore optimistic in the same way the flat procedure is.

A clean report states the nested mean with the outer fold values, names the grid that was searched, and states the outer fold count. Without the grid size the number is uninterpretable, because the bias it removes is a function of that size; a nested estimate over four configurations and one over four hundred are not comparable claims about a workflow, even when both report the same mean.

The final model’s own performance remains unmeasured by construction. Any number computed on data the final fit saw is a training number, and any number computed on a set held back from the whole procedure is a fresh test set that has now been spent. The nested estimate is the closest available proxy, and its remaining gap is the training-size effect rather than a selection effect.

Reading the output honestly

The $k$ outer scores give a spread, and the caveats from the non-nested case apply unchanged: the outer training sets overlap, so the scores are dependent and their sample standard deviation is not the standard error of the mean. The mean of the outer scores is the estimate; the spread describes partition sensitivity.

A large gap between the nested score and a non-nested tuned score is a measurement of the selection bias on this dataset, not proof that the model is bad. The gap depends on the grid size, the noise level, and the sample size, and it can be several points on a small dataset with a large grid. Reporting both numbers, and naming which is which, is more informative than reporting either alone.

The estimate is also specific to the search that was nested. If the configuration was chosen from a grid, the nested score covers that grid; a later search over a wider space has a different bias and needs its own estimate. Adding configurations after seeing the nested result invalidates the number, since the space that was searched has changed and the maximum over the larger space is higher.

For time-ordered data the outer loop must itself respect the ordering, and the inner loop must sit inside each training block, as described in Blocked and Rolling-Origin Validation for Time-Ordered Data. The same holds for grouped data: the outer partition must keep groups intact, and the inner partition must keep them intact within each training block, per Grouped Splits When Observations Are Not Independent. Nesting does not repair a violated independence assumption; it only separates selection from estimation.