Towards Practical Distribution Testing
summary
Claims a first polynomial algorithm to estimate total variation distance under subcube conditioning, returning an ε-accurate TV estimate with constant success probability using n^3 queries. Key tools: chain-rule decomposition into marginals, a stopping-rule estimator (Dagum et al.) that reduces a previous n^5 → n^2 subroutine for estimating an element’s probability when sampled from its own distribution, and a constructive nearby D' to avoid tiny marginals. Implementation finds real sampler bugs and comes with published tools.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 1:06High-dimensional testing importance
- 3:21SHUFFLE-1 bug example
- 6:55Gray box testing approach
- 9:58Problem statement and results
- 11:49Key contributions overview
- 13:56Estimation algorithm details
- 16:53Small marginal probabilities handling
- 18:16Complexity bounds and questions
- 18:57Applications in machine learning and model training
- 19:43Real-world impact
- 20:07Conclusion and future
- 20:50Q&A
related talks
01h 17mDistribution Testing: Hypothesis Testing from Very Little (or Very Private) Data
43mEfficient Distance Estimation And Causal Inference For Discrete Models
29mTesting Probability Distributions using Conditional Samples
45mTesting and Learning Distributions Under Local Information Constraints
44mSomething for Almost Nothing: Advances in Sub-Linear Time Algorithms
48mA New Paradigm for Learning with Distribution Shift
39mAbove Average-Case Analysis?
01h 02mEstimation Beyond the IID Setting (Two Vignettes)