Sparse Inverse Covariance Selection via Alternating Linearization Methods

Abstract

Gaussian graphical models are of great interest in statistical learning. Because the conditional independencies between different nodes correspond to zero entries in the inverse covariance matrix of the Gaussian distribution, one can learn the structure of the graph by estimating a sparse inverse covariance matrix from sample data, by solving a convex maximum likelihood problem with an ${\ell }_1$-regularization term. In this paper, we propose a first-order method based on an alternating linearization technique that exploits the problem's special structure; in particular, the subproblems solved in each iteration have closed-form solutions. Moreover, our algorithm obtains an $\epsilon$-optimal solution in $O(1/\epsilon )$ iterations. Numerical experiments on both synthetic and real data from gene association networks show that a practical version of this algorithm outperforms other competitive algorithms.

References in corpus (2)

• Projected Subgradient Methods for Learning Sparse Gaussians
• Fast Alternating Linearization Methods for Minimizing the Sum of Two Convex Functions

Cited by in corpus (28)

• Exact covariance thresholding into connected components for large-scale Graphical Lasso
• A Block Successive Upper Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization
• A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
• Logarithmic barriers for sparse matrix cones
• A Proximal Approach for a Class of Matrix Optimization Problems
• Parallel Direction Method of Multipliers
• Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems
• Linearized ADMM for Non-convex Non-smooth Optimization with Convergence Analysis
• Practical Inexact Proximal Quasi-Newton Method with Global Complexity Analysis
• Fused Multiple Graphical Lasso
• A proximal Newton framework for composite minimization: Graph learning without Cholesky decompositions and matrix inversions
• Bayesian Inference in Nonparanormal Graphical Models
• Stochastic Primal-Dual Proximal ExtraGradient Descent for Compositely Regularized Optimization
• G-AMA: Sparse Gaussian graphical model estimation via alternating minimization
• Alternating Direction Methods for Latent Variable Gaussian Graphical Model Selection
• A Flexible, Scalable and Efficient Algorithmic Framework for Primal Graphical Lasso
• Sparse Median Graphs Estimation in a High Dimensional Semiparametric Model
• Alternating Direction Method of Multipliers for Sparse Principal Component Analysis
• A Junction Tree Framework for Undirected Graphical Model Selection
• On the Theoretical Guarantees for Parameter Estimation of Gaussian Random Field Models: A Sparse Precision Matrix Approach
• A Coordinate-wise Optimization Algorithm for Sparse Inverse Covariance Selection
• An Extragradient-Based Alternating Direction Method for Convex Minimization
• Tensor Principal Component Analysis via Convex Optimization
• Constrained Bayesian ICA for Brain Connectome Inference
• Learning a Common Substructure of Multiple Graphical Gaussian Models
• The Cluster Graphical Lasso for improved estimation of Gaussian graphical models
• Estimation of Graphical Models through Structured Norm Minimization
• MARS: A second-order reduction algorithm for high-dimensional sparse precision matrices estimation