The Nested Cross-Validation Algorithm

Why the Algorithm Has Two Levels

A classifier’s performance can look better when the same validation results are used both to choose its tuning parameters and to report how well it performs. Nested cross-validation separates those jobs. Inner folds select a classifier configuration; outer folds evaluate the selection process on observations that played no part in that selection. This distinction is especially important in genomic prediction, where the number of candidate predictors and analysis choices can be large relative to the number of individuals.

The algorithm estimates the performance of a specified tuning-and-fitting procedure, not the performance of a model chosen once using all available outcomes. Each outer training set gets its own inner tuning step and may select a different configuration. The resulting outer-fold scores summarize how that procedure performs when trained on a subset of the data.

Set the Evaluation Rules Before Fitting

Let the data be \(D=\{(x_i,y_i):i=1,\ldots,n\}\), where \(x_i\) denotes the predictor information for observational unit \(i\) and \(y_i\) is its outcome. Specify the prediction target and unit of cross-validation, the classifier, the candidate configurations, the performance metric, and the fold construction before running the algorithm. For example, a configuration \(\theta\) might specify a regularization strength and a class-weighting choice. The candidate set \(\Theta\) is the finite collection of configurations that will be compared.

The folds must reflect the intended prediction setting. The units assigned to different folds should be separated in the way required by the target: for example, related individuals or observations from the same site may need to remain together. Use an appropriate fold construction, such as stratification when required by the design, rather than assuming that ordinary random folds are always valid. The split determines what is being evaluated; nested tuning does not repair an unsuitable split.

The performance metric must be defined in advance, including which direction is better. For accuracy, larger is better; for a loss such as classification error, smaller is better. All candidate configurations must be scored using the same metric and validation observations within a given outer training set. If a metric cannot be computed for a particular fold, that must be addressed in the design or specified scoring rule rather than handled ad hoc after seeing results.

The usual interpretation assumes that the folds represent the target population or sampling design, and that the observations used for evaluation are not used to fit or select the model being evaluated. Any learned operation belongs inside the fitting process: imputation, normalization, screening, feature selection, dimension reduction, and classifier fitting must be learned from the training portion at each stage. A fixed candidate list and a prespecified rule for resolving ties also make the procedure reproducible. If model fitting is stochastic, control or record its randomness so that differences in scores are not silently caused by unrelated random seeds.

The Nested Cross-Validation Algorithm

Write the outer folds as \(O_1,\ldots,O_K\), with corresponding outer training sets \(T_k=D\setminus O_k\). Within each \(T_k\), create \(J\) inner validation folds \(V_{k1},\ldots,V_{kJ}\); the training data for inner fold \(j\) are \(T_k\setminus V_{kj}\). For each candidate configuration, fit on each inner training set and score on its inner validation fold. Average the \(J\) scores using the prespecified rule, then select the candidate with the best average.

The outer fold is not a second tuning set. Once its observations have been used to calculate \(M_k\), changing the candidate set, preprocessing, or selection rule in response to that result turns it into part of model development. The same outer outcomes cannot then serve as an untouched evaluation of the revised procedure.

Why the Outer Evaluation Is Separate

The separation can be seen by following the information used at each stage. For a fixed outer iteration \(k\), the selected configuration \(\hat{\theta}_k\) is a function of the data in \(T_k\): every inner fit and validation score uses only observations from \(T_k\). The refitted classifier is also based only on \(T_k\). Thus the outcomes in \(O_k\) do not determine which candidate is selected or how the classifier is fit; they are used only to calculate its evaluation score.

This is the reason for nesting. If one instead tunes on all observations and reports the best cross-validation score from that same tuning, the reported score has participated in choosing the winner. The outer procedure evaluates the entire rule—“tune by this inner procedure, then fit”—on observations kept aside from that rule’s selection step.

This separation does not make the outer estimate exactly unbiased for every possible target. Each outer model is trained on less data than the final model that might later be fit to all \(n\) observations. The estimate therefore pertains most directly to the specified procedure trained on outer-training-set-sized samples, under the data-generating and fold design assumptions. It also has sampling variability, and the fold scores should not be treated as independent observations simply because they are listed separately.

Implementation Checks and Common Failure Modes

A practical implementation should record, for every outer iteration, the outer-fold membership, inner-fold membership, candidate scores, selected configuration, and outer score. This makes it possible to check that the reported result follows the algorithm rather than a convenient but different sequence of operations. In particular, verify that:

• every outer observation is evaluated only in its held-out outer fold, and never enters that iteration’s inner tuning;
• each candidate is scored on the same inner folds within an outer iteration;
• the selected configuration is refit on the full outer training set before outer predictions are made;
• all data-adaptive steps are refitted within each relevant training split; and
• the scoring rule and tie rule are applied consistently across outer iterations.

A common mistake is to run cross-validation once on the full data, select the configuration with the best score, and call that same best score the nested estimate. The reasoning is wrong because the score helped choose the configuration; it is not an outer evaluation. The correction is to repeat the complete inner selection separately inside every outer training set and score only the resulting refit on that iteration’s untouched outer fold.

Other failures include fitting feature selection before making inner folds, using outer results to revise the candidate set and still reporting those results as untouched, or allowing observations that should be grouped together to cross fold boundaries. Nested cross-validation does not fix leakage caused by a poorly defined observational unit, inappropriate folds, or an analysis step performed outside the folds. Nor does it guarantee that all possible sources of uncertainty are represented: it estimates performance for the chosen data, design, candidate set, and metric.

How to Read and Use the Estimate

The outer estimate answers a defined predictive question: how well does the specified procedure perform when its tuning is carried out using inner cross-validation and its fitted model is applied to observations held out by the outer design? State the metric, units or scale, and validation design alongside the numerical estimate. For example, “mean outer-fold accuracy was 66.7% under three-fold cross-validation” is more informative than “the model was 66.7% accurate.”

After evaluation, a final model intended for deployment can be trained by applying the prespecified tuning procedure to all available development data and then fitting the selected configuration on those data. That final fit is not itself evaluated by the outer folds as a model trained on all \(n\) observations. If its performance must be assessed independently, evaluation data not used for development provide a distinct source of evidence.