Source-linked AI summary
A Scalable Bootstrap for Massive Data
Ariel Kleiner, Ameet Talwalkar, Purnamrita Sarkar, Michael I. Jordan
TL;DR
Massive datasets make bootstrap-based estimator assessment prohibitively costly, while subsampling alternatives can be sensitive to hyperparameters and require analytical corrections. The paper introduces BLB, which bootstraps multiple small subsets using compact weighted representations. BLB retains bootstrap-like applicability and statistical properties while improving computational scalability and robustness in the reported studies.
Problem
Massive datasets make repeated full-data bootstrap computations difficult, while subsampling and the m out of n bootstrap can be sensitive to subset size and require convergence-rate information.
Method
BLB averages bootstrap-based estimator-quality assessments computed on multiple small subsets, representing each nominally n-sized resample through weighted subset observations.
Results
BLB retains bootstrap consistency, higher-order correctness, and generic applicability while providing a markedly better computational profile and greater robustness to subset-size choice.
Takeaways & Limitations
BLB is a computationally efficient alternative for assessing estimator quality on large datasets and is well suited to parallel and distributed architectures.
Takeaways & Limitations
BLB is not expected to apply in cases where the bootstrap fails, and automatic selection of subset size b remains difficult.
Abstract
from arXiv · showhide
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.
1 Introduction
Massive datasets make estimator-quality assessment computationally difficult, while existing reduced-data alternatives can require fragile hyperparameter choices and estimator-specific corrections. BLB is introduced to combine bootstrap applicability with the lower computational cost of working on small subsets.
- Motivation: Massive datasets complicate inference because estimator uncertainty and bias can remain substantial even when estimation is accurate.High dimensionality, complex models, many parameters, and multiple bias sources contribute to this challenge.
- Limitations of existing methods: Bootstrap assessment is broadly applicable and relatively automatic, but repeatedly applying an estimator to full-size resamples creates a substantial computational burden.Each resample has size comparable to the original dataset, making repeated computation costly.
- Limitations of existing methods: Approximately 63% of observations appear at least once in each bootstrap resample, further limiting bootstrap usefulness for massive datasets.The large number of distinct observations also makes distributing resamples expensive.
- Limitations of existing methods: Subsampling and the m out of n bootstrap reduce computation but are sensitive to resample size and require analytical rescaling based on estimator convergence rates.These requirements make them less automatic and less robust than the bootstrap.
- BLB: BLB combines bootstrapping multiple small subsets of the original data, reducing estimator computations while avoiding analytical rescaling of its output.The procedure is designed for scalable assessment on modern distributed architectures.
2 Bag of Little Bootstraps (BLB)
BLB approximates bootstrap-based estimator-quality assessments by averaging bootstrap results from multiple small subsets, while representing each nominally full-size resample through weighted counts. This representation reduces computation and supports parallel and distributed execution without requiring analytical corrections.
- Procedure: BLB estimates estimator quality by averaging bootstrap-based plugin approximations across multiple subsets of size b drawn from the original dataset.The subsets may be sampled randomly or selected as disjoint blocks from a random partition.
- Procedure: For each subset, BLB repeatedly resamples n observations with replacement, computes the estimator, and forms an empirical sampling distribution.This preserves the nominal full-data resample size while operating on a compact empirical distribution.
- Computational representation: Each BLB resample contains at most b distinct data points and can therefore be represented by subset observations with multinomially sampled counts.The compact representation is the key mechanism behind BLB’s computational savings.
- Computational representation: With b = n^0.6 and n = 1,000,000, BLB resamples contain at most 3,981 distinct points, compared with approximately 632,000 for a bootstrap resample.At 1 MB per point, the corresponding storage examples are at most 4 GB for BLB versus approximately 632 GB for the bootstrap.
- Scalability: BLB reduces repeated computation on full-size resamples and permits subsets and resamples to be processed naturally in parallel across compute nodes.This lowers total assessment cost and supports hierarchical distributed architectures.
- Statistical properties: BLB retains the bootstrap’s generic applicability and favorable statistical properties while being more robust than subsampling and the m out of n bootstrap to subset-size choice.The comparison is stated as a procedural advantage rather than as a requirement for analytical correction.
3 Statistical Performance
BLB matches the bootstrap’s consistency and higher-order correctness under comparable conditions while using subsets substantially smaller than the full dataset. Simulations show that BLB generally reaches low relative error faster and is more robust than the b out of n bootstrap and subsampling.
- Theoretical properties: BLB has asymptotic consistency and higher-order correctness identical to the bootstrap under the same conditions.The consistency result applies as b and n grow, while higher-order correctness requires sufficiently large s and b.
- Theoretical properties: BLB’s consistency result requires only b →∞ under the stated standard assumptions, while more general consistency results may require stronger assumptions.Theorem 1 uses standard bootstrap assumptions and allows any sequence b →∞ with fixed s; stronger assumptions may be needed when s also grows or ξ is generalized.
- Theoretical properties: BLB can retain bootstrap-level convergence while b/n → 0, so its subsets may remain substantially smaller than n.The result assumes sufficiently large b, but b can still grow much more slowly than n.
- Simulation design: BLB estimates marginal 95% confidence-interval boundaries from the 2.5th and 97.5th percentiles of component-wise estimator distributions.The simulation evaluates average relative deviation of estimated interval widths from ground-truth widths constructed from 2,000 simulated datasets.
- Simulation results: In regression, BLB reaches low relative error significantly faster than the bootstrap across all tested b values, while smaller-b b out of n bootstrap trajectories fail to converge.The b out of n bootstrap fails for b below n^0.7, and subsampling performs worse than the b out of n bootstrap.
- Simulation results: In classification, BLB’s performance varies by setting but is often comparable to or faster than the bootstrap and more robust than the b out of n bootstrap.For the challenging Gamma setting, BLB is comparable to the bootstrap for b > n^0.6; for larger b it again converges faster, while b out of n bootstrap fails for b ≤ n^0.7.
4 Computational Scalability
BLB scales estimator-quality assessment by exploiting parallel computation across smaller subsamples and resamples, avoiding repeated full-cluster processing of massive bootstrap resamples. In distributed experiments on a 150 GB dataset, BLB achieved high-accuracy output substantially faster than the bootstrap.
- Bootstrap bottlenecks: The bootstrap remains problematic at scale because each resample uses the entire cluster and repeatedly incurs communication and large-dataset disk-read overhead.This is especially costly when the full dataset cannot fit in memory.
- Computational architecture: BLB uses parallelism across multiple subsamples and resamples, enabling distributed implementations and computational gains.Its subsamples and resamples can be processed independently on individual compute nodes.
- Computational architecture: Generating BLB subsamples requires only a single pass over the full dataset, after which the subsamples can potentially remain in memory.This avoids repeatedly reading the full dataset from disk.
- Method comparisons: Subsampling and the m out of n bootstrap were excluded from scalability experiments because repeated access to many random subsets can be costly across a distributed cluster.BLB requires relatively few, potentially disjoint, subsamples instead.
- Distributed results: On 150 GB of data, BLB produced high-accuracy output in less time than the bootstrap needed to process even one resample in the disk-bound experiment.The experiment used a 10-worker-node cluster with 60 GB total memory, so the dataset was stored on disk.
- Distributed results: With the full dataset cached in memory, both methods improved, but BLB remained substantially better than the bootstrap.The cached experiment used a 20-worker-node cluster with 240 GB total memory.
5 Hyperparameter Selection
BLB’s hyperparameters r and s should be large enough for statistical accuracy but no larger than necessary, motivating adaptive selection. The proposed scheme monitors stabilization and can stop shortly after convergence, while b remains harder to select automatically.
- BLB requires sufficiently large r and s for statistical performance, but unnecessarily large values waste computation.
- For b = n^0.7, selecting s ≥3 and r ≥50 is sufficient for low relative error in the studied classification setting.
- Adaptive selection increases r or s until the corresponding BLB output ceases to fluctuate significantly.
- In the representative experiment, adaptive selection stopped shortly after convergence without degrading statistical performance.The procedure used ε = 0.05, with window sizes w = 20 for r and w = 3 for s.
- The adaptive scheme substantially reduces the burden of choosing r and s a priori, whereas efficient automatic selection of b remains difficult.The difficulty arises because computations for different b values cannot be easily reused; b = n^0.7 was considered reasonable in many situations.
6 Real Data
On real datasets without ground truth, the study compares the outputs of BLB, the bootstrap, and the b out of n bootstrap. On UCI connect4, BLB and the bootstrap agree closely, while BLB converges faster and b out of n bootstrap results vary with b.
- Because ground truth is unavailable for real datasets, the study compares outputs rather than objectively evaluating statistical correctness.
- On UCI connect4, BLB outputs across all tested b values and the bootstrap output are tightly clustered around the same value.The dataset uses logistic regression with d = 42 and n = 67,557.
- BLB converges more quickly than the bootstrap on UCI connect4.
- The b out of n bootstrap outputs vary significantly as b changes, highlighting its lack of robustness.Qualitatively similar results were obtained on six additional UCI datasets with linear and logistic regression.
7 Time Series
BLB can be extended to dependent data by replacing subsample selection and resampling with mechanisms that respect the data-generating process. A stationary BLB proof of concept achieves performance comparable to the stationary bootstrap for sufficiently large b.
- Bootstrap variants for non-i.i.d. data can be used within BLB to produce procedures applicable beyond independent observations.
- Stationary BLB selects randomly positioned time-series blocks and applies the stationary bootstrap within each selected block.Both subsample selection and resample generation are altered to respect stationarity.
- Table 1 compares standard and stationary bootstrap and BLB estimates for n = 5,000 across 10 trials against a true standard deviation of approximately 5.
- For b ≥ n^0.7, stationary BLB has statistical performance comparable to the stationary bootstrap.The experiment also reports improvement of stationary bootstrap over bootstrap and stationary BLB over BLB.
- The stationary BLB experiment is presented as a proof of concept requiring additional investigation of its performance characteristics.
8 Conclusion
BLB is presented as a scalable alternative for automatic estimator-quality assessment that retains the bootstrap’s consistency, higher-order correctness, and generic applicability. The authors identify unresolved questions around adaptive b selection, bootstrap-failure settings, and alternative aggregation losses.
- BLB combines the bootstrap’s consistency, higher-order correctness, and generic applicability with a typically better computational profile for large-scale data.
- A more precise theoretical characterization of the adaptive hyperparameter selection method remains an open question.
- Efficient adaptive selection of b remains undeveloped because computations for different b values cannot be easily reused.
- BLB is not expected to apply in cases where the bootstrap fails, including settings motivating the m out of n bootstrap and subsampling.
- Averaging BLB plugin approximations implicitly minimizes squared error, while alternative combinations such as medians could target other losses.
A Appendix: Proofs
This appendix supplies the full proofs for the theoretical results presented earlier in Section 3.1.
- The appendix states that it provides full proofs of the theoretical results from Section 3.1.
- Its purpose is to establish the paper’s theoretical results through detailed derivations.
- The appendix functions as the proof record supporting Section 3.1.
A.1 Consistency
The consistency analysis shows that BLB resamples from subsamples have the same asymptotic behavior as sampling from the underlying distribution, yielding consistent inference under stated assumptions.
- Under the stated Donsker-class and measurability assumptions, the resampled empirical process converges to a P-Brownian bridge in probability.
- Size-n resamples from each subsampled empirical distribution behave asymptotically as though drawn directly from the true distribution P.
- The proof invokes the functional delta method, the bootstrap delta method, and the continuous mapping theorem.
- The BLB bootstrap functional converges conditionally to the same limiting random element as the original estimator’s scaled distribution.
- Consequently, the relevant BLB distributional approximation is asymptotically consistent as b and n tend to infinity.
A.2 Higher-Order Correctness
The higher-order analysis derives variance and approximation properties for BLB’s subsample-based quantities using moment expansions, V-statistics, and U-statistic bounds.
- The appendix begins the higher-order analysis by proving two supporting lemmas.
- Var(ˆp_k(X_1, . . . , X_b)) = O(1/b) for the sample moment quantities analyzed in Lemma 3.
- The proof represents polynomial moment expressions as V-statistics and relates them to corresponding U-statistics.
- The appendix combines expansions and lemmas to establish the stated higher-order results, including subsequent theorems and remarks.
- Permutation symmetry makes the conditional expectation a U-statistic of order b, enabling application of Shao’s bounds.
B Appendix: Additional Real Data Results
The appendix reports additional real-data comparisons of BLB, the bootstrap, and the b out of n bootstrap using confidence-interval width versus processing time across UCI datasets.
- On UCI ct-slice, Figure 7 compares BLB and BOOT on the left and BOFN on the right for linear regression with d = 385 and n = 53,500.
- On UCI magic, Figure 8 uses the same comparison layout for logistic regression with d = 10 and n = 19,020.
- On UCI millionsong, Figure 9 compares the methods for linear regression with d = 90 and n = 50,000.
- On UCI parkinsons, Figure 10 evaluates linear regression with d = 16 and n = 5,875 using adaptive BLB hyperparameter selection.
- On UCI poker and shuttle, Figures 11 and 12 evaluate logistic regression with n = 50,000 and n = 43,500, respectively.