Preconditioning In Sparse Linear Regression Using Graphical Structure
summary
Shows a concrete claim: when covariates form a low treewidth Gaussian graphical model there is an explicit change-of-basis (a preconditioner) that preserves sparsity up to a factor O(treewidth log n) and makes LASSO recovery nearly information‑theoretic optimal, with sample complexity about k·t·log^2 n. The preconditioner uses the graph and empirical covariances (few samples suffice), is demonstrated on the random‑walk chain, and a matching lower bound via grid‑minor structure proves no sparse preconditioner works for high‑treewidth graphs.
AI-written summary · about
chapters (6)
- 0:00Introduction to the problem
- 3:55Lasso and its limitations
- 7:56Random walk analysis
- 13:54Preconditioning strategies
- 20:43Low tree-width graphs
- 24:07Complexity and future work
related talks
09mOn the Power of Preconditioning in Sparse Linear Regression
44mScalable Algorithmic Primitives for Data Science
01h 00mTensor Graphical Models For Complex And High Dimensional Data
45mHigh Dimensional Robust Sparse Regression
47mMultiscale Analysis on and of Graphs
40mThe Trimmed Lasso: Sparse Recovery Guarantees And Practical Optimization
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
28mRandomized Constrained Matrix Decompositions