Randomized Least Squares Regression: Combining Model- and Algorithm-Induced Uncertainties
summary
Derives exact equalities for the combined estimator bias and variance when row-sketching a Gaussian linear model, using pseudo-inverses, conditional expectations and deterministic perturbation bounds; introduces a comparison hat matrix to compare sketched vs original problems and shows the sketched estimator is unbiased iff the sketch preserves full column rank, otherwise the variance can be singular (in a toy example 12 of the 16 sketches rank deficient); provides exact equalities for total mean and variance and tighter multiplicative error bounds driven by condition number and angle.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:31Least Squares/Regression Models
- 1:45Objective
- 2:35Existing Work
- 3:03Model-Induced Uncertainty
- 8:47Perturbed Solution
- 10:32Example: Hat Matrix, and Comparison Hat Matrix
- 11:57Multiplicative Perturbation Bounds
- 13:28Conditioning on S. Mean
- 14:26Conditioning on S: Variance
- 15:27Conditioning on S: Summary
- 16:13Combined Uncertainty: Mean
- 17:09Combined Uncertainty: Variance
- 17:55Example: Best Case for Uniform Sampling
related talks
01h 04mSketching and Randomized Linear Algebra
28mSketching for M-Estimators: A Unified Approach to Robust Regression
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
53mSketching and Projecting
01h 03mSketching as a Tool for Numerical Linear Algebra
01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II
01h 27mPast, Present and Future of Randomized Numerical Linear Algebra I
01h 02mPrediction, Generalization, Complexity: Revisiting the Classical View from Statistics Part 2