Optimal estimation of Gaussian (poly)trees

Yuhao Wang, Ming Gao, Wai Ming Tai, Bryon Aragam, Arnab Bhattacharyya
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:3619-3627, 2024.

Abstract

We develop optimal algorithms for learning undirected Gaussian trees and directed Gaussian polytrees from data. We consider both problems of distribution learning (i.e. in KL distance) and structure learning (i.e. exact recovery). The first approach is based on the Chow-Liu algorithm, and learns an optimal tree-structured distribution efficiently. The second approach is a modification of the PC algorithm for polytrees that uses partial correlation as a conditional independence tester for constraint-based structure learning. We derive explicit finite-sample guarantees for both approaches, and show that both approaches are optimal by deriving matching lower bounds. Additionally, we conduct numerical experiments to compare the performance of various algorithms, providing further insights and empirical evidence.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-wang24i, title = {Optimal estimation of {G}aussian (poly)trees}, author = {Wang, Yuhao and Gao, Ming and Ming Tai, Wai and Aragam, Bryon and Bhattacharyya, Arnab}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {3619--3627}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/wang24i/wang24i.pdf}, url = {https://proceedings.mlr.press/v238/wang24i.html}, abstract = {We develop optimal algorithms for learning undirected Gaussian trees and directed Gaussian polytrees from data. We consider both problems of distribution learning (i.e. in KL distance) and structure learning (i.e. exact recovery). The first approach is based on the Chow-Liu algorithm, and learns an optimal tree-structured distribution efficiently. The second approach is a modification of the PC algorithm for polytrees that uses partial correlation as a conditional independence tester for constraint-based structure learning. We derive explicit finite-sample guarantees for both approaches, and show that both approaches are optimal by deriving matching lower bounds. Additionally, we conduct numerical experiments to compare the performance of various algorithms, providing further insights and empirical evidence.} }
Endnote
%0 Conference Paper %T Optimal estimation of Gaussian (poly)trees %A Yuhao Wang %A Ming Gao %A Wai Ming Tai %A Bryon Aragam %A Arnab Bhattacharyya %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-wang24i %I PMLR %P 3619--3627 %U https://proceedings.mlr.press/v238/wang24i.html %V 238 %X We develop optimal algorithms for learning undirected Gaussian trees and directed Gaussian polytrees from data. We consider both problems of distribution learning (i.e. in KL distance) and structure learning (i.e. exact recovery). The first approach is based on the Chow-Liu algorithm, and learns an optimal tree-structured distribution efficiently. The second approach is a modification of the PC algorithm for polytrees that uses partial correlation as a conditional independence tester for constraint-based structure learning. We derive explicit finite-sample guarantees for both approaches, and show that both approaches are optimal by deriving matching lower bounds. Additionally, we conduct numerical experiments to compare the performance of various algorithms, providing further insights and empirical evidence.
APA
Wang, Y., Gao, M., Ming Tai, W., Aragam, B. & Bhattacharyya, A.. (2024). Optimal estimation of Gaussian (poly)trees. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:3619-3627 Available from https://proceedings.mlr.press/v238/wang24i.html.

Related Material