Estimating Ising Models in Total Variation Distance
Not on the map. Why?
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.
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
46 of 90 references.
References · 46
- 2021Convex optimizationcited by 2,515
- 2014Convex Optimization: Algorithms and Complexitycited by 575
- 2015An Introduction to Matrix Concentration Inequalitiescited by 397
- 2022Statistical Efficiency of Score Matching: The View from Isoperimetrycited by 64
- 2020A Faster Interior Point Method for Semidefinite Programmingcited by 53
- 2014Efficiently learning Ising models on arbitrary graphscited by 50
- 2022Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localizationcited by 48
- 2016Interaction Screening: Efficient and Sample-Optimal Learning of Ising Modelscited by 43
- 2017Learning Graphical Models Using Multiplicative Weightscited by 43
- 2016Optimal structure and parameter learning of Ising modelscited by 26
- 2017Efficient Convex Optimization with Membership Oraclescited by 23
- 2019Multi-Item Mechanisms without Item-Independence: Learnability via Robustnesscited by 23
34 more
- 2017Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applicationscited by 21
- 2020Near-Optimal Learning of Tree-Structured Distributions by Chow-Liucited by 20
- 2018Sparse Logistic Regression Learns All Discrete Pairwise Graphical Modelscited by 16
- 2016Learning a Tree-Structured Ising Model in Order to Make Predictionscited by 15
- 2014Learning graphical models from the Glauber dynamicscited by 14
- 2020Privately Learning Markov Random Fieldscited by 14
- 2023A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Widthcited by 14
- 2020Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansioncited by 12
- 2018The Minimax Learning Rates of Normal and Ising Undirected Graphical Modelscited by 11
- 2018Learning Restricted Boltzmann Machines via Influence Maximizationcited by 10
- 2019Regression from Dependent Observationscited by 10
- 2023Sampling Multimodal Distributions with the Vanilla Score: Benefits of Data-Based Initializationcited by 10
- 2021Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Modelscited by 9
- 2021Statistical Estimation from Dependent Datacited by 9
- 2022Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methodscited by 9
- 2022Sudakov-Fernique post-AMP, and a new proof of the local convexity of the TAP free energycited by 9
- 2021On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorizationcited by 8
- 2024Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamicscited by 8
- 2018Predictive Learning on Hidden Tree-Structured Ising Modelscited by 7
- 2022Learning and Testing Latent-Tree Ising Models Efficientlycited by 7
- 2023Learning Hard-Constrained Models with One Samplecited by 7
- 2024Efficiently learning and sampling multimodal distributions with data-based initializationcited by 7
- 2020Logistic-Regression with peer-group effects via inference in higher order Ising modelscited by 5
- 2020Estimation in Tensor Ising Modelscited by 5
- 2024Learning the Sherrington-Kirkpatrick Model Even at Low Temperaturecited by 5
- 2019Modified log-Sobolev inequalities for strongly log-concave distributionscited by 4
- 2024Trickle-Down in Localization Schemes and Applicationscited by 4
- 2023Universality of Spectral Independence with Applications to Fast Mixing in Spin Glassescited by 3
- 2023Optimality of Glauber dynamics for general-purpose Ising model sampling and free energy approximationcited by 2
- 2024Fast Mixing in Sparse Random Ising Modelscited by 2
- 2024On Sampling from Ising Models with Spectral Constraintscited by 2
- 2024Discrete distributions are learnable from metastable samplescited by 2
- 2021Entropic Independence I: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Distributions and High-Temperature Ising Modelscited by 1
- 2022Ising Models on Dense Regular Graphscited by 1
Built on by
Citing papers per year: 2026: 3.
3 papers.