High-dimensional structure estimation in Ising models: Local separation criterion

Abstract

We consider the problem of high-dimensional Ising (graphical) model selection. We propose a simple algorithm for structure estimation based on the thresholding of the empirical conditional variation distances. We introduce a novel criterion for tractable graph families, where this method is efficient, based on the presence of sparse local separators between node pairs in the underlying graph. For such graphs, the proposed algorithm has a sample complexity of $n=\Omega (J_{\min }^{-2}\log p)$, where $p$ is the number of variables, and $J_{\min }$ is the minimum (absolute) edge potential in the model. We also establish nonasymptotic necessary and sufficient conditions for structure estimation.

Published in at http://dx.doi.org/10.1214/12-AOS1009 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (5)

• High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression
• Ising models on power-law random graphs
• Ising-like agent-based technology diffusion model: adoption patterns vs. seeding strategies
• Learning Latent Tree Graphical Models
• Learning High-Dimensional Markov Forest Distributions: Analysis of Error Rates

Cited by in corpus (26)

• Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses
• Estimating heterogeneous graphical models for discrete data with an application to roll call voting
• Learning loopy graphical models with latent variables: Efficient methods and guarantees
• Marginal Pseudo-Likelihood Learning of Markov Network structures
• Bayesian Graphical Models for Multivariate Functional Data
• Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing
• Structure learning of antiferromagnetic Ising models
• On the Information Theoretic Limits of Learning Ising Models
• Sparse model selection in the highly under-sampled regime
• The Social System Identification Problem
• Active Learning Algorithms for Graphical Model Selection
• A global approach for learning sparse Ising models
• Lower Bounds on Active Learning for Graphical Model Selection
• Adaptive Inferential Method for Monotone Graph Invariants
• On the Inductive Bias of Masked Language Modeling: From Statistical to Syntactic Dependencies
• Pseudo-likelihood-based $M$-estimation of random graphs with dependent edges and parameter vectors of increasing dimension
• Causal Structural Learning Via Local Graphs
• Exact Asymptotics for Learning Tree-Structured Graphical Models with Side Information: Noiseless and Noisy Samples
• A parallel algorithm for penalized learning of the multivariate exponential family from data of mixed types
• Mixing Times and Structural Inference for Bernoulli Autoregressive Processes
• Variational Bayes algorithm and posterior consistency of Ising model parameter estimation
• Limit theorems for dependent combinatorial data, with applications in statistical inference
• Graphical Fermat's Principle and Triangle-Free Graph Estimation
• Topology Inference over Networks with Nonlinear Coupling
• High Dimensional Logistic Regression Under Network Dependence
• Learning Graphs from Linear Measurements: Fundamental Trade-offs and Applications