# Estimating Ising Models in Total Variation Distance

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 90 references that are in the map.
- First posted on arXiv 26 Nov 2025.

## Builds on (most cited first, 30 of 46)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Statistical Efficiency of Score Matching: The View from Isoperimetry](https://mlsanity.com/paper/2210.00726/) (2022)
- [A Faster Interior Point Method for Semidefinite Programming](https://mlsanity.com/paper/2009.10217/) (2020)
- [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)
- [Optimal structure and parameter learning of Ising models](https://mlsanity.com/paper/1612.05024/) (2016)
- [Efficient Convex Optimization with Membership Oracles](https://mlsanity.com/paper/1706.07357/) (2017)
- [Multi-Item Mechanisms without Item-Independence: Learnability via Robustness](https://mlsanity.com/paper/1911.02146/) (2019)
- [Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications](https://mlsanity.com/paper/1705.11107/) (2017)
- [Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu](https://mlsanity.com/paper/2011.04144/) (2020)
- [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)
- [A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width](https://mlsanity.com/paper/2311.09197/) (2023)
- [Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion](https://mlsanity.com/paper/2011.02075/) (2020)
- [The Minimax Learning Rates of Normal and Ising Undirected Graphical Models](https://mlsanity.com/paper/1806.06887/) (2018)
- [Learning Restricted Boltzmann Machines via Influence Maximization](https://mlsanity.com/paper/1805.10262/) (2018)
- [Regression from Dependent Observations](https://mlsanity.com/paper/1905.03353/) (2019)
- [Sampling Multimodal Distributions with the Vanilla Score: Benefits of Data-Based Initialization](https://mlsanity.com/paper/2310.01762/) (2023)
- [Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models](https://mlsanity.com/paper/2106.03969/) (2021)
- [Statistical Estimation from Dependent Data](https://mlsanity.com/paper/2107.09773/) (2021)
- [Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods](https://mlsanity.com/paper/2202.08907/) (2022)
- [Sudakov-Fernique post-AMP, and a new proof of the local convexity of the TAP free energy](https://mlsanity.com/paper/2208.09550/) (2022)
- [On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization](https://mlsanity.com/paper/2103.07459/) (2021)
- [Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics](https://mlsanity.com/paper/2409.05284/) (2024)

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

- [Learning mathsfAC0 Under Graphical Models](https://mlsanity.com/paper/2604.06109/) (2026)
- [Learning mathsfAC0 under Locally Sampleable Graphical Models](https://mlsanity.com/paper/2607.08303/) (2026)
- [Causal Inference for Sequential Settings under Interference and Latent Confounding](https://mlsanity.com/paper/2607.14940/) (2026)

## Abstract (arXiv)

We consider the problem of estimating Ising models over n variables in Total Variation (TV) distance, given l independent samples from the model. While the statistical complexity of the problem is well-understood [DMR20], identifying computationally and statistically efficient algorithms has been challenging. In particular, remarkable progress has occurred in several settings, such as when the underlying graph is a tree [DP21, BGPV21], when the entries of the interaction matrix follow a Gaussian distribution [GM24, CK24], or when the bulk of its eigenvalues lie in a small interval [AJK+24, KLV24], but no unified framework for polynomial-time estimation in TV exists so far. Our main contribution is a unified analysis of the Maximum Pseudo-Likelihood Estimator (MPLE) for two general classes of Ising models. The first class includes models that have bounded operator norm and satisfy the Modified Log-Sobolev Inequality (MLSI), a functional inequality that was introduced to study the convergence of the associated Glauber dynamics to stationarity. In the second class of models, the interaction matrix has bounded infinity norm (or bounded width), which is the most common assumption in the literature for structure learning of Ising models. We show how our general results for these classes yield polynomial-time algorithms and optimal or near-optimal sample complexity guarantees in a variety of settings. Our proofs employ a variety of tools from tensorization inequalities to measure decompositions and concentration bounds.