On Learning Graph Binomial Distributions and Powers of Poisson Binomial Distributions

on YouTube ↗40m

" summary

Presents concrete results: learn a Poisson binomial distribution up to total variation ε with sample complexity ~O((log(1/δ))/ε^2) by estimate mean and variance in the high-variance (Gaussian) case and by finding an effective support interval and histogram in the low-variance case; proves that exact parameter recovery needs exp(1/ε) samples so approximating the distribution is strictly easier. Extends to learning all powered distributions by choosing a power L where P^L flattens, shows Newton identities plus noise cause exponential error amplification, and shows the graph-induced-edge-count distribution can be multimodal and is often hard to characterize.

AI-written summary · about

" chapters (11)

1. 0:00Intro
2. 3:42Distribution Learning (Small) Sample of Previous Work
3. 7:10Warm-up: Learning a Binomial Distribution Binn,p
4. 8:27Poisson Binomial Distributions (PBDs)
5. 13:16Learning Poisson Binomial Distributions
6. 20:27Powers of Poisson Binomial Distribution
7. 24:39Learning the powers of Binp
8. 26:48Sampling from the Right Power
9. 29:05Lower Bound on PBD Power Learning
10. 30:12Parameter Learning through Newton Identities
11. 34:04Graph Binomial Distributions

" related talks

• 21mTesting Distribution FamiliesJayadev Acharya · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 53mDesigning Robust LearnersJacob Steinhardt · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 45mThe lower tail: Poisson approximation revisitedLutz Warnke · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 04mNonparametric Bayesian Methods: Models, Algorithms, and Applications IIMichael Jordan · Foundations of Machine Learning Boot Camp 2017
• 01h 02mNonparametric Bayesian Methods: Models, Algorithms, and Applications IIIMichael Jordan · Foundations of Machine Learning Boot Camp 2017
• 29mOn Learning Distributions from their SamplesSudeep Kamath · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 01h 12mLearning probability distributions; what can, what can't be doneShai Ben-David · Modern Paradigms in Generalization Boot Camp 2024
• 36mPrivately Learning High-Dimensional DistributionsGautam Kamath · Data Privacy: From Foundations to Applications (Simons Institute workshop, 2019)