Gap Safe screening rules for sparsity enforcing penalties
arXiv:1611.05780
Abstract
In high dimensional regression settings, sparsity enforcing penalties have proved useful to regularize the data-fitting term. A recently introduced technique called screening rules propose to ignore some variables in the optimization leveraging the expected sparsity of the solutions and consequently leading to faster solvers. When the procedure is guaranteed not to discard variables wrongly the rules are said to be safe. In this work, we propose a unifying framework for generalized linear models regularized with standard sparsity enforcing penalties such as or norms. Our technique allows to discard safely more variables than previously considered safe rules, particularly for low regularization parameters. Our proposed Gap Safe rules (so called because they rely on duality gap computation) can cope with any iterative solver but are particularly well suited to (block) coordinate descent methods. Applied to many standard learning tasks, Lasso, Sparse-Group Lasso, multi-task Lasso, binary and multinomial logistic regression, etc., we report significant speed-ups compared to previously proposed safe rules on all tested data sets.
References in corpus (8)
- Safe Feature Elimination in Sparse Supervised Learning
- Dynamic Screening: Accelerating First-Order Algorithms for the Lasso and Group-Lasso
- The biglasso Package: A Memory- and Computation-Efficient Solver for Lasso Model Fitting with Big Data in R
- Mind the duality gap: safer rules for the Lasso
- Efficient Smoothed Concomitant Lasso Estimation for High Dimensional Regression
- GAP Safe screening rules for sparse multi-task and multi-class models
- Two-Layer Feature Reduction for Sparse-Group Lasso via Decomposition of Convex Sets
- Screening Rules for Overlapping Group Lasso