Majorization-Minimization Dual Stagewise Algorithm for Generalized Lasso
This work addresses a computational bottleneck for researchers and practitioners using generalized lasso in large-scale, non-linear statistical problems, though it is incremental as it builds on existing stagewise and majorization-minimization techniques.
The paper tackled the computational inefficiency of the generalized lasso in non-Gaussian and non-linear models by proposing the MM-DUST algorithm, which efficiently traces full solution paths with demonstrated effectiveness in simulations and applications like regularized logistic regression and Cox models.
The generalized lasso is a natural generalization of the celebrated lasso approach to handle structural regularization problems. Many important methods and applications fall into this framework, including fused lasso, clustered lasso, and constrained lasso. To elevate its effectiveness in large-scale problems, extensive research has been conducted on the computational strategies of generalized lasso. However, to our knowledge, most studies are under the linear setup, with limited advances in non-Gaussian and non-linear models. We propose a majorization-minimization dual stagewise (MM-DUST) algorithm to efficiently trace out the full solution paths of the generalized lasso problem. The majorization technique is incorporated to handle different convex loss functions through their quadratic majorizers. Utilizing the connection between primal and dual problems and the idea of ``slow-brewing'' from stagewise learning, the minimization step is carried out in the dual space through a sequence of simple coordinate-wise updates on the dual coefficients with a small step size. Consequently, selecting an appropriate step size enables a trade-off between statistical accuracy and computational efficiency. We analyze the computational complexity of MM-DUST and establish the uniform convergence of the approximated solution paths. Extensive simulation studies and applications with regularized logistic regression and Cox model demonstrate the effectiveness of the proposed approach.