Learning a Tree-Structured Ising Model in Order to Make Predictions

on YouTube ↗33m

" summary

Claim: learning a tree Ising model only to get accurate pairwise posteriors needs far fewer samples than learning the exact graph. Method: compute empirical pairwise correlations, run Chow‑Liu MST, truncate edges below a threshold, then project by matching edge marginals; proof uses an edge‑pairing lemma to control errors along differing paths. Guarantee: with n = O(max(e^{2β}, η^{-2}) · log p) samples the reconstructed model gives all pairwise correlations within η. Only proven for trees and K=2 marginals.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 0:25learning graphical models from data
3. 0:48two questions in graphical model learning
4. 1:33medical diagnosis
5. 2:39recommendation system
6. 3:09the structure learning problem
7. 4:25sample complexity lower bound
8. 6:01neighborhood search algorithm
9. 11:28the learning for predictions problem
10. 11:43approximate learning
11. 12:47high girth graphs with corr. decay
12. 14:17a distance between distributions
13. 15:01this talk: trees and k = 2
14. 21:28learning a forest
15. 22:52illustrative example
16. 24:58proof sketch
17. 30:46inductive argument

" related talks

• 48mHow Hard Is Inference for Structured Prediction?Tim Roughgarden · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 53mStatistical Estimation from Dependent DataConstantinos Daskalakis · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 52mNew Algorithms For The Graph Alignment ProblemMarc Lelarge · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 51mHow to Predict When Estimation is Hard: Algorithms for Learning on GraphsSasha Rakhlin · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)
• 49mMetric Representations: Algorithms and GeometryAnna Gilbert · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 27mDistribution Learning Meets Graph Structure SamplingSayantan Sen · Workshop on Local Algorithms (WoLA) 2024
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 40mTesting Correlation of Unlabeled Random GraphsJiaming Xu · Computational Phase Transitions (Simons Institute, 2020)