High-dimensional Gaussian graphical model selection: walk summability and local separation criterion

zbMATH Open1433.68322arXiv1107.1270MaRDI QIDQ5405191FDOQ5405191

Authors: Animashree Anandkumar, Vincent Y. F. Tan, Furong Huang, Alan S. Willsky 

Publication date: 1 April 2014

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.

Full work available at URL: https://arxiv.org/abs/1107.1270

Recommendations

• High-dimensional structure estimation in Ising models: local separation criterion
• Estimation of Gaussian graphs by model selection
• Asymptotic normality and optimalities in estimation of large Gaussian graphical models
• High-dimensional graphs and variable selection with the Lasso
• High-dimensional covariance estimation based on Gaussian graphical models

zbMATH Keywords

local-separation propertyhigh-dimensional learningGaussian graphical model selectionwalk-summabilitynecessary conditions for model selection

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Measures of association (correlation, canonical correlation, etc.) (62H20) Probabilistic graphical models (62H22) Ridge regression; shrinkage estimators (Lasso) (62J07)

Cited In (18)

• Total positivity in exponential families with application to binary variables
• Region selection in Markov random fields: Gaussian case
• High-dimensional consistency in score-based and hybrid structure learning
• Estimating high dimensional faithful Gaussian graphical models by low-order conditioning
• Discovering the topology of complex networks via adaptive estimators
• Generalized chordality, vertex separators and hyperbolicity on graphs
• Causal Structural Learning via Local Graphs
• The reduced PC-algorithm: improved causal structure learning in large random networks
• Estimation of positive definite \(M\)-matrices and structure learning for attractive Gaussian Markov random fields
• The shape of partial correlation matrices
• Maximum likelihood estimation in Gaussian models under total positivity
• Integrative analysis with a system of semiparametric projection non-linear regression models
• Learning unfaithful \(K\)-separable Gaussian graphical models
• Title not available (Why is that?)
• Learning loopy graphical models with latent variables: efficient methods and guarantees
• Large deviations of convex polyominoes
• High-dimensional structure estimation in Ising models: local separation criterion
• A unified framework for structured graph learning via spectral constraints

This page was built for publication: High-dimensional Gaussian graphical model selection: walk summability and local separation criterion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5405191)