mlsanityData to 7 Oct 2026

Learning and Testing Latent-Tree Ising Models Efficiently

arXiv 2211.13291 ↗First posted 23 Nov 2022cs.LG cs.DS math.PRcited by 7

Not on the map. Why?

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.

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

Builds on

30 of 86 references.

References · 30

  1. 2016Variational Inference: A Review for Statisticianscited by 1,466
  2. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 82
  3. 2017The power of sum-of-squares for detecting hidden structurescited by 54
  4. 2014Efficiently learning Ising models on arbitrary graphscited by 50
  5. 2020Reducibility and Statistical-Computational Gaps from Secret Leakagecited by 50
  6. 2016Interaction Screening: Efficient and Sample-Optimal Learning of Ising Modelscited by 43
  7. 2017Learning Graphical Models Using Multiplicative Weightscited by 43
  8. 2019Subexponential-Time Algorithms for Sparse PCAcited by 41
  9. 2020Computational Barriers to Estimation from Low-Degree Polynomialscited by 38
  10. 2018Learning and Testing Causal Models with Interventionscited by 29
  11. 2018High-dimensional estimation via sum-of-squares proofscited by 25
  12. 2016Testing Ising Modelscited by 23
18 more
  1. 2016Testing Bayesian Networkscited by 23
  2. 2019Multi-Item Mechanisms without Item-Independence: Learnability via Robustnesscited by 22
  3. 2017Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applicationscited by 21
  4. 2019Efficient Learning of Discrete Graphical Modelscited by 21
  5. 2020Near-Optimal Learning of Tree-Structured Distributions by Chow-Liucited by 20
  6. 2020Sparse PCA: Algorithms, Adversarial Perturbations and Certificatescited by 18
  7. 2016Learning a Tree-Structured Ising Model in Order to Make Predictionscited by 14
  8. 2016Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testingcited by 11
  9. 2018The Minimax Learning Rates of Normal and Ising Undirected Graphical Modelscited by 11
  10. 2018Learning Restricted Boltzmann Machines via Influence Maximizationcited by 10
  11. 2021Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Modelscited by 9
  12. 2021Statistical Estimation from Dependent Datacited by 9
  13. 2021The Complexity of Sparse Tensor PCAcited by 7
  14. 2021Learning to Sample from Censored Markov Random Fieldscited by 6
  15. 2022Independence Testing for Bounded Degree Bayesian Networkcited by 5
  16. 2020From Boltzmann Machines to Neural Networks and Back Againcited by 4
  17. 2021Maximum Likelihood Estimation for Brownian Motion Tree Models Based on One Samplecited by 4
  18. 2019Learning Restricted Boltzmann Machines with Arbitrary External Fieldscited by 2

Built on by

Cited by year

Citing papers per year: 2023: 3; 2024: 2; 2025: 2.

7 papers.

  1. 2023A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Widthcited by 13
  2. 2024Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamicscited by 8
  3. 2023Learning Hard-Constrained Models with One Samplecited by 7
  4. 2023Near-Optimal Degree Testing for Bayes Netscited by 3
  5. 2025Bias Detection via Maximum Subgroup Discrepancycited by 2
  6. 2025Estimating Ising Models in Total Variation Distancecited by 2
  7. 2024Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Informationcited by 0