What Is Uncertain After Selection?
A validation score can serve two roles: it can help choose among candidate models, and it can estimate how well the chosen model will perform on new data. Using the same score for both roles creates a problem. The chosen model is the one that looked best on the validation sample, so its score tends to include a favorable accident of that sample. The resulting score is not generally an ordinary, unbiased estimate of the selected model’s risk.
Uncertainty assessment also depends on the target. One target is the risk of the particular fitted model selected using the development data. Another is the risk of the entire procedure that fits candidates, tunes them, and selects among them when given a new training sample. Fresh test data and nested cross-validation address these targets differently.
Selection Makes the Minimum Score Optimistic
Suppose a development sample \(D\) is used to fit a fixed collection of \(M\) candidate predictors \(f_1(D),\ldots,f_M(D)\). A separate validation sample \(V=(Z_1,\ldots,Z_n)\) is used to calculate their scores. For a loss function \(L\), define the conditional risk of candidate \(m\), given \(D\), by
Here \(Z\) is a new observation from the target population. If the validation observations are independent of \(D\) and are independent draws from that population, the validation score is
For a fixed candidate, \(E[\widehat R_m\mid D]=R_m(D)\). But if the selected index is \(\hat m=\arg\min_m\widehat R_m\), the minimum is chosen partly because of random validation fluctuations. The following result makes the direction of this effect precise.
Proof. For every realization of the validation sample, \(\widehat R_{\hat m}=\min_m\widehat R_m\). Therefore
The inequality follows because the minimum of a finite collection is no larger than any one member, so its expectation is no larger than the expectation of any candidate score. Also, for every validation sample, \(R_{\hat m}(D)\geq\min_m R_m(D)\). Taking conditional expectations gives \(E[R_{\hat m}(D)\mid D]\geq\min_m R_m(D)\). Combining the inequalities proves the result. Equality can occur, for example, if there is only one candidate or the scores do not vary. \(\square\)
This is a statement about average optimism, not a guarantee that every selected score is too small. It also depends on the candidate set being fixed independently of the validation observations. If analysts repeatedly change models after seeing validation results, the candidate set itself has been adapted to those results, and the simple argument does not account for that additional reuse.
Worked Example: Two Candidates and One Validation Observation
Consider two fixed candidates with equal risk \(1/2\). For illustration, suppose each candidate’s loss on the one validation observation is Bernoulli with success probability \(1/2\), independently across candidates. Each score is individually unbiased: its expectation is \(1/2\).
The selected score is the smaller of the two losses. Since the losses are either 0 or 1, their minimum is 1 only if both are 1. Thus
The selected candidate still has risk \(1/2\), because both candidates have that risk. The selected validation score averages \(1/4\), which is lower by \(1/4\). This deliberately small example isolates selection: unbiased candidate scores do not make their minimum unbiased for the risk of the selected candidate.
Fresh Test Data: Risk of the Selected Fitted Model
After all fitting, tuning, and selection decisions are complete, a fresh test sample can estimate the risk of the resulting fitted model. The test observations must not have been used to choose the candidate set, tune it, select a model, or otherwise modify the analysis. Conditional on all development data and decisions, the selected predictor is then fixed.
Proof. Given \(D^\ast\), the predictor \(f^\ast\) is fixed. Independence and identical distribution of the test observations imply that each loss has conditional expectation \(R(f^\ast)\) and conditional variance \(\operatorname{Var}_Z(L(f^\ast,Z)\mid D^\ast)\). Linearity of expectation gives \(E[\widehat R_{\mathrm{test}}\mid D^\ast]=R(f^\ast)\). Independence makes the conditional covariances between distinct test losses zero, so the variance of their average is the single-loss variance divided by \(N\). \(\square\)
This statement concerns the risk of the particular fitted predictor, conditional on its development history. It does not say that the test score estimates the average performance of the full training-and-selection procedure over new development samples. Nor does one test score quantify every source of uncertainty in future deployment, such as population shift.
Worked Example: A Test-Set Interval for a Selected Classifier
A classification procedure is fully tuned and selected using development data. It is then evaluated on 100 independent test observations. It misclassifies 18, so the test error estimate is \(18/100=0.18\). Treat misclassification loss as lying in \([0,1]\).
For independent losses in \([0,1]\), Hoeffding’s inequality gives \(P(|\widehat R_{\mathrm{test}}-R(f^\ast)|\geq\epsilon\mid D^\ast)\leq 2\exp(-2N\epsilon^2)\). Setting the right-hand side to \(0.05\) and solving yields
Consequently, a two-sided Hoeffding interval is approximately \([0.18-0.136,\;0.18+0.136]=[0.044,\;0.316]\), clipped to the possible risk range \([0,1]\). Its coverage is at least 95% conditional on the development data, under the stated independence and sampling assumptions. The interval is wide because a distribution-free bound can be conservative; it should not be read as evidence that the true error is exactly near either endpoint.
Nested Cross-Validation: Risk of a Selection Procedure
Nested cross-validation separates tuning from evaluation within the available data. In each outer split, the inner analysis uses only the outer training portion to fit and select a model. That entire fitted-and-selected pipeline is then evaluated on the outer holdout. The outer holdout therefore evaluates the selection procedure as applied to that outer training sample, rather than evaluating candidates using scores that chose among them.
For a \(K\)-fold outer split of \(n\) independent observations, each outer training set has size \(s=n(K-1)/K\), assuming equal folds. Let \(A\) denote the whole inner fitting and selection procedure, including any specified algorithmic randomness. Define its size-\(s\) risk by
where \(D_s\) is an independent training sample of size \(s\), and \(Z\) is a new observation independent of that sample. Under independent and identically distributed sampling and a split independent of the observed values, the expected outer-fold average targets \(R_s\). Indeed, for each fold, its training observations are independent of its held-out observations. Conditional on that training set, each held-out loss has expectation equal to the risk of the pipeline fitted on that set. Averaging those losses and then taking expectation over training sets gives \(R_s\); averaging across the \(K\) folds preserves that expectation. This expectation argument does not make the fold scores independent.
The distinction in target matters. Nested cross-validation estimates performance for a pipeline trained on the outer training-set size, not exactly the risk of a final model refit on all \(n\) observations. Its result can be useful for comparing procedures or estimating their performance at the corresponding training size, but a gap between \(R_s\) and the risk at size \(n\) may remain.
Worked Example: Reading an Outer-Fold Summary
Suppose four outer folds give losses \(0.20, 0.25, 0.15,\) and \(0.30\). The nested cross-validation estimate is their average:
The sample variance of these four fold losses is \((0.000625+0.000625+0.005625+0.005625)/3=0.004167\), giving a sample standard deviation of about \(0.0645\). Dividing by \(\sqrt{4}\) would produce \(0.0323\), but that calculation is not automatically a valid standard error: outer training sets overlap, and the fold scores share observations and fitted-data information. The mean \(0.225\) is the reported point estimate; the fold-to-fold spread is descriptive unless an uncertainty method justifies its inferential interpretation.
Choosing an Uncertainty Assessment
| Assessment | Main target | Key condition or limitation |
|---|---|---|
| Fresh independent test sample | Risk of the particular selected fitted model | Test data must remain unused throughout model development. |
| Nested cross-validation | Risk of the fitting-and-selection procedure at the outer training size | Outer-fold scores are dependent; the target need not equal full-sample refit risk. |
| Reused selection validation score | Generally optimistic score of the selected candidate | The same random scores both choose and assess the winner. |
A fresh test sample is especially direct when the scientific question concerns one final fitted model and enough independent data can be reserved. Nested resampling is useful when an external test sample is unavailable and the question concerns a repeatable tuning pipeline. Neither choice removes the need to define the target population, loss, and training size.
Common Pitfall
Wrong reasoning: “Every candidate’s validation score is unbiased, so the score of the candidate with the smallest value is unbiased too.” The premise applies to each fixed candidate separately; it does not survive choosing the minimum. The selection rule favors candidates with unusually low validation noise as well as genuinely low risk.
Correction: Keep selection and evaluation separate. Use fresh data untouched by all selection decisions to estimate the final fitted model’s risk, or evaluate the whole selection pipeline in outer folds. Do not treat the selected validation score as an ordinary independent estimate, and do not infer a standard error merely by dividing the standard deviation of dependent fold scores by the square root of the fold count.
Check Your Understanding
Answer each question by identifying the target and the relevant independence condition.
- Why can the minimum of several individually unbiased validation scores be biased downward?
- What must remain independent of the development process for a test score to be conditionally unbiased for the selected fitted model’s risk?
- In a nested cross-validation design, what does the outer holdout evaluate, and what training size does the resulting estimate most directly address?
- Why is the standard deviation of outer-fold scores not, by itself, a justification for a standard error obtained by dividing by the square root of the number of folds?
- If the selected model is refit using all available observations after nested cross-validation, does the nested estimate exactly target that refitted model’s risk? Explain.