Efficient sparse semismooth Newton methods for the clustered lasso problem

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)

Abstract

We focus on solving the clustered Lasso problem, which is a least squares problem with the \ell 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(n2) to O(nlog(n)). We then propose an inexact semismooth Newton augmented Lagrangian (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 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 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 Ssnal algorithm substantially outperforms the best alternative algorithm for the clustered Lasso problem.

Original languageEnglish
Pages (from-to)2026-2052
Number of pages27
JournalSIAM Journal on Optimization
Volume29
Issue number3
DOIs
Publication statusPublished - 30 Jul 2019

Keywords

  • Augmented Lagrangian method
  • Clustered Lasso
  • Convex minimization
  • Semismooth Newton method

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Cite this