# Convergence of linear programming hierarchies for Gibbs states of spin systems

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 14 references that are in the map.
- First posted on arXiv 6 Jun 2025.

## Builds on (most cited first, 4 of 4)

- [Sum-of-Squares Relaxations for Information Theory and Variational Inference](https://mlsanity.com/paper/2206.13285/) (2022)
- [How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods](https://mlsanity.com/paper/1607.03183/) (2016)
- [Bootstrapping the Ising Model on the Lattice](https://mlsanity.com/paper/2206.12538/) (2022)
- [Bootstrap, Markov Chain Monte Carlo, and LP/SDP Hierarchy for the Lattice Ising Model](https://mlsanity.com/paper/2309.01016/) (2023)

## Abstract (arXiv)

We consider the problem of computing expectation values of local functions under the Gibbs distribution of a spin system. In particular, we study two families of linear programming hierarchies for this problem. The first hierarchy imposes local spin flip equalities and has been considered in the bootstrap literature in high energy physics. For this hierarchy, we prove fast convergence under a spatial mixing (decay of correlations) condition. This condition is satisfied for example above the critical temperature for Ising models on a d-dimensional grid. The second hierarchy is based on a Markov chain having the Gibbs state as a fixed point and has been studied in the optimization literature and more recently in the bootstrap literature. For this hierarchy, we prove fast convergence provided the Markov chain mixes rapidly. Both hierarchies lead to an varepsilon-approximation for local expectation values using a linear program of size quasi-polynomial in n/varepsilon, where n is the total number of sites, provided the interactions can be embedded in a d-dimensional grid with constant d. Compared to standard Monte Carlo methods, an advantage of this approach is that it always (i.e., for any system) outputs rigorous upper and lower bounds on the expectation value of interest, without needing an a priori analysis of the convergence speed.