Research map / Learning theory and algorithms / Sample complexity
Optimal Algorithms for Augmented Testing of Discrete Distributions
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 sample-optimal augmented uniformity, identity, and closeness testers that use a predicted distribution with TV-distance accuracy, with a search wrapper that needs no knowledge of prediction accuracy.
Problem
Distribution testing (uniformity, identity, closeness) with a predicted distribution whose accuracy, measured by total variation distance, is unknown; the goal is to reduce sample complexity when the prediction is good while never exceeding the standard bounds.
Approach
Augmented tester that can output "inaccurate" when the prediction is not alpha-close, combined with a doubling search over suggested accuracy levels alpha; uses Scheffé-set tests for identity/uniformity and augmented flattening (exploiting the prediction) for closeness, with matching lower bounds from multivariate coupling.</核心>
Key results
- Augmented identity/uniformity testing uses Theta(min(1/(dist-alpha)^2, sqrt(n)/eps^2)) samples when dist > alpha, matching lower bounds.
- Augmented closeness testing uses Theta(n^{2/3} alpha^{1/3}/eps^{4/3} + sqrt(n)/eps^2) samples, improving on the standard n^{2/3}/eps^{4/3} bound when alpha = o(1).
- Experiments show over 20x sample reduction on hard instances and up to 40% reduction on real network traffic data.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a prediction distribution within α of p | Closeness testing · Closeness testing | sample complexity: \Theta\left(\frac{n^{2/3}}{\epsilon^{4/3}} +\frac{\sqrt{n}}{\epsilon^2}\right) -> \Theta\left(\frac{n^{2/3} \alpha^{1/3} | Helped |
| Use a prediction distribution when dist > α | Identity/uniformity testing · Identity/uniformity testing, dist > α | sample complexity: \Theta\left(\frac{\sqrt{n}}{\epsilon^2}\right) -> \Theta\left(\min\left(\frac{1}{(\dist-\alpha)^2},\ \frac{\sqrt{n}}{\ep | Helped |
| Use a prediction distribution when dist ≤ α | Identity/uniformity testing · Identity/uniformity testing, dist ≤ α | sample complexity: \Theta\left(\frac{\sqrt{n}}{\epsilon^2}\right) -> \Theta\left(\frac{\sqrt{n}}{\epsilon^2}\right) | No clear effect |
| Use predictions | Augmented closeness testing · Theoretically hard instances | sample complexity reduction: >20x | Helped |
| Use predictions | Augmented closeness testing · Network traffic data | sample complexity reduction: up to 40% | Helped |
| Use a prediction that may be noisy | Augmented closeness testing · Network traffic data | robustness to noisy predictions | Helped |
Surprising findings
- Tolerant testing lower bounds do not transfer: the search finds an alpha that may be much smaller than the true TV distance, so it does not estimate it.
Limitations
- Accuracy measured by TV distance only; other distances (L_p, KL, Hellinger) left open.
- Assumes the predicted distribution is known in full to the algorithm.
- Confidence delta treated as small constant; amplification adds log(1/delta) overhead.
Experimental setup
Datasets: real network traffic data (curated distributions) synthetic hard instances
Metrics: sample complexity accuracy/error vs number of samples
Baselines: standard uniformity/identity testers standard closeness tester CRS'15 point-wise predictor-based tester
Builds on: Diakonikolas and Kane flattening Chan et al. closeness tester Aliakbarpour et al. closeness testing Acharya-Daskalakis-Kamath uniformity/identity tester (standard)
Closest papers by meaning
- Replicable Distribution Testing (NeurIPS 2025 · similarity 0.89)
- Replicable Uniformity Testing (NeurIPS 2024 · similarity 0.87)
- Entropy testing and its application to testing Bayesian networks (NeurIPS 2024 · similarity 0.86)
- Testing Calibration in Nearly-Linear Time (NeurIPS 2024 · similarity 0.86)
- Sample-Adaptivity Tradeoff in On-Demand Sampling (NeurIPS 2025 · similarity 0.86)
- Optimal Hypothesis Selection in (Almost) Linear Time (NeurIPS 2024 · 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.