On the Power of Preconditioning in Sparse Linear Regression
summary
Proves that using the precision-matrix graph and a nested dissection preconditioner lets Lasso attain the information-theoretic Mahalanobis error rate when the graph has bounded treewidth, with performance degrading smoothly as treewidth grows. Builds a preconditioner from samples (via empirical covariance) and demonstrates huge gains: for random-walk covariances Lasso needs ~√D samples while preconditioned Lasso needs only log D samples. Also gives matching lower bounds showing no preconditioner makes Lasso match best-subset selection on certain graphs.
AI-written summary · about
related talks
30mPreconditioning In Sparse Linear Regression Using Graphical Structure
44mScalable Algorithmic Primitives for Data Science
40mThe Trimmed Lasso: Sparse Recovery Guarantees And Practical Optimization
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
25mAki720
28mRandomized Constrained Matrix Decompositions
31mRandomized Riemannian Preconditioning for Quadratically Constrained Problems
01h 31mPast, Present and Future of Randomized Numerical Linear Algebra II