Research map / Federated learning and privacy / Differential privacy
Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms
Thomas Berrett, Cristina Butucea
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace noninteractive privacy with sequentially interactive privacy | Locally private goodness-of-fit testing · Uniform[d], L1 | separation rate: \frac{d^{3/4}}{\sqrt{n\alpha^2}} -> \frac{d^{1/2}}{\sqrt{n\alpha^2}} | Improved |
| Replace noninteractive privacy with sequentially interactive privacy | Locally private goodness-of-fit testing · Uniform[d], L2 | separation rate: \leq \frac{d^{1/4}}{\sqrt{n\alpha^2}} -> \frac{1}{\sqrt{n\alpha^2}} | Improved |
| Replace noninteractive privacy with sequentially interactive privacy | Locally private goodness-of-fit testing · Polynomially decreasing distributions, L1 | separation rate: (n \alpha^2)^{-\frac{2 \beta}{4 \beta +3}} \wedge \frac{d^{3/4}}{\sqrt{n\alpha^2}} -> (n \alpha^2)^{-\frac{2 \beta}{4 \b | Improved |
| Replace noninteractive privacy with sequentially interactive privacy | Locally private goodness-of-fit testing · Polynomially decreasing distributions, L2 | separation rate: \leq (n \alpha^2)^{-\frac{2 \beta}{4 \beta +1}} \wedge \frac{d^{1/4}}{\sqrt{n\alpha^2}} -> \frac{1}{\sqrt{n\alpha^2}} | Improved |
| Replace noninteractive privacy with sequentially interactive privacy | Locally private goodness-of-fit testing · Exponentially decreasing distributions, L1 | separation rate: \frac{\log^{3/(4\beta)}(n \alpha^2) \wedge d^{3/4}}{\sqrt{n\alpha^2}} -> \frac{\log^{2/(4\beta)}(n \alpha^2) \wedge d^{1 | Improved |
| Replace noninteractive privacy with sequentially interactive privacy | Locally private goodness-of-fit testing · Exponentially decreasing distributions, L2 | separation rate: \frac{\log^{1/(4\beta)}(n \alpha^2) \wedge d^{1/4}}{\sqrt{n\alpha^2}} -> \frac{1}{\sqrt{n\alpha^2}} | Improved |
| Use the two-step interactive mechanism: estimate probabilities on an initial sample portion, then encode the censored estimates in later privatized samples | Interactive LDP goodness-of-fit testing · Discrete distributions, L2 | separation rate: \mathcal{E}_{n,\alpha}(p_0, \mathbb{L}_2) \leq \frac{C}{(n \alpha^2 \gamma^2)^{1/2}} | Improved |
Closest papers by meaning
- Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.92)
- Minimax Optimal Two-Sample Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.91)
- Extremal Mechanisms for Local Differential Privacy (JMLR 2016 · similarity 0.90)
- Optimal Rates for Differentially Private Hypothesis Testing with E-values (NeurIPS 2026 · similarity 0.88)
- A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility (AAAI 2024 · similarity 0.88)
- Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph (NeurIPS 2025 · similarity 0.88)
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.
