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

José Bento, Andrea Montanari

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…