Research map / Federated learning and privacy / Differential privacy

Minimax Optimal Two-Sample Testing under Local Differential Privacy

NeurIPS 2026 · Federated learning and privacy › Differential privacy · approach: Local-DP and private estimation · 0 citations (OpenAlex)

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.

Develops permutation-based two-sample tests under local differential privacy for multinomial and binned continuous data (Laplace, discrete Laplace, RAPPOR mechanisms), proving minimax separation rates and an adaptive Bonferroni-type density test.

Problem

Two-sample testing of multinomial and continuous (Hölder/Besov) distributions under local differential privacy: characterizing the privacy-utility trade-off in minimax separation rates.

Approach

Uses permutation tests on U-statistics computed from LDP-privatized one-hot (or binned) views via Laplace, discrete Laplace, or RAPPOR mechanisms, giving finite-sample type I error control and minimax-optimal l2 / L2 separation rates; density testing reduces to multinomial testing on equal-width bins with a Bonferroni multiscale adaptive variant.

Key results

• Minimax multinomial l2 two-sample rate under LDP is (k^{1/4}/(n_1 alpha^2)^{1/2}) ∨ n_1^{-1/2}, with matching upper and lower bounds up to constants for bounded alpha.
• Density testing under LDP attains L2 rate (n_1 alpha^2)^{-2s/(4s+3d)} ∨ n_1^{-2s/(4s+d)} for Hölder and Besov classes, with finite-sample type I error control.
• Simulations show RAPPOR-based tests have highest power for large k and density testing, while GenRR is best only for small k (k=4); permutation-calibrated LapU+l2 controls type I error while asymptotic chi-square tests deviate.

Surprising findings

• Generalized randomized response is suboptimal in separation rate for large number of categories, and its power degrades in high-dimensional settings.
• Laplace-based mechanisms perform worst empirically despite having the same theoretical rate as RAPPOR.

Limitations

• Equal-width binning may be problematic in high dimensions because many bins are empty.
• Adaptive test carries extra log factors (log^2 n_1 log log n_1) and conservative type I error via union bound.
• Lower and upper bounds for the multinomial case differ by alpha versus z_alpha terms in some regimes.

Experimental setup

Metrics: type I error rate power (rejection ratio over 2000 repetitions)

Baselines: GenRR+Chi RAPPOR+ProjChi GenRR+l2

Builds on: Ingster's method two-moments method for permutation tests Laplace mechanism RAPPOR generalized randomized response

Closest papers by meaning

• Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.91)
• Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.91)
• Optimal Rates for Differentially Private Hypothesis Testing with E-values (NeurIPS 2026 · similarity 0.90)
• Differentially Private Equivalence Testing for Continuous Distributions and Applications (NeurIPS 2024 · similarity 0.89)
• Exactly Minimax-Optimal Locally Differentially Private Sampling (NeurIPS 2024 · similarity 0.89)
• Privacy Guarantees in Posterior Sampling under Contamination (NeurIPS 2026 · similarity 0.88)