Structure learning of antiferromagnetic Ising models

Abstract

In this paper we investigate the computational complexity of learning the graph structure underlying a discrete undirected graphical model from i.i.d. samples. We first observe that the notoriously difficult problem of learning parities with noise can be captured as a special case of learning graphical models. This leads to an unconditional computational lower bound of $\Omega (p^{d/2})$ for learning general graphical models on $p$ nodes of maximum degree $d$, for the class of so-called statistical algorithms recently introduced by Feldman et al (2013). The lower bound suggests that the $O(p^d)$ runtime required to exhaustively search over neighborhoods cannot be significantly improved without restricting the class of models. Aside from structural assumptions on the graph such as it being a tree, hypertree, tree-like, etc., many recent papers on structure learning assume that the model has the correlation decay property. Indeed, focusing on ferromagnetic Ising models, Bento and Montanari (2009) showed that all known low-complexity algorithms fail to learn simple graphs when the interaction strength exceeds a number related to the correlation decay threshold. Our second set of results gives a class of repelling (antiferromagnetic) models that have the opposite behavior: very strong interaction allows efficient learning in time $O(p^2)$. We provide an algorithm whose performance interpolates between $O(p^2)$ and $O(p^{d+2})$ depending on the strength of the repulsion.

15 pages. NIPS 2014

References in corpus (6)

• Absence of Phase Transition for Antiferromagnetic Potts Models via the Dobrushin Uniqueness Theorem
• High-dimensional structure estimation in Ising models: Local separation criterion
• Consistent estimation of the basic neighborhood of Markov random fields
• On Learning Discrete Graphical Models Using Greedy Methods
• Which graphical models are difficult to learn?
• Learning Loosely Connected Markov Random Fields

Cited by in corpus (9)

• Logistic-Regression with peer-group effects via inference in higher order Ising models
• Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
• Privately Learning Markov Random Fields
• Outlier-Robust Learning of Ising Models Under Dobrushin's Condition
• Statistical Inference in the Differential Privacy Model
• Learning Restricted Boltzmann Machines with Sparse Latent Variables
• Learning Gaussian Graphical Models via Multiplicative Weights
• Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time
• On resampling vs. adjusting probabilistic graphical models in estimation of distribution algorithms