A Scalable Bootstrap for Massive Data
Top Cited Papers
- 17 March 2014
- journal article
- Published by Oxford University Press (OUP) in Journal of the Royal Statistical Society Series B: Statistical Methodology
- Vol. 76 (4) , 795-816
Abstract
Summary: The bootstrap provides a simple and powerful means of assessing the quality of estimators. However, in settings involving large data sets—which are increasingly prevalent—the calculation of bootstrap-based quantities can be prohibitively demanding computationally. Although variants such as subsampling and the m out of n bootstrap can be used in principle to reduce the cost of bootstrap computations, these methods are generally not robust to specification of tuning parameters (such as the number of subsampled data points), and they often require knowledge of the estimator's convergence rate, in contrast with the bootstrap. As an alternative, we introduce the ‘bag of little bootstraps’ (BLB), which is 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. The 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 the BLB's favourable statistical performance via a theoretical analysis elucidating the procedure's properties, as well as a simulation study comparing the BLB with the bootstrap, the m out of n bootstrap and subsampling. In addition, we present results from a large-scale distributed implementation of the BLB demonstrating its computational superiority on massive data, a method for adaptively selecting the BLB's tuning parameters, an empirical study applying the BLB to several real data sets and an extension of the BLB to time series data.Keywords
All Related Versions
Funding Information
- US Army Research Laboratory
- US Army Research Office (W911NF-11-1-0391)
- National Science Foundation (1122732)
This publication has 19 references indexed in Scilit:
- Bootstrapping Quantile Regression EstimatorsEconometric Theory, 1995
- On General Resampling Algorithms and their Performance in Distribution EstimationThe Annals of Statistics, 1994
- An Introduction to the Bootstrap1993
- The Bootstrap and Edgeworth Expansion1992
- Bootstrapping General Empirical MeasuresThe Annals of Probability, 1990
- More Efficient Bootstrap ComputationsJournal of the American Statistical Association, 1990
- Richardson Extrapolation and the BootstrapJournal of the American Statistical Association, 1988
- Computer-Intensive Methods in StatisticsScientific American, 1983
- Some Asymptotic Theory for the BootstrapThe Annals of Statistics, 1981
- Bootstrap Methods: Another Look at the JackknifeThe Annals of Statistics, 1979