A proximal point algorithm for log-determinant optimization with group Lasso regularization

J. Yang, Defeng Sun, K.-C. Toh

Research output: Journal article publicationJournal articleAcademic researchpeer-review

17 Citations (Scopus)

Abstract

We consider the covariance selection problem where variables are clustered into groups and the inverse covariance matrix is expected to have a blockwise sparse structure. This problem is realized via penalizing the maximum likelihood estimation of the inverse covariance matrix by group Lasso regularization. We propose to solve the resulting log-determinant optimization problem with the classical proximal point algorithm (PPA). At each iteration, as it is difficult to update the primal variables directly, we first solve the dual subproblem by an inexact semismooth Newton-CG method and then update the primal variables by explicit formulas based on the computed dual variables. We also propose to accelerate the PPA by an inexact generalized Newton's method when the iterate is close to the solution. Theoretically, we prove that at the optimal solution, the nonsingularity of the generalized Hessian matrices of the dual subproblem is equivalent to the constraint nondegeneracy condition for the primal problem. Global and local convergence results are also presented for the proposed PPA. Moreover, based on the augmented Lagrangian function of the dual problem we derive an alternating direction method (ADM), which is easily implementable and is demonstrated to be efficient for random problems. Numerical results, including comparisons with the ADM on both synthetic and real data, are presented to demonstrate that the proposed Newton-CG based PPA is stable and efficient and, in particular, outperforms the ADM when high accuracy is required. © 2013 Society for Industrial and Applied Mathematics.
Original languageEnglish
Pages (from-to)857-893
Number of pages37
JournalSIAM Journal on Optimization
Volume23
Issue number2
DOIs
Publication statusPublished - 1 Aug 2013
Externally publishedYes

Keywords

  • Alternating direction method
  • Augmented Lagrangian
  • Covariance selection
  • Gaussian graphical model
  • Group Lasso regularization
  • Log-determinant optimization
  • Newton's method
  • Proximal point algorithm

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Cite this