# A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 58 references that are in the map.
- First posted on arXiv 15 Nov 2023.

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

- [Statistical Efficiency of Score Matching: The View from Isoperimetry](https://mlsanity.com/paper/2210.00726/) (2022)
- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization](https://mlsanity.com/paper/2203.05093/) (2022)
- [Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models](https://mlsanity.com/paper/1605.07252/) (2016)
- [Learning Graphical Models Using Multiplicative Weights](https://mlsanity.com/paper/1706.06274/) (2017)
- [On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities](https://mlsanity.com/paper/1510.03925/) (2015)
- [Testing Ising Models](https://mlsanity.com/paper/1612.03147/) (2016)
- [Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications](https://mlsanity.com/paper/1705.11107/) (2017)
- [Efficient Learning of Discrete Graphical Models](https://mlsanity.com/paper/1902.00600/) (2019)
- [Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models](https://mlsanity.com/paper/1810.11905/) (2018)
- [Learning a Tree-Structured Ising Model in Order to Make Predictions](https://mlsanity.com/paper/1604.06749/) (2016)
- [Learning graphical models from the Glauber dynamics](https://mlsanity.com/paper/1410.7659/) (2014)
- [Privately Learning Markov Random Fields](https://mlsanity.com/paper/2002.09463/) (2020)
- [Outlier-Robust Learning of Ising Models Under Dobrushin's Condition](https://mlsanity.com/paper/2102.02171/) (2021)
- [The Minimax Learning Rates of Normal and Ising Undirected Graphical Models](https://mlsanity.com/paper/1806.06887/) (2018)
- [Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models](https://mlsanity.com/paper/2106.03969/) (2021)
- [Sudakov-Fernique post-AMP, and a new proof of the local convexity of the TAP free energy](https://mlsanity.com/paper/2208.09550/) (2022)
- [Learning Ising Models with Independent Failures](https://mlsanity.com/paper/1902.04728/) (2019)
- [Learning and Testing Latent-Tree Ising Models Efficiently](https://mlsanity.com/paper/2211.13291/) (2022)
- [Learning to Sample from Censored Markov Random Fields](https://mlsanity.com/paper/2101.06178/) (2021)
- [Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics](https://mlsanity.com/paper/2104.00995/) (2021)
- [A statistical physics approach to learning curves for the Inverse Ising problem](https://mlsanity.com/paper/1705.05403/) (2017)

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

- [Structure learning of Hamiltonians from real-time evolution](https://mlsanity.com/paper/2405.00082/) (2024)
- [Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics](https://mlsanity.com/paper/2409.05284/) (2024)
- [Learning the Sherrington-Kirkpatrick Model Even at Low Temperature](https://mlsanity.com/paper/2411.11174/) (2024)
- [Estimating Ising Models in Total Variation Distance](https://mlsanity.com/paper/2511.21008/) (2025)
- [Discrete distributions are learnable from metastable samples](https://mlsanity.com/paper/2410.13800/) (2024)
- [Local and Mixing-Based Algorithms for Gaussian Graphical Model Selection from Glauber Dynamics](https://mlsanity.com/paper/2412.18594/) (2024)
- [Learning CNF formulas from uniform random solutions in the local lemma regime](https://mlsanity.com/paper/2511.02487/) (2025)
- [Learning Gaussian Graphical Models from a Glauber Trajectory Without Mixing](https://mlsanity.com/paper/2606.31230/) (2026)
- [Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information](https://mlsanity.com/paper/2411.11516/) (2024)
- [One-Shot Learning for k-SAT](https://mlsanity.com/paper/2502.07135/) (2025)
- [Computationally sufficient statistics for Ising models](https://mlsanity.com/paper/2602.12449/) (2026)
- [Mixing-Free and Signal-Optimal Learning of Gaussian Graphical Models from Glauber Dynamics](https://mlsanity.com/paper/2607.18559/) (2026)
- [Efficient Learning of Truncated Boolean Product Distributions: Influence to the Rescue](https://mlsanity.com/paper/2607.22889/) (2026)
- [Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm](https://mlsanity.com/paper/2609.15268/) (2026)

## Abstract (arXiv)

We revisit the problem of efficiently learning the underlying parameters of Ising models from data. Current algorithmic approaches achieve essentially optimal sample complexity when given i.i.d. samples from the stationary measure and the underlying model satisfies "width" bounds on the total ℓ1 interaction involving each node. We show that a simple existing approach based on node-wise logistic regression provably succeeds at recovering the underlying model in several new settings where these assumptions are violated: (1) Given dynamically generated data from a wide variety of local Markov chains, like block or round-robin dynamics, logistic regression recovers the parameters with optimal sample complexity up to loglog n factors. This generalizes the specialized algorithm of Bresler, Gamarnik, and Shah [IEEE Trans. Inf. Theory'18] for structure recovery in bounded degree graphs from Glauber dynamics. (2) For the Sherrington-Kirkpatrick model of spin glasses, given mathsfpoly(n) independent samples, logistic regression recovers the parameters in most of the known high-temperature regime via a simple reduction to weaker structural properties of the measure. This improves on recent work of Anari, Jain, Koehler, Pham, and Vuong [ArXiv'23] which gives distribution learning at higher temperature. (3) As a simple byproduct of our techniques, logistic regression achieves an exponential improvement in learning from samples in the M-regime of data considered by Dutt, Lokhov, Vuffray, and Misra [ICML'21] as well as novel guarantees for learning from the adversarial Glauber dynamics of Chin, Moitra, Mossel, and Sandon [ArXiv'23]. Our approach thus significantly generalizes the elegant analysis of Wu, Sanghavi, and Dimakis [Neurips'19] without any algorithmic modification.