The Vertex Sample Complexity of Free Energy is Polynomial

We study the following question: given a massive Markov random field on n nodes, can a small sample from it provide a rough approximation to the free energy Fn = logZn? Results in graph limit literature by Borgs, Chayes, Lov'asz, S'os, and Vesztergombi show that for Ising models on n nodes and interactions of strength Theta(1/n), an ε approximation to log Zn / n can be achieved by sampling a randomly induced model on 2O(1/ε2) nodes. We show that the sampling complexity of this problem is em polynomial in 1/ε. We further show a polynomial dependence on ε cannot be avoided. Our results are very general as they apply to higher order Markov random fields. For Markov random fields of order r, we obtain an algorithm that achieves ε approximation using a number of samples polynomial in r and 1/ε and running time that is 2O(1/ε2) up to polynomial factors in r and ε. For ferromagnetic Ising models, the running time is polynomial in 1/ε. Our results are intimately connected to recent research on the regularity lemma and property testing, where the interest is in finding which properties can tested within ε error in time polynomial in 1/ε. In particular, our proofs build on results from a recent work by Alon, de la Vega, Kannan and Karpinski, who also introduced the notion of polynomial vertex sample complexity. Another critical ingredient of the proof is an effective bound by the authors of the paper relating the variational free energy and the free energy.