Distribution Testing: Hypothesis Testing from Very Little (or Very Private) Data

on YouTube ↗01h 17m

" summary

Overview of concrete results: distribution testing under total-variation needs Θ(√k/ε²) samples for uniformity, and common reductions let many identity tests reduce to uniformity. Key tools are Poissonization to make counts independent, the collision-based tester and the complementary unique-elements / chi-squared statistics, plus a surprising workable empirical estimator for identity. For private data the talk maps central/local/shuffle models to tight sample bounds and uses shuffle amplification to turn local protocols into shuffle-private ones.

AI-written summary · about

" chapters (11)

1. 0:00Introduction and preliminaries
2. 3:43Defining property testing
3. 5:44Properties and examples
4. 15:05Testing vs. learning
5. 21:03Hardness of uniformity testing
6. 25:15Methodologies and tricks
7. 32:51Uniformity testing algorithms
8. 40:20Advanced testing techniques
9. 57:04Differential privacy overview
10. 1:03:49Private distribution testing
11. 1:14:21Open problems and conclusion

" related talks

• 45mTesting and Learning Distributions Under Local Information ConstraintsClément Canonne · Sublinear Algorithms and Nearest-Neighbor Search
• 30mStatistical Property Testing and Estimation Beyond the i.i.d. SettingGregory Valiant · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 23mTowards Practical Distribution TestingYash Pote · Workshop on Local Algorithms (WoLA) 2024
• 29mTesting Probability Distributions using Conditional SamplesRocco A. Servedio · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 21mTesting Distribution FamiliesJayadev Acharya · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 44mSomething for Almost Nothing: Advances in Sub-Linear Time AlgorithmsRonitt Rubinfeld · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 33mLearning and Testing Structured DistributionsIlias Diakonikolas · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 48mA New Paradigm for Learning with Distribution ShiftAdam R. Klivans · Unknown Futures of Generalization 2024