# Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 61 references that are in the map.
- First posted on arXiv 2 Apr 2021.

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

- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [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)
- [Convergence Rates of Active Learning for Maximum Likelihood Estimation](https://mlsanity.com/paper/1506.02348/) (2015)
- [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)
- [Learning graphical models from the Glauber dynamics](https://mlsanity.com/paper/1410.7659/) (2014)
- [Asymptotic Analysis of Objectives based on Fisher Information in Active Learning](https://mlsanity.com/paper/1605.08798/) (2016)

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

- [A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width](https://mlsanity.com/paper/2311.09197/) (2023)
- [Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics](https://mlsanity.com/paper/2409.05284/) (2024)
- [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)
- [On Model Selection Consistency of Lasso for High-Dimensional Ising Models](https://mlsanity.com/paper/2110.08500/) (2021)
- [Mixing-Free and Signal-Optimal Learning of Gaussian Graphical Models from Glauber Dynamics](https://mlsanity.com/paper/2607.18559/) (2026)

## Abstract (arXiv)

The usual setting for learning the structure and parameters of a graphical model assumes the availability of independent samples produced from the corresponding multivariate probability distribution. However, for many models the mixing time of the respective Markov chain can be very large and i.i.d. samples may not be obtained. We study the problem of reconstructing binary graphical models from correlated samples produced by a dynamical process, which is natural in many applications. We analyze the sample complexity of two estimators that are based on the interaction screening objective and the conditional likelihood loss. We observe that for samples coming from a dynamical process far from equilibrium, the sample complexity reduces exponentially compared to a dynamical process that mixes quickly.