Error Estimation for Randomized Numerical Linear Algebra: Bootstrap Methods
summary
Uses the bootstrap to estimate the actual error of a single randomized sketched product or least-squares solution by resampling rows of the sketch (multiplier or without-replacement variants) to generate pseudo-errors, taking empirical quantiles, and extrapolate 1/√T from a small pilot sketch. Empirical claim: 20 bootstrap samples is often sufficient; starting from T0≈390 predicts quantiles out past T≈10,000. Method is cheap, parallelizable, uses warm starts, and matches theoretical nonasymptotic guarantees.
AI-written summary · about
chapters (19)
- 0:00Intro
- 0:53Preface about bootstrap methods
- 2:25Randomized numerical linear algebra (RandNLA)
- 2:57Trading off computational cost and accuracy
- 4:00Practical error bounds?
- 5:19Review of randomized matrix mult.
- 7:41How does error depend on sketch size?
- 10:39Estimating the error quantiles
- 11:57Intuition for bootstrap
- 15:53Bootstrap procedure (multiplier version)
- 16:34Speeding things up with extrapolation
- 18:33The cost of the bootstrap
- 20:41Brief comments on theoretical results
- 25:06Empirical performance
- 28:45Review of randomized LS
- 29:30Problem formulation error estimation
- 29:51Intuition for the bootstrap
- 30:31Algorithm (Error estimate for Classic Sketch)
- 33:25Summary
related talks
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
01h 27mPast, Present and Future of Randomized Numerical Linear Algebra I
01h 31mPast, Present and Future of Randomized Numerical Linear Algebra II
01h 04mSketching and Randomized Linear Algebra
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods
33mRandomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomp...
53mSketching and Projecting
01h 02mSampling for Linear Algebra, Statistics, and Optimization II