# Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2020.

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

- [Outlier-Robust Learning of Ising Models Under Dobrushin's Condition](https://mlsanity.com/paper/2102.02171/) (2021)
- [Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coverage](https://mlsanity.com/paper/2310.18434/) (2023)
- [High-Probability Risk Bounds via Sequential Predictors](https://mlsanity.com/paper/2308.07588/) (2023)
- [Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models](https://mlsanity.com/paper/2106.03969/) (2021)
- [Learning and Testing Latent-Tree Ising Models Efficiently](https://mlsanity.com/paper/2211.13291/) (2022)
- [Concentration Bounds for Discrete Distribution Estimation in KL Divergence](https://mlsanity.com/paper/2302.06869/) (2023)
- [Generative Modeling via Tree Tensor Network States](https://mlsanity.com/paper/2209.01341/) (2022)
- [Learning bounded-degree polytrees with known skeleton](https://mlsanity.com/paper/2310.06333/) (2023)
- [Learning the Sherrington-Kirkpatrick Model Even at Low Temperature](https://mlsanity.com/paper/2411.11174/) (2024)
- [Nearly Minimax Discrete Distribution Estimation in Kullback-Leibler Divergence with High Probability](https://mlsanity.com/paper/2507.17316/) (2025)
- [Near-Optimal Degree Testing for Bayes Nets](https://mlsanity.com/paper/2304.06733/) (2023)
- [On Different Notions of Redundancy in Conditional-Independence-Based Discovery of Graphical Models](https://mlsanity.com/paper/2502.08531/) (2025)
- [Learning Juntas under Markov Random Fields](https://mlsanity.com/paper/2506.00764/) (2025)
- [Estimating Ising Models in Total Variation Distance](https://mlsanity.com/paper/2511.21008/) (2025)
- [Ratio Covers of Convex Sets and Optimal Mixture Density Estimation](https://mlsanity.com/paper/2602.16142/) (2026)
- [Learning Sparse Fixed-Structure Gaussian Bayesian Networks](https://mlsanity.com/paper/2107.10450/) (2021)
- [Private and Communication-Efficient Algorithms for Entropy Estimation](https://mlsanity.com/paper/2305.07751/) (2023)
- [Efficient inference of interventional distributions](https://mlsanity.com/paper/2107.11712/) (2021)
- [Recoverability Landscape of Tree Structured Markov Random Fields under Symmetric Noise](https://mlsanity.com/paper/2102.08554/) (2021)
- [Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees](https://mlsanity.com/paper/2110.14341/) (2021)

## Abstract (arXiv)

We provide finite sample guarantees for the classical Chow-Liu algorithm (IEEE Trans.~Inform.~Theory, 1968) to learn a tree-structured graphical model of a distribution. For a distribution P on Sigman and a tree T on n nodes, we say T is an varepsilon-approximate tree for P if there is a T-structured distribution Q such that D(P;||;Q) is at most varepsilon more than the best possible tree-structured distribution for P. We show that if P itself is tree-structured, then the Chow-Liu algorithm with the plug-in estimator for mutual information with widetildeO(|Sigma|3 nvarepsilon-1) i.i.d.~samples outputs an varepsilon-approximate tree for P with constant probability. In contrast, for a general P (which may not be tree-structured), Omega(n2varepsilon-2) samples are necessary to find an varepsilon-approximate tree. Our upper bound is based on a new conditional independence tester that addresses an open problem posed by Canonne, Diakonikolas, Kane, and Stewart~(STOC, 2018): we prove that for three random variables X,Y,Z each over Sigma, testing if I(X; Y mid Z) is 0 or ≥ varepsilon is possible with widetildeO(|Sigma|3/varepsilon) samples. Finally, we show that for a specific tree T, with widetildeO (|Sigma|2nvarepsilon-1) samples from a distribution P over Sigman, one can efficiently learn the closest T-structured distribution in KL divergence by applying the add-1 estimator at each node.