# Gap Safe screening rules for sparsity enforcing penalties

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Nov 2016.

## Built on by (most cited first, 30 of 39)

- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [Only Train Once: A One-Shot Neural Network Training And Pruning Framework](https://mlsanity.com/paper/2107.07467/) (2021)
- [Benchopt: Reproducible, efficient and collaborative optimization benchmarks](https://mlsanity.com/paper/2206.13424/) (2022)
- [Beyond L1: Faster and Better Sparse Models with skglm](https://mlsanity.com/paper/2204.07826/) (2022)
- [Smooth Bilevel Programming for Sparse Regularization](https://mlsanity.com/paper/2106.01429/) (2021)
- [An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification](https://mlsanity.com/paper/2208.06058/) (2022)
- [Smooth over-parameterized solvers for non-smooth structured optimization](https://mlsanity.com/paper/2205.01385/) (2022)
- [Expanding boundaries of Gap Safe screening](https://mlsanity.com/paper/2102.10846/) (2021)
- [Safe rules for the identification of zeros in the solutions of the SLOPE problem](https://mlsanity.com/paper/2110.11784/) (2021)
- [Safe Screening for Logistic Regression with ℓ0-ℓ2 Regularization](https://mlsanity.com/paper/2202.00467/) (2022)
- [Dynamic Sasvi: Strong Safe Screening for Norm-Regularized Least Squares](https://mlsanity.com/paper/2102.04108/) (2021)
- [Hybrid ISTA: Unfolding ISTA With Convergence Guarantees Using Free-Form Deep Neural Networks](https://mlsanity.com/paper/2204.11640/) (2022)
- [The Hessian Screening Rule](https://mlsanity.com/paper/2104.13026/) (2021)
- [Look-Ahead Screening Rules for the Lasso](https://mlsanity.com/paper/2105.05648/) (2021)
- [Continuation Path with Linear Convergence Rate](https://mlsanity.com/paper/2112.05104/) (2021)
- [Screening for Sparse Online Learning](https://mlsanity.com/paper/2101.06982/) (2021)
- [Beyond GAP screening for Lasso by exploiting new dual cutting half-spaces with supplementary material](https://mlsanity.com/paper/2203.00987/) (2022)
- [Efficient Model Selection for Predictive Pattern Mining Model by Safe Pattern Pruning](https://mlsanity.com/paper/2306.13561/) (2023)
- [One to beat them all: "RYU" -- a unifying framework for the construction of safe balls](https://mlsanity.com/paper/2312.00640/) (2023)
- [Strong Screening Rules for Group-based SLOPE Models](https://mlsanity.com/paper/2405.15357/) (2024)
- [Feature Selection from Differentially Private Correlations](https://mlsanity.com/paper/2408.10862/) (2024)
- [Distributed Dynamic Safe Screening Algorithms for Sparse Regularization](https://mlsanity.com/paper/2204.10981/) (2022)
- [Self-concordant smoothing in proximal quasi-Newton algorithms for large-scale convex composite optimization](https://mlsanity.com/paper/2309.01781/) (2023)
- [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)
- [Accelerating Non-Negative and Bounded-Variable Linear Regression Algorithms with Safe Screening](https://mlsanity.com/paper/2202.07258/) (2022)
- [Best Subset Selection with Efficient Primal-Dual Algorithm](https://mlsanity.com/paper/2207.02058/) (2022)
- [A Screening Strategy for Structured Optimization Involving Nonconvex ℓq,p Regularization](https://mlsanity.com/paper/2208.02161/) (2022)
- [Reducing Discretization Error in the Frank-Wolfe Method](https://mlsanity.com/paper/2304.01432/) (2023)
- [Safe Screening for Unbalanced Optimal Transport](https://mlsanity.com/paper/2307.00247/) (2023)

## Abstract (arXiv)

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 ℓ1 or ℓ1/ℓ2 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.