# Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 69 references that are in the map.
- First posted on arXiv 17 Feb 2022.

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

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Estimation of Low-Rank Matrices via Approximate Message Passing](https://mlsanity.com/paper/1711.01682/) (2017)
- [Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models](https://mlsanity.com/paper/1807.00891/) (2018)
- [Simulated Tempering Langevin Monte Carlo II: An Improved Proof using Soft Markov Chain Decomposition](https://mlsanity.com/paper/1812.00793/) (2018)
- [Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds](https://mlsanity.com/paper/1911.03043/) (2019)
- [The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity](https://mlsanity.com/paper/1802.06126/) (2018)
- [Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective](https://mlsanity.com/paper/1808.07226/) (2018)
- [Sampling for Bayesian Mixture Models: MCMC with Polynomial-Time Mixing](https://mlsanity.com/paper/1912.05153/) (2019)
- [Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction](https://mlsanity.com/paper/2004.09083/) (2020)
- [Random cluster dynamics for the Ising model is rapidly mixing](https://mlsanity.com/paper/1605.00139/) (2016)
- [How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods](https://mlsanity.com/paper/1607.03183/) (2016)
- [SETH-Based Lower Bounds for Subset Sum and Bicriteria Path](https://mlsanity.com/paper/1704.04546/) (2017)
- [Fast algorithms at low temperatures via Markov chains](https://mlsanity.com/paper/1901.06653/) (2019)
- [The Vertex Sample Complexity of Free Energy is Polynomial](https://mlsanity.com/paper/1802.06129/) (2018)
- [Efficient sampling and counting algorithms for the Potts model on mathbb Zd at all temperatures](https://mlsanity.com/paper/1909.09298/) (2019)

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

- [Private estimation algorithms for stochastic block models and mixture models](https://mlsanity.com/paper/2301.04822/) (2023)
- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [On the query complexity of sampling from non-log-concave distributions](https://mlsanity.com/paper/2502.06200/) (2025)
- [Steering diffusion models with quadratic rewards: a fine-grained analysis](https://mlsanity.com/paper/2602.16570/) (2026)
- [Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling](https://mlsanity.com/paper/2207.09102/) (2022)
- [Low-rank combinatorial optimization and statistical learning by spatial photonic Ising machine](https://mlsanity.com/paper/2303.14993/) (2023)
- [Estimating Ising Models in Total Variation Distance](https://mlsanity.com/paper/2511.21008/) (2025)
- [Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributions](https://mlsanity.com/paper/2505.15059/) (2025)
- [Hubbard-Stratonovich Detector for Simple Trainable MIMO Signal Detection](https://mlsanity.com/paper/2302.04461/) (2023)

## Abstract (arXiv)

We consider Ising models on the hypercube with a general interaction matrix J, and give a polynomial time sampling algorithm when all but O(1) eigenvalues of J lie in an interval of length one, a situation which occurs in many models of interest. This was previously known for the Glauber dynamics when *all* eigenvalues fit in an interval of length one; however, a single outlier can force the Glauber dynamics to mix torpidly. Our general result implies the first polynomial time sampling algorithms for low-rank Ising models such as Hopfield networks with a fixed number of patterns and Bayesian clustering models with low-dimensional contexts, and greatly improves the polynomial time sampling regime for the antiferromagnetic/ferromagnetic Ising model with inconsistent field on expander graphs. It also improves on previous approximation algorithm results based on the naive mean-field approximation in variational methods and statistical physics. Our approach is based on a new fusion of ideas from the MCMC and variational inference worlds. As part of our algorithm, we define a new nonconvex variational problem which allows us to sample from an exponential reweighting of a distribution by a negative definite quadratic form, and show how to make this procedure provably efficient using stochastic gradient descent. On top of this, we construct a new simulated tempering chain (on an extended state space arising from the Hubbard-Stratonovich transform) which overcomes the obstacle posed by large positive eigenvalues, and combine it with the SGD-based sampler to solve the full problem.