Motivation
A cross-validation score can serve two different purposes. It can help choose a learning rule, or it can assess a rule whose choices have already been made without the assessed observations. Using the same number for both purposes hides a selection step. A large candidate search can find a low score partly by finding favorable evaluation noise.
Nested cross-validation assigns these jobs to different observations within each outer iteration. Inner folds choose a configuration. The whole selected pipeline is then refitted on that iteration's outer training portion. Its outer fold supplies predictions that did not use that fold's observations in fitting or selection. Different outer iterations may choose different configurations: that is part of the procedure being assessed.
The sparse-learning note described this arrangement, and the regression-workflow note separated training, validation, refitting and an independent final test. Here we make the nested algorithm finite and executable. We also identify its actual target. An outer average concerns several smaller-training-sample learning procedures. It is not automatically a confidence interval, nor is it the independently measured risk of the final predictor fitted on all available development data.
Definitions
Definition 27.1.1
(An ordered configuration list and a complete fitting operation)
Let , where , and fix a nonnegative prediction loss . Prespecify a finite ordered list of pipeline configurations. Write for the predictor obtained by fitting configuration using only observations with indices in .
The fitting operation includes every estimated transformation: imputation, centering, scaling, feature selection, dimension reduction, fitted coefficients and any learned prediction threshold. A configuration specifies the fitting recipe; its fitted state depends on the supplied observations. Break all score ties by the order in .
A fixed polynomial degree is a configuration choice. Its fitted column means and coefficient vector are state. An early-stopping rule is also part of the recipe; if it uses a further validation split, that split must remain inside the current fitting portion. A stochastic fitter needs declared seeds and a rule for generating them independently of observations excluded from that fit. Every requested fit must be well defined; for example, a pipeline requiring two classes cannot silently be fitted to a one-class training portion.
Definition 27.1.2
(Outer partitions, inner partitions and observation weighting)
Choose a partition of into nonempty outer folds, with nonempty complements . For each , choose a partition of , with and every inner training complement nonempty. These are inner validation folds. Let and .
Use observation-weighted inner and outer losses:
Here is the refitted selected pipeline defined in the algorithm below. When folds have unequal sizes, this is not the unweighted average of their mean losses. Each observation receives weight in the outer score. Different aggregation rules may be useful for other scientific targets, but they must be stated. The probability theorem below uses a deterministic index partition fixed before observing the data. An independently randomized partition requires conditioning on that partition, as explained after the theorem. Label-stratified, grouped and time-ordered sampling need their own account of the resulting distribution; they do not automatically satisfy that theorem.
Theorem/Proposition
Theorem 27.1.3
(A finite nested algorithm with a visible information boundary)
For each outer fold , perform these steps in order.
- For every and inner fold , fit a fresh complete pipeline on . Score it on and compute .
- Select minimizing under the declared tie rule.
- Discard those inner fitted states. Fit a fresh pipeline , including reestimation of every learned transformation.
- Record predictions and losses on once. Do not use those outer scores to change that iteration's choices.
Pool the recorded outer losses using the displayed observation weights. If the fitting and splitting rules use only the stated inputs and permitted seeds, each is a function of and those seeds, with no dependence on .
The list of configurations, loss, split recipe, tie rule, preprocessing order and failure policy should be locked before the assessment. If someone examines the outer results and then changes these choices, the changed procedure has not been assessed by untouched observations. Keeping the best outer score among several nested experiments reintroduces selection at a higher level.
Theorem 27.1.4
(What the outer average targets under iid sampling)
Suppose are iid from , the outer partition is deterministic and fixed before observing them, and all permitted fitting seeds are independent of the data. For each , let collect its seeds and define the fresh-observation risk
Assume all displayed losses have finite expectations. Then
If all outer training sizes are and every iteration applies the same size- selection-and-refitting rule, including the same inner split recipe up to relabeling and the same seed law, the right-hand side is the repeated-training expected risk of that size- procedure. For unequal sizes or different inner recipes, it is a weighted mixture of the corresponding expected risks.
For a randomized outer partition, suppose the partition and all fitting seeds are jointly independent of the data. Condition on its realized index sets before applying the theorem. Its identities then hold conditionally on that partition. If fold sizes are random, their weights must remain inside any subsequent expectation over partitions.
This precise expectation identity does not identify the conditional risk of a particular all-data final predictor. It supplies no general ordering between that predictor's risk and the smaller-sample target. A more complicated procedure can behave worse after receiving more data, and the grid winner can change with training size. Even when larger samples tend to help, a correction from to needs additional evidence or assumptions.
Theorem 27.1.5
(An exact leave-one-out score for a fitted mean)
For real responses with , let . The squared-loss leave-one-out score of the sample-mean predictor is
For a prespecified constant predictor , the same score is . Neither formula requires a stochastic sampling assumption.
Proof sketch or proof idea
Proof
(Trace which observations may enter each fitted state)
Within outer iteration , every inner fitting subset and every inner validation subset lies inside . Thus its fitted transformation, predictor, score and tie-broken selected configuration depend only on and the declared seeds. The fresh refit has the same information boundary. Composing these operations cannot introduce an observation from . Applying to an outer input evaluates the already fixed function; it does not permit reestimating transformations from that input or its label.
This argument certifies the stated data flow, not that the inner selector chooses a statistically optimal configuration. Fitting one scaler on all of before its inner splits would still keep the outer fold untouched, but it would no longer be the inner train-only procedure specified here. Fit every inner pipeline afresh to preserve both boundaries.
Proof
(Condition one outer iteration at a time)
Fix and condition on and . The predictor is then fixed. Because the index split is independent of iid observations, each remaining in still has distribution and is independent of the conditioned objects. Consequently each conditional expected loss is . Averaging the terms gives the first identity. Applying total expectation and the equality gives the second identity by linearity.
No independence between different was used. Their predictors are fitted on overlapping data. In fact an observation scored in one outer iteration is a training observation in others. We may condition on one iteration's permitted information to prove its expectation identity; conditioning simultaneously on all outer fitted predictors would generally reveal information about the very observations being assessed.
Proof
(The held-out residual is an inflated centered residual)
When response is omitted, the fitted mean is . Therefore
Square and average these identities to obtain the formula. The constant predictor is unchanged by omission, so its score is simply its empirical squared loss. The mean predictor's leave-one-out error generally exceeds its training error: the factor multiplying the mean centered squared residual is .
Proof X-ray
An honest held-out prediction does not make fold means independent
The information-boundary proof concerns one fitted function and its own excluded observations. The expectation proof uses that boundary separately for each fold and then adds expectations. Neither establishes independent fold means. A standard error obtained by dividing their sample standard deviation by therefore needs a justification beyond the existence of folds.
Worked examples
Worked example 27.1.6
(Six observations, two configurations, three outer fits)
Let every input be the same constant, and specify the deterministic responses in index order as . Choose the index folds , and in advance; this example is not a rule that groups observed labels. Use squared loss, inner leave-one-out, and the ordered configurations : always predict the prespecified constant one; : predict the fitting sample's mean. There is no other preprocessing.
For , the outer training responses are . Their mean is , and the sum of centered squares is one. Hence , whereas . Select , refit its mean to on all four outer training observations, and predict that value for both zeros. The outer mean squared loss is .
For , the outer training responses are . Their mean is one and centered sum of squares is four. Thus and . Select ; both excluded responses are one, so the outer loss is zero. For , symmetry gives the following complete table.
| Outer fold | Outer training responses | Inner score A | Inner score B | Selected | Refit prediction | Outer mean loss |
|---|---|---|---|---|---|---|
| 1 | 1, 1, 2, 2 | 1/2 | 4/9 | B | 3/2 | 9/4 |
| 2 | 0, 0, 2, 2 | 1 | 16/9 | A | 1 | 0 |
| 3 | 0, 0, 1, 1 | 1/2 | 4/9 | B | 1/2 | 9/4 |
The six outer losses are , giving . Averaging the three winning inner scores instead gives . That is a different number with a different role; it is not the outer assessment.
Worked example 27.1.7
(Refit the procedure on all development observations)
After the assessment, run the same configuration-selection recipe on all six development observations, using leave-one-out internally. Their mean is one, and their centered sum of squares is four. Thus , while . Select and produce the final constant-one predictor. The outer winners are not a majority vote to select ; the declared final selection step is run afresh on all development data.
The final predictor's training error is . Its fresh-observation risk has not been measured by that training number or by the nested score . These six deterministic observations do not establish iid sampling from any specified population. The calculation illustrates the algorithm and the changing selection result; it is not a real-data experiment or a population-performance guarantee.
The complete standard-library program below uses exact rational arithmetic. Its indices start at zero; the printed fold numbers start at one. Every inner fit excludes its scored response, and the selected configuration is freshly refitted before an outer prediction.
from fractions import Fraction as F
y = tuple(map(F, (0, 0, 1, 1, 2, 2)))
CONFIGS = ("A", "B") # Fixed one, then fitted mean; this is the tie order.
OUTER = ((0, 1), (2, 3), (4, 5))
ALL = tuple(range(len(y)))
def fit(indices, config):
assert indices and config in CONFIGS
return F(1) if config == "A" else sum(y[i] for i in indices) / len(indices)
def inner_scores(indices):
assert len(indices) >= 2
scores = {}
for config in CONFIGS:
total = F(0)
for held in indices:
train = tuple(i for i in indices if i != held)
prediction = fit(train, config)
total += (prediction - y[held]) ** 2
scores[config] = total / len(indices)
return scores
def select_and_refit(indices):
scores = inner_scores(indices)
chosen = min(CONFIGS, key=lambda c: (scores[c], CONFIGS.index(c)))
return chosen, fit(indices, chosen), scores
losses = {}
for number, held in enumerate(OUTER, 1):
train = tuple(i for i in ALL if i not in held)
chosen, prediction, scores = select_and_refit(train)
for i in held:
assert i not in train and i not in losses
losses[i] = (prediction - y[i]) ** 2
outer_mean = sum(losses[i] for i in held) / len(held)
print(f"fold {number}: A={scores['A']} B={scores['B']} "
f"choose={chosen} predict={prediction} outer={outer_mean}")
assert set(losses) == set(ALL)
print("nested MSE:", sum(losses.values()) / len(y))
chosen, prediction, scores = select_and_refit(ALL)
print(f"full development: A={scores['A']} B={scores['B']} "
f"choose={chosen} predict={prediction}")
fold 1: A=1/2 B=4/9 choose=B predict=3/2 outer=9/4
fold 2: A=1 B=16/9 choose=A predict=1 outer=0
fold 3: A=1/2 B=4/9 choose=B predict=1/2 outer=9/4
nested MSE: 3/2
full development: A=2/3 B=24/25 choose=A predict=1
Worked example 27.1.8
(Perfectly dependent held-out errors in a two-point calculation)
Let be independent fair binary labels, and let a learner trained on one observation predict its label for every input. Use zero-one loss. In ordinary two-fold leave-one-out evaluation, both losses equal . Thus , , and .
The sample standard deviation of the two observed fold losses is always zero: each dataset produces either or . Dividing that zero by would conceal all repeated-sample variation. This is an ordinary-CV dependence example, not a nested run with an impossible inner split of a singleton. The same logical problem remains available in nested evaluation: held-out status alone does not establish independence across outer losses.
Common mistakes
Counterexample mode
Choosing from pooled outer scores turns them into selection data
Consider iid fair binary labels and two prespecified predictors, constant zero and constant one, with zero-one loss. With two observations, each fixed predictor's pooled leave-one-out error is its observed error fraction. Select the smaller of those two fractions and report it as the selected predictor's evaluation.
If the labels agree, the reported minimum is zero; if they disagree, it is . Each case has probability , so the expected report is . Yet whichever constant is selected, its conditional risk on an independent fair fresh label is exactly . Every fixed-candidate held-out prediction was legitimate; choosing the winner using both labels destroyed the proposed final-evaluation interpretation. Here the optimism is exactly in expectation. It does not mean every dataset has a strictly optimistic report.
Repair the information boundary by choosing configurations inside each outer training portion and assessing that complete selector on its excluded observations. An outer comparison used for further selection needs another untouched assessment or an explicitly different inferential analysis.
Counterexample mode
A pooled target-encoding table can contain the held-out answer
Suppose inputs are iid continuous identifiers and labels are independent fair bits. Identifiers are distinct almost surely. Build a lookup table mapping every observed identifier to its observed label before splitting; predict with that table, using zero for an unseen identifier. A supposed cross-validation run that reuses this pooled table scores zero on every held-out observation, because the transformation already stores its label.
A genuinely fresh identifier is absent almost surely, so the resulting predictor's conditional fresh-label error is . If the table is fitted only on the permitted training observations, an excluded identifier is also absent and no longer receives its own answer. A transformation can leak labels before the final estimator is fitted; excluding a row from the final coefficient fit does not undo that earlier use.
Common mistake
(Repeated splits are not new datasets)
Repeated random splits can describe sensitivity to a split recipe, but the repetitions reuse observations. They do not create independent new datasets. Likewise, disagreement among selected configurations describes instability without establishing a probability that a particular model is scientifically correct. For grouped subjects or future-time prediction, design splits around the actual independent sampling unit and target; randomly scattering related records across folds can assess the wrong task.
Concept lens
Three objects that a reported score can describe
The minimum inner score is a selected comparison number. The pooled outer score assesses the declared selection-and-refitting rule at its outer training sizes, under the relevant sampling assumptions. A fresh independent final test assesses the locked final predictor conditional on its development data. They can all be useful, but replacing one label by another changes the claim without changing the arithmetic.
Quick check
Quick check
(Two outer folds have sizes and and mean losses and . Compute the observation-weighted score and the unweighted mean of fold means. Which was defined in this note?)
Count how many observations each fold mean represents.
Solution · Answer
The defined score is . The unweighted mean is . They differ because a loss in the smaller fold receives more weight under an unweighted fold average. Neither arithmetic is inherently impossible, but this note declares equal weight per assessed observation.
Quick check
(A fitting sample has responses . Under squared loss compare inner leave-one-out selection between the fixed predictor one and the sample mean, then give the selected refit prediction.)
Compute the centered sum of squares before applying the exact formula.
Solution · Answer
The fitting mean is one and the centered sum of squares is four. The leave-one-out sample-mean score is . Fixed one has score . Select fixed one and refit according to that configuration, giving prediction one. Identical full-sample predictions do not imply identical inner scores: omitting an observation changes the fitted mean but does not change the fixed predictor.
Quick check
(A nested run uses outer fold sizes , and in a dataset of nine. Under the iid theorem, is its expectation the risk of a procedure trained on six observations? State the actual mixture.)
Each outer training size is nine minus its held-out size.
Solution · Answer
Write for expected fresh loss of the specified size- inner-selection/refitting rule. At a given size, use the same inner split recipe up to relabeling and the same seed law in every iteration. The actual expectation is . It equals only under an additional equality or special relationship among those risks. A simple average of the training sizes is not a theorem equating their risks.
Quick check
(In the fair-label pooled-selection counterexample, replace two observations by three. Compute the expected reported minimum and compare it with fresh-label risk. Explain why refitting the chosen constant cannot repair the report.)
The number of ones has the binomial distribution with parameters three and one half.
Solution · Answer
Let count the ones. For or three, total probability , the reported minimum is zero. For or two, total probability , it is . Its expectation is therefore , whereas the selected constant still has conditional fresh-label risk . The gap remains in this three-observation construction. Refitting a constant has no learned state to change; more generally, refitting cannot turn observations already used for selection into an untouched evaluation sample.