# Learnability of Parameter-Bounded Bayes Nets

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 19 references that are in the map.
- First posted on arXiv 1 Jul 2024.

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

- [Learning Bayesian Networks: The Combination of Knowledge and Statistical Data](https://mlsanity.com/paper/1302.6815/) (2013)
- [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)
- [Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians](https://mlsanity.com/paper/1312.1054/) (2013)
- [Learning Polytrees](https://mlsanity.com/paper/1301.6688/) (2013)

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

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

## Abstract (arXiv)

Bayes nets are extensively used in practice to efficiently represent joint probability distributions over a set of random variables and capture dependency relations. In a seminal paper, Chickering et al. (JMLR 2004) showed that given a distribution mathbbP, that is defined as the marginal distribution of a Bayes net, it is mathsfNP-hard to decide whether there is a parameter-bounded Bayes net that represents mathbbP. They called this problem LEARN. In this work, we extend the mathsfNP-hardness result of LEARN and prove the mathsfNP-hardness of a promise search variant of LEARN, whereby the Bayes net in question is guaranteed to exist and one is asked to find such a Bayes net. We complement our hardness result with a positive result about the sample complexity that is sufficient to recover a parameter-bounded Bayes net that is close (in TV distance) to a given distribution mathbbP, that is represented by some parameter-bounded Bayes net, generalizing a degree-bounded sample complexity result of Brustle et al. (EC 2020).