Why Correct Apparent Risk?
A prediction procedure is often more than a fixed model: it may fit parameters, compare candidate models, tune hyperparameters, and choose one based on the observed data. Its training loss is then measured on the same observations that shaped those choices. It typically looks better than performance on new observations. Bootstrap optimism correction estimates this gap by repeating the entire data-dependent procedure on bootstrap samples.
The procedure being assessed must be defined clearly. If model selection is part of what a practitioner will do with a new training sample, then the target is the performance of that fitted-and-selected procedure—not the performance of the model that happened to win on one particular data set.
Definition of Optimism and Its Bootstrap Estimate
Let \(Z_1,\ldots,Z_n\) be independent observations from a distribution \(P\), and let \(D_n=(Z_1,\ldots,Z_n)\). A learning procedure \(A\) maps a training data set to a predictor \(f_{D_n}=A(D_n)\); any fitting and selection steps are included in \(A\). Let \(\ell(f,z)\) be a measurable loss, assumed integrable for the predictors and distributions under consideration. Write \(P g=E[g(Z)]\) for expectation over a fresh observation and \(P_n g=n^{-1}\sum_{i=1}^n g(Z_i)\) for the empirical average.
The test-risk term uses a new observation independent of the training data. In contrast, the apparent-risk term evaluates the fitted procedure on its own training observations. The expectation in \(O_n\) averages over possible training data sets; optimism is not necessarily positive for every realized data set.
For the bootstrap estimate, draw \(D_n^*=(Z_1^*,\ldots,Z_n^*)\) independently from the empirical distribution \(P_n\), conditional on the observed data. Fit and select \(f_{D_n^*}=A(D_n^*)\). The bootstrap sample has \(n\) draws with replacement, so some original observations can appear more than once and some not at all. Define \(P_n^*g=n^{-1}\sum_{i=1}^n g(Z_i^*)\).
In computation, the conditional expectation is usually approximated with \(B\) bootstrap replicates: average the difference between each bootstrap-fitted procedure’s loss on the original data and its loss on that bootstrap sample. The original-data evaluation is sometimes called the bootstrap test evaluation, but it is not a genuinely independent test set. The estimate is a plug-in approximation: \(P_n\) stands in for the unknown \(P\), and the empirical distribution generates the resamples.
Two Identities That Clarify the Correction
The first identity makes explicit what the correction targets. It does not require a special model class; it follows from the definitions, provided the losses are integrable and the observations are identically distributed and independent.
Conditional on \(D_n\), the predictor is fixed and \(Z_{n+1}\) has distribution \(P\). Thus \(E[\ell(f_{D_n},Z_{n+1})\mid D_n]=P\ell(f_{D_n},\cdot)\).
By definition, \(P_n\ell(f_{D_n},\cdot)=n^{-1}\sum_{i=1}^n\ell(f_{D_n},Z_i)\).
Taking expectations of the two expressions in Steps 1 and 2 gives exactly the definition of \(O_n\). The integrability assumption ensures these expectations exist. \(\square\)
The bootstrap uses the same difference in a conditional, empirical world. It does not make that difference an exact estimate of the population optimism in every finite sample. Its usefulness depends on whether resampling from \(P_n\) reasonably represents the data-generating process for the procedure at hand.
A second identity explains why refitting matters. If a predictor \(f\) is held fixed through bootstrap resampling, then its conditional expected bootstrap difference is zero:
To prove this, condition on the data, so the values \(\ell(f,Z_i)\) are fixed. Each bootstrap draw has distribution \(P_n\), and therefore \(E_*[P_n^*\ell(f,\cdot)]=P_n\ell(f,\cdot)\). Subtracting the two equal quantities proves the result. \(\square\)
This result is not a claim that a data-selected predictor has no optimism. It says that if one keeps the predictor fixed while resampling, one removes the predictor’s dependence on the resampled data from the bootstrap calculation. To estimate the optimism of a fitted-and-selected procedure, refit and reselect inside each resample.
Worked Calculations
Worked Example: Bootstrap Correction for a Selected Classifier
There are four observed binary labels, \(0,0,0,1\). The procedure chooses between two constant classifiers, predicting all 0 or all 1, by minimizing training misclassification rate. In a tie it chooses all 1. What is the apparent risk and what correction results from the exact conditional bootstrap expectation?
On the original data, predicting all 0 makes one error out of four, while predicting all 1 makes three. The selected classifier predicts 0, so its apparent risk is \(1/4\).
In a bootstrap sample, let \(K\) be the number of label-1 draws. Then \(K\) has a binomial distribution with four draws and success probability \(1/4\). The procedure selects all 1 when \(K\geq 2\) and all 0 otherwise. The table gives the bootstrap probability, the bootstrap training loss, the loss on the original data, and their difference \(P_n\ell-P_n^*\ell\):
| \(K\) | Bootstrap probability | Bootstrap loss | Original-data loss | Difference |
|---|---|---|---|---|
| 0 | \(81/256\) | 0 | \(1/4\) | \(1/4\) |
| 1 | \(108/256\) | \(1/4\) | \(1/4\) | 0 |
| 2 | \(54/256\) | \(1/2\) | \(3/4\) | \(1/4\) |
| 3 | \(12/256\) | \(1/4\) | \(3/4\) | \(1/2\) |
| 4 | \(1/256\) | 0 | \(3/4\) | \(3/4\) |
For example, when \(K=2\), the tie rule selects all 1. It makes two errors in the bootstrap sample, giving bootstrap loss \(2/4\), and three errors on the original data, giving original-data loss \(3/4\). Averaging the differences gives $$ \widehat O_{\mathrm{boot}} =\frac{81+54+24+3}{1024} =\frac{162}{1024} =0.158203125. $$ The corrected apparent risk is \(0.25+0.158203125=0.408203125\). This exact bootstrap calculation is illustrative; it does not establish that the corrected value equals the true risk.
Worked Example: Why Selection Must Be Repeated
Consider four cases with labels \((0,0,1,1)\). Candidate A predicts \((0,0,0,0)\), and candidate B predicts \((0,0,1,0)\). The procedure selects the candidate with smaller training misclassification rate, breaking ties in favor of A. Three bootstrap samples are \((1,2,3,3)\), \((1,1,2,2)\), and \((3,4,4,4)\), where indices refer to the original cases. Calculate their optimism differences.
On the original data, A makes two errors and B makes one, so the selected model is B and the apparent risk is \(1/4\).
For sample \((1,2,3,3)\), A’s bootstrap loss is \(2/4\) and B’s is \(0/4\), so B is selected. B’s original-data loss is \(1/4\), giving optimism difference \(1/4-0=1/4\).
For sample \((1,1,2,2)\), both candidates have zero bootstrap loss, so the tie rule selects A. A’s original-data loss is \(2/4\), giving difference \(2/4-0=1/2\).
For sample \((3,4,4,4)\), A’s bootstrap loss is \(4/4\), while B’s is \(3/4\), so B is selected. B’s original-data loss is \(1/4\), giving difference \(1/4-3/4=-1/2\). The mean difference across these three deliberately limited replicates is \((1/4+1/2-1/2)/3=1/12\). Adding it to the apparent risk gives \(1/4+1/12=1/3\).
If instead the original winner B were held fixed in every bootstrap sample, the three bootstrap losses would be \(0,0,3/4\). The corresponding differences would be \(1/4,1/4,-1/2\), with mean zero. This calculation shows how suppressing reselection can omit a source of optimism. Three replicates are far too few for a reliable Monte Carlo estimate; the arithmetic illustrates the procedure, not a recommended choice of \(B\).
Worked Example: Resample Clusters, Not Their Members Independently
Suppose four patients come from two clinics: the two patients in clinic A have losses \(0,0\), and the two in clinic B have losses \(1,1\). Treating all four patients as independent resampling units gives a different bootstrap distribution from resampling the two clinics as units.
For a sample of size four drawn from the empirical distribution of patient losses, each draw is 0 or 1 with probability \(1/2\). The bootstrap mean loss has variance \((1/2)(1/2)/4=1/16\).
If clinics are the sampling units, resample two clinics with replacement and retain both patients in each selected clinic. The bootstrap mean loss is 0 if A is drawn twice, 1 if B is drawn twice, and \(1/2\) if one clinic of each type is drawn. These values have probabilities \(1/4,1/4,1/2\), respectively. The mean is \(1/2\), and the variance is \((1/4)(0-1/2)^2+(1/4)(1-1/2)^2+(1/2)(1/2-1/2)^2=1/8\). Independent patient resampling therefore understates variability in this example. For optimism correction, the same principle applies: the resampling unit should reflect the independent sampling unit, not automatically the row in a data table.
Practical Interpretation and Common Pitfalls
The correction addresses a useful target: expected fresh-data performance of the full procedure trained on \(n\) observations. But it is an estimate, not a guarantee of unbiasedness or a substitute for every assessment design. Its accuracy can be affected by small samples, rare categories, unstable selection, and the mismatch between the empirical distribution and the population. Report the correction as such, and avoid interpreting a negative estimate or a value above the possible range of a bounded loss as proof of a calculation error; finite-sample estimates can behave that way.
- Leaving out selection. Refitting only the model selected on the original data estimates a different procedure. Repeat the selection rule, including any tuning or data-driven preprocessing that would be repeated in actual use.
- Using the wrong resampling unit. Resampling individual rows as if independent is not justified when the sampled units are clusters or other dependent groups. Preserve the independent units represented by the study design.
- Calling the original-data evaluation independent test risk. Bootstrap samples are drawn from those same original observations. The contrast is a plug-in estimate, not an independent validation experiment.
- Confusing the correction with a guarantee. Adding estimated optimism does not ensure unbiased performance assessment. The target, sampling assumptions, and uncertainty in the correction still matter.
Check Your Understanding
Use the definitions and calculations above to test your understanding.
- In the definition of optimism, why is the fresh observation independent of the data used to fit the predictor?
- What two losses are subtracted in the conditional bootstrap estimate of optimism?
- Why does holding a predictor fixed through resampling give conditional expected bootstrap optimism equal to zero?
- In a procedure that selects a tuning parameter from the data, which steps should be repeated in each bootstrap sample?
- Give an example of a study design where resampling rows independently would use the wrong resampling unit, and state an appropriate unit instead.