The Vertex Sample Complexity of Free Energy is Polynomial

Understand

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 $\mathcal{F}_n = \log{Z_n}$? 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 $\epsilon$ approximation to $\log Z_n / n$ can be achieved by sampling a randomly induced model on $2^{O(1/\epsilon^2)}$ nodes.

• We show that the sampling complexity of this problem is {\em polynomial in} $1/\epsilon$.
• We further show a polynomial dependence on $\epsilon$ cannot be avoided.
• Our results are very general as they apply to higher order Markov random fields.