Celer: a Fast Solver for the Lasso with Dual Extrapolation
This work addresses the computational bottleneck in high-dimensional machine learning for researchers and practitioners using Lasso, offering incremental improvements to existing screening and working set techniques.
The paper tackles the slow optimization in Lasso problems by proposing a dual extrapolation technique that improves dual points, enabling tighter optimality control and better screening performance, resulting in significant computational speedups on real-world problems.
Convex sparsity-inducing regularizations are ubiquitous in high-dimensional machine learning, but solving the resulting optimization problems can be slow. To accelerate solvers, state-of-the-art approaches consist in reducing the size of the optimization problem at hand. In the context of regression, this can be achieved either by discarding irrelevant features (screening techniques) or by prioritizing features likely to be included in the support of the solution (working set techniques). Duality comes into play at several steps in these techniques. Here, we propose an extrapolation technique starting from a sequence of iterates in the dual that leads to the construction of improved dual points. This enables a tighter control of optimality as used in stopping criterion, as well as better screening performance of Gap Safe rules. Finally, we propose a working set strategy based on an aggressive use of Gap Safe screening rules. Thanks to our new dual point construction, we show significant computational speedups on multiple real-world problems.