Learning bounded-degree polytrees with known skeleton
This work addresses efficient learning of high-dimensional probability distributions for applications in graphical models, but it is incremental as it extends prior results from trees to bounded-degree polytrees.
The paper tackles the problem of learning bounded-degree polytrees, a subclass of Bayesian networks, by providing an efficient algorithm that learns them in polynomial time and sample complexity when the skeleton is known, with nearly tight lower bounds on sample complexity.
We establish finite-sample guarantees for efficient proper learning of bounded-degree polytrees, a rich class of high-dimensional probability distributions and a subclass of Bayesian networks, a widely-studied type of graphical model. Recently, Bhattacharyya et al. (2021) obtained finite-sample guarantees for recovering tree-structured Bayesian networks, i.e., 1-polytrees. We extend their results by providing an efficient algorithm which learns $d$-polytrees in polynomial time and sample complexity for any bounded $d$ when the underlying undirected graph (skeleton) is known. We complement our algorithm with an information-theoretic sample complexity lower bound, showing that the dependence on the dimension and target accuracy parameters are nearly tight.