Research map / Federated learning and privacy / Differential privacy
Differentially Private Equivalence Testing for Continuous Distributions and Applications
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 the first differentially private algorithm for equivalence testing between two continuous distributions in A_k-distance, privatizing the Diakonikolas et al. tester via sorted-index binning with Bernoulli-shifted partition points and Poisson subsampling.
Problem
Testing whether two continuous distributions are identical or far apart in A_k-norm under differential privacy, where discretizing the real line from the data is highly sensitive.
Approach
Replace data-resampling with sorted-index bin boundaries perturbed by Ber(1/2) noise so that neighboring datasets change only a few bins, then privatize a two-part non-private tester (autocorrelation statistic with Laplace noise, plus repeated L2 closeness tests over merged bins) using Poisson-subsampled bins for the utility proof.
Key results
- Gives an (2ϵ, 2δ)-DP equivalence tester for continuous distributions with sample complexity Õ(max{k^{4/5}/α^{6/5}, k^{2/3}/(αϵ^{1/3}), k^{1/2}/α², k^{1/3}/(α^{4/3}ϵ^{2/3}), √k/(αϵ)}).
- Improves over the subsample-and-aggregate baseline with sample complexity O((k^{4/5}/α^{6/5} + k^{1/2}/α²)/ϵ) and yields numerical estimators explaining accept/reject decisions.
- Extends to families such as t-piecewise constant, log-concave, and MHR distributions with explicit private sample complexity bounds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed private tester instead of Subsample-and-Aggregate | Equivalence testing for continuous distributions under Ak-norm · Continuous distributions | sample complexity | Helped |
Limitations
- Sample complexity has an extra sqrt(k)/(αϵ) term due to high L2-based sensitivity, leaving a gap to the private lower bound.
- Log factors in the bound are not optimized.
- Purely theoretical; no experiments reported.
Experimental setup
Metrics: sample complexity type I/II error
Baselines: Subsample-and-Aggregate applied to Diakonikolas et al. tester
Builds on: Diakonikolas et al. closeness tester (A_k-norm) Subsample-and-Aggregate Propose-Test-Release
Closest papers by meaning
- Minimax Optimal Two-Sample Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.89)
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.87)
- Privacy Guarantees in Posterior Sampling under Contamination (NeurIPS 2026 · similarity 0.87)
- Lightweight Protocols for Distributed Private Quantile Estimation (ICML 2025 · similarity 0.86)
- Private Evolution Converges (NeurIPS 2025 · similarity 0.86)
- Optimal Rates for Differentially Private Hypothesis Testing with E-values (NeurIPS 2026 · 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.