# Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 54 references that are in the map.
- First posted on arXiv 18 Nov 2024.

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

- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [Learning Graphical Models Using Multiplicative Weights](https://mlsanity.com/paper/1706.06274/) (2017)
- [Optimal Testing for Properties of Distributions](https://mlsanity.com/paper/1507.05952/) (2015)
- [Testing Bayesian Networks](https://mlsanity.com/paper/1612.03156/) (2016)
- [On the Properties of Kullback-Leibler Divergence Between Multivariate Gaussian Distributions](https://mlsanity.com/paper/2102.05485/) (2021)
- [Local permutation tests for conditional independence](https://mlsanity.com/paper/2112.11666/) (2021)
- [Testing Conditional Independence of Discrete Distributions](https://mlsanity.com/paper/1711.11560/) (2017)
- [Learning Some Popular Gaussian Graphical Models without Condition Number Bounds](https://mlsanity.com/paper/1905.01282/) (2019)
- [Learning a Tree-Structured Ising Model in Order to Make Predictions](https://mlsanity.com/paper/1604.06749/) (2016)
- [Optimal Testing of Discrete Distributions with High Probability](https://mlsanity.com/paper/2009.06540/) (2020)
- [A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width](https://mlsanity.com/paper/2311.09197/) (2023)
- [Testing Conditional Independence on Discrete Data using Stochastic Complexity](https://mlsanity.com/paper/1903.04829/) (2019)
- [Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models](https://mlsanity.com/paper/2106.03969/) (2021)
- [Maximum Likelihood Bounded Tree-Width Markov Networks](https://mlsanity.com/paper/1301.2311/) (2013)
- [Learning and Testing Latent-Tree Ising Models Efficiently](https://mlsanity.com/paper/2211.13291/) (2022)
- [Independence Testing for Bounded Degree Bayesian Network](https://mlsanity.com/paper/2204.08690/) (2022)
- [Learning bounded-degree polytrees with known skeleton](https://mlsanity.com/paper/2310.06333/) (2023)
- [Conditional Independence Testing for Discrete Distributions: Beyond chi2- and G-tests](https://mlsanity.com/paper/2308.05373/) (2023)
- [Optimal estimation of Gaussian (poly)trees](https://mlsanity.com/paper/2402.06380/) (2024)
- [Learning Sparse Fixed-Structure Gaussian Bayesian Networks](https://mlsanity.com/paper/2107.10450/) (2021)
- [Bayesian learning of forest and tree graphical models](https://mlsanity.com/paper/2108.13992/) (2021)

## Abstract (arXiv)

Learning high-dimensional distributions is a significant challenge in machine learning and statistics. Classical research has mostly concentrated on asymptotic analysis of such data under suitable assumptions. While existing works [Bhattacharyya et al.: SICOMP 2023, Daskalakis et al.: STOC 2021, Choo et al.: ALT 2024] focus on discrete distributions, the current work addresses the tree structure learning problem for Gaussian distributions, providing efficient algorithms with solid theoretical guarantees. This is crucial as real-world distributions are often continuous and differ from the discrete scenarios studied in prior works. In this work, we design a conditional mutual information tester for Gaussian random variables that can test whether two Gaussian random variables are independent, or their conditional mutual information is at least varepsilon, for some parameter varepsilon ∈ (0,1) using O(varepsilon-1) samples which we show to be near-optimal. In contrast, an additive estimation would require Omega(varepsilon-2) samples. Our upper bound technique uses linear regression on a pair of suitably transformed random variables. Importantly, we show that the chain rule of conditional mutual information continues to hold for the estimated (conditional) mutual information. As an application of such a mutual information tester, we give an efficient varepsilon-approximate structure-learning algorithm for an n-variate Gaussian tree model that takes widetildeTheta(nvarepsilon-1) samples which we again show to be near-optimal. In contrast, when the underlying Gaussian model is not known to be tree-structured, we show that widetildeTheta(n2varepsilon-2) samples are necessary and sufficient to output an varepsilon-approximate tree structure. We perform extensive experiments that corroborate our theoretical convergence bounds.