  We study approximations of the partition function of dense graphical models.
Partition functions of graphical models play a fundamental role is statistical
physics, in statistics and in machine learning. Two of the main methods for
approximating the partition function are Markov Chain Monte Carlo and
Variational Methods. An impressive body of work in mathematics, physics and
theoretical computer science provides conditions under which Markov Chain Monte
Carlo methods converge in polynomial time. These methods often lead to
polynomial time approximation algorithms for the partition function in cases
where the underlying model exhibits correlation decay. There are very few
theoretical guarantees for the performance of variational methods. One
exception is recent results by Risteski (2016) who considered dense graphical
models and showed that using variational methods, it is possible to find an
$O(\epsilon n)$ additive approximation to the log partition function in time
$n^{O(1/\epsilon^2)}$ even in a regime where correlation decay does not hold.
  We show that under essentially the same conditions, an $O(\epsilon n)$
additive approximation of the log partition function can be found in constant
time, independent of $n$. In particular, our results cover dense Ising and
Potts models as well as dense graphical models with $k$-wise interaction. They
also apply for low threshold rank models.
