High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion

Abstract

We consider the problem of high-dimensional Gaussian graphical model selection. We identify a set of graphs for which an efficient estimation algorithm exists, and this algorithm is based on thresholding of empirical conditional covariances. Under a set of transparent conditions, we establish structural consistency (or sparsistency) for the proposed algorithm, when the number of samples n=omega(J_{min}^{-2} log p), where p is the number of variables and J_{min} is the minimum (absolute) edge potential of the graphical model. The sufficient conditions for sparsistency are based on the notion of walk-summability of the model and the presence of sparse local vertex separators in the underlying graph. We also derive novel non-asymptotic necessary conditions on the number of samples required for sparsistency.

References in corpus (7)

• Loopy Belief Propagation for Approximate Inference: An Empirical Study
• Extended Bayesian Information Criteria for Gaussian Graphical Models
• Stability Approach to Regularization Selection (StARS) for High Dimensional Graphical Models
• Forest Density Estimation
• Ising models on power-law random graphs
• A rigorous analysis of the cavity equations for the minimum spanning tree
• High Dimensional Structure Learning of Ising Models on Sparse Random Graphs

Cited by in corpus (23)

• Learning Graphs with Monotone Topology Properties and Multiple Connected Components
• The Multivariate Hawkes Process in High Dimensions: Beyond Mutual Excitation
• Learning loopy graphical models with latent variables: Efficient methods and guarantees
• Total positivity in exponential families with application to binary variables
• Learning High-dimensional Gaussian Graphical Models under Total Positivity without Adjustment of Tuning Parameters
• Active Learning Algorithms for Graphical Model Selection
• An Efficient Pseudo-likelihood Method for Sparse Binary Pairwise Markov Network Estimation
• Lower Bounds on Active Learning for Graphical Model Selection
• Learning Some Popular Gaussian Graphical Models without Condition Number Bounds
• Pairwise MRF Calibration by Perturbation of the Bethe Reference Point
• A Junction Tree Framework for Undirected Graphical Model Selection
• Nonparametric causal structure learning in high dimensions
• Recovering the Graph Underlying Networked Dynamical Systems under Partial Observability: A Deep Learning Approach
• Active Sampling for the Quickest Detection of Markov Networks
• Statistical Structure Learning, Towards a Robust Smart Grid
• Identifiability in Gaussian Graphical Models
• Region Detection in Markov Random Fields: Gaussian Case
• Causal Structural Learning Via Local Graphs
• Learning Gaussian Graphical Models via Multiplicative Weights
• Learning Continuous Exponential Families Beyond Gaussian
• Mixing Times and Structural Inference for Bernoulli Autoregressive Processes
• Stationary Geometric Graphical Model Selection
• Topology Inference over Networks with Nonlinear Coupling