# Distribution Learning Meets Graph Structure Sampling

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 84 references that are in the map.
- First posted on arXiv 13 May 2024.

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

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Learning Geometric Concepts with Nasty Noise](https://mlsanity.com/paper/1707.01242/) (2017)
- [Learning Graphical Models Using Multiplicative Weights](https://mlsanity.com/paper/1706.06274/) (2017)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [Settling the complexity of computing approximate two-player Nash equilibria](https://mlsanity.com/paper/1606.04550/) (2016)
- [Testing Ising Models](https://mlsanity.com/paper/1612.03147/) (2016)
- [Multi-Item Mechanisms without Item-Independence: Learnability via Robustness](https://mlsanity.com/paper/1911.02146/) (2019)
- [Learning Bayesian Network Structure from Massive Datasets: The "Sparse Candidate" Algorithm](https://mlsanity.com/paper/1301.6696/) (2013)
- [The Recovery of Causal Poly-Trees from Statistical Data](https://mlsanity.com/paper/1304.2736/) (2013)
- [Learning Polytrees](https://mlsanity.com/paper/1301.6688/) (2013)
- [Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning](https://mlsanity.com/paper/2002.05378/) (2020)
- [Efficient Bayesian network structure learning via local Markov boundary search](https://mlsanity.com/paper/2110.06082/) (2021)
- [High-Probability Risk Bounds via Sequential Predictors](https://mlsanity.com/paper/2308.07588/) (2023)
- [On the Sample Complexity of Learning Bayesian Networks](https://mlsanity.com/paper/1302.3579/) (2013)
- [Robust Learning of Fixed-Structure Bayesian Networks](https://mlsanity.com/paper/1606.07384/) (2016)
- [The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination](https://mlsanity.com/paper/2307.10273/) (2023)
- [Learning bounded-degree polytrees with known skeleton](https://mlsanity.com/paper/2310.06333/) (2023)
- [Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models](https://mlsanity.com/paper/2206.04589/) (2022)
- [Sampling Equilibria: Fast No-Regret Learning in Structured Games](https://mlsanity.com/paper/2201.10758/) (2022)
- [Mixtures of All Trees](https://mlsanity.com/paper/2302.14202/) (2023)
- [Optimal estimation of Gaussian (poly)trees](https://mlsanity.com/paper/2402.06380/) (2024)
- [Optimal Strategies of Blotto Games: Beyond Convexity](https://mlsanity.com/paper/1901.04153/) (2019)
- [Learning Sparse Fixed-Structure Gaussian Bayesian Networks](https://mlsanity.com/paper/2107.10450/) (2021)
- [Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time](https://mlsanity.com/paper/2105.05555/) (2021)
- [A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the same Skeleton](https://mlsanity.com/paper/2310.04218/) (2023)

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

- [Entropy Equivalence Testing](https://mlsanity.com/paper/2605.23225/) (2026)

## Abstract (arXiv)

This work establishes a novel link between the problem of PAC-learning high-dimensional graphical models and the task of (efficient) counting and sampling of graph structures, using an online learning framework. We observe that if we apply the exponentially weighted average (EWA) or randomized weighted majority (RWM) forecasters on a sequence of samples from a distribution P using the log loss function, the average regret incurred by the forecaster's predictions can be used to bound the expected KL divergence between P and the predictions. Known regret bounds for EWA and RWM then yield new sample complexity bounds for learning Bayes nets. Moreover, these algorithms can be made computationally efficient for several interesting classes of Bayes nets. Specifically, we give a new sample-optimal and polynomial time learning algorithm with respect to trees of unknown structure and the first polynomial sample and time algorithm for learning with respect to Bayes nets over a given chordal skeleton.