# Mind the duality gap: safer rules for the Lasso

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2015.

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

- [Beyond L1: Faster and Better Sparse Models with skglm](https://mlsanity.com/paper/2204.07826/) (2022)
- [An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification](https://mlsanity.com/paper/2208.06058/) (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)
- [Sparse Subspace Clustering in Diverse Multiplex Network Model](https://mlsanity.com/paper/2206.07602/) (2022)
- [Coordinate Descent for SLOPE](https://mlsanity.com/paper/2210.14780/) (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)
- [Generalized Low-Rank Update: Model Parameter Bounds for Low-Rank Training Data Modifications](https://mlsanity.com/paper/2306.12670/) (2023)
- [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)
- [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)
- [Safe Screening Rules for Group OWL Models](https://mlsanity.com/paper/2504.03152/) (2025)
- [Concatenated Matrix SVD: Compression Bounds, Incremental Approximation, and Error-Constrained Clustering](https://mlsanity.com/paper/2601.11626/) (2026)
- [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)
- [A Screening Strategy for Structured Optimization Involving Nonconvex ℓq,p Regularization](https://mlsanity.com/paper/2208.02161/) (2022)
- [Fast Screening Rules for Optimal Design via Quadratic Lasso Reformulation](https://mlsanity.com/paper/2310.08939/) (2023)
- [Dynamic Incremental Optimization for Best Subset Selection](https://mlsanity.com/paper/2402.02322/) (2024)
- [A Safe Screening Rule with Bi-level Optimization of nu Support Vector Machine](https://mlsanity.com/paper/2403.01769/) (2024)
- [Distributionally Robust Safe Sample Elimination under Covariate Shift](https://mlsanity.com/paper/2406.05964/) (2024)
- [Safe Screening Rules for Group SLOPE](https://mlsanity.com/paper/2506.09451/) (2025)
- [Efficient Solvers for SLOPE in R, Python, Julia, and C++](https://mlsanity.com/paper/2511.02430/) (2025)

## Abstract (arXiv)

Screening rules allow to early discard irrelevant variables from the optimization in Lasso problems, or its derivatives, making solvers faster. In this paper, we propose new versions of the so-called textitsafe rules for the Lasso. Based on duality gap considerations, our new rules create safe test regions whose diameters converge to zero, provided that one relies on a converging solver. This property helps screening out more variables, for a wider range of regularization parameter values. In addition to faster convergence, we prove that we correctly identify the active sets (supports) of the solutions in finite time. While our proposed strategy can cope with any solver, its performance is demonstrated using a coordinate descent algorithm particularly adapted to machine learning use cases. Significant computing time reductions are obtained with respect to previous safe rules.