Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

The Bootstrap: Uncertainty When the Algebra Runs Out

7 minute read

Published:

TL;DR: The bootstrap treats the empirical distribution as a stand-in for the population: draw \(n\) points with replacement from your \(n\) observations, recompute the statistic, repeat thousands of times, and read the spread of the results as the sampling distribution. It needs no formula for the statistic, which is its whole appeal. It breaks for extremes, for infinite-variance tails, and for dependent data. Permutation tests and cross-validation are the same substitution applied to testing and to model assessment.

The substitution

The quantity you want is the sampling distribution of \(\hat\theta\) under the true \(F\) — and you cannot have it, because you have one sample, not many, and you do not know \(F\). The bootstrap replaces \(F\) with \(\hat F_n\), the empirical distribution putting mass \(1/n\) on each observed point, and samples from that. Sampling from \(\hat F_n\) is exactly drawing \(n\) points with replacement.

\[ \hat\theta^{*(b)} = \hat\theta\big(x_1^{*(b)},\dots,x_n^{*(b)}\big), \qquad b = 1,\dots,B, \qquad x_i^{*} \sim \hat F_n \]

The spread of \(\{\hat\theta^{*(b)}\}\) estimates the spread of \(\hat\theta\). The justification is asymptotic: \(\hat F_n \to F\) uniformly by Glivenko–Cantelli, and for smooth enough statistics the bootstrap distribution converges to the true sampling distribution. Note that a bootstrap resample omits any given observation with probability \((1-1/n)^n \to e^{-1} = 0.368\), so each resample uses about 63% of the distinct data points — the fact behind out-of-bag error in random forests.

A worked interval

Twelve request latencies in milliseconds: 12, 13, 14, 15, 15, 16, 18, 19, 22, 27, 41, 88. The mean is 25.0 and \(s = 21.40\), so the normal-theory interval is \(25 \pm 2.201 \times 6.178 = [11.40,\ 38.60]\), using \(t^\star_{11} = 2.201\).

The percentile bootstrap takes the 2.5th and 97.5th percentiles of the resampled means directly. One run of \(B = 10{,}000\) resamples gives \([16.08,\ 38.25]\), with a bootstrap standard error of 5.89 against the formula’s 6.18.

Bootstrap distribution of the sample mean against the normal-theory intervalA histogram of ten thousand bootstrap resample means for the twelve latency observations. It peaks near 22 and has a long right tail, clearly right-skewed rather than symmetric. The percentile bootstrap interval runs from 16.08 to 38.25 and sits under the mass of the histogram. The normal-theory t interval, drawn beneath it, runs from 11.40 to 38.60 and extends far to the left into a region where the bootstrap distribution has essentially no mass. x̄ = 25.0 percentile bootstrap [16.08, 38.25] normal-theory t [11.40, 38.60] 1015202530354045
Notice that the bootstrap distribution is skewed right, so the interval it produces is not centred on 25.0. The symmetric t interval buys its left-hand coverage in a region the data never visit, and is 23% wider as a result (27.2 against 22.2).

The bootstrap interval is asymmetric because the bootstrap distribution is — the right answer for skewed data, and one the \(t\) interval cannot give since it is symmetric by construction.

Where it fails

The failure cases are the interview question.

Extremes. For \(\hat\theta = \max_i x_i\), every resample maximum is one of the observed values and equals the sample maximum with probability \(1 - (1-1/n)^n \approx 0.632\). The bootstrap distribution has an atom of mass there and cannot represent the smooth true one. Bickel and Freedman (1981) give the condition: the statistic must depend smoothly on the underlying distribution, and extreme order statistics do not.

Heavy tails. With infinite variance — a Cauchy, or a Pareto with tail index below 2 — the sample mean has no limiting normal distribution and the bootstrap is inconsistent for it.

Dependence. The resampling step assumes exchangeability. Applied naively to a time series it destroys autocorrelation, so it will underestimate the variance of a mean by a factor that grows with the dependence. The fix is to resample contiguous blocks — the moving-block or stationary bootstrap (Politis and Romano, 1994) — with block length long enough to preserve the correlation structure.

Permutation tests

To test whether two groups differ, apply the same trick to the null. Under \(H_0\) the group labels are meaningless, so any reassignment is as likely as the one observed: enumerate the relabellings, compute the statistic for each, and see where the observed value lands.

Group A: 12, 15, 15, 18. Group B: 22, 27, 41, 88. The observed difference of means is \(44.5 - 15.0 = 29.5\). There are \(\binom{8}{4} = 70\) ways to split eight numbers into two groups of four, and exactly 2 of them — the observed split and its mirror image — give a difference of 29.5 or more in absolute value. So the exact two-sided p-value is \(2/70 = 0.029\).

Interview trap — resolution is bounded by the design: that 0.029 is the smallest p-value obtainable with four observations per group, because the most extreme split already sits at \(2/70\). No effect size, however enormous, can push a 4-versus-4 permutation test below 0.01. The same logic applies to the bootstrap: with \(B\) resamples a percentile interval can only resolve tail probabilities to about \(1/B\), so \(B = 1{,}000\) is not enough for a 99% interval. Use \(B \ge 10{,}000\) when you care about the tails.

Cross-validation is resampling too

\(k\)-fold CV is a resampling estimate of generalisation error, and it inherits a resampling problem: the folds are not independent. Any two training sets in 5-fold CV share three of the five parts — 75% of each training set — so the models are correlated, and so are their errors.

The naive standard error \(s/\sqrt{k}\) across folds therefore understates the true variability, often badly. Bengio and Grandvalet (2004) proved something stronger: there is no unbiased estimator of the variance of \(k\)-fold cross-validation. Fold spread is a rough signal, not a confidence interval.

Key Insight — what the bootstrap actually assumes: not normality, and not a formula for \(\hat\theta\), but that \(\hat F_n\) is a good enough stand-in for \(F\) for the functional you are computing. That is why it works beautifully for means, medians and correlations, all of which depend on \(F\) smoothly, and fails for maxima, which depend on the sharp edge of \(F\) that a finite sample never observes. Ask "does my statistic depend on a part of the distribution my sample can see?" and the failure cases stop needing memorisation.

Recap

  • Resample \(n\) points with replacement, recompute, repeat. Each resample misses about 36.8% of the distinct points, since \((1-1/n)^n \to e^{-1}\).
  • Percentile CI = the 2.5th and 97.5th percentiles of the resampled statistics; it inherits the skew of the data, unlike a symmetric \(t\) interval.
  • Fails for extremes, infinite-variance tails and dependent data; use a block bootstrap for time series.
  • Permutation tests give exact p-values, but resolution is limited by the number of relabellings: 4 versus 4 bottoms out at \(2/70 = 0.029\).
  • k-fold CV is resampling with correlated folds — no unbiased variance estimator exists, so do not read fold spread as a confidence interval.

References

  1. Efron, B. Bootstrap Methods: Another Look at the Jackknife. The Annals of Statistics, 7(1), 1–26, 1979.
  2. Bickel, P. J., & Freedman, D. A. Some Asymptotic Theory for the Bootstrap. The Annals of Statistics, 9(6), 1196–1217, 1981.
  3. Politis, D. N., & Romano, J. P. The Stationary Bootstrap. Journal of the American Statistical Association, 89(428), 1303–1313, 1994.
  4. Bengio, Y., & Grandvalet, Y. No Unbiased Estimator of the Variance of K-Fold Cross-Validation. Journal of Machine Learning Research, 5, 1089–1105, 2004.

You May Also Enjoy

Noether’s Theorem: Symmetry, Conservation, and Equivariant Networks

7 minute read

Published:

Energy is conserved because the laws of physics do not care what time it is. That single sentence is Noether’s theorem, and its machine learning descendant is the reason an equivariant network needs less data than one that must learn the symmetry from examples.

Entropy and Free Energy: From the Second Law to the ELBO

7 minute read

Published:

Thermodynamic entropy and Shannon entropy differ by a constant with units. Once you accept that, the ELBO stops being an inference trick and becomes a free energy — and diffusion models stop being a clever architecture and become a driven non-equilibrium process.

Statistical Mechanics: The Boltzmann Distribution and the Cost of Z

6 minute read

Published:

Counting microstates gives you the Boltzmann distribution, and the Boltzmann distribution gives you softmax, simulated annealing and energy-based models. The partition function is not a bookkeeping constant — it is the object that contains every thermodynamic quantity, and it is intractable for exactly that reason.