# Optimal estimation of Gaussian (poly)trees

arXiv: https://arxiv.org/abs/2402.06380 · HTML: https://mlsanity.com/paper/2402.06380/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 103 references that are in the map.
- First posted on arXiv 9 Feb 2024.

## Builds on (most cited first, 30 of 30)

- [High-dimensional learning of linear causal networks via inverse covariance estimation](https://mlsanity.com/paper/1311.3492/) (2013)
- [Greedy Relaxations of the Sparsest Permutation Algorithm](https://mlsanity.com/paper/2206.05421/) (2022)
- [On Causal Discovery with Equal Variance Assumption](https://mlsanity.com/paper/1807.03419/) (2018)
- [Learning linear structural equation models in polynomial time and sample complexity](https://mlsanity.com/paper/1707.04673/) (2017)
- [High-dimensional consistency in score-based and hybrid structure learning](https://mlsanity.com/paper/1507.02608/) (2015)
- [Causal Structure Learning: a Combinatorial Perspective](https://mlsanity.com/paper/2206.01152/) (2022)
- [A polynomial-time algorithm for learning nonparametric causal graphs](https://mlsanity.com/paper/2006.11970/) (2020)
- [Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity](https://mlsanity.com/paper/1703.01196/) (2017)
- [High-Dimensional Causal Discovery Under non-Gaussianity](https://mlsanity.com/paper/1803.11273/) (2018)
- [Learning Bayesian Network Structure from Massive Datasets: The "Sparse Candidate" Algorithm](https://mlsanity.com/paper/1301.6696/) (2013)
- [Testing Conditional Independence of Discrete Distributions](https://mlsanity.com/paper/1711.11560/) (2017)
- [The Recovery of Causal Poly-Trees from Statistical Data](https://mlsanity.com/paper/1304.2736/) (2013)
- [Optimal estimation of Gaussian DAG models](https://mlsanity.com/paper/2201.10548/) (2022)
- [Learning Polytrees](https://mlsanity.com/paper/1301.6688/) (2013)
- [Efficient Bayesian network structure learning via local Markov boundary search](https://mlsanity.com/paper/2110.06082/) (2021)
- [Marginal likelihood and model selection for Gaussian latent tree and forest models](https://mlsanity.com/paper/1412.8285/) (2014)
- [Advances in Learning Bayesian Networks of Bounded Treewidth](https://mlsanity.com/paper/1406.1411/) (2014)
- [A Weaker Faithfulness Assumption based on Triple Interactions](https://mlsanity.com/paper/2010.14265/) (2020)
- [On the Sample Complexity of Learning Bayesian Networks](https://mlsanity.com/paper/1302.3579/) (2013)
- [Structure Learning for Directed Trees](https://mlsanity.com/paper/2108.08871/) (2021)
- [Maximum Likelihood Bounded Tree-Width Markov Networks](https://mlsanity.com/paper/1301.2311/) (2013)
- [Information-theoretic limits of Bayesian network structure learning](https://mlsanity.com/paper/1601.07460/) (2016)
- [Sample-Optimal and Efficient Learning of Tree Ising models](https://mlsanity.com/paper/2010.14864/) (2020)
- [Learning Linear Non-Gaussian Polytree Models](https://mlsanity.com/paper/2208.06701/) (2022)
- [On the Parameterized Complexity of Polytree Learning](https://mlsanity.com/paper/2105.09675/) (2021)
- [A Survey on Latent Tree Models and Applications](https://mlsanity.com/paper/1402.0577/) (2014)
- [A Fast Non-parametric Approach for Local Causal Structure Learning](https://mlsanity.com/paper/2111.14969/) (2021)
- [Learning bounded-degree polytrees with known skeleton](https://mlsanity.com/paper/2310.06333/) (2023)
- [Nonparametric Latent Tree Graphical Models: Inference, Estimation, and Structure Learning](https://mlsanity.com/paper/1401.3940/) (2014)
- [KL-BSS: Rethinking optimality for neighbourhood selection in structural equation models](https://mlsanity.com/paper/2306.02244/) (2023)

## Built on by (most cited first, 3 of 3)

- [Distribution Learning Meets Graph Structure Sampling](https://mlsanity.com/paper/2405.07914/) (2024)
- [Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information](https://mlsanity.com/paper/2411.11516/) (2024)
- [Optimal structure learning and conditional independence testing](https://mlsanity.com/paper/2507.05689/) (2025)

## Abstract (arXiv)

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.