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 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).