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

arXiv: https://arxiv.org/abs/1802.06126 · HTML: https://mlsanity.com/paper/1802.06126/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Feb 2018.

## Built on by (most cited first, 7 of 7)

- [Weakly-Supervised Hierarchical Models for Predicting Persuasive Strategies in Good-faith Textual Requests](https://mlsanity.com/paper/2101.06351/) (2021)
- [Local convexity of the TAP free energy and AMP convergence for Z2-synchronization](https://mlsanity.com/paper/2106.11428/) (2021)
- [Variational Inference in high-dimensional linear regression](https://mlsanity.com/paper/2104.12232/) (2021)
- [Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods](https://mlsanity.com/paper/2202.08907/) (2022)
- [CoRMF: Criticality-Ordered Recurrent Mean Field Ising Solver](https://mlsanity.com/paper/2403.03391/) (2024)
- [Wasserstein Contraction of Coordinate Ascent Variational Inference](https://mlsanity.com/paper/2605.30253/) (2026)
- [Variational-Ising-Attention:Tailored Attention Matters for Science](https://mlsanity.com/paper/2607.23634/) (2026)

## Abstract (arXiv)

The mean field approximation to the Ising model is a canonical variational tool that is used for analysis and inference in Ising models. We provide a simple and optimal bound for the KL error of the mean field approximation for Ising models on general graphs, and extend it to higher order Markov random fields. Our bound improves on previous bounds obtained in work in the graph limit literature by Borgs, Chayes, Lov'asz, S'os, and Vesztergombi and another recent work by Basak and Mukherjee. Our bound is tight up to lower order terms. Building on the methods used to prove the bound, along with techniques from combinatorics and optimization, we study the algorithmic problem of estimating the (variational) free energy for Ising models and general Markov random fields. For a graph G on n vertices and interaction matrix J with Frobenius norm | J |F, we provide algorithms that approximate the free energy within an additive error of ε n |J|F in time exp(poly(1/ε)). We also show that approximation within (n |J|F)1-δ is NP-hard for every δ > 0. Finally, we provide more efficient approximation algorithms, which find the optimal mean field approximation, for ferromagnetic Ising models and for Ising models satisfying Dobrushin's condition.