A Greedy Homotopy Method for Regression with Nonconvex Constraints
This addresses variable selection in high-dimensional data like GWAS, offering a novel method with proven and empirical improvements over existing approaches, though it is incremental as it builds on Lasso-style algorithms.
The paper tackles the problem of constrained least squares regression with nonconvex constraints to select few variables from few groups, introducing RepLasso, a greedy homotopy algorithm that in some cases recovers global minima and empirically outperforms Lasso and other methods, as demonstrated in a GWAS application for ankylosing spondylitis.
Constrained least squares regression is an essential tool for high-dimensional data analysis. Given a partition $\mathcal{G}$ of input variables, this paper considers a particular class of nonconvex constraint functions that encourage the linear model to select a small number of variables from a small number of groups in $\mathcal{G}$. Such constraints are relevant in many practical applications, such as Genome-Wide Association Studies (GWAS). Motivated by the efficiency of the Lasso homotopy method, we present RepLasso, a greedy homotopy algorithm that tries to solve the induced sequence of nonconvex problems by solving a sequence of suitably adapted convex surrogate problems. We prove that in some situations RepLasso recovers the global minima of the nonconvex problem. Moreover, even if it does not recover global minima, we prove that in relevant cases it will still do no worse than the Lasso in terms of support and signed support recovery, while in practice outperforming it. We show empirically that the strategy can also be used to improve over other Lasso-style algorithms. Finally, a GWAS of ankylosing spondylitis highlights our method's practical utility.