Mind the duality gap: safer rules for the Lasso

Olivier Fercoq, Alexandre Gramfort, Joseph Salmon
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:333-342, 2015.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-fercoq15, title = {Mind the duality gap: safer rules for the Lasso}, author = {Fercoq, Olivier and Gramfort, Alexandre and Salmon, Joseph}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {333--342}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/fercoq15.pdf}, url = {https://proceedings.mlr.press/v37/fercoq15.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Mind the duality gap: safer rules for the Lasso %A Olivier Fercoq %A Alexandre Gramfort %A Joseph Salmon %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-fercoq15 %I PMLR %P 333--342 %U https://proceedings.mlr.press/v37/fercoq15.html %V 37 %X 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.
RIS
TY - CPAPER TI - Mind the duality gap: safer rules for the Lasso AU - Olivier Fercoq AU - Alexandre Gramfort AU - Joseph Salmon BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-fercoq15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 333 EP - 342 L1 - http://proceedings.mlr.press/v37/fercoq15.pdf UR - https://proceedings.mlr.press/v37/fercoq15.html AB - 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. ER -
APA
Fercoq, O., Gramfort, A. & Salmon, J.. (2015). Mind the duality gap: safer rules for the Lasso. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:333-342 Available from https://proceedings.mlr.press/v37/fercoq15.html.

Related Material