Research map / Federated learning and privacy / Differential privacy
Optimal Private and Communication Constraint Distributed Goodness-of-Fit Testing for Discrete Distributions in the Large Sample Regime
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.
Derives matching minimax separation rates for distributed uniformity testing of discrete distributions under bandwidth and local differential privacy constraints in the large-sample regime, by transferring results from a Gaussian mean model via Le Cam statistical equivalence.
Problem
Distributed goodness-of-fit testing for discrete distributions when each of m servers holds many (n) samples over a domain of size d, under bandwidth or local differential privacy constraints; prior minimax rates were known only for n=1.
Approach
Uses Le Cam's deficiency distance to show the multinomial model is asymptotically equivalent to a d-dimensional Gaussian mean model when md log d / sqrt(n) -> 0, so minimax rates transfer from the Gaussian problem; also shows the multinomial and Gaussian models are asymptotically non-equivalent when n is small relative to d.
Key results
- Under bandwidth constraints, the minimax separation rate is rho^2 ≍ (d/(sqrt(d∧b) m n)) ∧ (sqrt(d)/(sqrt(m) n)) with shared randomness, and d^{3/2}/((d∧b) m n) ∧ sqrt(d)/(sqrt(m) n) with local randomness only.
- Under local (epsilon,delta)-DP, the rates match the Gaussian model with phase transitions (e.g. d/(mn eps^2) for shared randomness when eps >= sqrt(d)/sqrt(m)).
- The distributed multinomial and Gaussian models are shown to be asymptotically non-equivalent when d/(n log d) >= C and n >= sqrt(d) log d, since the bandwidth rates differ.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use shared randomness instead of local randomness under a bandwidth constraint | Distributed multinomial uniformity testing · Large-sample regime, md log d / sqrt(n) = o(1) | minimax separation rate | Mixed |
| Use shared randomness instead of local randomness under local differential privacy | Distributed multinomial uniformity testing · Large-sample regime, md log d / sqrt(n) = o(1) | minimax separation rate | Mixed |
| Increase the communication budget | Distributed multinomial uniformity testing · Large-sample regime | communication efficiency | Helped |
| Increase the communication budget | Distributed multinomial uniformity testing · One observation per server (n=1) | communication efficiency | Helped |
| Approximate the multinomial model with the corresponding Gaussian model using statistical equivalence | Distributed goodness-of-fit testing under bandwidth or privacy constraints · Large-sample regime, md log d / sqrt(n) = o(1) | minimax separation rate | No clear effect |
| Use the Gaussian model in place of the multinomial model when sample size is small relative to domain size | Distributed goodness-of-fit testing · Bandwidth-constrained regime with d/(n log(d)) >= C and n >= sqrt(d) log(d) | Le Cam deficiency | Hurt |
Surprising findings
- Unlike the n=1 case, the bandwidth benefit is only linear (sub-linear in b) in the large-sample regime, with no exponential communication efficiency.
- Multinomial and Gaussian models are asymptotically non-equivalent in the small-n regime, despite being equivalent for large n.
Limitations
- Results require m d log d / sqrt(n) -> 0, restricting the regime considered.
- Joint bandwidth and privacy constraints are not treated since the Gaussian minimax rates for joint constraints are unknown.
- Equivalence approach does not directly give minimax-optimal estimators/tests.
Experimental setup
Metrics: minimax testing risk minimax separation rate Le Cam deficiency distance
Baselines: Acharya et al. single-observation-per-server bandwidth minimax rates Acharya et al. single-observation-per-server private minimax rates
Builds on: Le Cam deficiency distance Gaussian mean-model distributed testing minimax rates (Acharya et al.) Yu/Cai-type multinomial-to-Gaussian equivalence
Closest papers by meaning
- Minimax Optimal Two-Sample Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.88)
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.86)
- Replicable Distribution Testing (NeurIPS 2025 · similarity 0.86)
- Instance-Optimality for Private KL Distribution Estimation (NeurIPS 2025 · similarity 0.86)
- Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.86)
- Differentially Private Equivalence Testing for Continuous Distributions and Applications (NeurIPS 2024 · similarity 0.86)
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.