The bootstrap provides a simple and powerful means of assessing the quality of estimators.  However, in settings involving large datasets — which are increasingly prevalent — the computation of bootstrap-based quantities can be prohibitively demanding computationally. While variants such as subsampling and the m out of n bootstrap can be used in principle to reduce the cost of bootstrap computations, we find that these methods are generally not robust to specification of hyperparameters (such as the number of subsampled data points), and they often require use of more prior information (such as rates of convergence of estimators) than the bootstrap.  As an alternative, we introduce the Bag of Little Bootstraps (BLB), a new procedure which incorporates features of both the bootstrap and subsampling to obtain a robust, computationally efficient means of assessing the quality of estimators.  BLB is well suited to modern parallel and distributed computing architectures and furthermore retains the generic applicability and statistical efficiency of the bootstrap.  We provide a theoretical analysis elucidating the properties of BLB, as well as empirical results comparing BLB to the bootstrap, the m out of n bootstrap, and subsampling.

A Scalable Bootstrap for Massive Data (technical report)