# Expanding boundaries of Gap Safe screening

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 57 references that are in the map.
- First posted on arXiv 22 Feb 2021.

## Builds on (most cited first, 13 of 13)

- [Gap Safe screening rules for sparsity enforcing penalties](https://mlsanity.com/paper/1611.05780/) (2016)
- [Mind the duality gap: safer rules for the Lasso](https://mlsanity.com/paper/1505.03410/) (2015)
- [Nonlinear hyperspectral unmixing with robust nonnegative matrix factorization](https://mlsanity.com/paper/1401.5649/) (2014)
- [Screening Tests for Lasso Problems](https://mlsanity.com/paper/1405.4897/) (2014)
- [Safe Screening With Variational Inequalities and Its Application to LASSO](https://mlsanity.com/paper/1307.7577/) (2013)
- [Dynamic Screening: Accelerating First-Order Algorithms for the Lasso and Group-Lasso](https://mlsanity.com/paper/1412.4080/) (2014)
- [GAP Safe Screening Rules for Sparse-Group-Lasso](https://mlsanity.com/paper/1602.06225/) (2016)
- [Two-Layer Feature Reduction for Sparse-Group Lasso via Decomposition of Convex Sets](https://mlsanity.com/paper/1410.4210/) (2014)
- [Scaling SVM and Least Absolute Deviations via Exact Data Reduction](https://mlsanity.com/paper/1310.7048/) (2013)
- [Primal-Dual Algorithms for Non-negative Matrix Factorization with the Kullback-Leibler Divergence](https://mlsanity.com/paper/1412.1788/) (2014)
- [Safe Triplet Screening for Distance Metric Learning](https://mlsanity.com/paper/1802.03923/) (2018)
- [From safe screening rules to working sets for faster Lasso-type solvers](https://mlsanity.com/paper/1703.07285/) (2017)
- [Stable safe screening and structured dictionaries for faster L1 regularization](https://mlsanity.com/paper/1812.06635/) (2018)

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

- [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)
- [Efficient Model Selection for Predictive Pattern Mining Model by Safe Pattern Pruning](https://mlsanity.com/paper/2306.13561/) (2023)
- [Accelerating Non-Negative and Bounded-Variable Linear Regression Algorithms with Safe Screening](https://mlsanity.com/paper/2202.07258/) (2022)
- [Safe Screening for Unbalanced Optimal Transport](https://mlsanity.com/paper/2307.00247/) (2023)
- [Generalized Kernel Inducing Points by Duality Gap for Dataset Distillation](https://mlsanity.com/paper/2502.12607/) (2025)
- [Simpler Methods Work Better for L1 Penalized Logistic Models and Large Datasets](https://mlsanity.com/paper/2609.23995/) (2026)

## Abstract (arXiv)

Sparse optimization problems are ubiquitous in many fields such as statistics, signal/image processing and machine learning. This has led to the birth of many iterative algorithms to solve them. A powerful strategy to boost the performance of these algorithms is known as safe screening: it allows the early identification of zero coordinates in the solution, which can then be eliminated to reduce the problem's size and accelerate convergence. In this work, we extend the existing Gap Safe screening framework by relaxing the global strong-concavity assumption on the dual cost function. Instead, we exploit local regularity properties, that is, strong concavity on well-chosen subsets of the domain. The non-negativity constraint is also integrated to the existing framework. Besides making safe screening possible to a broader class of functions that includes beta-divergences (e.g., the Kullback-Leibler divergence), the proposed approach also improves upon the existing Gap Safe screening rules on previously applicable cases (e.g., logistic regression). The proposed general framework is exemplified by some notable particular cases: logistic function, beta = 1.5 and Kullback-Leibler divergences. Finally, we showcase the effectiveness of the proposed screening rules with different solvers (coordinate descent, multiplicative-update and proximal gradient algorithms) and different data sets (binary classification, hyperspectral and count data).