Learnability of Parameter-Bounded Bayes Nets
<|reference_start|>Learnability of Parameter-Bounded Bayes Nets: 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 $\mathbb{P}$, that is defined as the marginal distribution of a Bayes net, it is $\mathsf{NP}$-hard to decide whether there is a parameter-bounded Bayes net that represents $\mathbb{P}$. They called this problem LEARN. In this work, we extend the $\mathsf{NP}$-hardness result of LEARN and prove the $\mathsf{NP}$-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 $\mathbb{P}$, that is represented by some parameter-bounded Bayes net, generalizing a degree-bounded sample complexity result of Brustle et al. (EC 2020).<|reference_end|>
@article{bhattacharyya2024learnability,
    title={Learnability of Parameter-Bounded Bayes Nets},
    author={Arnab Bhattacharyya, Davin Choo, Sutanu Gayen, Dimitrios Myrisiotis},
    journal={arXiv preprint arXiv:2407.00927},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.00927},
    primaryClass={cs.LG cs.CC stat.ML}
}