Screening Tests for Lasso Problems

Abstract

This paper is a survey of dictionary screening for the lasso problem. The lasso problem seeks a sparse linear combination of the columns of a dictionary to best match a given target vector. This sparse representation has proven useful in a variety of subsequent processing and decision tasks. For a given target vector, dictionary screening quickly identifies a subset of dictionary columns that will receive zero weight in a solution of the corresponding lasso problem. These columns can be removed from the dictionary prior to solving the lasso problem without impacting the optimality of the solution obtained. This has two potential advantages: it reduces the size of the dictionary, allowing the lasso problem to be solved with less resources, and it may speed up obtaining a solution. Using a geometrically intuitive framework, we provide basic insights for understanding useful lasso screening tests and their limitations. We also provide illustrative numerical studies on several datasets.

Accepted to IEEE Transactions on Pattern Analysis and Machine Intelligence

References in corpus (4)

• Safe Feature Elimination in Sparse Supervised Learning
• Complexity Analysis of the Lasso Regularization Path
• Sequential Lasso for feature selection with ultra-high dimensional feature space
• Feedback-Controlled Sequential Lasso Screening

Cited by in corpus (33)

• Mind the duality gap: safer rules for the Lasso
• Estimating Feature-Label Dependence Using Gini Distance Statistics
• Estimating Sparse Signals Using Integrated Wideband Dictionaries
• Hybrid safe-strong rules for efficient optimization in lasso-type problems
• GAP Safe screening rules for sparse multi-task and multi-class models
• Simultaneous Safe Screening of Features and Samples in Doubly Sparse Modeling
• Safe RuleFit: Learning Optimal Sparse Rule Model by Meta Safe Screening
• Gap Safe screening rules for sparsity enforcing penalties
• Safe squeezing for antisparse coding
• Dual Extrapolation for Sparse Generalized Linear Models
• Fast OSCAR and OWL Regression via Safe Screening Rules
• From safe screening rules to working sets for faster Lasso-type solvers
• ExSIS: Extended Sure Independence Screening for Ultrahigh-dimensional Linear Models
• Expanding boundaries of Gap Safe screening
• Secure Approximation Guarantee for Cryptographically Private Empirical Risk Minimization
• Safe Pattern Pruning: An Efficient Approach for Predictive Pattern Mining
• Stable safe screening and structured dictionaries for faster L1 regularization
• Dynamic Sasvi: Strong Safe Screening for Norm-Regularized Least Squares
• Feedback-Controlled Sequential Lasso Screening
• Adaptive Sieving with PPDNA: Generating Solution Paths of Exclusive Lasso Models
• The Symmetry of a Simple Optimization Problem in Lasso Screening
• Interval-based Prediction Uncertainty Bound Computation in Learning with Missing Values
• On Newton Screening
• Tighter Bound Estimation of Sensitivity Analysis for Incremental and Decremental Data Modification
• Screening for Sparse Online Learning
• Persistent Reductions in Regularized Loss Minimization for Variable Selection
• Safe Feature Elimination for Non-Negativity Constrained Convex Optimization
• Efficiently Bounding Optimal Solutions after Small Data Modification in Large-Scale Empirical Risk Minimization
• Safe Screening Rules for ${\ell }_0$-Regression
• Accelerated Sparse Bayesian Learning via Screening Test and Its Applications
• Joint Screening Tests for LASSO
• l1-norm quantile regression screening rule via the dual circumscribed sphere
• Regularization parameter selection for low rank matrix recovery