# From safe screening rules to working sets for faster Lasso-type solvers

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Mar 2017.

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

- [Expanding boundaries of Gap Safe screening](https://mlsanity.com/paper/2102.10846/) (2021)
- [High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent](https://mlsanity.com/paper/2207.01560/) (2022)
- [A Generic Branch-and-Bound Algorithm for ℓ0-Penalized Problems with Supplementary Material](https://mlsanity.com/paper/2506.03974/) (2025)

## Abstract (arXiv)

Convex sparsity-promoting regularizations are ubiquitous in modern statistical learning. By construction, they yield solutions with few non-zero coefficients, which correspond to saturated constraints in the dual optimization formulation. Working set (WS) strategies are generic optimization techniques that consist in solving simpler problems that only consider a subset of constraints, whose indices form the WS. Working set methods therefore involve two nested iterations: the outer loop corresponds to the definition of the WS and the inner loop calls a solver for the subproblems. For the Lasso estimator a WS is a set of features, while for a Group Lasso it refers to a set of groups. In practice, WS are generally small in this context so the associated feature Gram matrix can fit in memory. Here we show that the Gauss-Southwell rule (a greedy strategy for block coordinate descent techniques) leads to fast solvers in this case. Combined with a working set strategy based on an aggressive use of so-called Gap Safe screening rules, we propose a solver achieving state-of-the-art performance on sparse learning problems. Results are presented on Lasso and multi-task Lasso estimators.