Optimal estimation of Gaussian (poly)trees
Not on the map. Why?
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.
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
30 of 103 references.
References · 30
- 2013High-dimensional learning of linear causal networks via inverse covariance estimationcited by 87
- 2022Greedy Relaxations of the Sparsest Permutation Algorithmcited by 64
- 2018On Causal Discovery with Equal Variance Assumptioncited by 59
- 2017Learning linear structural equation models in polynomial time and sample complexitycited by 51
- 2015High-dimensional consistency in score-based and hybrid structure learningcited by 46
- 2022Causal Structure Learning: a Combinatorial Perspectivecited by 46
- 2020A polynomial-time algorithm for learning nonparametric causal graphscited by 30
- 2017Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexitycited by 27
- 2018High-Dimensional Causal Discovery Under non-Gaussianitycited by 24
- 2013Learning Bayesian Network Structure from Massive Datasets: The "Sparse Candidate" Algorithmcited by 22
- 2017Testing Conditional Independence of Discrete Distributionscited by 22
- 2013The Recovery of Causal Poly-Trees from Statistical Datacited by 19
18 more
- 2022Optimal estimation of Gaussian DAG modelscited by 17
- 2013Learning Polytreescited by 14
- 2021Efficient Bayesian network structure learning via local Markov boundary searchcited by 14
- 2014Marginal likelihood and model selection for Gaussian latent tree and forest modelscited by 12
- 2014Advances in Learning Bayesian Networks of Bounded Treewidthcited by 10
- 2020A Weaker Faithfulness Assumption based on Triple Interactionscited by 10
- 2013On the Sample Complexity of Learning Bayesian Networkscited by 9
- 2021Structure Learning for Directed Treescited by 9
- 2013Maximum Likelihood Bounded Tree-Width Markov Networkscited by 7
- 2016Information-theoretic limits of Bayesian network structure learningcited by 7
- 2020Sample-Optimal and Efficient Learning of Tree Ising modelscited by 7
- 2022Learning Linear Non-Gaussian Polytree Modelscited by 7
- 2021On the Parameterized Complexity of Polytree Learningcited by 6
- 2014A Survey on Latent Tree Models and Applicationscited by 5
- 2021A Fast Non-parametric Approach for Local Causal Structure Learningcited by 5
- 2023Learning bounded-degree polytrees with known skeletoncited by 5
- 2014Nonparametric Latent Tree Graphical Models: Inference, Estimation, and Structure Learningcited by 2
- 2023KL-BSS: Rethinking optimality for neighbourhood selection in structural equation modelscited by 1
Built on by
Citing papers per year: 2024: 2; 2025: 1.
3 papers.