# Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 58 references that are in the map.
- First posted on arXiv 9 Sep 2024.

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

- [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)
- [Continuous LWE](https://mlsanity.com/paper/2005.09595/) (2020)
- [On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities](https://mlsanity.com/paper/1510.03925/) (2015)
- [Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures](https://mlsanity.com/paper/2204.02550/) (2022)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications](https://mlsanity.com/paper/1705.11107/) (2017)
- [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)
- [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)
- [Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models](https://mlsanity.com/paper/2106.03969/) (2021)
- [Structure learning of Hamiltonians from real-time evolution](https://mlsanity.com/paper/2405.00082/) (2024)
- [Trace Complexity of Network Inference](https://mlsanity.com/paper/1308.2954/) (2013)
- [Structure learning of antiferromagnetic Ising models](https://mlsanity.com/paper/1412.1443/) (2014)
- [Learning and Testing Latent-Tree Ising Models Efficiently](https://mlsanity.com/paper/2211.13291/) (2022)
- [Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics](https://mlsanity.com/paper/2104.00995/) (2021)
- [Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles](https://mlsanity.com/paper/2309.09457/) (2023)
- [From Boltzmann Machines to Neural Networks and Back Again](https://mlsanity.com/paper/2007.12815/) (2020)
- [Learning Graphs from Noisy Epidemic Cascades](https://mlsanity.com/paper/1903.02650/) (2019)
- [Finding Super-spreaders in Network Cascades](https://mlsanity.com/paper/2403.03205/) (2024)

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

- [Estimating Ising Models in Total Variation Distance](https://mlsanity.com/paper/2511.21008/) (2025)
- [Learning CNF formulas from uniform random solutions in the local lemma regime](https://mlsanity.com/paper/2511.02487/) (2025)
- [The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficiently](https://mlsanity.com/paper/2605.10237/) (2026)
- [Learning Gaussian Graphical Models from a Glauber Trajectory Without Mixing](https://mlsanity.com/paper/2606.31230/) (2026)
- [Learning mathsfAC0 under Locally Sampleable Graphical Models](https://mlsanity.com/paper/2607.08303/) (2026)
- [One-Shot Learning for k-SAT](https://mlsanity.com/paper/2502.07135/) (2025)
- [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 consider the problem of learning graphical models, also known as Markov random fields (MRFs) from temporally correlated samples. As in many traditional statistical settings, fundamental results in the area all assume independent samples from the distribution. However, these samples generally will not directly correspond to more realistic observations from nature, which instead evolve according to some stochastic process. From the computational lens, even generating a single sample from the true MRF distribution is intractable unless mathsfNP=mathsfRP, and moreover, any algorithm to learn from i.i.d. samples requires prohibitive runtime due to hardness reductions to the parity with noise problem. These computational barriers for sampling and learning from the i.i.d. setting severely lessen the utility of these breakthrough results for this important task; however, dropping this assumption typically only introduces further algorithmic and statistical complexities. In this work, we surprisingly demonstrate that the direct trajectory data from a natural evolution of the MRF overcomes the fundamental computational lower bounds to efficient learning. In particular, we show that given a trajectory with widetildeOk(n) site updates of an order k MRF from the Glauber dynamics, a well-studied, natural stochastic process on graphical models, there is an algorithm that recovers the graph and the parameters in widetildeOk(n2) time. By contrast, all prior algorithms for learning order k MRFs inherently suffer from nTheta(k) runtime even in sparse instances due to the reductions to sparse parity with noise. Our results thus surprisingly show that this more realistic, but intuitively less tractable, model for MRFs actually leads to efficiency far beyond what is known and believed to be true in the traditional i.i.d. case.