# Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 52 references that are in the map.
- First posted on arXiv 7 Jun 2021.

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

- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [Efficiently learning Ising models on arbitrary graphs](https://mlsanity.com/paper/1411.6156/) (2014)
- [Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models](https://mlsanity.com/paper/1605.07252/) (2016)
- [Learning Graphical Models Using Multiplicative Weights](https://mlsanity.com/paper/1706.06274/) (2017)
- [Learning Some Popular Gaussian Graphical Models without Condition Number Bounds](https://mlsanity.com/paper/1905.01282/) (2019)
- [Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu](https://mlsanity.com/paper/2011.04144/) (2020)
- [Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models](https://mlsanity.com/paper/1810.11905/) (2018)
- [Learning a Tree-Structured Ising Model in Order to Make Predictions](https://mlsanity.com/paper/1604.06749/) (2016)
- [Outlier-Robust Learning of Ising Models Under Dobrushin's Condition](https://mlsanity.com/paper/2102.02171/) (2021)
- [The Minimax Learning Rates of Normal and Ising Undirected Graphical Models](https://mlsanity.com/paper/1806.06887/) (2018)
- [Learning Restricted Boltzmann Machines via Influence Maximization](https://mlsanity.com/paper/1805.10262/) (2018)
- [On Learning Continuous Pairwise Markov Random Fields](https://mlsanity.com/paper/2010.15031/) (2020)
- [Learning Ising Models with Independent Failures](https://mlsanity.com/paper/1902.04728/) (2019)
- [Predictive Learning on Hidden Tree-Structured Ising Models](https://mlsanity.com/paper/1812.04700/) (2018)
- [Robust Estimation of Tree Structured Ising Models](https://mlsanity.com/paper/2006.05601/) (2020)
- [Sample-Optimal and Efficient Learning of Tree Ising models](https://mlsanity.com/paper/2010.14864/) (2020)

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

- [A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width](https://mlsanity.com/paper/2311.09197/) (2023)
- [Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics](https://mlsanity.com/paper/2409.05284/) (2024)
- [Learning Linear Non-Gaussian Polytree Models](https://mlsanity.com/paper/2208.06701/) (2022)
- [Learning and Testing Latent-Tree Ising Models Efficiently](https://mlsanity.com/paper/2211.13291/) (2022)
- [Learning Polynomial Transformations](https://mlsanity.com/paper/2204.04209/) (2022)
- [Estimating Ising Models in Total Variation Distance](https://mlsanity.com/paper/2511.21008/) (2025)
- [Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees](https://mlsanity.com/paper/2110.14341/) (2021)
- [Polynomial-time derivation of optimal k-tree topology from Markov networks](https://mlsanity.com/paper/2404.05991/) (2024)
- [Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information](https://mlsanity.com/paper/2411.11516/) (2024)

## Abstract (arXiv)

We consider the problem of learning a tree-structured Ising model from data, such that subsequent predictions computed using the model are accurate. Concretely, we aim to learn a model such that posteriors P(Xi|XS) for small sets of variables S are accurate. Since its introduction more than 50 years ago, the Chow-Liu algorithm, which efficiently computes the maximum likelihood tree, has been the benchmark algorithm for learning tree-structured graphical models. A bound on the sample complexity of the Chow-Liu algorithm with respect to the prediction-centric local total variation loss was shown in [BK19]. While those results demonstrated that it is possible to learn a useful model even when recovering the true underlying graph is impossible, their bound depends on the maximum strength of interactions and thus does not achieve the information-theoretic optimum. In this paper, we introduce a new algorithm that carefully combines elements of the Chow-Liu algorithm with tree metric reconstruction methods to efficiently and optimally learn tree Ising models under a prediction-centric loss. Our algorithm is robust to model misspecification and adversarial corruptions. In contrast, we show that the celebrated Chow-Liu algorithm can be arbitrarily suboptimal.