Sketching for M-Estimators: A Unified Approach to Robust Regression
summary
Presents algorithms that compress an N×D regression to about poly(D) log N rows using sparse sign sketches and diagonal subsampling, then solves the smaller convex problem. Claims input-sparsity time performance: for the Huber loss a randomized sampler + recursion gives a 1+ε relative error solution in O(nnz(A) log N + poly(D) log N) time; for a broad class of “nice” M-estimators it gives a constant-factor approximation in nnz(A)+poly(D) log N time. Core tools are Count Sketch blocks and a mixture of L1 and L2 leverage scores; sketches are lopsided embeddings that avoid contracting the optimal residual.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:11Regression
- 2:13Fitness Measures
- 5:27Huber Loss Function
- 6:24Other Examples
- 7:11Nice M-Estimators
- 10:27Our Results
- 13:30Talk Outline
- 13:40Naive Sampling Algorithm
- 15:00Leverage Score Sampling
- 17:18Leverage Coor
- 25:53Conclusions
related talks
59mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch I
01h 03mSketching as a Tool for Numerical Linear Algebra
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods
46mSketching Techniques for Kernel Density Estimation
01h 04mSketching and Randomized Linear Algebra
01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
48mComputational-Statistical Tradeoffs in Robust High-Dimensional Estimation