Research map / Federated learning and privacy / Differential privacy
Differentially Private Testing of Identity and Closeness of Discrete Distributions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 |
|---|---|---|---|
| Add differential privacy to binary identity testing | Binary identity testing · Binary identity testing | sample complexity: \Theta\Paren{\frac1{\alpha^2} +\frac1{\alpha\varepsilon}} versus \Theta\Paren{\frac1{\alpha^2}} | Hurt |
| Add differential privacy to identity testing | Identity testing · Identity testing | sample complexity: S({\tt IT}, k, \alpha,\varepsilon) = \Theta\Paren{\frac{\sqrt k}{\alpha^2}+{\max\left\{\frac{k^{1/2}}{\alpha(\varepsilon | Hurt |
| Use the coupling lower-bound framework | Differentially private statistical testing · Binary, identity, and closeness testing | sample complexity lower bound: D = \Omega\Paren{\frac1{\varepsilon}} | Helped |
| Add differential privacy to closeness testing in the sparse regime | Closeness testing · Closeness testing, sparse regime | sample complexity: \Theta\Paren{\frac{k^{2/3}}{\alpha^{4/3}}+\frac{\sqrt k}{\alpha\sqrt \varepsilon}} versus \Theta{ \left(\frac{k^{2/3}}{\ | Hurt |
| Privatize the empirical-distance identity-test statistic using sigmoid randomization | Uniformity testing · Identity testing, sparse sample regime | sample complexity: O\Paren{\frac{\sqrt{k}}{\alpha^2}+\frac{\sqrt{k}}{\alpha\sqrt{\varepsilon}}} | Helped |
| Privatize the empirical-distribution distance statistic | Uniformity testing · Identity testing, all parameter ranges | sample complexity: S({\tt IT}, k, \alpha,\varepsilon) = \Theta\Paren{\frac{\sqrt k}{\alpha^2} + \frac{k^{1/2}}{\alpha\varepsilon^{1/2}}} | Helped |
| Privatize the chi-square-based closeness statistic with sigmoid randomization | Closeness testing · Closeness testing, sparse regime | sample complexity: \Theta\Paren{\frac{k^{2/3}}{\alpha^{4/3}}+\frac{\sqrt k}{\alpha\sqrt \varepsilon}} | Helped |
Closest papers by meaning
- Minimax Optimal Two-Sample Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.91)
- Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.89)
- Optimal Private and Communication Constraint Distributed Goodness-of-Fit Testing for Discrete Distributions in the Large Sample Regime (NeurIPS 2024 · similarity 0.89)
- Optimal Rates for Differentially Private Hypothesis Testing with E-values (NeurIPS 2026 · similarity 0.89)
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.89)
- Privacy Guarantees in Posterior Sampling under Contamination (NeurIPS 2026 · 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.