Skip to Main content Skip to Navigation
Conference papers

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

Eugène Ndiaye 1, 2 Olivier Fercoq 1, 2 Alexandre Gramfort 1, 2 Joseph Salmon 1, 2 
1 S2A - Signal, Statistique et Apprentissage
LTCI - Laboratoire Traitement et Communication de l'Information
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 safe. In this paper we derive new safe rules for generalized linear models regularized with ℓ1 and ℓ1/ℓ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.
Complete list of metadata
Contributor : TelecomParis HAL Connect in order to contact the contributor
Submitted on : Friday, September 13, 2019 - 4:42:40 PM
Last modification on : Tuesday, October 19, 2021 - 11:16:12 AM


  • HAL Id : hal-02287197, version 1


Eugène Ndiaye, Olivier Fercoq, Alexandre Gramfort, Joseph Salmon. GAP Safe screening rules for sparse multi-task and multi-class models. Conference on Neural Information Processing Systems, Dec 2015, Montréal, Canada. ⟨hal-02287197⟩



Record views