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

arXiv: https://arxiv.org/abs/1506.03736 · HTML: https://mlsanity.com/paper/1506.03736/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2015.

## Built on by (most cited first, 16 of 16)

- [Smooth Bilevel Programming for Sparse Regularization](https://mlsanity.com/paper/2106.01429/) (2021)
- [Dynamic Sasvi: Strong Safe Screening for Norm-Regularized Least Squares](https://mlsanity.com/paper/2102.04108/) (2021)
- [Generalized Low-Rank Update: Model Parameter Bounds for Low-Rank Training Data Modifications](https://mlsanity.com/paper/2306.12670/) (2023)
- [Screening for Sparse Online Learning](https://mlsanity.com/paper/2101.06982/) (2021)
- [Distributed Dynamic Safe Screening Algorithms for Sparse Regularization](https://mlsanity.com/paper/2204.10981/) (2022)
- [Distributionally Robust Safe Screening](https://mlsanity.com/paper/2404.16328/) (2024)
- [Distributionally Robust Coreset Selection under Covariate Shift](https://mlsanity.com/paper/2501.14253/) (2025)
- [Safe Screening Rules for Group OWL Models](https://mlsanity.com/paper/2504.03152/) (2025)
- [Safe Distributionally Robust Feature Selection under Covariate Shift](https://mlsanity.com/paper/2603.16062/) (2026)
- [Screening for a Reweighted Penalized Conditional Gradient Method](https://mlsanity.com/paper/2107.01106/) (2021)
- [Best Subset Selection with Efficient Primal-Dual Algorithm](https://mlsanity.com/paper/2207.02058/) (2022)
- [Dynamic Incremental Optimization for Best Subset Selection](https://mlsanity.com/paper/2402.02322/) (2024)
- [Dual Feature Reduction for the Sparse-group Lasso and its Adaptive Variant](https://mlsanity.com/paper/2405.17094/) (2024)
- [Distributionally Robust Safe Sample Elimination under Covariate Shift](https://mlsanity.com/paper/2406.05964/) (2024)
- [Generalized Kernel Inducing Points by Duality Gap for Dataset Distillation](https://mlsanity.com/paper/2502.12607/) (2025)
- [Gap Safe Screening Rules for Fast Training of Robust Support Vector Machines under Feature Noise](https://mlsanity.com/paper/2603.25221/) (2026)

## Abstract (arXiv)

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.