Unbiased Estimates for Linear Regression via Volume Sampling

on YouTube ↗36m

" summary

Volume sampling picks D rows with probability proportional to det(X_S^T X_S) and yields an unbiased least‑squares estimator whose expected total loss equals (d+1) times the optimal loss and whose expected pseudoinverse equals X^+ estimator unbiased (exact identity). Algorithms sample by repeated downsampling with a rejection trick, achieving roughly runtime O(n d^2) after X^T X is formed. Extensions give a regularized volume sample that needs about the statistical dimension many points, a matrix‑variance formula for the estimator, and experiments showing strong gains when the label budget is small.

AI-written summary · about

" chapters (20)

1. 0:00Intro
2. 0:35Least squares regression
3. 1:37Answer: one label
4. 4:54Volume Sampling (DRVW06, AB13)
5. 6:57Linear regression with dimension many labels
6. 10:31What about iid leverage score sampling?
7. 14:25Why volume sampling?
8. 16:03Volume sampling is closed under subsampling
9. 16:39Outline
10. 18:31Expectation formulas: key technique
11. 20:19Expectation formulas key technique
12. 21:11Unbiased estimators are easy to combine
13. 23:15Open problems for unbiased estimators
14. 24:08Reverse iterative volume sampling
15. 24:46Faster algorithm via rejection sampling
16. 25:17Extension: regularized volume sampling DW18a
17. 26:38Extension: Leveraged volume sampling DWH18
18. 28:14Efficiency of volume sampling
19. 31:09Conclusion
20. 31:54References

" related talks

• 48mRandomized Numerical Linear AlgebraPetros Drineas · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 44mActive Regression via Linear-Sample SparsificationEric Price · Real-Time Decision Making 2018
• 01h 02mSampling for Linear Algebra, Statistics, and Optimization IIMichael Mahoney · Foundations of Data Science Boot Camp 2018
• 01h 03mSampling for Linear Algebra, Statistics, and Optimization IMichael Mahoney · Foundations of Data Science Boot Camp 2018
• 28mSketching for M-Estimators: A Unified Approach to Robust RegressionDavid P. Woodruff · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 33mRandomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomp...Tamara Kolda · Extroverted Sublinear Algorithms 2024
• 01h 27mPast, Present and Future of Randomized Numerical Linear Algebra IMichael Mahoney, Petros Drineas · Big Data Boot Camp 2013
• 45mHigh Dimensional Robust Sparse RegressionConstantine Caramanis · Sublinear Algorithms and Nearest-Neighbor Search