Source-linked AI summary
A highly efficient semismooth Newton augmented Lagrangian method for solving Lasso problems
Xudong Li, Defeng Sun, Kim-Chuan Toh
TL;DR
The paper addresses the difficulty of solving large-scale Lasso problems accurately and efficiently despite many existing solvers. It proposes Ssnal, which combines augmented Lagrangian and semismooth Newton methods while exploiting second-order sparsity. Numerical studies report fast, robust performance on difficult real-data problems, subject to limitations when linear operators are available only as black boxes.
Problem
Existing Lasso solvers do not efficiently handle difficult large-scale regression problems with real data.
Method
Ssnal combines an augmented Lagrangian method with semismooth Newton steps and exploits the sparsity of the second-order generalized Hessian.
Results
Ssnal outperforms competing solvers on difficult large-scale Lasso instances, solving a dataset with approximately 4.3 million features in 20 seconds.
Takeaways & Limitations
The proposed framework is reported as efficient and robust for large-scale ℓ1-regularized least-squares problems, including degenerate instances.
Takeaways & Limitations
When A and A* are available only as black-box linear maps, second-order sparsity can hardly be fully exploited.
Abstract
from arXiv · showhide
We develop a fast and robust algorithm for solving large scale convex composite optimization models with an emphasis on the $\ell_1$-regularized least squares regression (Lasso) problems. Despite the fact that there exist a large number of solvers in the literature for the Lasso problems, we found that no solver can efficiently handle difficult large scale regression problems with real data. By leveraging on available error bound results to realize the asymptotic superlinear convergence property of the augmented Lagrangian algorithm, and by exploiting the second order sparsity of the problem through the semismooth Newton method, we are able to propose an algorithm, called {\sc Ssnal}, to efficiently solve the aforementioned difficult problems. Under very mild conditions, which hold automatically for Lasso problems, both the primal and the dual iteration sequences generated by {\sc Ssnal} possess a fast linear convergence rate, which can even be superlinear asymptotically. Numerical comparisons between our approach and a number of state-of-the-art solvers, on real data sets, are presented to demonstrate the high efficiency and robustness of our proposed algorithm in solving difficult large scale Lasso problems.
1 Introduction
The paper targets efficient, robust solvers for large-scale Lasso and related convex composite problems. Ssnal combines augmented Lagrangian and semismooth Newton techniques to exploit second-order sparsity and achieve fast convergence without nondegeneracy assumptions.
- Lasso is widely used in compressive sensing, high-dimensional variable selection, image reconstruction, statistics, and machine learning.
- Existing Lasso solvers use either first-order gradient information or second-order information, with second-order methods generally relying on nondegeneracy assumptions.
- The approach avoids nondegeneracy assumptions by analyzing well-conditioned symmetric positive definite generalized Jacobian matrices.
- Ssnal solves the Lasso dual using a semismooth Newton augmented Lagrangian framework that exploits sparsity in the second-order generalized Hessian.
- For large-scale sparse Lasso problems, Ssnal reaches desired accuracy in at most a few dozen outer iterations with inexpensive inner semismooth Newton subproblems.
- The paper establishes asymptotic superlinear augmented Lagrangian convergence from the Lasso problem’s piecewise linear-quadratic structure and develops related convergence analysis.
2 Preliminaries
The preliminaries develop stability and error-bound tools for the dual KKT mapping. Under mild assumptions, these tools establish metric subregularity, supporting linear and asymptotically superlinear convergence of Ssnal.
- Metric subregularity and error bounds are introduced as stability properties used to analyze augmented Lagrangian convergence.
- Assumption 1 requires h* to be essentially smooth and p* to be an indicator or support function of a nonempty polyhedral convex set.
- The paper formulates a general convex composite model, its dual, Lagrangian, KKT system, and associated maximal monotone operators.
- Under essential smoothness, the KKT system can be rewritten with ∇h* and restricted to int(dom h*) × X.
- The critical cone and second-order sufficient condition characterize the local structure used in the metric-subregularity analysis.
- If the KKT system has a solution, Assumption 1 and the second-order sufficient condition imply metric subregularity of Tl at the corresponding solution.
- For Lasso and elastic-net regularized least squares, polyhedrality ensures the error-bound condition; analogous results are stated for logistic regression operators.
3 An augmented Lagrangian method with asymptotic superlinear convergence
The paper develops Ssnal, an inexact augmented Lagrangian method whose semismooth Newton subproblems exploit second-order sparsity. Under error-bound and regularity conditions, its primal and dual sequences converge globally and can converge asymptotically superlinearly.
- Algorithm framework: Ssnal applies an inexact augmented Lagrangian method to the dual convex composite problem, using a semismooth Newton method for its subproblems.The algorithm updates the primal variable and penalty parameter iteratively while solving inner problems approximately.
- Global convergence: Under Assumption 2 and a nonempty primal solution set, Ssnal produces bounded sequences whose primal iterates converge to an optimal solution and whose dual iterates converge to the unique optimal dual solution.The dual limit lies in int(dom h∗) × dom p∗.
- Convergence analysis: Metric subregularity and error-bound conditions support fast local convergence of both primal and dual iteration sequences.The convergence analysis uses metric subregularity of the KKT mapping and stopping criteria for the inner subproblems.
- Convergence analysis: If the penalty parameter diverges, the primal and dual sequences converge Q-superlinearly and R-superlinearly, respectively.The paper states that Ssnal is asymptotically superlinearly convergent for the dual of the Lasso problem.
- Efficient implementation: For Lasso, the semismooth Newton generalized Hessian is positive definite and sparse, enabling efficient solution of the Newton systems through second-order sparsity.The active index set reduces the costs of computing AU A^T and AU A^T d from O(m^2n) and O(mn) to O(m^2r) and O(mr), respectively.
- Efficient implementation: When r ≪ m, additional numerical linear algebra reduces the total Newton-system cost to O(r^2(m + r)).Here r is the cardinality of the active index set J, which is typically much smaller than n because of the sparsity-promoting regularizer.
4 Numerical experiments for Lasso problems
Experiments compare Ssnal with first- and second-order Lasso solvers on large-scale regression and Sparco instances. Ssnal is generally faster and more robust on difficult problems, while its advantage is less clear on easy instances where second-order sparsity cannot be fully exploited.
- Experimental setup: The experiments compare Ssnal with mfIPM, FPCAS, APG, ADMM, LADMM, and PSSas using large-scale regression datasets and Sparco instances.Tests use LIBSVM/UCI regression data and two Sparco instances, with accuracy measured by a relative KKT residual.
- Large-scale regression: Ssnal solves log1p.E2006.train with approximately 4.3 million features in 20 seconds and can be up to 300 times faster than mfIPM.Both Ssnal and mfIPM remain robust despite huge dimensions and possibly badly conditioned data, with Ssnal more efficient across the tested instances.
- Scaling: Normalization leaves Ssnal generally invariant and still much faster and more robust, whereas APG and ADMM-type solvers perform worse after scaling.PSSas solves only 5 of 22 instances and fails on all instances when λc = 10^-4.
- Sparco collection: All algorithms perform well on the easy srcsep1 and srcsep2 instances, so Ssnal has no clear advantage; limited access to A and A* also prevents fully exploiting second-order sparsity.Ssnal remains generally faster than mfIPM, APG, and LADMM and is comparable with FPCAS in this setting.
5 Conclusion
The paper proposes Ssnal, an inexact augmented Lagrangian method combining semismooth Newton steps with second-order sparsity exploitation for large-scale convex composite problems. Numerical evidence supports its efficiency and robustness on large-scale ℓ1-regularized least-squares problems.
- Ssnal is an inexact augmented Lagrangian method designed for large-scale convex composite optimization, especially ℓ1-regularized least-squares problems.
- The semismooth Newton component enables Ssnal to exploit the problems’ second-order sparsity.
- Ssnal has an asymptotic superlinear convergence rate within the proposed augmented Lagrangian framework.
- Numerical results demonstrate Ssnal’s superior efficiency and robustness for large-scale ℓ1-regularized least-squares problems.The authors also suggest adapting the framework to other large-scale convex composite optimization problems.