Testing Distribution Families
summary
Proposes a two-step method: use a proper learning routine (LP-based for discrete log-concave and specific estimators for Poisson binomial) to get an ε^2-accurate hypothesis, then run an L2 test on sample counts. Claims sample complexity ~K^{1/4}/ε^2 (plus an ε-independent term) for Poisson binomial and ~√K/ε^2 for log-concave, with runtime linear in the sample size and matching lower bounds (up to logs) via Fano; analysis uses mean/variance of the count statistic and Cauchy–Schwarz.
AI-written summary · about
chapters (15)
- 0:00Testing distribution families
- 1:24Problem setup and hypothesis testing
- 3:31Known results and gaps
- 5:38Testing identity and monotonicity
- 6:41Unimodality motivating example
- 7:43General approach for testing
- 10:35Learning distributions in class
- 11:40Poisson binomial and log-concave
- 13:07Sample complexity for Poisson binomials
- 13:28Sample complexity for log-concave
- 14:51Comparison with other approaches
- 15:36Learning log-concave distributions
- 17:22Testing phase and test statistic
- 19:31Summary and future directions
- 20:37Q&A
related talks
40mOn Learning Graph Binomial Distributions and Powers of Poisson Binomial Distributions
45mTesting and Learning Distributions Under Local Information Constraints
01h 17mDistribution Testing: Hypothesis Testing from Very Little (or Very Private) Data
53mDesigning Robust Learners
01h 05mDistribution Estimation and Applications III
01h 02mEstimation Beyond the IID Setting (Two Vignettes)
23mTowards Practical Distribution Testing
01h 28mMulti-Distribution Learning, for Robustness, Fairness, and Collaboration