A scalable bootstrap for massive data

Ariel Kleiner, Ameet Talwalkar, Purnamrita Sarkar and Michael I. Jordan

Journal of the Royal Statistical Society Series B, 2014, vol. 76, issue 4, 795-816

Abstract: type="main" xml:id="rssb12050-abs-0001">

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.

Date: 2014
References: Add references at CitEc
Citations: View citations in EconPapers (29)

Downloads: (external link)
http://hdl.handle.net/10.1111/rssb.2014.76.issue-4 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bla:jorssb:v:76:y:2014:i:4:p:795-816

Ordering information: This journal article can be ordered from
http://ordering.onli ... 1111/(ISSN)1467-9868

Access Statistics for this article

Journal of the Royal Statistical Society Series B is currently edited by P. Fryzlewicz and I. Van Keilegom

More articles in Journal of the Royal Statistical Society Series B from Royal Statistical Society Contact information at EDIRC.
Bibliographic data for series maintained by Wiley Content Delivery ().