Mind the duality gap: safer rules for the Lasso
arXiv:1505.03410
Abstract
Screening rules allow to early discard irrelevant variables from the optimization in Lasso problems, or its derivatives, making solvers faster. In this paper, we propose new versions of the so-called for the Lasso. Based on duality gap considerations, our new rules create safe test regions whose diameters converge to zero, provided that one relies on a converging solver. This property helps screening out more variables, for a wider range of regularization parameter values. In addition to faster convergence, we prove that we correctly identify the active sets (supports) of the solutions in finite time. While our proposed strategy can cope with any solver, its performance is demonstrated using a coordinate descent algorithm particularly adapted to machine learning use cases. Significant computing time reductions are obtained with respect to previous safe rules.
erratum to ICML 2015, "The authors would like to thanks Jalal Fadili and Jingwei Liang for helping clarifying some misleading statements on the equicorrelation set"
References in corpus (5)
- Nearly unbiased variable selection under minimax concave penalty
- Pathwise coordinate optimization
- Safe Feature Elimination in Sparse Supervised Learning
- Complexity Analysis of the Lasso Regularization Path
- Small-sample Brain Mapping: Sparse Recovery on Spatially Correlated Designs with Randomization and Clustering
Cited by in corpus (23)
- The iterative reweighted Mixed-Norm Estimate for spatio-temporal MEG/EEG source reconstruction
- GAP Safe Screening Rules for Sparse-Group-Lasso
- Efficient Smoothed Concomitant Lasso Estimation for High Dimensional Regression
- Graphical Lasso and Thresholding: Equivalence and Closed-form Solutions
- Gap Safe screening rules for sparsity enforcing penalties
- From safe screening rules to working sets for faster Lasso-type solvers
- Expanding boundaries of Gap Safe screening
- Secure Approximation Guarantee for Cryptographically Private Empirical Risk Minimization
- Stable safe screening and structured dictionaries for faster L1 regularization
- A scalable hierarchical lasso for gene-environment interactions
- Safe Screening for the Generalized Conditional Gradient Method
- Safe Triplet Screening for Distance Metric Learning
- Feedback-Controlled Sequential Lasso Screening
- A Fast, Principled Working Set Algorithm for Exploiting Piecewise Linear Structure in Convex Problems
- Proceedings of the third "international Traveling Workshop on Interactions between Sparse models and Technology" (iTWIST'16)
- One to beat them all: "RYU" -- a unifying framework for the construction of safe balls
- The Symmetry of a Simple Optimization Problem in Lasso Screening
- Safe Sample Screening for Robust Support Vector Machine
- Interval-based Prediction Uncertainty Bound Computation in Learning with Missing Values
- Safe Element Screening for Submodular Function Minimization
- Joint Screening Tests for LASSO
- Safe Feature Elimination for Non-Negativity Constrained Convex Optimization
- Safe Screening Rules for -Regression