The Vertex Sample Complexity of Free Energy is Polynomial

MaRDI QIDQ6297880zbMATH OpenFDO

Authors Vishesh Jain, Frederic Koehler, Elchanan Mossel

Publication date 16 February 2018

Abstract: 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/epsilo{n}^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. For Markov random fields of order $r$, we obtain an algorithm that achieves $epsilon$ approximation using a number of samples polynomial in $r$ and $1/epsilon$ and running time that is $2^{O(1/epsilo{n}^2)}$ up to polynomial factors in $r$ and $epsilon$. For ferromagnetic Ising models, the running time is polynomial in $1/epsilon$. 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 $epsilon$ error in time polynomial in $1/epsilon$. 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.

This page was built for publication: The Vertex Sample Complexity of Free Energy is Polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6297880)