# bootstrap

*Entry of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org) (course edition), by Alexander Jung, Aalto University. CC BY 4.0. Updated 2026-11-08. [HTML](https://dictionaryofml.org/terms/bootstrap.html) · [typeset PDF](https://dictionaryofml.org/terms/bootstrap.pdf) · [LaTeX](https://dictionaryofml.org/terms/bootstrap.tex) · [Python demo](https://dictionaryofml.org/terms/bootstrap.py) · [notebook](https://dictionaryofml.org/terms/bootstrap.ipynb)*

Math is LaTeX with the book's macros expanded, so no notation package is needed to read it.

## Abstract

The bootstrap is a stochastic algorithm that generates perturbed variants, referred to as bootstrap samples, of a given dataset. Each bootstrap sample is obtained by randomly selecting data points, with replacement, from the original dataset. The bootstrap samples have the same size as the original dataset. However, they might repeat some of the original data points while omitting others. Several bootstrap samples allow the study of the properties of a machine learning method. For example, a robust machine learning method delivers similar model parameters for two datasets that differ only in the random fluctuations of the data generation. Bootstrap samples can also be used to estimate a confidence interval for a validation error. Another application of the bootstrap is bagging, where the hypotheses learned from the bootstrap samples are aggregated into one.

## Definition

Five days of weather recordings at Krems an der Donau are all the data there is. Each day is a data point, its feature the minimum temperature of the day and its label the maximum temperature of the same day (Fig. 1). This dataset is small: it does not allow the training of a high-dimensional model, and a hypothesis learned from it depends on which five days happened to be recorded. The bootstrap is a stochastic algorithm, stated as Algorithm 1, that generates additional datasets from the recorded one, the so-called bootstrap samples (Efron and Tibshirani, 1993), and so makes that dependence measurable. Fig. 1 shows two bootstrap samples obtained from Algorithm 1. A bootstrap sample can contain a data point of $\mathcal{D}$ several times, so it is a list of data points rather than a set. The bootstrap is based on the independent and identically distributed assumption.

![Algorithm 1 of the entry bootstrap](https://dictionaryofml.org/terms/fig/bootstrap-alg1.svg)

*Algorithm 1: The bootstrap*

![Figure 1 of the entry bootstrap](https://dictionaryofml.org/terms/fig/bootstrap-fig1.svg)

*Figure 1: A dataset of five data points representing daily weather conditions at Krems an der Donau, the $15$th of February, April, June, August, and October $2022$, and below it two bootstrap samples obtained from it by Algorithm 1. In (a) each day is a data point (open circle, numbered). In (b) and (c) the gray open circles repeat the five days, and the filled markers are the five draws of the bootstrap sample: $\widetilde{\mathcal{D}}^{(1)}$ (filled squares) holds the days $2, 3, 3, 4, 5$ and omits day $1$, while $\widetilde{\mathcal{D}}^{(2)}$ (filled triangles) holds the days $1, 2, 2, 4, 5$ and omits day $3$. The second marker of a day drawn twice sits slightly above the first, so that two draws of one day do not hide each other. Weather data: GeoSphere Austria (GeoSphere Austria, 2026). Data generated by pythondemos/bootstrap.py*

Here, a dataset $\mathcal{D} = \big\{ {\mathbf z}^{(1)},
\,\ldots, \,{\mathbf z}^{(m)}\big\}$ is interpreted as the realizations of $m$ independent and identically distributed RVs with a common probability distribution $\mathbb{P}$. That $\mathbb{P}$ is unknown and must be estimated from $\mathcal{D}$ itself. The bootstrap estimates it by the empirical distribution $\mathbb{P}^{(\mathcal{D})}$ of $\mathcal{D}$ (Efron, 1979; Efron and Tibshirani, 1993; Hastie et al., 2009, Sect. 8.2.1). For every event $\mathcal{A}$, the fraction of the data points ${\mathbf z}^{(r)}$ that fall into it approximates its probability by the law of large numbers (Billingsley, 1986, Thm. 6.1; Efron and Tibshirani, 1993, Sect. 4.2),

$$
\frac{1}{m} \big| r: {\mathbf z}^{(r)}
\in \mathcal{A} \big| \approx \mathbb{P}\left(\mathcal{A}\right) \text{.}
$$

The empirical distribution $\mathbb{P}^{(\mathcal{D})}$ is a fully specified probability distribution and can be sampled as often as wanted. As many data points and as many datasets as needed can therefore be generated from the collected dataset. The gain is copies, not information. Each copy keeps the size $m$ of $\mathcal{D}$, because the quantity being imitated is the spread of a dataset of that size drawn from $\mathbb{P}$. Nor does a copy contain new data points: $\mathbb{P}^{(\mathcal{D})}$ places all its mass on the $m$ data points observed, so no draw can produce one that $\mathcal{D}$ does not already contain. A variant, the smoothed bootstrap, draws from a smoothed version of $\mathbb{P}^{(\mathcal{D})}$ in which each data point is replaced by a small bump-shaped probability density function; it produces data points that $\mathcal{D}$ does not contain, which the bootstrap itself never does.

Sampling $m$ data points from $\mathbb{P}^{(\mathcal{D})}$ is the same as drawing $m$ times from $\mathcal{D}$ with replacement, which is what Algorithm 1 does: every draw is made from the whole of $\mathcal{D}$, so a data point can be drawn twice and another not at all (Fig. 2). The number $B$ of bootstrap samples is limited only by the computation they cost.

![Figure 2 of the entry bootstrap](https://dictionaryofml.org/terms/fig/bootstrap-fig2.svg)

*Figure 2: Three bootstrap samples $\widetilde{\mathcal{D}}^{(1)}$, $\widetilde{\mathcal{D}}^{(2)}$, $\widetilde{\mathcal{D}}^{(3)}$ drawn from a dataset $\mathcal{D}$ of $m = 8$ data points (shaded), each by drawing $8$ times with replacement. Every row has the same length as $\mathcal{D}$, repeats some data points and omits others; each of the three happens to contain $5$ of the $8$ distinct data points, against the $0.63 \cdot 8 \approx 5$ that the calculation below predicts*

A data point is left out of a bootstrap sample with probability $(1 - 1/m)^{m}$, so it appears in one with probability $1 - (1 -
1/m)^{m}$, which approaches $1 - 1/e \approx
0.63$ as $m$ grows, since $(1 - 1/m)^{m}$ converges to $1/e$. The number of distinct data points in a bootstrap sample follows from that one probability alone. Write $I_{r}$ for the random variable that takes the value one when ${\mathbf z}^{(r)}$ appears in $\widetilde{\mathcal{D}}^{(b)}$ and zero otherwise. The count of distinct data points is $\sum_{r=1}^{m}
I_{r}$, so its expectation is

$$
{\mathbb{E}} \Big\{ \sum_{r=1}^{m} I_{r}
\Big\} = \sum_{r=1}^{m}
\mathbb{P}\left(I_{r} = 1\right) = m \big( 1 -
(1 - 1/m)^{m} \big) \approx
0.63\,m \text{.}
$$

The $I_{r}$ are not independent: a day drawn twice forces another to be left out. The expectation of a sum is the sum of the expectations nonetheless.

A bootstrap sample therefore holds about $0.63\,m$ distinct data points and overlaps $\mathcal{D}$ heavily. That overlap is what separates the bootstrap from k-fold cross-validation, which partitions $\mathcal{D}$ into blocks that do not overlap at all. Used naively to estimate the prediction error of a learned hypothesis, the bootstrap therefore evaluates it on data points that entered its own training, and the estimate comes out optimistic (Hastie et al., 2009, Sect. 7.11).

Machine learning training methods can be applied separately to each bootstrap sample, giving the learned hypotheses $\widehat{h}^{(1)}, \,\ldots,
\,\widehat{h}^{(B)}$. A quantity computed from $\widetilde{\mathcal{D}}^{(b)}$ is a bootstrap replication (Efron and Tibshirani, 1993), such as the hypothesis $\widehat{h}^{(b)}$ learned by empirical risk minimization from $\widetilde{\mathcal{D}}^{(b)}$ or its prediction $\widehat{h}^{(b)}({\mathbf x})$ for a fixed data point. The spread of the $B$ bootstrap replications estimates how much the output of the machine learning method changes due to random fluctuations in the data generation (Hastie et al., 2009, Sect. 8.2.1).

Fig. 3 shows the bootstrap for learning a linear hypothesis from weather data recorded at Krems an der Donau during $2024$, $m = 366$ days. Each dot is one data point, its feature the minimum temperature and its label the maximum temperature of the day; the figure draws $20$ of them. The thick line is the hypothesis learned from all $366$ by empirical risk minimization with the squared error loss. The thin lines show bootstrap replications $\widehat{h}^{(b)}$, $b = 1, \,\ldots, \,B$, learned by the same empirical risk minimization problem from bootstrap samples. Their spread is narrow here, and the $95\%$ confidence interval for the slope is $[1.05, 1.15]$.

![Figure 3 of the entry bootstrap](https://dictionaryofml.org/terms/fig/bootstrap-fig3.svg)

*Figure 3: Daily minimum and maximum temperature at Krems an der Donau in $2024$. The dots are $20$ of the $m = 366$ data points, every $19$th day of the year. The thick line is the hypothesis $\widehat{h}$ learned from all $m$ data points, the thin lines are the bootstrap replications $\widehat{h}^{(b)}$ learned from the first $25$ of $B = 500$ bootstrap samples, and the spread of all $500$ gives the confidence interval for the slope. Weather data: GeoSphere Austria (GeoSphere Austria, 2026). Data generated by pythondemos/bootstrap.py*

While basic validation gives a point estimate for the risk of a hypothesis, i.e., the validation error, the bootstrap adds a confidence interval to this point estimate. A hypothesis $\widehat{h}$ is learned once from the training set $\mathcal{D}^{(\rm train)}$, and the validation set $\mathcal{D}^{(\rm val)}$ is resampled $B$ times with replacement, each bootstrap sample of the size of $\mathcal{D}^{(\rm val)}$. Evaluating the same $\widehat{h}$ on each of them gives $B$ estimates of the risk. The sample mean of these estimates is the risk estimate, and the square root of their sample variance is its bootstrap standard error (Efron and Tibshirani, 1993, Sect. 6.2). The estimate plus or minus a standard normal quantile times this standard error is a confidence interval (Efron and Tibshirani, 1993, Sect. 13.2).

Bagging is the bootstrap put to a different use: instead of measuring the spread of $\widehat{h}^{(1)}, \,\ldots,
\,\widehat{h}^{(B)}$, it averages them into one hypothesis, which is how a random forest is built from decision trees.

**See also:** empirical distribution, [independent and identically distributed](https://dictionaryofml.org/terms/iid.html), [random variable](https://dictionaryofml.org/terms/rv.html), [probability distribution](https://dictionaryofml.org/terms/probdist.html), [variance](https://dictionaryofml.org/terms/variance.html), [$k$-fold cross-validation](https://dictionaryofml.org/terms/kfoldcv.html), [bagging](https://dictionaryofml.org/terms/bagging.html), confidence interval, validation, [validation set](https://dictionaryofml.org/terms/valset.html), [validation error](https://dictionaryofml.org/terms/valerr.html).

## References

- GeoSphere Austria (2026). GeoSphere Austria climate station archive. <https://dataset.api.hub.geosphere.at/v1/station/historical/klima-v2-1d>
- Efron and Tibshirani (1993). An Introduction to the Bootstrap. *Chapman & Hall*.
- Efron (1979). Bootstrap Methods: Another Look at the Jackknife. *Ann. Statist.*. <https://doi.org/10.1214/aos/1176344552>
- Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. *Springer Science+Business Media*. <https://doi.org/10.1007/978-0-387-84858-7>
- Billingsley (1986). Probability and Measure. *Wiley*.

## Cite this entry

```bibtex
@misc{dictml_bootstrap,
  author = {Jung, Alexander},
  editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
  title = {bootstrap},
  howpublished = {Dictionary of Applied Machine Learning (course edition)},
  year = {2026},
  doi = {10.5281/zenodo.21569296},
  note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-11-11},
  url = {https://dictionaryofml.org/terms/bootstrap.html}
}
```