Model Selection Through Sparse Maximum Likelihood Estimation

Abstract

We consider the problem of estimating the parameters of a Gaussian or binary distribution in such a way that the resulting undirected graphical model is sparse. Our approach is to solve a maximum likelihood problem with an added l_1-norm penalty term. The problem as formulated is convex but the memory requirements and complexity of existing interior point methods are prohibitive for problems with more than tens of nodes. We present two new algorithms for solving problems with at least a thousand nodes in the Gaussian case. Our first algorithm uses block coordinate descent, and can be interpreted as recursive l_1-norm penalized regression. Our second algorithm, based on Nesterov's first order method, yields a complexity estimate with a better dependence on problem size than existing interior point methods. Using a log determinant relaxation of the log partition function (Wainwright & Jordan (2006)), we show that these same algorithms can be used to solve an approximate sparse maximum likelihood problem for the binary case. We test our algorithms on synthetic data, as well as on gene expression and senate voting records data.

References in corpus (1)

• A direct formulation for sparse PCA using semidefinite programming

Cited by in corpus (35)

• The huge Package for High-dimensional Undirected Graph Estimation in R
• Estimating time-varying networks
• Stability Approach to Regularization Selection (StARS) for High Dimensional Graphical Models
• Estimation of Simultaneously Sparse and Low Rank Matrices
• Forest Density Estimation
• Adaptive Lasso for High Dimensional Regression and Gaussian Graphical Modeling
• Sparse inverse covariance estimation with the lasso
• Decomposable Principal Component Analysis
• Covariance estimation in decomposable Gaussian graphical models
• Graph Estimation From Multi-attribute Data
• Estimating heterogeneous graphical models for discrete data with an application to roll call voting
• A Constrained L1 Minimization Approach to Sparse Precision Matrix Estimation
• The Nonparanormal SKEPTIC
• Penalty Decomposition Methods for $L0$-Norm Minimization
• Local and Global Inference for High Dimensional Nonparanormal Graphical Models
• Graph-Valued Regression
• Estimation of Gaussian graphs by model selection
• Sparsistent Estimation of Time-Varying Discrete Markov Random Fields
• Sparse Approximation via Penalty Decomposition Methods
• Inference for Sparse Conditional Precision Matrices
• Tuning parameter selection for penalized likelihood estimation of inverse covariance matrix
• Robust estimators for non-decomposable elliptical graphical models
• Improved Estimation of High-dimensional Ising Models
• A Hierarchical Graphical Model for Big Inverse Covariance Estimation with an Application to fMRI
• Gaussian Graphical Model Estimation with False Discovery Rate Control
• Sparse Median Graphs Estimation in a High Dimensional Semiparametric Model
• Modeling Brain Connectivity with Graphical Models on Frequency Domain
• The Nonparanormal: Semiparametric Estimation of High Dimensional Undirected Graphs
• Identifying Small Mean Reverting Portfolios
• Network-Scale Traffic Modeling and Forecasting with Graphical Lasso and Neural Networks
• Joint Estimation of Multiple Dependent Gaussian Graphical Models with Applications to Mouse Genomics
• Inference of Sparse Networks with Unobserved Variables. Application to Gene Regulatory Networks
• Indirect multivariate response linear regression
• Composite likelihood estimation of sparse Gaussian graphical models with symmetry
• Efficient structure learning with automatic sparsity selection for causal graph processes