GAP Safe screening rules for sparse multi-task and multi-class models

Abstract

High dimensional regression benefits from sparsity promoting regularizations. Screening rules leverage the known sparsity of the solution by ignoring some variables in the optimization, hence speeding up solvers. When the procedure is proven not to discard features wrongly the rules are said to be \emph{safe}. In this paper we derive new safe rules for generalized linear models regularized with ${\ell }_1$ and ${\ell }_1/{\ell }_2$ norms. The rules are based on duality gap computations and spherical safe regions whose diameters converge to zero. This allows to discard safely more variables, in particular for low regularization parameters. The GAP Safe rule can cope with any iterative solver and we illustrate its performance on coordinate descent for multi-task Lasso, binary and multinomial logistic regression, demonstrating significant speed ups on all tested datasets with respect to previous safe rules.

in Proceedings of the 29-th Conference on Neural Information Processing Systems (NIPS), 2015

References in corpus (2)

• Safe Feature Elimination in Sparse Supervised Learning
• Dynamic Screening: Accelerating First-Order Algorithms for the Lasso and Group-Lasso

Cited by in corpus (9)

• GAP Safe Screening Rules for Sparse-Group-Lasso
• Simultaneous Safe Screening of Features and Samples in Doubly Sparse Modeling
• Graphical Lasso and Thresholding: Equivalence and Closed-form Solutions
• Gap Safe screening rules for sparsity enforcing penalties
• Dual Extrapolation for Sparse Generalized Linear Models
• Dynamic Sasvi: Strong Safe Screening for Norm-Regularized Least Squares
• Screening Rules and its Complexity for Active Set Identification
• Safe Active Feature Selection for Sparse Learning
• Screening for Sparse Online Learning