Learning Bounded-Degree Polytrees with Known Skeleton
Abstract
We establish finite-sample guarantees for efficient proper learning of bounded-degree {\em 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.
Cite
Text
Choo et al. "Learning Bounded-Degree Polytrees with Known Skeleton." Proceedings of The 35th International Conference on Algorithmic Learning Theory, 2024.Markdown
[Choo et al. "Learning Bounded-Degree Polytrees with Known Skeleton." Proceedings of The 35th International Conference on Algorithmic Learning Theory, 2024.](https://mlanthology.org/alt/2024/choo2024alt-learning/)BibTeX
@inproceedings{choo2024alt-learning,
title = {{Learning Bounded-Degree Polytrees with Known Skeleton}},
author = {Choo, Davin and Yang, Joy Qiping and Bhattacharyya, Arnab and Canonne, Clément L},
booktitle = {Proceedings of The 35th International Conference on Algorithmic Learning Theory},
year = {2024},
pages = {402-443},
volume = {237},
url = {https://mlanthology.org/alt/2024/choo2024alt-learning/}
}