Nested Cross-Validation for Model Selection

Why Model Selection Needs Its Own Evaluation

Cross-validation can be used both to choose among candidate models and to estimate prediction performance. The difficulty is that these are different jobs. If we choose the model with the best score on a set of validation folds and report that same best score as an evaluation, the reported value has benefited from the choice: among several noisy scores, the smallest may look good partly by chance.

Nested cross-validation separates those jobs. Inner folds select a model or setting using only the data available for that selection. Outer folds evaluate the resulting selection-and-fitting procedure on observations that did not take part in that outer fold’s selection or fitting. The outer evaluation is therefore about the complete procedure, not just about a model chosen in advance.

Definition: In nested cross-validation, an outer cross-validation loop divides the data into training and held-out folds. Within each outer training set, an inner cross-validation loop compares candidate models or settings and selects one according to a prespecified rule. The selected setting is fitted using the full outer training set, and its predictions are evaluated on the outer held-out fold. The outer-fold results are combined to estimate the performance of this selection procedure.

A candidate might be a model type, a tuning value, or a combination of choices. For example, candidates could be linear models with different sets of predictors, or one model fitted with several penalty settings. The selection rule includes the candidate set, the score used to compare candidates, and how ties are resolved. These choices should be specified before examining outer-fold evaluation results.

Tracing the Two Loops

Suppose there are \(n\) observations and we use \(K\) outer folds. For outer fold \(k\), call the outer training data \(D_{-k}\) and the held-out data \(D_k\). The outer training data are used for every operation that determines the prediction rule for this fold. They are split again into inner folds. Each candidate is fitted on the inner-training portions and scored on the corresponding inner-validation portions. The inner scores are combined according to a fixed rule, and the selected candidate is then fitted using all of \(D_{-k}\).

Only after that fit is complete do we predict outcomes for \(D_k\). Those outcomes must not have affected preprocessing, feature selection, tuning, or any other part of the fitted prediction procedure for outer fold \(k\). The outer held-out fold is an evaluation set for that fold, not another opportunity to revise the model.

Hold out an outer fold.
Set aside \(D_k\). Do not use it to choose settings, fit the prediction rule, or make data-dependent preprocessing decisions.

Select inside the outer training data.
Run inner cross-validation using only \(D_{-k}\). Compare the prespecified candidates using the prespecified selection score and rule.

Fit the selected candidate.
Using all of \(D_{-k}\), fit the prediction procedure with the setting chosen in Step 2. Any data-dependent preprocessing is part of this fit.

Evaluate on the outer fold.
Predict for \(D_k\), calculate the chosen loss for its held-out observations, and save the results. Repeat for each outer fold.

Combine the outer results.
Average the held-out losses across all outer observations, or use an explicitly chosen fold-weighted summary when fold sizes differ.

For example, let \(\ell(y_i,\hat{y}_i)\) denote a prespecified loss for outcome \(y_i\) and prediction \(\hat{y}_i\). If every observation appears in exactly one outer held-out fold, the pooled outer estimate is

\widehat{R}_{\text{nested}}=\frac{1}{n}\sum_{k=1}^{K}\sum_{i\in D_k}\ell(y_i,\hat{y}_{i,-k})

Here \(\hat{y}_{i,-k}\) is the prediction for observation \(i\) from the procedure selected and fitted without outer fold \(k\). For squared-error loss, \(\ell(y_i,\hat{y}_i)=(y_i-\hat{y}_i)^2\). The loss and its units depend on the chosen measure; for squared-error loss they are squared outcome units.

Worked Example: Following One Observation Through the Loops

Suppose a hypothetical dataset has 12 observations and uses three outer folds of four observations each. For outer fold 1, observations 1–4 are held out, and observations 5–12 form \(D_{-1}\). The candidates are two predictor sets, A and B, and the prespecified inner score is average squared prediction error.

The eight observations in \(D_{-1}\) are divided into inner folds. Each candidate is fitted on an inner-training portion and scored on the corresponding inner-validation portion. Suppose the combined inner scores are 5.2 squared outcome units for A and 6.1 for B. The selection rule chooses A because 5.2 is smaller.

Candidate A is then fitted anew using all eight observations in \(D_{-1}\). If observation 2 has outcome 10 and this fit predicts 8, its outer-fold squared error is \( (10-8)^2=4 \) squared outcome units. Observation 2 was not used in choosing A or fitting this fold’s version of A; it contributes only to outer evaluation.

The same process is repeated with a different outer fold held out each time. The model selected in another outer fold need not be A. The purpose is to evaluate the repeated selection procedure, not to insist that one candidate must be selected in every fold.

What Performance Does the Estimate Target?

Nested cross-validation estimates the predictive performance of a specified selection-and-fitting procedure when it is given training data of roughly the size of an outer training fold. The procedure includes the candidate set, inner-fold design, selection score and rule, and fitting steps. With \(K\) similarly sized outer folds, each outer fit uses about \(n(K-1)/K\) observations.

The target is not simply the performance of the single candidate that happened to win most often, nor is it automatically the performance of a final model fitted using all \(n\) observations. The model choice can vary from outer fold to outer fold. The estimate summarizes predictions from procedures trained on outer training subsets and tested on their held-out observations.

As with other cross-validation estimates, the result is an estimate, not an exact guarantee of future performance. Its relevance depends on the data and validation design representing the intended prediction setting. In particular, the way observations are split should respect their structure: when observations are dependent or prediction concerns later time periods or new groups, folds should be constructed to reflect that target rather than randomly mixing related observations across training and validation data.

Worked Example: Interpreting the Training-Set Size

A hypothetical analysis has \(n=120\) independent observations and uses five outer folds of 24 observations each. For each outer fold, the procedure uses the other \(120-24=96\) observations for inner selection and fitting.

Suppose each outer training set is itself assessed using four inner folds. In each inner split, approximately \(96(3/4)=72\) observations fit a candidate and about \(96/4=24\) assess it. The inner scores select a setting; then that setting is fitted on all 96 outer-training observations and evaluated on the 24 outer-held-out observations.

If the pooled outer loss is 3.4 squared outcome units, the interpretation is that the nested procedure’s estimated average squared prediction loss is 3.4 squared outcome units under this validation design, with outer fits trained on 96 observations. It is not a claim that a particular setting has loss exactly 3.4, or that the procedure trained on all 120 observations must have that same loss.

Why the Separation Matters

The reason to nest the folds can be expressed simply. Suppose each of several fixed candidates has a noisy validation score. Even if each score is centered on its candidate’s expected score, choosing the smallest observed score tends to favor a candidate whose noise happened to be favorable. For scores \(\widehat{R}_1,\ldots,\widehat{R}_J\), the minimum is no greater than any one score, so

E\!\left[\min_{1\leq j\leq J}\widehat{R}_j\right] \leq \min_{1\leq j\leq J}E[\widehat{R}_j]

This inequality explains why the minimum score used to select a candidate is generally too optimistic as an evaluation of that selection. It does not say that every selected model will perform poorly; it says that the score used for selection is not an independent assessment of the choice.

In nested cross-validation, the outer observations are not used to select the candidate for their fold. Conditional on that fold’s outer training data, the selected candidate and its fitted prediction rule are determined without the held-out outcomes. This separation makes outer performance informative about the selection procedure. Outer fold results are still related because their training sets overlap, so they should not be treated as independent replicates merely because they come from different folds.

Worked Example: Finding Leakage in a Proposed Analysis

A hypothetical analyst uses all 80 observations to rank predictors and retain the five strongest. The analyst then runs nested cross-validation, selecting a tuning value inside each outer training set, and reports the outer-fold error.

The tuning step is nested, but the predictor ranking is not: each outer held-out outcome helped determine which five predictors were available. Thus the outer fold did not evaluate the complete data-driven selection procedure on unseen observations. The reported estimate can be optimistic because information from the held-out outcomes entered the prediction process.

To correct the data flow, predictor ranking and retention must occur using only the relevant training data. In each outer fold, perform that step using \(D_{-k}\); if its choices are also tuned by inner validation, perform it separately within each inner-training split. Then select the setting inside the outer training data, refit the complete procedure on \(D_{-k}\), and evaluate on \(D_k\). The evaluation fold now remains outside all data-dependent choices for that outer fit.

Common Mistakes

Reporting the winning inner score as the final performance. That score helped choose the candidate and may be optimistic. Use the outer held-out results to evaluate the selection procedure.
Using outer results to revise the procedure. If the outer results guide changes to candidates, preprocessing, or tuning rules, they are no longer a clean evaluation of the revised procedure. A separate evaluation would be needed for that revised analysis.
Leaving a selection step outside the folds. Any data-dependent operation that affects predictions must be confined to the training portion for each evaluation split.
Claiming the estimate describes a full-data fit exactly. Outer fits use only outer training observations. State the approximate training-set size and treat the estimate as an approximation to performance in the intended setting.
Assuming every fold must choose the same model. Variation in the selected candidate is possible. Nested cross-validation evaluates the algorithm that makes the choice, including that variation.

Key takeaway: Inner folds choose; outer folds evaluate. Keep every data-dependent decision inside the relevant training data, and interpret the combined outer loss as an estimate for the complete selection procedure at the outer training-set size—not as the guaranteed performance of one final model.

Check Your Understanding

Try these questions before moving on.

In nested cross-validation, what decisions may use an outer held-out fold’s outcomes?
Why is the smallest inner validation score not, by itself, a suitable estimate of the selected procedure’s performance?
With \(n=150\) observations and five equally sized outer folds, approximately how many observations fit each outer-fold procedure?
An analyst ranks predictors using the full dataset before starting nested cross-validation. Explain why the outer folds no longer provide a clean evaluation.
What does a nested cross-validation estimate target, and why may it differ from the performance of a model later fitted using all observations?