Statistical Property Testing and Estimation Beyond the i.i.d. Setting

on YouTube ↗30m

" summary

Provides a tight, instance-optimal sample complexity for identity testing to a known distribution p: samples = Theta(max(1/epsilon, ||p after trimming epsilon mass and removing largest prob||_{2/3} / epsilon^2)) up to constants. Achieves this with a modified chi-squared test that replaces expected counts by observed xi and uses p^{2/3}-normalization. Analysis uses variance bounds (Chebyshev) and matching lower bounds; also gives an algorithmic decomposition for multiplicative inequalities with working Matlab code.

AI-written summary · about

" chapters (7)

1. 0:00Introduction
2. 0:58The basic setting
3. 2:37What do we really want
4. 4:55Whats Known
5. 16:45Analysis
6. 22:26Geometric Interpretation
7. 26:23Further Directions

" related talks

• 01h 17mDistribution Testing: Hypothesis Testing from Very Little (or Very Private) DataClément Canonne · Sublinear Algorithms Boot Camp 2024
• 14mEfficient Universal Estimators For Symmetric Property EstimationKirankumar Shiragur · Meet the Fellows Welcome Event
• 01h 02mEstimation Beyond the IID Setting (Two Vignettes)Gregory Valiant · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 39mDetecting Weak Signals via Hypothesis TestingRavi Kannan · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 45mTesting and Learning Distributions Under Local Information ConstraintsClément Canonne · Sublinear Algorithms and Nearest-Neighbor Search
• 45mEfficient Profile Maximum Likelihood for Universal Symmetric Property EstimationMoses Charikar · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 00mAlgorithmic High Dimensional Robust Statistics IIlias Diakonikolas · Foundations of Data Science Boot Camp 2018
• 53mDesigning Robust LearnersJacob Steinhardt · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)