The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity.

The mean field approximation to the Ising model is a canonical variationaltool that is used for analysis and inference in Ising models. We provide asimple and optimal bound for the KL error of the mean field approximation forIsing models on general graphs, and extend it to higher order Markov randomfields. Our bound improves on previous bounds obtained in work in the graphlimit literature by Borgs, Chayes, Lov\'asz, S\'os, and Vesztergombi andanother recent work by Basak and Mukherjee. Our bound is tight up to lowerorder terms. Building on the methods used to prove the bound, along withtechniques from combinatorics and optimization, we study the algorithmicproblem of estimating the (variational) free energy for Ising models andgeneral Markov random fields. For a graph $G$ on $n$ vertices and interactionmatrix $J$ with Frobenius norm $\| J \|_F$, we provide algorithms thatapproximate the free energy within an additive error of $\epsilon n \|J\|_F$ intime $\exp(poly(1/\epsilon))$. We also show that approximation within $(n\|J\|_F)^{1-\delta}$ is NP-hard for every $\delta > 0$. Finally, we providemore efficient approximation algorithms, which find the optimal mean fieldapproximation, for ferromagnetic Ising models and for Ising models satisfyingDobrushin's condition.