Why selection needs its own data
A learning algorithm may produce several predictors: perhaps one for each regularization strength, network size, or training time. The training loss helps fit each predictor, but it also rewards adaptation to the training sample. Selecting the smallest training loss therefore does not by itself tell us which predictor will perform best on new observations. A validation set provides a second comparison: fit candidates on training data, freeze them, and evaluate each on observations not used in their construction.
The distinction between fitting and selection is essential. Validation data influence the identity of the selected predictor, so its smallest validation loss can be optimistic after searching over many candidates. A final, untouched test set can estimate the risk of the realized selected predictor, conditional on the earlier training and validation data. Estimating a training-averaged procedure risk requires accounting for repeated training and selection. Repeatedly inspecting the test set and changing the procedure in response turns it into another validation set.
Setup and a selection theorem
Let denote all training data and training randomness. Given , choose a finite, nonempty list of measurable predictors ; they may have been trained in arbitrarily complicated ways. The list is frozen before any validation observation is examined.
Definition 20.1.1
(Validation risk and holdout selection)
Let be i.i.d. validation observations with common distribution , independent of , where . For a loss with , the risk and the validation risk of a predictor are
Holdout selection returns an index minimizing over , with ties broken by a fixed deterministic rule.
The expectation in is over a fresh draw, with the trained candidate held fixed. All candidates may be evaluated on the same validation set: they need not have independent validation losses across .
Theorem 20.1.2
(Finite holdout selection)
For , with probability at least over training and validation randomness,
This compares the selected predictor with the best member of the frozen candidate list, not with every conceivable predictor.
Proof
(Condition on training, then apply a union bound)
Condition on . The list is now fixed and each validation loss for a fixed candidate is an i.i.d. random variable in . Hoeffding's inequality gives
A union bound over the candidates does not require independence between their losses. Thus, with conditional probability at least , every deviation is at most . On this event choose a true-risk minimizer in the finite list. Selection gives
The conditional bound is the same for every realization of ; averaging over proves the unconditional claim. A bound exceeding one remains valid but is uninformative for losses in .
Proof X-ray
Where independence and the frozen list are used
Independence of the validation sample from is used once, at the start: it makes the validation observations i.i.d. from even after conditioning on , so each fixed candidate's validation risk is an average of independent bounded terms. This is the only place the training process appears, which is why candidates may be trained in arbitrarily complicated ways.
The key move is to control all deviations on one event before is known. The selected index depends on the validation data, so Hoeffding cannot be applied to directly; on the uniform event, however, every candidate is within , whichever one is chosen. The union bound costs only the factor inside the logarithm and needs no independence between candidates. The chain then closes in three links: deviation for the selected candidate, the selection inequality, and deviation for the best candidate, hence . A list enlarged after looking at validation losses breaks the first step, because the candidates would no longer be fixed given .
The list may depend on training data, and the theorem still applies after conditioning. It may not be expanded adaptively after inspecting the same validation results while retaining the same in the bound. A predetermined larger collection can be covered by its total size, even if a sequential search visits only part of it. Unbounded squared or log loss needs additional tail or boundedness assumptions; the displayed Hoeffding proof does not automatically apply.
The same conditioning argument, with a single candidate, justifies the final test estimate.
Corollary 20.1.3
(An untouched test set estimates the selected risk)
Let be i.i.d. test observations from , independent of and of the validation sample, and let be the average test loss. For , with probability at least ,
Proof
(A single frozen predictor)
Condition on and on the validation sample. Then is one fixed predictor, and its test losses are i.i.d. in with mean . Hoeffding's inequality with gives the bound conditionally, and averaging over the conditioning variables gives it unconditionally. If the test set is consulted again to change the selection, the selected predictor is no longer fixed given the conditioning variables and this argument no longer applies.
Worked comparisons
Worked example 20.1.4
(A numerical guarantee)
Suppose , , and . Then , giving and excess risk at most with probability at least . If the validation losses are and for two particular candidates, the first can be selected only if no other candidate has a smaller loss. This guarantee concerns its true risk relative to the best of all ten, not the claim that its risk equals .
Worked example 20.1.5
(Choosing a threshold)
A training set produces fixed threshold classifiers and . On validation inputs with labels , their predictions are and . Their zero-one validation losses are and ; choose . The example shows the calculation, not evidence that its population error is zero.
Worked example 20.1.6
(When the bound is vacuous, and when there is nothing to select)
In the threshold example, and . With , , so the bound is . A zero-one excess risk never exceeds one, so the guarantee is valid but says nothing. Requiring gives , so validation observations would suffice for excess .
At the other extreme, makes the left side zero: with one candidate there is no selection to pay for. The validation set then plays the role of a test set, and the corollary with gives the accuracy of its estimate.
A leakage counterexample
Counterexample mode
A candidate built from the validation labels
Claim: the selection bound holds for any finite list, however it was produced. Let inputs be distinct continuous identifiers, independent of the labels, and let each label be with probability , independently. Take : the constant predictor , with risk , and a lookup table built after reading the validation labels, which returns the memorized label on a validation identifier and on any other. A fresh identifier is unseen with probability one, so .
On the validation set has loss , while has loss equal to the fraction of positive labels, which is positive unless all labels are (probability ). So is selected and the excess risk is . With and the bound is , and it fails with probability at least . The hypothesis violated is that the list is fixed given and independent of the validation sample; calling the same records a holdout does not repair the argument.
A separate test set must also be sampled in a way relevant to the intended deployment. Independence alone does not fix a distribution shift between the test population and future users. When samples come from the same person or a time series, a random row split may fail to represent the intended prediction task; the split must respect the dependence and the time at which information becomes available.
Common mistake
(Fitting preprocessing on all records before splitting)
Fitting a scaler, imputer, feature selector, or vocabulary on all records before splitting lets validation information enter every candidate, so the candidates are no longer independent of the validation sample. Fit such transformations using the training portion only, and apply the fitted transformation to validation and test records.
Common mistake
(Reporting the smallest validation loss as the risk)
The minimum validation loss is biased downward. Let labels be fair coins independent of the inputs, and compare a classifier with its complement ; both have risk . On a single validation point exactly one of them is correct, so the smaller validation loss is always . The theorem bounds the selected risk relative to the best candidate; an estimate of the selected risk itself needs fresh data, as in the corollary.
Exercises with solutions
Quick check
(If with , give the selection bound.)
Solution · Answer
Apply the theorem to , which takes values in and has the same minimizers. Multiplying back by gives .
Quick check
(Find a sufficient to guarantee excess at most with confidence for .)
Solution · Answer
Require , so . Taking suffices. This is sufficient, not a necessary minimum.
Quick check
(For fixed , what happens to the bound if is doubled?)
Solution · Answer
The expression under the square root increases by ; equivalently, the square of the bound increases by . The bound grows; the actual risk need not grow, since a richer list can also contain a better predictor.
Quick check
(A team picks the better of two models on a test set, then reports the smaller test error as an unbiased estimate of the chosen model's risk. Is this justified?)
Solution · Answer
No. The choice depends on the reported test errors. Even if each fixed model's test error is unbiased, the minimum of the two estimates is generally downward biased relative to the minimum of their risks. Freeze the choice using validation data, then evaluate once on an independent test set.