Active Regression via Linear-Sample Sparsification

on YouTube ↗44m

" summary

Shows that agnostic L2 regression on a d‑dimensional linear class needs only about kappa log d samples if points are drawn proportional to sup_F F(x)^2 (kappa = E_x sup_F F(x)^2, and for any linear space kappa = Θ(d)), replacing the usual K = max_x sup_F F(x)^2. Uses leverage‑score importance sampling and a randomized BSS/Lee‑Sun sparsification to get Θ(d) labeled queries (Θ(k log d) unlabeled), with mean‑zero noise → ε‑relative error and arbitrary noise → (1+ε).

AI-written summary · about

" chapters (4)

1. 0:00Agnostic regression basics
2. 26:22Leverage score sampling
3. 28:39Active learning improvement
4. 33:06Nonlinear extensions

" related talks

• 56mSparsifying Generalized Linear ModelsYang Liu · Optimization and Algorithm Design 2023
• 45mHigh Dimensional Robust Sparse RegressionConstantine Caramanis · Sublinear Algorithms and Nearest-Neighbor Search
• 01h 03mSampling for Linear Algebra, Statistics, and Optimization IMichael Mahoney · Foundations of Data Science Boot Camp 2018
• 36mUnbiased Estimates for Linear Regression via Volume SamplingMichal Derezinski · Randomized Numerical Linear Algebra and Applications 2018
• 28mSketching for M-Estimators: A Unified Approach to Robust RegressionDavid P. Woodruff · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 01h 30mHigh-Dimensional Statistics IMartin Wainwright · Big Data Boot Camp 2013
• 48mInput-sparsity Time Algorithms for Embeddings and Regression ProblemsMichael Mahoney · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 45mThe Statistical Fairness-Accuracy FrontierAlireza Fallah · Learning from Heterogeneous Sources 2026