# A highly efficient semismooth Newton augmented Lagrangian method for solving Lasso problems

arXiv: https://arxiv.org/abs/1607.05428 · HTML: https://mlsanity.com/paper/1607.05428/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jul 2016.

## Built on by (most cited first, 14 of 14)

- [TransFusion: Covariate-Shift Robust Transfer Learning for High-Dimensional Regression](https://mlsanity.com/paper/2404.01153/) (2024)
- [A Semismooth Newton Stochastic Proximal Point Algorithm with Variance Reduction](https://mlsanity.com/paper/2204.00406/) (2022)
- [FAStEN: An Efficient Adaptive Method for Feature Selection and Estimation in High-Dimensional Functional Regressions](https://mlsanity.com/paper/2303.14801/) (2023)
- [Lightweight Deep Unfolding Networks with Enhanced Robustness for Infrared Small Target Detection](https://mlsanity.com/paper/2509.08205/) (2025)
- [A new computationally efficient algorithm to solve Feature Selection for Functional Data Classification in high-dimensional spaces](https://mlsanity.com/paper/2401.05765/) (2024)
- [Non-Asymptotic Uncertainty Quantification in High-Dimensional Learning](https://mlsanity.com/paper/2407.13666/) (2024)
- [Accelerating Multi-Block Constrained Optimization Through Learning to Optimize](https://mlsanity.com/paper/2409.17320/) (2024)
- [A dual semismooth Newton based augmented Lagrangian method for large-scale linearly constrained sparse group square-root Lasso problems](https://mlsanity.com/paper/2111.13878/) (2021)
- [Multi-task Learning for Gaussian Graphical Regressions with High Dimensional Covariates](https://mlsanity.com/paper/2205.10672/) (2022)
- [Self-concordant smoothing in proximal quasi-Newton algorithms for large-scale convex composite optimization](https://mlsanity.com/paper/2309.01781/) (2023)
- [A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport](https://mlsanity.com/paper/2310.14087/) (2023)
- [A proximal-proximal majorization-minimization algorithm for nonconvex tuning-free robust regression problems](https://mlsanity.com/paper/2106.13683/) (2021)
- [Fast Computation of Superquantile-Constrained Optimization Through Implicit Scenario Reduction](https://mlsanity.com/paper/2405.07965/) (2024)
- [Convex Estimation of Gaussian Graphical Regression Models with Covariates](https://mlsanity.com/paper/2410.06326/) (2024)

## Abstract (arXiv)

We develop a fast and robust algorithm for solving large scale convex composite optimization models with an emphasis on the ℓ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.