Learning bounded-degree polytrees with known skeleton

Davin Choo, Joy Qiping Yang, Arnab Bhattacharyya, Clément L Canonne
Proceedings of The 35th International Conference on Algorithmic Learning Theory, PMLR 237:402-443, 2024.

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 this Paper

BibTeX
@InProceedings{pmlr-v237-choo24a, title = {Learning bounded-degree polytrees with known skeleton}, author = {Choo, Davin and Yang, Joy Qiping and Bhattacharyya, Arnab and Canonne, Cl{\'e}ment L}, booktitle = {Proceedings of The 35th International Conference on Algorithmic Learning Theory}, pages = {402--443}, year = {2024}, editor = {Vernade, Claire and Hsu, Daniel}, volume = {237}, series = {Proceedings of Machine Learning Research}, month = {25--28 Feb}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v237/choo24a/choo24a.pdf}, url = {https://proceedings.mlr.press/v237/choo24a.html}, 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.} }
Endnote
%0 Conference Paper %T Learning bounded-degree polytrees with known skeleton %A Davin Choo %A Joy Qiping Yang %A Arnab Bhattacharyya %A Clément L Canonne %B Proceedings of The 35th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Claire Vernade %E Daniel Hsu %F pmlr-v237-choo24a %I PMLR %P 402--443 %U https://proceedings.mlr.press/v237/choo24a.html %V 237 %X 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.
APA
Choo, D., Yang, J.Q., Bhattacharyya, A. & Canonne, C.L.. (2024). Learning bounded-degree polytrees with known skeleton. Proceedings of The 35th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 237:402-443 Available from https://proceedings.mlr.press/v237/choo24a.html.

Related Material