The Trimmed Lasso: Sparse Recovery Guarantees And Practical Optimization
summary
Addresses best-subset sparse recovery by using the trimmed lasso penalty (L1 minus L1 of the top-k entries) and proves stability: any local minimizer with objective below the k-sparse projection yields L1 error bounded by noise plus the distance of x0 to k-sparsity divided by the one-sided RIP constant alpha_{2k} (alpha_{2k}>0 only). Introduces a smooth generalized soft-min surrogate, a homotopy MM scheme that reduces each step to weighted L1 solves, and a careful O(KD) evaluation routine; simulations show correct-support recovery with roughly 20% fewer samples than competitors.
AI-written summary · about
chapters (11)
- 0:00Introduction to sparsity
- 1:38Problem formulation
- 4:00Existing algorithmic approaches
- 9:08Empirical performance analysis
- 12:54The trimmed lasso penalty
- 18:01Recovery guarantees
- 23:44Optimization challenges
- 26:13Generalized soft-min surrogate
- 30:56Majorization-minimization
- 34:00Conclusion and results
- 35:52Q&A and announcements
related talks
01h 05mRecovering Hidden Sparsity via Sum of Squares
45mHigh Dimensional Robust Sparse Regression
01h 06mAnalytic Methods for Supervised Learning III
42mAdaptive Sparse Recovery with Limited Adaptivity
01h 26mStreaming, Sketching and Sufficient Statistics II
09mOn the Power of Preconditioning in Sparse Linear Regression
45mSemi-Random Models and Robustness in Unsupervised Learning
29mLatent Variable models and Subset Smoothing