# Estimating the Algorithmic Variance of Randomized Ensembles via the Bootstrap

arXiv: https://arxiv.org/abs/1907.08742 · HTML: https://mlsanity.com/paper/1907.08742/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jul 2019.

## Built on by (most cited first, 10 of 10)

- [Bootstrapping the error of Oja's algorithm](https://mlsanity.com/paper/2106.14857/) (2021)
- [Are Ensembles Getting Better all the Time?](https://mlsanity.com/paper/2311.17885/) (2023)
- [Corrected generalized cross-validation for finite ensembles of penalized estimators](https://mlsanity.com/paper/2310.01374/) (2023)
- [Extrapolated cross-validation for randomized ensembles](https://mlsanity.com/paper/2302.13511/) (2023)
- [When do Random Forests work?](https://mlsanity.com/paper/2504.12860/) (2025)
- [Random Forests as Statistical Procedures: Design, Variance, and Dependence](https://mlsanity.com/paper/2602.13104/) (2026)
- [How Many Trees in a Random Forest? A Revisited Approach with Plateau Search and Optuna Integration](https://mlsanity.com/paper/2606.03549/) (2026)
- [Cheap Bootstrap for Fast Uncertainty Quantification of Stochastic Gradient Descent](https://mlsanity.com/paper/2310.11065/) (2023)
- [Centroid Decision Forest](https://mlsanity.com/paper/2503.19306/) (2025)
- [A Stationary-Distribution Theory for Triplet-Based Plateau Search in Random Forest Ensemble-Size Selection](https://mlsanity.com/paper/2606.30837/) (2026)

## Abstract (arXiv)

Although the methods of bagging and random forests are some of the most widely used prediction methods, relatively little is known about their algorithmic convergence. In particular, there are not many theoretical guarantees for deciding when an ensemble is "large enough" --- so that its accuracy is close to that of an ideal infinite ensemble. Due to the fact that bagging and random forests are randomized algorithms, the choice of ensemble size is closely related to the notion of "algorithmic variance" (i.e. the variance of prediction error due only to the training algorithm). In the present work, we propose a bootstrap method to estimate this variance for bagging, random forests, and related methods in the context of classification. To be specific, suppose the training dataset is fixed, and let the random variable Errt denote the prediction error of a randomized ensemble of size t. Working under a "first-order model" for randomized ensembles, we prove that the centered law of Errt can be consistently approximated via the proposed method as t→∞. Meanwhile, the computational cost of the method is quite modest, by virtue of an extrapolation technique. As a consequence, the method offers a practical guideline for deciding when the algorithmic fluctuations of Errt are negligible.