Testing and Learning Distributions Under Local Information Constraints
summary
Study uses the simultaneous referee model with n players each getting one sample and limited by a family of channels W. Exact claims: centralized sample needs Θ(k/ε^2) for learning and Θ(√k/ε^2) for uniformity testing; with L-bit channels these numbers blow up by about a factor of k/2^L for learning and by √(k/2^L) for testing, while public randomness yields the √-improvement for testing via a minimally contracting hashing reduction. Proofs use chi-square contraction, associate each channel to a PSD matrix H_W and bound Frobenius/trace norms; results extend to local differential privacy.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 6:28Remarks
- 11:06Tasks
- 12:36Information Constraints
- 15:29Communication
- 17:21OneParty Approach
- 23:56Public Coin Protocol
- 29:03Local Differential Pricing
- 29:14Local Differential Privacy
- 32:48Lower Bounds
- 34:04Uniformity
- 41:43Conclusion
- 42:35Summary
related talks
01h 17mDistribution Testing: Hypothesis Testing from Very Little (or Very Private) Data
21mTesting Distribution Families
53mDesigning Robust Learners
01h 28mMulti-Distribution Learning, for Robustness, Fairness, and Collaboration
53mOptimality in Locally Private Estimation and Learning
23mTowards Practical Distribution Testing
43mIs Interaction Necessary for Distributed Private Learning?
29mTesting Probability Distributions using Conditional Samples