Projected Subgradient Methods for Learning Sparse Gaussians

Abstract

Gaussian Markov random fields (GMRFs) are useful in a broad range of applications. In this paper we tackle the problem of learning a sparse GMRF in a high-dimensional space. Our approach uses the l1-norm as a regularization on the inverse covariance matrix. We utilize a novel projected gradient method, which is faster than previous methods in practice and equal to the best performing of these in asymptotic complexity. We also extend the l1-regularized objective to the problem of sparsifying entire blocks within the inverse covariance matrix. Our methods generalize fairly easily to this case, while other methods do not. We demonstrate that our extensions give better generalization performance on two real domains--biological network analysis and a 2D-shape modeling image task.

Appears in Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI2008)

References in corpus (1)

• High-Dimensional Graphical Model Selection Using ${\ell }_1$-Regularized Logistic Regression

Cited by in corpus (28)

• Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation
• Brain covariance selection: better individual functional connectivity models using population prior
• Estimating time-varying networks
• Sparse Inverse Covariance Selection via Alternating Linearization Methods
• A Unified Framework for Structured Graph Learning via Spectral Constraints
• L0 Sparse Inverse Covariance Estimation
• Inferring large graphs using l1-penalized likelihood
• Markov models for fMRI correlation structure: is brain functional connectivity small world, or decomposable into networks?
• Group Sparse Priors for Covariance Estimation
• A Proximal Approach for a Class of Matrix Optimization Problems
• Inverse Covariance Estimation for High-Dimensional Data in Linear Time and Space: Spectral Methods for Riccati and Sparse Models
• Sparsistent Estimation of Time-Varying Discrete Markov Random Fields
• Inference for Sparse Conditional Precision Matrices
• A Graphical Model Formulation of Collaborative Filtering Neighbourhood Methods with Fast Maximum Entropy Training
• Joint Association Graph Screening and Decomposition for Large-scale Linear Dynamical Systems
• De-biased graphical Lasso for high-frequency data
• Improved Estimation of High-dimensional Ising Models
• A Bayesian Graphical Approach for Large-Scale Portfolio Management with Fewer Historical Data
• Estimation of sparse Gaussian graphical models with hidden clustering structure
• A Coordinate-wise Optimization Algorithm for Sparse Inverse Covariance Selection
• A dual spectral projected gradient method for log-determinant semidefinite problems
• Fast Sampling for Bayesian Max-Margin Models
• Learning a Common Substructure of Multiple Graphical Gaussian Models
• Sparse Inverse Covariance Estimation via an Adaptive Gradient-Based Method
• Fast and Accurate Graph Learning for Huge Data via Minipatch Ensembles
• Gaussian Graphical Model exploration and selection in high dimension low sample size setting
• Minimization over the l1-ball using an active-set non-monotone projected gradient
• Bayesian Inference in Sparse Gaussian Graphical Models