Research map / Learning theory and algorithms / Sample complexity
Replicable Distribution Testing
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Systematic study of replicable distribution testing: new lower-bound framework giving near-tight bounds for replicable uniformity and closeness testing, plus new replicable closeness and independence testers.
Problem
Characterizing the sample complexity cost of algorithmic replicability for distribution testing properties (uniformity, closeness, independence) in total variation distance.
Approach
A lower-bound technique that avoids symmetry assumptions on the tester: acceptance probability under a random instance concentrates when the tester is moderately replicable, using random walks over sample sets and Poissonization. Upper bounds use randomized thresholding and, for independence, averaging over flattening randomness with a variance bound via non-singleton counts.
Key results
- Sample complexity of replicable uniformity testing is tilde-Theta(sqrt(n) eps^-2 rho^-1 + eps^-2 rho^-2), settling an open question from prior work.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use randomized thresholding with the closeness test statistic | Closeness testing · Closeness testing over [n] | sample complexity: O( n^{2/3} \varepsilon^{-4/3} \rho^{-2/3} + \sqrt{n} \varepsilon^{-2} \rho^{-1} + \varepsilon^{-2} \rho^{-2} ) | Helped |
| Average the independence statistic over the flattening procedure's internal randomness | Independence testing · Independence testing over [n_1] × [n_2], n_1 ≥ n_2 | variance: O( \log^3 (n_1n_2) ) \mathbb{E}[ N_a( S_\mathbf p , S_\mathbf q ) ] | Helped |
| Apply randomized flattening and average the independence statistic over its internal randomness | Independence testing · Independence testing over [n_1] × [n_2], n_1 ≥ n_2 | sample complexity: \tilde O\left(\frac{n_1^{2/3}n_2^{1/3}}{\rho^{2/3}\varepsilon^{4/3}} + \frac{\sqrt{n_1 n_2}}{\rho\varepsilon^2} + \frac{ | Helped |
Surprising findings
- Replicable sample complexities mirror the high-probability (log(1/delta)) sample complexities of non-replicable testers with rho^-1 replaced by sqrt(log(1/delta)).
- The lower-bound argument works without assuming the tester is symmetric under domain relabeling, which prior work required.
Limitations
- Independence tester has polylog gap and no matching lower bound; the authors conjecture near-optimality.
- Independence tester runs in sample-polynomial time due to averaging, not linear time.
- Closeness and uniformity bounds hold up to polylogarithmic factors.
Experimental setup
Metrics: sample complexity
Baselines: replicable uniformity tester (prior work) high-probability closeness tester high-probability independence tester
Builds on: replicability (Impagliazzo et al.) flattening for independence testing Efron-Stein inequality
Closest papers by meaning
- Replicable Uniformity Testing (NeurIPS 2024 · similarity 0.93)
- Optimal Algorithms for Augmented Testing of Discrete Distributions (NeurIPS 2024 · similarity 0.89)
- Computationally Efficient Replicable Learning of Parities and Applications (NeurIPS 2026 · similarity 0.86)
- How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions (ICLR 2025 · similarity 0.86)
- Optimal Private and Communication Constraint Distributed Goodness-of-Fit Testing for Discrete Distributions in the Large Sample Regime (NeurIPS 2024 · similarity 0.86)
- Minimax Optimal Two-Sample Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.