Celer: a Fast Solver for the Lasso with Dual Extrapolation

Mathurin MASSIAS, Alexandre Gramfort, Joseph Salmon
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:3315-3324, 2018.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-massias18a, title = {Celer: a Fast Solver for the Lasso with Dual Extrapolation}, author = {MASSIAS, Mathurin and Gramfort, Alexandre and Salmon, Joseph}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {3315--3324}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/massias18a/massias18a.pdf}, url = {https://proceedings.mlr.press/v80/massias18a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Celer: a Fast Solver for the Lasso with Dual Extrapolation %A Mathurin MASSIAS %A Alexandre Gramfort %A Joseph Salmon %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-massias18a %I PMLR %P 3315--3324 %U https://proceedings.mlr.press/v80/massias18a.html %V 80 %X 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.
APA
MASSIAS, M., Gramfort, A. & Salmon, J.. (2018). Celer: a Fast Solver for the Lasso with Dual Extrapolation. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:3315-3324 Available from https://proceedings.mlr.press/v80/massias18a.html.

Related Material