Choose your reading route
eduKateSG · Why Mathematics? · Bag of Little Bootstraps: Scalable Distributed Uncertainty
Start with the question, audit the worked example, or jump to the assumptions and practice. Every chapter stays open for uninterrupted reading.
Understand the question
Define the quantity and follow the mechanism.Route 2 · Chapters 8–14
Reproduce the example
Audit the numbers one step at a time.Route 3 · Chapters 15–21
Check assumptions
See where design and calibration matter.Route 4 · Chapters 22–28
Explore applications
Connect the method to a concrete investigation.Route 5 · Chapters 29–34
Study and verify
Practise, inspect failure cases and read further.
Full chapter index · Practice and checking · Mathematics Learning Hub
Why is mathematics important when a conventional bootstrap repeatedly scans a dataset too large for one machine or one memory budget? The bag of little bootstraps divides the data into small subsets, runs nominal-n weighted bootstrap resamples inside each subset, and combines uncertainty summaries across subsets.
Did You Know? A BLB resample can represent n observations while touching only b distinct rows. Multinomial counts summing to n act as compact weights, so computation stays local to a small subset.
Full chapter index
Chapters 1–7 · Understand the question
Chapters 8–14 · Reproduce the example
Chapters 15–21 · Check assumptions
Chapters 22–28 · Explore applications
Chapters 29–34 · Study and verify
Ordinary bootstrap replicates contain n sampled rows and can require repeated full-data communication. BLB seeks bootstrap-quality uncertainty using small subsets that can be processed independently.
Kleiner and colleagues introduced BLB as a scalable procedure combining bootstrap and subsampling ideas for parallel and distributed computing. Read the JRSSB article summary.
Draw s subsets of size b from the full n observations, commonly without replacement within each subset. Each subset is a small empirical support for an independent local bootstrap experiment.
Within a subset, draw a count vector from Multinomial(n;1/b,…,1/b). The counts sum to n, so the fitted statistic represents a nominal-n resample using at most b distinct rows.
Let n=1,000 and b=5. One valid local count vector is (180,210,190,205,215). It sums to 1,000 and assigns all nominal observations to the five subset rows.
| n | b | Counts | Sum |
|---|---|---|---|
| 1000 | 5 | 180,210,190,205,215 | 1000 |
For subset values (2,4,6,8,10), that count vector gives weighted mean (180×2+210×4+190×6+205×8+215×10)/1000=6.13.
| Values | Counts | Mean |
|---|---|---|
| 2,4,6,8,10 | 180,210,190,205,215 | 6.13 |
The multinomial total n preserves the full-sample scale for many estimators. This differs from fitting an estimator to only b unweighted observations and pretending its uncertainty is full-sample uncertainty.
Run r weighted resamples inside each subset and calculate the desired quality measure, such as standard error, interval width or quantile. Summarise replicates within the subset first.
Average or otherwise combine the s subset-level quality assessments. Aggregating all replicate statistics as if they came from one bootstrap distribution can confuse within- and between-subset variation.
Theory often uses b=n^gamma for gamma between roughly 0.5 and 1 under stated regularity conditions. Hardware, estimator behaviour and accuracy determine a practical grid.
For n=1,000,000 and gamma=0.7, b≈15,849. Each worker handles about 1.6% of the distinct rows while count weights still sum to one million.
More subsets improve representation of the full dataset; more resamples per subset improve each local assessment. Convergence monitoring can stop when the aggregate quality measure stabilises.
Subsets can be assigned to workers, each producing a compact summary. Communication costs are largely limited to subset assignment, model outputs and aggregation.
The estimator must accept frequency or observation weights correctly. Replicating rows physically defeats the memory advantage and can change algorithms that mishandle weights.
Random subsets should represent the full sampling distribution. Sorted, time-ordered or geographically partitioned data can produce biased local supports unless the design explicitly respects that structure.
A weighted regression can be fitted repeatedly on b rows with multinomial counts. Diagnostics must confirm that the software treats zero and large counts as frequency weights, not inverse-variance weights.
BLB can estimate prediction uncertainty for scalable estimators. Hyperparameter selection nested inside every replicate changes the target and substantially increases computation.
Ordinary bootstrap repeatedly processes n sampled cases. BLB processes small supports with nominal-n weights and aggregates subset-level uncertainty assessments.
m-out-of-n changes the resample size and may require a convergence-rate correction. BLB uses small support b but keeps multinomial resample size n to retain ordinary-bootstrap scaling under suitable conditions.
On a manageable data slice, compare BLB with the ordinary bootstrap, vary b, s and r, measure endpoint error and runtime, test weight semantics and inspect subset heterogeneity.
BLB relies on representative subsets, weighted estimator support and regularity conditions. Rare classes, clusters, time dependence, nonregular statistics and distributed-system failures need tailored designs.
Store subset ID, b, multinomial counts, weighted statistic and subset-level uncertainty summary. Check every count vector sums to n and aggregate summaries only after finishing each subset.
Use independent seeded streams by subset and replicate, verify weighted versus expanded-data fits on a tiny example, unit-test the count sum and weighted mean 6.13, and log worker failures.
BLB supports large-scale statistics, machine learning, engineering telemetry and distributed data systems. Careers combine statistical inference, numerical software and systems design.
Generate one million simulated rows, compare BLB grids with an ordinary bootstrap on a smaller benchmark, and plot accuracy against wall time, memory and network transfer.
A little bag is not a resample of size b, count weights are not survey weights, parallelism does not fix biased subsets, and many worker jobs do not guarantee independent scientific units.
CHAPTER 27 OF 34 · Explore applications
27. Connection to recent mathematics articles
The m-out-of-n guide explains smaller resample size. The balanced-bootstrap guide explains a different count constraint.
Students should verify a count vector and weighted statistic by hand. Parents can ask whether subsets represent the population and whether software interprets counts correctly.
- Sum the count vector.
- Recompute 6.13.
- Calculate n^0.7.
- Distinguish b from nominal n.
- Compare aggregation strategies.
### How many distinct rows are used locally? At most b.
### What do counts sum to? n.
### Can subsets run in parallel? Yes.
### Is BLB ordinary subsampling? No.
Report n, subset method, b or gamma, s, r, multinomial convention, weight type, seed streams, estimator, aggregation rule, worker failures, accuracy benchmark and resource use.
Approximate local storage scales with b rows rather than n duplicated rows. Total fits scale with s×r, while elapsed time depends on worker parallelism, model cost and communication.
Confirm random or design-valid subsets, nominal-n count sums, correct weight semantics, separated within/across-subset summaries, stability across tuning grids and an ordinary-bootstrap benchmark where feasible.
Continue through the Mathematics Learning Hub. Reproduce one nested, transformed or distributed resampling calculation by hand before trusting a large automated run.
Extended practice laboratory
Practice case 1: Define n
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 1. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 2: Choose subset size b
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 2. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 3: Choose subsets s
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 3. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 4: Choose replicates r
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 4. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 5: Draw subset
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 5. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 6: Draw multinomial counts
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 6. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 7: Check count sum
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 7. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 8: Fit weighted estimator
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 8. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 9: Repeat local fits
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 9. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 10: Summarise subset
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 10. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 11: Repeat subsets
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 11. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 12: Aggregate summaries
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 12. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 13: Calculate weighted mean
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 13. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 14: Change b
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 14. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 15: Change s
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 15. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 16: Change r
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 16. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 17: Check weight semantics
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 17. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 18: Check rare class
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 18. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 19: Check partition order
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 19. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 20: Parallelise subsets
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 20. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 21: Log worker failure
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 21. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 22: Compare ordinary bootstrap
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 22. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 23: Compare m-out-of-n
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 23. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 24: Name limits
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 24. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.
Practice case 25: Write conclusion
Setup: Start from the article’s bag-of-little-bootstraps mechanism for case 25. Task: Change the named quantity, recompute the dependent result and compare with the original.
Check: Preserve the resampling unit, verify the probability or weighting identity, and state one diagnostic before interpretation. Show the arithmetic, name the response and predictor units, and separate the numerical result from the claim it supports. Then vary one defensible assumption, calculate again and explain whether the conclusion changed because of the data, the fitted model or the validation purpose. Finish with one compact table or graph that could reveal a failure hidden by the summary.