Efficient sparse semismooth Newton methods for the clustered Lasso problem

DOI10.1137/18M1207752MaRDI QIDQ5231697zbMATH OpenFDO

Authors Meixia Lin, Yong-Jin Liu, Defeng Sun, Kim-Chuan Toh

Publication date 27 August 2019

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.07181

zbMATH Keywords

augmented Lagrangian methodclustered Lassoconvex minimizationsemismooth Newton method

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Convex programming (90C25) Applications of mathematical programming (90C90)

Abstract: We focus on solving the clustered lasso problem, which is a least squares problem with the $el{l}_1$-type penalties imposed on both the coefficients and their pairwise differences to learn the group structure of the regression parameters. Here we first reformulate the clustered lasso regularizer as a weighted ordered-lasso regularizer, which is essential in reducing the computational cost from $O(n^2)$ to $O(nlog(n))$. We then propose an inexact semismooth Newton augmented Lagrangian ({sc Ssnal}) algorithm to solve the clustered lasso problem or its dual via this equivalent formulation, depending on whether the sample size is larger than the dimension of the features. An essential component of the {sc Ssnal} algorithm is the computation of the generalized Jacobian of the proximal mapping of the clustered lasso regularizer. Based on the new formulation, we derive an efficient procedure for its computation. Comprehensive results on the global convergence and local linear convergence of the {sc Ssnal} algorithm are established. For the purpose of exposition and comparison, we also summarize/design several first-order methods that can be used to solve the problem under consideration, but with the key improvement from the new formulation of the clustered lasso regularizer. As a demonstration of the applicability of our algorithms, numerical experiments on the clustered lasso problem are performed. The experiments show that the {sc Ssnal} algorithm substantially outperforms the best alternative algorithm for the clustered lasso problem.

Recommendations

• A highly efficient semismooth Newton augmented Lagrangian method for solving lasso problems
• An efficient Hessian based algorithm for solving large-scale sparse group Lasso problems
• Sparse regression with exact clustering
• A dual semismooth Newton based augmented Lagrangian method for large-scale linearly constrained sparse group square-root Lasso problems
• On efficiently solving the subproblems of a level-set method for fused lasso problems

Cites work

• A dual algorithm for the solution of nonlinear variational problems via finite element approximation
• A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• A highly efficient semismooth Newton augmented Lagrangian method for solving lasso problems
• A Newton-CG augmented Lagrangian method for semidefinite programming
• A nonsmooth version of Newton's method
• A unified primal-dual algorithm framework based on Bregman iteration
• Active set algorithms for isotonic regression; a unifying framework
• An efficient Hessian based algorithm for solving large-scale sparse group Lasso problems
• An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming
• Asymptotic Convergence Analysis of the Proximal Point Algorithm
• Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
• Convex Analysis
• Fused Lasso approach in regression coefficients clustering -- learning parameter heterogeneity in data integration
• Hankel matrix rank minimization with applications to system identification and realization
• scientific article; zbMATH DE number 4082855 (Why is no real title available?)
• scientific article; zbMATH DE number 3574917 (Why is no real title available?)
• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• Model Selection and Estimation in Regression with Grouped Variables
• Monotone Operators and the Proximal Point Algorithm
• Newton and quasi-Newton methods for normal maps with polyhedral sets
• On efficiently solving the subproblems of a level-set method for fused lasso problems
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope
• On the R-superlinear convergence of the KKT residuals generated by the augmented Lagrangian method for convex composite conic programming
• Regularization and Variable Selection Via the Elastic Net
• Semismooth and Semiconvex Functions in Constrained Optimization
• Semismooth Matrix-Valued Functions
• Simultaneous Regression Shrinkage, Variable Selection, and Supervised Clustering of Predictors with OSCAR
• Solving the OSCAR and SLOPE models using a semismooth Newton-based augmented Lagrangian method
• Some continuity properties of polyhedral multifunctions
• Sparse Reconstruction by Separable Approximation
• Sparse regression with exact clustering
• Sparsity and Smoothness Via the Fused Lasso
• Split Bregman method for large scale fused Lasso

Cited in

(25)

• Sparse regression with exact clustering
• An efficient Hessian based algorithm for singly linearly and box constrained least squares regression
• A semismooth Newton-based augmented Lagrangian algorithm for density matrix least squares problems
• A geometric proximal gradient method for sparse least squares regression with probabilistic simplex constraint
• An efficient Hessian based algorithm for solving large-scale sparse group Lasso problems
• On efficiently solving the subproblems of a level-set method for fused lasso problems
• A highly efficient semismooth Newton augmented Lagrangian method for solving lasso problems
• An efficient linearly convergent regularized proximal point algorithm for fused multiple graphical Lasso problems
• Efficient sparse Hessian-based semismooth Newton algorithms for Dantzig selector
• Difference-of-Convex Algorithms for a Class of Sparse Group \ell₀ Regularized Optimization Problems
• A proximal point dual Newton algorithm for solving group graphical Lasso problems
• The linear and asymptotically superlinear convergence rates of the augmented Lagrangian method with a practical relative error criterion
• Solving the OSCAR and SLOPE models using a semismooth Newton-based augmented Lagrangian method
• A dual-based stochastic inexact algorithm for a class of stochastic nonsmooth convex composite problems
• A dual semismooth Newton based augmented Lagrangian method for large-scale linearly constrained sparse group square-root Lasso problems
• An efficient algorithm for Fantope-constrained sparse principal subspace estimation problem
• Minimum residual shift-splitting iteration method for non-Hermitian positive definite and positive semidefinite linear systems
• A VMiPG method for composite optimization with nonsmooth term having no closed-form proximal mapping
• A highly efficient algorithm for solving exclusive lasso problems
• Efficient path algorithms for clustered Lasso and OSCAR
• An inexact semismooth Newton-based augmented Lagrangian algorithm for multi-task Lasso problems
• On the analysis of semismooth Newton-type methods for composite optimization
• Multiple regression for matrix and vector predictors: models, theory, algorithms, and beyond
• The augmented Lagrangian methods: overview and recent advances
• A semismooth Newton based augmented Lagrangian algorithm for Lovász theta SDP problem

Describes a project that uses

Uses Software

• LIBSVM
• FPC_AS

This page was built for publication: Efficient sparse semismooth Newton methods for the clustered Lasso problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5231697)