A highly efficient semismooth Newton augmented Lagrangian method for solving lasso problems
From MaRDI portal
Abstract: We develop a fast and robust algorithm for solving large scale convex composite optimization models with an emphasis on the -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.
Recommendations
- An efficient Hessian based algorithm for solving large-scale sparse group Lasso problems
- Efficient sparse semismooth Newton methods for the clustered Lasso problem
- A dual semismooth Newton based augmented Lagrangian method for large-scale linearly constrained sparse group square-root Lasso problems
- Solving the OSCAR and SLOPE models using a semismooth Newton-based augmented Lagrangian method
- A dual based semismooth Newton-type algorithm for solving large-scale sparse Tikhonov regularization problems
Cites work
- A coordinate gradient descent method for nonsmooth separable minimization
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- A family of second-order methods for convex \(\ell _1\)-regularized optimization
- A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A nonsmooth version of Newton's method
- A note on upper Lipschitz stability, error bounds, and critical multipliers for Lipschitz-continuous KKT systems
- A partial proximal point algorithm for nuclear norm regularized matrix least squares problems
- A second-order method for convex _1-regularized optimization with active-set prediction
- A semismooth Newton method with multidimensional filter globalization for l₁-optimization
- A unified approach to error bounds for structured convex optimization problems
- A unified primal-dual algorithm framework based on Bregman iteration
- An inexact successive quadratic approximation method for L-1 regularized optimization
- Asymptotic Convergence Analysis of the Proximal Point Algorithm
- Atomic Decomposition by Basis Pursuit
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Convex Analysis
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- scientific article; zbMATH DE number 1099075 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Implicit Functions and Solution Mappings
- Level-set methods for convex optimization
- Local behavior of an iterative framework for generalized equations with nonisolated solutions
- Local strong convexity and local Lipschitz continuity of the gradient of convex functions
- Matrix-free interior point method for compressed sensing problems
- Monotone Operators and the Proximal Point Algorithm
- NESTA: A fast and accurate first-order method for sparse recovery
- On the Linear Convergence of Descent Methods for Convex Essentially Smooth Minimization
- Optimization and nonsmooth analysis
- Probing the Pareto frontier for basis pursuit solutions
- Proximal Newton-type methods for minimizing composite functions
- Regularization and Variable Selection Via the Elastic Net
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Semismooth and Semiconvex Functions in Constrained Optimization
- Semismooth Matrix-Valued Functions
- Some continuity properties of polyhedral multifunctions
- Sparse Reconstruction by Separable Approximation
- The Adaptive Lasso and Its Oracle Properties
- Upper Lipschitz behavior of solutions to perturbed \(C^{1,1}\) programs
- Variational Analysis
Cited in
(99)- Convergence of the augmented decomposition algorithm
- Double fused Lasso penalized LAD for matrix regression
- A dual based semismooth Newton-type algorithm for solving large-scale sparse Tikhonov regularization problems
- A unified primal dual active set algorithm for nonconvex sparse recovery
- An efficient Hessian based algorithm for singly linearly and box constrained least squares regression
- Smoothing Newton method for \(\ell^0\)-\(\ell^2\) regularized linear inverse problem
- Unified convergence analysis of a second-order method of multipliers for nonlinear conic programming
- High-performance statistical computing in the computing environments of the 2020s
- A semismooth Newton-based augmented Lagrangian algorithm for density matrix least squares problems
- A decomposition method for Lasso problems with zero-sum constraint
- An inexact successive quadratic approximation method for a class of difference-of-convex optimization problems
- An investigation on semismooth Newton based augmented Lagrangian method for image restoration
- An inexact interior-point Lagrangian decomposition algorithm with inexact oracles
- tSSNALM: a fast two-stage semi-smooth Newton augmented Lagrangian method for sparse CCA
- An active-set proximal-Newton algorithm for \(\ell_1\) regularized optimization problems with box constraints
- An efficient Hessian based algorithm for solving large-scale sparse group Lasso problems
- On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope
- A semismooth Newton method for support vector classification and regression
- An efficient augmented Lagrangian method with semismooth Newton solver for total generalized variation
- A note on application of Nesterov's method in solving lasso-type problems
- Composite difference-MAX programs for modern statistical estimation problems
- On efficiently solving the subproblems of a level-set method for fused lasso problems
- A linearly convergent majorized ADMM with indefinite proximal terms for convex composite programming and its applications
- scientific article; zbMATH DE number 7370526 (Why is no real title available?)
- An efficient linearly convergent regularized proximal point algorithm for fused multiple graphical Lasso problems
- Calibrated zero-norm regularized LS estimator for high-dimensional error-in-variables regression
- Efficient sparse Hessian-based semismooth Newton algorithms for Dantzig selector
- Sparse approximations with interior point methods
- A new homotopy proximal variable-metric framework for composite convex minimization
- Efficient projection onto the intersection of a half-space and a box-like set and its generalized Jacobian
- An iterative reduction FISTA algorithm for large-scale LASSO
- Difference-of-Convex Algorithms for a Class of Sparse Group \ell₀ Regularized Optimization Problems
- An Asymptotically Superlinearly Convergent Semismooth Newton Augmented Lagrangian Method for Linear Programming
- An efficient augmented Lagrangian method for support vector machine
- scientific article; zbMATH DE number 7306909 (Why is no real title available?)
- The linear and asymptotically superlinear convergence rates of the augmented Lagrangian method with a practical relative error criterion
- Iteratively reweighted FGMRES and FLSQR for sparse reconstruction
- Proximal gradient method for nonsmooth optimization over the Stiefel manifold
- Solving the OSCAR and SLOPE models using a semismooth Newton-based augmented Lagrangian method
- An efficient proximal block coordinate homotopy method for large-scale sparse least squares problems
- Spectral operators of matrices: semismoothness and characterizations of the generalized Jacobian
- On the nonergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming
- Efficient sparse semismooth Newton methods for the clustered Lasso problem
- Randomized block proximal damped Newton method for composite self-concordant minimization
- A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
- An inexact semismooth Newton method on Riemannian manifolds with application to duality-based total variation denoising
- An active-set proximal quasi-Newton algorithm for ℓ1-regularized minimization over a sphere constraint
- A Trust-region Method for Nonsmooth Nonconvex Optimization
- An efficient semismooth Newton method for adaptive sparse signal recovery problems
- scientific article; zbMATH DE number 7668288 (Why is no real title available?)
- A dual-based stochastic inexact algorithm for a class of stochastic nonsmooth convex composite problems
- Transformed primal-dual methods for nonlinear saddle point systems
- An efficient semi-proximal ADMM algorithm for low-rank and sparse regularized matrix minimization problems with real-world applications
- Generalized damped Newton algorithms in nonsmooth optimization via second-order subdifferentials
- A dual active set method for \(\ell1\)-regularized problem
- A semismooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifolds
- A dual semismooth Newton based augmented Lagrangian method for large-scale linearly constrained sparse group square-root Lasso problems
- Globally convergent coderivative-based generalized Newton methods in nonsmooth optimization
- On proximal augmented Lagrangian based decomposition methods for dual block-angular convex composite programming problems
- Proximal gradient/semismooth Newton methods for projection onto a polyhedron via the duality-gap-active-set strategy
- A global two-stage algorithm for non-convex penalized high-dimensional linear regression problems
- Local convergence analysis of augmented Lagrangian method for nonlinear semidefinite programming
- A semismooth Newton stochastic proximal point algorithm with variance reduction
- Nonsmooth optimization over the Stiefel manifold and beyond: proximal gradient method and recent variants
- An efficient sieving-based secant method for sparse optimization problems with least-squares constraints
- A fast and effective algorithm for sparse linear regression with \(\ell_p\)-norm data fidelity and elastic net regularization
- Smoothing composite proximal gradient algorithm for sparse group Lasso problems with nonsmooth loss functions
- A VMiPG method for composite optimization with nonsmooth term having no closed-form proximal mapping
- A highly efficient algorithm for solving exclusive lasso problems
- Nonconvex regularizer and homotopy-based sparse optimization: convergent algorithms and applications
- Nonconvex truncated conditional value at risk-based sparse linear regression
- Wasserstein distributionally robust optimization and its tractable regularization formulation
- A quadratically convergent semismooth Newton method for nonlinear semidefinite programming without generalized Jacobian regularity
- Multi-Task Learning for Gaussian Graphical Regressions with High Dimensional Covariates
- Quasi-Newton L-BFGS based inexact primal-dual proximal point algorithms to solve nonsmooth convex composite programs for sparse signal recovery applications
- Adaptive sieving: a dimension reduction technique for sparse optimization problems
- An efficient active-set method with applications to sparse approximations and risk minimization
- An inexact Bregman proximal difference-of-convex algorithm with two types of relative stopping criteria
- A trust region-type normal map-based semismooth Newton method for nonsmooth nonconvex composite optimization
- FAStEN: An Efficient Adaptive Method for Feature Selection and Estimation in High-Dimensional Functional Regressions
- An inexact semismooth Newton-based augmented Lagrangian algorithm for multi-task Lasso problems
- A guide to stochastic optimisation for large-scale inverse problems
- On the analysis of semismooth Newton-type methods for composite optimization
- An L₂ regularization reduced quadratic surface support vector machine model
- On a globally convergent semismooth^* Newton method in nonsmooth nonconvex optimization
- A Riemannian optimization approach to clustering problems
- An inexact proximal Newton method for nonconvex composite minimization
- An augmented Lagrangian primal-dual semismooth Newton method for multi-block composite optimization
- Multiple regression for matrix and vector predictors: models, theory, algorithms, and beyond
- A new inexact gradient descent method with applications to nonsmooth convex optimization
- An efficient algorithm for the weighted elastic net penalized quantile regression
- A second-order descent method with active-set prediction for group-sparse optimization
- Self-concordant smoothing in proximal quasi-Newton algorithms for large-scale convex composite optimization
- Fast computation of superquantile-constrained optimization through implicit scenario reduction
- Inexact proximal linearized algorithm for difference of convex composite functions
- The augmented Lagrangian methods: overview and recent advances
- A semismooth Newton based augmented Lagrangian algorithm for Lovász theta SDP problem
- An augmented Lagrangian method-based framework in the adjoint space for sparse reconstruction of acoustic sources
- Hybrid safe-strong rules for efficient optimization in Lasso-type problems
This page was built for publication: A highly efficient semismooth Newton augmented Lagrangian method for solving lasso problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606653)
