Cross-Validation and the Bootstrap: Error and Uncertainty from One Sample

What a Model Learns ended with a rule: fit on training data, choose on validation data, report on test data once. With a large data set that is easy. With a small one, every observation set aside for validation is missing from the training set, and a single split gives an estimate that depends on luck. Resampling methods use the same data several times, refitting the model on different subsets, to get more out of it.

This post covers the two most important ones. Cross-validation estimates how well a model will predict new data, to compare and choose models. The bootstrap estimates how uncertain a statistic is, from a single sample. Both are simple, both are widely misused, and three things often called “bootstrap” are in fact different methods. Every claim below is measured.

---

1. Resampling

A resampling method repeatedly draws samples from the training data and refits a model on each, to learn something a single fit cannot tell: how the fit would change with different data. Two tasks need this:

Task	Question	Typical tool
Model assessment	How large will the error be on new data?	cross-validation
Model selection	Which model, or which flexibility, is best?	cross-validation
Uncertainty of an estimate	How much would this number change with another sample?	bootstrap

The running example for cross-validation is the one from the earlier posts: polynomials of degree 1 to 10 fitted to noisy points from $f(x)=\sin (2\pi x)+x/2$ (noise standard deviation 0.3), now with 100 observations, so that the truth is known and every estimate can be checked.

---

2. Three Ways to Hold Data Out

The validation set approach

Split the data at random into a training and a validation half; fit each candidate model on the first and compute its MSE on the second. Simple, with two weaknesses, both visible in the data set of 100 points:

1. It depends on the split. Ten random 50/50 splits of the same data gave ten different error curves, which chose degrees 3, 3, 5, 5, 5, 6, 6, 8, 8 and 8.
2. It trains on half the data, and a model fitted to fewer points predicts worse, so the validation error overestimates the error of the model fitted to all of them.

k-fold cross-validation

Divide the data at random into $k$ folds of about equal size. Use each fold once as the validation set, train on the other $k-1$, and average the $k$ errors:

$${\text{CV}}_{(k)}=\frac{1}{k}\sum _{i=1}^k{\text{MSE}}_i.$$

(For classification, the misclassification rate replaces the MSE.) Every observation is used for training $k-1$ times and for validation once, and the result no longer hinges on a single split. $k=5$ or $10$ is standard. For classification with rare classes, stratified folds keep the class proportions equal in every fold; for time series, folds must respect time order, or the model is validated on its own past’s future (Bergmeir & Benítez, 2012).

Leave-one-out cross-validation (LOOCV)

LOOCV is k-fold with $k=n$: each observation is held out alone and predicted by a model fitted to the other $n-1$. That sounds like $n$ fits, but for least squares (and other linear smoothers) a single fit is enough:

$${\text{CV}}_{(n)}=\frac{1}{n}\sum _{i=1}^n{\left(\frac{y_i-{\hat{y}}_i}{1-h_i}\right)}^2,$$

where $h_i$ is the leverage of observation $i$, a diagonal element of the hat matrix. On the data set of 100 points, the shortcut and 100 actual refits gave the same number to ten decimal places (0.0974548162 for degree 3).

Degree (n = 100)	True test MSE · LOOCV	5-fold · 10-fold CV
1	0.291 · 0.356	0.359 · 0.349
3	0.098 · 0.098	0.094 · 0.096
5	0.097 · 0.090	0.088 · 0.093
10	0.101 · 0.096	0.106 · 0.097
Degree chosen	5 · 5	5 · 6

From degree 3 on, all the true errors lie between 0.096 and 0.101: the curve is flat, so which of those degrees is chosen hardly matters. What matters is that every method rejected degrees 1 and 2, the real mistake.

---

3. What Cross-Validation Actually Estimates

Cross-validation is usually described as an estimate of “the test error of the model”. Measured over 1,000 data sets of 50 points (degree 3), against each fitted model’s own test error on 20,000 new points:

Estimate	Mean · bias	Spread over data sets · correlation with this model’s own error
True test error	0.1040 · –	0.0073 · –
Validation set (25/25)	0.1175 · +0.0135	0.0476 · +0.02
5-fold CV	0.1071 · +0.0032	0.0236 · −0.03
10-fold CV	0.1060 · +0.0020	0.0229 · −0.01
LOOCV	0.1049 · +0.0009	0.0222 · −0.02

Three findings:

1. All estimates are slightly pessimistic, more so the less they train on: the validation set, which trains on half, is 13% too high; LOOCV, which trains on all but one, is nearly unbiased.
2. LOOCV did not have the highest variance here. A common claim says that LOOCV has lower bias but higher variance than k-fold CV, because its $n$ training sets are nearly identical and their errors highly correlated. In this experiment LOOCV’s estimates varied slightly less (0.0222) than 10-fold’s (0.0229) and 5-fold’s (0.0236). The claim is a statement about some models, not a theorem: for stable methods such as least squares, LOOCV’s variance is not larger, while for unstable ones (trees, nearest neighbours) it can be (Burman, 1989; Bengio & Grandvalet, 2004; Zhang & Yang, 2015). 5- and 10-fold CV remain the usual choice because they are cheaper and rarely much worse.
3. No estimate tracks the error of the particular fitted model. Each fitted model’s own test error varies from one data set to the next (sd 0.0073), and the correlation between that error and any CV estimate is essentially zero. Cross-validation estimates the average test error of the method over training sets of this size, not the error of the model in hand (Bates, Hastie & Tibshirani, 2024). This is enough to compare methods, and the reason it should not be quoted as “this model’s accuracy”.

---

4. The Wrong and the Right Way

Cross-validation only works if the validation fold plays no part in building the model. A common violation is to select predictors on the full data and cross-validate only the final fit (Hastie et al., 2009, §7.10.2). An extreme test: 50 observations, 5,000 predictors of pure noise, class labels assigned at random, so that the true error rate of every classifier is 0.5. Keep the 100 predictors most correlated with the labels, then classify with one nearest neighbour, using 5-fold CV (50 data sets):

Where the screening happens	Cross-validated error rate
On all 50 observations, before CV	0.012
Inside each fold, on its training part only	0.516
Truth	0.500

Screening first found the 100 predictors that happened to correlate with these labels, including in the observations that would later be validation folds; CV then reported almost perfect accuracy on pure noise. The rule is general: every step that learns from the data (selecting predictors, choosing a transformation, tuning a hyperparameter, even standardising with the data’s mean) belongs inside the cross-validation loop. When CV is used to choose a model, the chosen model’s CV error is itself optimistic for the same reason (§8 of What a Model Learns); an honest estimate then needs a second, outer loop (nested cross-validation; Varma & Simon, 2006) or an untouched test set.

---

5. The Bootstrap

The bootstrap (Efron, 1979) estimates the uncertainty of a statistic, its standard error or a confidence interval, when there is no formula for it, or when the formula’s assumptions are doubtful. The name comes from pulling oneself up by one’s own bootstraps: the method creates new data sets out of the one available.

The example: a portfolio

Two assets return $X$ and $Y$. Investing a fraction $\alpha$ in $X$ and $1-\alpha$ in $Y$, the risk $\mathrm{Var}(\alpha X+(1-\alpha )Y)$ is smallest at

$$\alpha =\frac{{\sigma }_Y^2-{\sigma }_{XY}}{{\sigma }_X^2+{\sigma }_Y^2-2{\sigma }_{XY}},$$

and $\alpha$ is estimated by plugging in the sample variances and covariance. With ${\sigma }_X^2=1$, ${\sigma }_Y^2=1.25$, ${\sigma }_{XY}=0.5$, the true value is $\alpha =0.6$. How precise is $\hat{\alpha }$ from 100 observations?

If the population were known, the answer would be simulation: draw 1,000 new samples of 100 from it, compute $\hat{\alpha }$ on each, and take the standard deviation. Here: mean 0.599, standard deviation 0.083. In practice the population is unknown and only one sample exists.

The bootstrap treats that one sample as a stand-in for the population. It draws $B$ new data sets of the same size from the sample itself, with replacement, computes the statistic on each, and uses their spread:

$${\mathrm{SE}}_B(\hat{\alpha })=\sqrt{\frac{1}{B-1}\sum _{r=1}^B{\left({\hat{\alpha }}^{\ast r}-\overline{{\hat{\alpha }}^{\ast }}\right)}^2}.$$

Sampling with replacement means that some observations appear several times in a resample and others not at all. The chance that a given observation appears at least once is $1-(1-1/n{)}^n$, which tends to $1-1/e=0.632$:

n	Probability an observation is in a resample	Simulated share
10	0.6513	0.6495
100	0.6340	0.6344
1,000	0.6323	0.6325

The sample used in the lab gave $\hat{\alpha }=0.557$ and a bootstrap SE of 0.057 from 1,000 resamples, with a 95% percentile interval of [0.447, 0.672]. That SE is lower than the true 0.083: the bootstrap inherits the luck of its one sample. Over 200 different samples, the bootstrap SE averaged 0.079, with the middle 90% between 0.063 and 0.101. It is an estimate, and a good one on average.

Three things called resampling

The bootstrap is often confused with two neighbours:

• Drawing new samples from the population (measure 5 students, then 5 more, and so on, 20 times) is ordinary repeated sampling. It is what the bootstrap tries to imitate, and it needs access to the population; the bootstrap needs only the one sample.
• Bagging (bootstrap aggregating; Breiman, 1996) fits a model to each bootstrap resample and averages the predictions into a new model. It uses bootstrap resamples, but its goal is a better, more stable predictor, not a measure of uncertainty. It is the basis of random forests, in the next post.

When the formula and the bootstrap disagree

For the mtcars slope of Linear Regression, Read Correctly, the textbook formula gives a standard error of 0.559. Resampling the 32 cars (5,000 resamples) gives 0.714, and a percentile interval of [−6.96, −4.14] against the formula’s [−6.49, −4.20]. The formula assumes the model is right: a straight line with constant noise. That post found curvature in the data, and resampling whole cars carries such misspecification into the standard error, where the formula ignores it. A large gap between the two is a hint that the model’s assumptions deserve a look.

Where the bootstrap fails

The bootstrap assumes the statistic behaves smoothly when the data change a little. The sample maximum does not: a resample can never exceed the sample’s largest value, and it contains that value with probability 0.636 (for n = 50; measured 0.636). For 50 draws from Uniform(0, 1), the bootstrap distribution of the maximum is a spike at the sample maximum, and a nominal 95% bootstrap interval covered the true maximum (1) in only 88.2% of 1,000 samples. Extremes, boundaries and very small samples need other methods.

---

6. Common Claims, Checked

Claim	Verdict
”CV_(k) = Σ MSEᵢ.”	That is a sum. The k-fold estimate is the average: (1/k) Σ MSEᵢ.
”A validation set gives a reliable error estimate.”	Ten 50/50 splits of the same 100 points chose degrees from 3 to 8; over 1,000 data sets its estimate was 13% too high and twice as variable as 5-fold CV’s.
”LOOCV has lower bias but higher variance than k-fold CV.”	Lower bias, yes (+0.0009 vs. +0.0032). Higher variance, not here: 0.0222 vs. 0.0229 (10-fold) and 0.0236 (5-fold). It depends on how stable the method is.
”LOOCV needs n refits.”	Not for least squares: the leverage shortcut matched 100 refits to ten decimals.
”CV tells you the test error of your model.”	It estimates the average error of the method over training sets of that size; its correlation with the fitted model’s own error was about 0.
”Select predictors on all the data, then cross-validate.”	On pure noise this reported an error of 0.012; screening inside each fold gave 0.516 (truth 0.5). Every data-driven step goes inside the loop.
”Bootstrap: measure 5 students, repeat 20 times, average.”	That is repeated sampling from the population. The bootstrap resamples one sample, with replacement.
”In the bootstrap, a model is fitted to each sample and the results are averaged into the final model.”	That is bagging. The bootstrap measures uncertainty (SE 0.079 vs. a true 0.083 on average); bagging builds a better model.
”The bootstrap SE equals the true SE.”	On average, roughly (0.079 vs. 0.083 over 200 samples); for one sample it can be well off (0.057).
”If the formula SE and the bootstrap SE differ, the bootstrap is wrong.”	Often the formula is: for mtcars, 0.559 vs. 0.714, because the formula assumes a linear model with constant noise.
”The bootstrap works for any statistic.”	Not for the maximum: 63.6% of resamples repeat the sample maximum, and the 95% interval covered the truth 88.2% of the time.
”A bootstrap sample contains most of the data.”	About 63.2% of the distinct observations (1 − 1/e); the other 36.8% are “out of bag”, which bagging uses for validation.

---

Summary

Idea	In one line
Validation set	Simple, but split-dependent and pessimistic
k-fold CV	Average of k fold errors; k = 5 or 10; stratify classes, respect time order
LOOCV	Least biased; a one-fit shortcut for least squares; variance depends on the method
What CV estimates	The method’s average error over training sets, not this model’s error
Right way	Every data-driven step inside the loop; nested CV to assess a chosen model
Bootstrap	Resample the one sample with replacement to estimate SEs and intervals
Not the bootstrap	Sampling the population again (simulation), averaging models (bagging)
Limits	Fails for extremes and boundaries; inherits its one sample’s luck

Next: Decision Trees and Their Ensembles: Bagging, Random Forests and Boosting: trees built from scratch, pruned by cross-validation, measured for instability, and combined by the hundred.

The experiments: resampling.py (numpy 2.1, seeded). The lab runs cross-validation, the screening experiment (with 2,000 instead of 5,000 predictors, to stay fast) and the bootstrap in the browser, with the polynomial fits verified against numpy in What a Model Learns; its random draws are its own, so its values differ slightly from the seeded runs in the text.

---

References

Cross-validation

• Stone, M. (1974). Cross-validatory choice and assessment of statistical predictions. Journal of the Royal Statistical Society B, 36(2).
• Burman, P. (1989). A comparative study of ordinary cross-validation, v-fold cross-validation and the repeated learning-testing methods. Biometrika, 76(3).
• Bengio, Y., & Grandvalet, Y. (2004). No unbiased estimator of the variance of k-fold cross-validation. Journal of Machine Learning Research, 5.
• Varma, S., & Simon, R. (2006). Bias in error estimation when using cross-validation for model selection. BMC Bioinformatics, 7.
• Bergmeir, C., & Benítez, J. M. (2012). On the use of cross-validation for time series predictor evaluation. Information Sciences, 191.
• Zhang, Y., & Yang, Y. (2015). Cross-validation for selecting a model selection procedure. Journal of Econometrics, 187(1).
• Bates, S., Hastie, T., & Tibshirani, R. (2024). Cross-validation: What does it estimate and how well does it do it? Journal of the American Statistical Association, 119(546).

The bootstrap and bagging

• Efron, B. (1979). Bootstrap methods: Another look at the jackknife. Annals of Statistics, 7(1).
• Efron, B., & Tibshirani, R. J. (1993). An Introduction to the Bootstrap. Chapman & Hall.
• Bickel, P. J., & Freedman, D. A. (1981). Some asymptotic theory for the bootstrap. Annals of Statistics, 9(6).
• Breiman, L. (1996). Bagging predictors. Machine Learning, 24(2).

Textbooks

• James, G., Witten, D., Hastie, T., & Tibshirani, R. (2021). An Introduction to Statistical Learning (2nd ed.). Springer.
• Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed.). Springer.