mlsanityData to 14 Oct 2026

Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics

arXiv 2104.00995 ↗First posted 2 Apr 2021cs.LG cond-mat.stat-mech physics.data-ancited by 6

Not on the map. Why?

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.

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

9 of 61 references.

References · 9

  1. 2014Efficiently learning Ising models on arbitrary graphscited by 50
  2. 2016Interaction Screening: Efficient and Sample-Optimal Learning of Ising Modelscited by 43
  3. 2017Learning Graphical Models Using Multiplicative Weightscited by 43
  4. 2016Optimal structure and parameter learning of Ising modelscited by 26
  5. 2015Convergence Rates of Active Learning for Maximum Likelihood Estimationcited by 25
  6. 2017Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applicationscited by 21
  7. 2019Efficient Learning of Discrete Graphical Modelscited by 21
  8. 2014Learning graphical models from the Glauber dynamicscited by 14
  9. 2016Asymptotic Analysis of Objectives based on Fisher Information in Active Learningcited by 14

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 0; 2023: 1; 2024: 3; 2025: 0; 2026: 1.

6 papers.

  1. 2023A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Widthcited by 14
  2. 2024Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamicscited by 8
  3. 2024Discrete distributions are learnable from metastable samplescited by 2
  4. 2024Local and Mixing-Based Algorithms for Gaussian Graphical Model Selection from Glauber Dynamicscited by 2
  5. 2021On Model Selection Consistency of Lasso for High-Dimensional Ising Modelscited by 1
  6. 2026Mixing-Free and Signal-Optimal Learning of Gaussian Graphical Models from Glauber Dynamicscited by 0