# Learning and Testing Latent-Tree Ising Models Efficiently

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 86 references that are in the map.
- First posted on arXiv 23 Nov 2022.

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

- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [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)
- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020)
- [Learning and Testing Causal Models with Interventions](https://mlsanity.com/paper/1805.09697/) (2018)
- [High-dimensional estimation via sum-of-squares proofs](https://mlsanity.com/paper/1807.11419/) (2018)
- [Testing Ising Models](https://mlsanity.com/paper/1612.03147/) (2016)
- [Testing Bayesian Networks](https://mlsanity.com/paper/1612.03156/) (2016)
- [Multi-Item Mechanisms without Item-Independence: Learnability via Robustness](https://mlsanity.com/paper/1911.02146/) (2019)
- [Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications](https://mlsanity.com/paper/1705.11107/) (2017)
- [Efficient Learning of Discrete Graphical Models](https://mlsanity.com/paper/1902.00600/) (2019)
- [Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu](https://mlsanity.com/paper/2011.04144/) (2020)
- [Sparse PCA: Algorithms, Adversarial Perturbations and Certificates](https://mlsanity.com/paper/2011.06585/) (2020)
- [Learning a Tree-Structured Ising Model in Order to Make Predictions](https://mlsanity.com/paper/1604.06749/) (2016)
- [Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing](https://mlsanity.com/paper/1612.03164/) (2016)
- [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)
- [Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models](https://mlsanity.com/paper/2106.03969/) (2021)
- [Statistical Estimation from Dependent Data](https://mlsanity.com/paper/2107.09773/) (2021)
- [The Complexity of Sparse Tensor PCA](https://mlsanity.com/paper/2106.06308/) (2021)
- [Learning to Sample from Censored Markov Random Fields](https://mlsanity.com/paper/2101.06178/) (2021)
- [Independence Testing for Bounded Degree Bayesian Network](https://mlsanity.com/paper/2204.08690/) (2022)
- [From Boltzmann Machines to Neural Networks and Back Again](https://mlsanity.com/paper/2007.12815/) (2020)
- [Maximum Likelihood Estimation for Brownian Motion Tree Models Based on One Sample](https://mlsanity.com/paper/2112.00816/) (2021)
- [Learning Restricted Boltzmann Machines with Arbitrary External Fields](https://mlsanity.com/paper/1906.06595/) (2019)

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

- [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 Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [Near-Optimal Degree Testing for Bayes Nets](https://mlsanity.com/paper/2304.06733/) (2023)
- [Estimating Ising Models in Total Variation Distance](https://mlsanity.com/paper/2511.21008/) (2025)
- [Bias Detection via Maximum Subgroup Discrepancy](https://mlsanity.com/paper/2502.02221/) (2025)
- [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 provide time- and sample-efficient algorithms for learning and testing latent-tree Ising models, i.e. Ising models that may only be observed at their leaf nodes. On the learning side, we obtain efficient algorithms for learning a tree-structured Ising model whose leaf node distribution is close in Total Variation Distance, improving on the results of prior work. On the testing side, we provide an efficient algorithm with fewer samples for testing whether two latent-tree Ising models have leaf-node distributions that are close or far in Total Variation distance. We obtain our algorithms by showing novel localization results for the total variation distance between the leaf-node distributions of tree-structured Ising models, in terms of their marginals on pairs of leaves.