mlsanityData to 7 Oct 2026

Mind the duality gap: safer rules for the Lasso

arXiv 1505.03410 ↗First posted 13 May 2015stat.ML cs.LG math.OCcited by 31

Not on the map. Why?

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.

Key facts. Cited by 31 papers in the map (data through 7 Oct 2026). First posted on arXiv 13 May 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 9; 2023: 4; 2024: 5; 2025: 3; 2026: 3.

31 papers.

Sort:

  1. 2022Beyond L1: Faster and Better Sparse Models with skglmcited by 16
  2. 2022An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identificationcited by 14
  3. 2021Expanding boundaries of Gap Safe screeningcited by 7
  4. 2021Safe rules for the identification of zeros in the solutions of the SLOPE problemcited by 6
  5. 2022Safe Screening for Logistic Regression with ℓ0-ℓ2 Regularizationcited by 6
  6. 2021Dynamic Sasvi: Strong Safe Screening for Norm-Regularized Least Squarescited by 4
  7. 2022Sparse Subspace Clustering in Diverse Multiplex Network Modelcited by 4
  8. 2022Coordinate Descent for SLOPEcited by 4
  9. 2021The Hessian Screening Rulecited by 3
  10. 2021Look-Ahead Screening Rules for the Lassocited by 3
  11. 2021Continuation Path with Linear Convergence Ratecited by 3
  12. 2023Generalized Low-Rank Update: Model Parameter Bounds for Low-Rank Training Data Modificationscited by 3
19 more
  1. 2022Beyond GAP screening for Lasso by exploiting new dual cutting half-spaces with supplementary materialcited by 2
  2. 2023Efficient Model Selection for Predictive Pattern Mining Model by Safe Pattern Pruningcited by 2
  3. 2023One to beat them all: "RYU" -- a unifying framework for the construction of safe ballscited by 2
  4. 2024Strong Screening Rules for Group-based SLOPE Modelscited by 2
  5. 2022Distributed Dynamic Safe Screening Algorithms for Sparse Regularizationcited by 1
  6. 2024Distributionally Robust Safe Screeningcited by 1
  7. 2025Safe Screening Rules for Group OWL Modelscited by 1
  8. 2026Concatenated Matrix SVD: Compression Bounds, Incremental Approximation, and Error-Constrained Clusteringcited by 1
  9. 2026Safe Distributionally Robust Feature Selection under Covariate Shiftcited by 1
  10. 2021Screening for a Reweighted Penalized Conditional Gradient Methodcited by 0
  11. 2022Best Subset Selection with Efficient Primal-Dual Algorithmcited by 0
  12. 2022A Screening Strategy for Structured Optimization Involving Nonconvex ℓq,p Regularizationcited by 0
  13. 2023Fast Screening Rules for Optimal Design via Quadratic Lasso Reformulationcited by 0
  14. 2024Dynamic Incremental Optimization for Best Subset Selectioncited by 0
  15. 2024A Safe Screening Rule with Bi-level Optimization of nu Support Vector Machinecited by 0
  16. 2024Distributionally Robust Safe Sample Elimination under Covariate Shiftcited by 0
  17. 2025Safe Screening Rules for Group SLOPEcited by 0
  18. 2025Efficient Solvers for SLOPE in R, Python, Julia, and C++cited by 0
  19. 2026Gap Safe Screening Rules for Fast Training of Robust Support Vector Machines under Feature Noisecited by 0