Distribution Learning Meets Graph Structure Sampling

on YouTube ↗27m

" summary

Draws a concrete bridge from online expert algorithms to PAC learning of graphical models: running EWA or RWM on iid samples with log loss gives an average-regret bound that directly controls expected KL, yielding new sample-complexity guarantees. Builds a polynomial-time sampler for Bayes nets with a given chordal skeleton (first such algorithm) and a new tree-structured learner that drops the prior k^3 factor to k^2 dependence. Key tools include clipping/bucketing of probabilities and clique-tree decompositions; algorithms run in polynomial time and match known tightness for the tree case.

AI-written summary · about

" chapters (18)

1. 0:00Introduction
2. 1:12Central problem
3. 3:38Bayesian networks role
4. 5:49Variants of distribution learning
5. 7:14Tree-structured results
6. 8:40Chordal distributions learning
7. 9:21Online learning model
8. 11:30Regret minimization
9. 13:46Proof overview
10. 15:53New results and bounds
11. 16:55Tree-structured algorithms
12. 17:37Chordal-structured algorithms
13. 19:26Exploiting structural properties
14. 21:59Regret learning with experts
15. 22:25Tree-structured algorithm
16. 23:10Clique tree decomposition
17. 24:57Conclusion
18. 26:05Future directions

" related talks

• 01h 26mStreaming, Sketching and Sufficient Statistics IIGraham Cormode · Big Data Boot Camp 2013
• 23mDynamic inference in probabilistic graphical modelsWeiming Feng, Kun He, Xiaoming Sun, Yitong Yin · ITCS 2021
• 32mLearning Ill-Conditioned Gaussian Graphical ModelsRaghu Meka · Algorithmic Aspects of Causal Inference 2022
• 39mA PAC Approach to Application-Specific Algorithm SelectionRishi Gupta · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 29mSampling Algorithms for Combinatorial Pure ExplorationAnupam Gupta · Optimization, Statistics and Uncertainty
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 01h 04mNonparametric Bayesian Methods: Models, Algorithms, and Applications IVTamara Broderick · Foundations of Machine Learning Boot Camp 2017
• 51mHow to Predict When Estimation is Hard: Algorithms for Learning on GraphsSasha Rakhlin · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)