A Greedy Homotopy Method for Regression with Nonconvex Constraints

Fabian Wauthier, Peter Donnelly
Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, PMLR 38:1051-1060, 2015.

Abstract

The goal of this paper is to estimate sparse linear regression models, where for a given partition \mathcalG of input variables, the selected variables are chosen from a \it diverse set of groups in \mathcalG. We consider a novel class of nonconvex constraint functions, and develop RepLasso, a greedy homotopy method that exploits geometrical properties of the constraint functions to build a sequence of suitably adapted convex surrogate problems. We prove that in some situations RepLasso recovers the global minima path of the nonconvex problem. Moreover, even if it does not recover the global minima, we prove that it will often do no worse than the Lasso in terms of (signed) support recovery, while in practice outperforming it. We show empirically that the strategy can also be used to improve over various other Lasso-style algorithms. Finally, a GWAS of ankylosing spondylitis highlights our method’s practical utility.

Cite this Paper

BibTeX
@InProceedings{pmlr-v38-wauthier15, title = {{A Greedy Homotopy Method for Regression with Nonconvex Constraints}}, author = {Wauthier, Fabian and Donnelly, Peter}, booktitle = {Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics}, pages = {1051--1060}, year = {2015}, editor = {Lebanon, Guy and Vishwanathan, S. V. N.}, volume = {38}, series = {Proceedings of Machine Learning Research}, address = {San Diego, California, USA}, month = {09--12 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v38/wauthier15.pdf}, url = {https://proceedings.mlr.press/v38/wauthier15.html}, abstract = {The goal of this paper is to estimate sparse linear regression models, where for a given partition \mathcalG of input variables, the selected variables are chosen from a \it diverse set of groups in \mathcalG. We consider a novel class of nonconvex constraint functions, and develop RepLasso, a greedy homotopy method that exploits geometrical properties of the constraint functions to build a sequence of suitably adapted convex surrogate problems. We prove that in some situations RepLasso recovers the global minima path of the nonconvex problem. Moreover, even if it does not recover the global minima, we prove that it will often do no worse than the Lasso in terms of (signed) support recovery, while in practice outperforming it. We show empirically that the strategy can also be used to improve over various other Lasso-style algorithms. Finally, a GWAS of ankylosing spondylitis highlights our method’s practical utility.} }
Endnote
%0 Conference Paper %T A Greedy Homotopy Method for Regression with Nonconvex Constraints %A Fabian Wauthier %A Peter Donnelly %B Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2015 %E Guy Lebanon %E S. V. N. Vishwanathan %F pmlr-v38-wauthier15 %I PMLR %P 1051--1060 %U https://proceedings.mlr.press/v38/wauthier15.html %V 38 %X The goal of this paper is to estimate sparse linear regression models, where for a given partition \mathcalG of input variables, the selected variables are chosen from a \it diverse set of groups in \mathcalG. We consider a novel class of nonconvex constraint functions, and develop RepLasso, a greedy homotopy method that exploits geometrical properties of the constraint functions to build a sequence of suitably adapted convex surrogate problems. We prove that in some situations RepLasso recovers the global minima path of the nonconvex problem. Moreover, even if it does not recover the global minima, we prove that it will often do no worse than the Lasso in terms of (signed) support recovery, while in practice outperforming it. We show empirically that the strategy can also be used to improve over various other Lasso-style algorithms. Finally, a GWAS of ankylosing spondylitis highlights our method’s practical utility.
RIS
TY - CPAPER TI - A Greedy Homotopy Method for Regression with Nonconvex Constraints AU - Fabian Wauthier AU - Peter Donnelly BT - Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics DA - 2015/02/21 ED - Guy Lebanon ED - S. V. N. Vishwanathan ID - pmlr-v38-wauthier15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 38 SP - 1051 EP - 1060 L1 - http://proceedings.mlr.press/v38/wauthier15.pdf UR - https://proceedings.mlr.press/v38/wauthier15.html AB - The goal of this paper is to estimate sparse linear regression models, where for a given partition \mathcalG of input variables, the selected variables are chosen from a \it diverse set of groups in \mathcalG. We consider a novel class of nonconvex constraint functions, and develop RepLasso, a greedy homotopy method that exploits geometrical properties of the constraint functions to build a sequence of suitably adapted convex surrogate problems. We prove that in some situations RepLasso recovers the global minima path of the nonconvex problem. Moreover, even if it does not recover the global minima, we prove that it will often do no worse than the Lasso in terms of (signed) support recovery, while in practice outperforming it. We show empirically that the strategy can also be used to improve over various other Lasso-style algorithms. Finally, a GWAS of ankylosing spondylitis highlights our method’s practical utility. ER -
APA
Wauthier, F. & Donnelly, P.. (2015). A Greedy Homotopy Method for Regression with Nonconvex Constraints. Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 38:1051-1060 Available from https://proceedings.mlr.press/v38/wauthier15.html.

Related Material