The Big Data Bootstrap
By Ariel Kleiner, Ameet Talwalkar, Purnamrita Sarkar, Michael I. Jordan. 2012
152 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 datasets, the computation of bootstrap-based quantities can be prohibitively demanding. As an alternative, we present 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 estimator quality. BLB is well suited to modern parallel and distributed computing architectures and retains the generic applicability, statistical efficiency, and favorable theoretical properties of the bootstrap. We provide the results of an extensive empirical and theoretical investigation of BLB's behavior, including a study of its statistical correctness, its large-scale implementation and performance, selection of hyperparameters, and performance on real 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
- Sergey Levine
- Michael I. Jordan
- Pieter Abbeel
- Percy Liang
- Ruslan Salakhutdinov
- Yoshua Bengio
- Chelsea Finn
- Quoc V. Le
In Statistics and Probability
- Michael I. Jordan
- Martin J. Wainwright
- John C. Duchi
- Yuchen Zhang
- Bin Yu
- Francis R. Bach
- Tong Zhang
- Nicolai Meinshausen
Citations in the corpus
- Uncertainty-Aware Reinforcement Learning for Collision Avoidance (2017, background): “This intuition is backed with theoretical guarantees [13].”
- Streaming Variational Bayes (2013, background): “Significant progress on scalable learning procedures has been made in recent years [e.g., 1, 2].”
- Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates (2013, methodology): “Divide-and-conquer approaches have been studied by several authors, including McDonald et al. (2010) for perceptron-based algorithms, Kleiner et al. (2012) in distributed versions of the bootstrap, and Zhang et al. (2013) for parametric smooth convex optimization problems.”
- Deep forest (2017, background): “Besides random sampling, it is interesting to explore smarter sampling strategies, such as BLB [27], or feature hashing [60] when adequate.”
- A statistical perspective on algorithmic leveraging (2013, background): “In addition, the goal of resampling is traditionally to perform statistical inference and not to improve the running time of an algorithm, except in the very recent work (Kleiner et al., 2012).”
- Big Data Quality: A Quality Dimensions Evaluation (2016, methodology): “In the context of Big Data, Bootstrap sampling has been addressed in many works [23]–[25].”
- Deep Metric Learning via Facility Location (2016, methodology): “In the future, we plan to explore sampling based gradient averaging scheme where we ask the algorithm to cluster several random subsets of the data within the training batch and then average the loss gradient from multiple sampled subsets in similar spirit to Bag of Little Bootstraps (BLB) [16] .”