Testing Probability Distributions using Conditional Samples
summary
Introduces a conditional-sampling model where an algorithm queries a subset and receives a sample conditioned on that subset, and shows concrete gains: uniformity testing uses pair-conditional queries with Θ(1/ε^2) queries (tight) versus Θ(√n/ε^2) for standard sampling, and identity/equivalence can be done with query complexity independent of n or polylog n in stronger variants. Key tools are a comparison oracle, a gamma-neighborhood estimator (approximate only), and a simulated approximate evaluation oracle built with polylogarithmic conditional queries.
AI-written summary · about
chapters (17)
- 0:00Introduction
- 0:47General Framework
- 3:07Standard Remarks
- 3:48Standard Framework
- 4:57Results
- 6:10Conditional Sampling Oracle
- 7:31Criticisms
- 9:46Is it worth studying
- 11:24Outline
- 17:58Extending Conditional Samples
- 19:13PointSubset Pairs
- 20:23Comparison Oracle
- 20:56Gamma Neighborhood
- 22:51Approximate eval Oracle
- 24:14Approximate eval simulator
- 24:31Binary flowchart
- 25:44Applications
related talks
01h 17mDistribution Testing: Hypothesis Testing from Very Little (or Very Private) Data
23mTowards Practical Distribution Testing
44mSomething for Almost Nothing: Advances in Sub-Linear Time Algorithms
45mTesting and Learning Distributions Under Local Information Constraints
01h 02mImportance Sampling in High Dimensions via Hashing
01h 02mSampling for Linear Algebra, Statistics, and Optimization II
01h 00mDifferential Privacy And The Complexity Of Simple Queries
01h 01mRobustness, Stochastics, Uncertainty 1