Research map / Learning theory and algorithms / Sample complexity
Replicable Uniformity 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.
Gives a replicable uniformity tester using a random threshold on the total-variation statistic with about sqrt(n) eps^-2 rho^-1 samples (nearly linear in 1/rho), plus a nearly matching lower bound for symmetric testers.
Problem
Uniformity testing is usually analyzed only on promise inputs (uniform or far from uniform), so testers can behave non-replicably on distributions that are neither; the paper asks for replicable testers under arbitrary distributions and their sample complexity.
Approach
Use the total-variation statistic (linear in per-element counts) instead of collision/chi-square statistics, compare its median against a random threshold drawn from the expectation gap, and show that large variance from heavy elements forces consistent rejection; this shaves one factor of rho compared to the black-box reduction from coin testing.
Key results
- Replicable uniformity tester with sample complexity Õ(sqrt(n) eps^-2 rho^-1 + eps^-2 rho^-2), nearly linear in 1/rho in the dominating term.
- Lower bound Ω̃(sqrt(n) eps^-2 rho^-1 + rho^-2 eps^-2) for symmetric replicable uniformity testers, matching the upper bound up to polylog factors.
- Identity testing reduces to uniformity testing preserving replicability, giving a replicable identity tester with the same asymptotic sample complexity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the total variation statistic and a randomized threshold instead of converting a non-replicable tester through a replicable coin tester | Uniformity testing · Replicable uniformity testing | sample complexity: \tilde \Theta(\sqrt{n} \rho^{-2} \varepsilon^{-2}) -> \bigtO{\frac{\sqrt{n}}{\varepsilon^2 \rho} + \frac{1}{\rho^2 \vare | Helped |
Surprising findings
- The black-box reduction from replicable coin testing gives sqrt(n) rho^-2 eps^-2, but a direct TV-statistic tester removes one factor of rho.
Limitations
- Lower bound holds only for symmetric algorithms; unconditional lower bound for all replicable testers is left open.
- Bounds hold up to polylogarithmic factors in n and rho.
- Analysis of sublinear regime relies on heavy/light element decomposition and technical concentration arguments.
Experimental setup
Metrics: sample complexity replicability probability
Baselines: black-box reduction from replicable coin testing collision-based uniformity testers chi-square uniformity testers
Builds on: replicability (STOC '22) total variation statistic uniformity tester (Diakonikolas-Kane high-probability Kleitman's lemma McDiarmid's inequality
Closest papers by meaning
- Replicable Distribution Testing (NeurIPS 2025 · similarity 0.93)
- Optimal Algorithms for Augmented Testing of Discrete Distributions (NeurIPS 2024 · similarity 0.87)
- Computationally Efficient Replicable Learning of Parities and Applications (NeurIPS 2026 · similarity 0.84)
- On the Computational Landscape of Replicable Learning (NeurIPS 2024 · similarity 0.83)
- How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions (ICLR 2025 · similarity 0.83)
- Replicable Learning of Large-Margin Halfspaces (ICML 2024 · similarity 0.83)
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.