On the trade-off between complexity and correlation decay in structural learning algorithms

Abstract

We consider the problem of learning the structure of Ising models (pairwise binary Markov random fields) from i.i.d. samples. While several methods have been proposed to accomplish this task, their relative merits and limitations remain somewhat obscure. By analyzing a number of concrete examples, we show that low-complexity algorithms often fail when the Markov random field develops long-range correlations. More precisely, this phenomenon appears to be related to the Ising model phase transition (although it does not coincide with it).

References in corpus (4)

• High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression
• Adaptive Cluster Expansion for Inferring Boltzmann Machines with Noisy Data
• Information-theoretic limits of selecting binary graphical models in high dimensions
• High Dimensional Structure Learning of Ising Models on Sparse Random Graphs