Sampling for Linear Algebra, Statistics, and Optimization II

on YouTube ↗01h 02m

" summary

Mixing importance sampling with a small uniform fraction reduces estimator variance, with an empirical sweet spot near half leverage plus half uniform (roughly 0.7 in one setup). Claims rest on Taylor expansions and asymptotic MSE formulas that put sampling probabilities in the denominator, and on algorithmic proxies for leverage like low-stretch spanning trees for graphs (million × 10 million incidence example). Practical workflows use sketching plus iterate via Hessian sketch, and bootstrap heuristics predict ~63% coverage from coupon-collector sampling.

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 3:02Extensions and Applications of Basic Rand NLA Principles
3. 9:06Statistics versus machine learning
4. 14:00Bias and variance of subsampling estimators (1 of 3)
5. 17:25Bias and variance of subsampling estimators (3 of 3)
6. 22:08Tackling statistical properties of subsampling estimators
7. 23:56Subsampling Estimators for Estimating the Parameter
8. 27:49The statistical approach
9. 28:47A statistical perspective on the algorithmic approach
10. 30:14Corollary of key structural lemma
11. 34:42A statistical perspective on randomized sketching (2 of 2)
12. 35:34Sketched ridge regression
13. 39:19Summary of connection with Bootstrapping
14. 42:49Optimization Overview
15. 50:45Brief overview of stochastic optimization
16. 53:49Sub-sampled second-order optimization

" related talks

• 01h 02mImportance Sampling in High Dimensions via HashingMoses Charikar · Sublinear Algorithms and Nearest-Neighbor Search
• 33mRandomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomp...Tamara Kolda · Extroverted Sublinear Algorithms 2024
• 01h 26mStreaming, Sketching and Sufficient Statistics IIGraham Cormode · Big Data Boot Camp 2013
• 32mRandomized Numerical Linear Algebra: OverviewPetros Drineas · Randomized Numerical Linear Algebra and Applications 2018
• 36mUnbiased Estimates for Linear Regression via Volume SamplingMichal Derezinski · Randomized Numerical Linear Algebra and Applications 2018
• 34mError Estimation for Randomized Numerical Linear Algebra: Bootstrap MethodsMiles Lopes · Randomized Numerical Linear Algebra and Applications 2018
• 48mRandomized Numerical Linear AlgebraPetros Drineas · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 01mRobustness, Stochastics, Uncertainty 1Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017