A scalable bootstrap for massive data

By Ariel Kleiner, Ameet Talwalkar, Purnamrita Sarkar, Michael I. Jordan. 2011

443 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Deep Exploration via Bootstrapped DQN (2016, background): “The approach can even scale to massive data with sub-linear computational cost (Kleiner et al., 2014).”
Consistency of Random Forests (2014, background): “The connection between LNN and random forests has been first observed by Lin and Jeon (2006), and latter worked out by Biau and Devroye (2010).”
B-tests: Low Variance Kernel Two-Sample Tests (2013, methodology): “es these estimates. The difference with respect to our approach is that we use the asymptotic distribution of the average over block statistics to determine a threshold for a hypothesis test, whereas [15] is concerned with proving the consistency of a statistic obtained by averaging over bootstrap e”
Toward enhanced understanding and projections of climate extremes using physics-guided data mining techniques (2014, methodology): “The recently developed method of “bag of little bootstraps” (Kleiner et al., 2014), claims to have significantly improved the timecomplexity of the bootstrap method for large data sets with theoretical guarantees of correctness of uncertainty estimates.”
Random Forests for Big Data (2015, methodology): “One variant relies on subsampling while three others are related to parallel implementations of random forests and involve either various adaptations of bootstrap to Big Data or “divide-and-conquer” approaches.”
The Big Data Bootstrap (2012, background): “See Kleiner et al. (2012) for our theoretical results on higher-order correctness.”
Communication-Efficient Distributed Statistical Inference (2016, background): “…emerge, both in a frequentist setting (Duchi, Agar-wal, and Wainwright 2012; Zhang, Duchi, and Wainwright 2013; Kannan, Vempala, and Woodruff 2014; Kleiner et al. 2014; Shamir, Srebro, and Zhang 2014; Mackey, Talwalkar, and Jordan 2015; Zhang and Lin 2015a; Lee et al. 2015a), and a Bayesian…”
From Dependence to Causation (2016, unknown): “Each bootstrap set is a random subset of m examples of the data sampled with replacement (Kleiner et al., 2014).”
Distributed Bayesian Learning with Stochastic Natural Gradient Expectation Propagation and the Posterior Server (2015, methodology): “Typically known as divide-andconquer or consensus inference (Zhang et al., Accepted, Zhao et al., 2014, Kleiner et al., 2014, Battey et al., 2015), it is also well-known that this situation is harder than typical distributed learning settings where it is assumed that all data is accessible on all…”
On nonnegative unbiased estimators (2013, background): “For instance, in thecommon case where the cost of evaluating the likelihood function grows at least linearly with the size of the dataset, pointwise posterior density evaluations become prohibitive for large datasets (Welling and Teh, 2011; Kleiner et al., 2014).”
Big Data and Data Science Methods for Management Research (2016, background): “Kleiner et al. (2014) provide advice on the number of subsamples and subsample size.”
Handbook of Big Data (2016, methodology): “Existing independent research that relates to D&R that can serve as a platform for new research includes Bayesian consensus Monte Carlo [13], bag of little bootstraps [11], alternating direction method of multipliers [2], and scatter matrix stability weighting [10].”