  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 yield 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
demonstrate BLB's favorable statistical performance via a theoretical analysis
elucidating the procedure's properties, as well as a simulation study comparing
BLB to the bootstrap, the $m$ out of $n$ bootstrap, and subsampling. In
addition, we present results from a large-scale distributed implementation of
BLB demonstrating its computational superiority on massive data, a method for
adaptively selecting BLB's hyperparameters, an empirical study applying BLB to
several real datasets, and an extension of BLB to time series data.

Methodology;Computation;Machine Learning