Research map / Federated learning and privacy / Differential privacy

Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy

NeurIPS 2026 · Federated learning and privacy › Differential privacy · approach: Privacy accounting and mechanisms · 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.

Shows that optimal ε-LDP mechanisms for binary hypothesis testing under f-divergence utility can be chosen as sort-partition-randomize (SPR) mechanisms, enabling an exact O(ℓk²) dynamic program (O(k³) unconstrained).

Problem

Designing ε-locally differentially private mechanisms that maximize an f-divergence (TV, KL, hockey-stick) between output distributions for binary hypothesis testing on a finite alphabet; prior exact methods were exponential in k or ℓ.

Approach

After sorting the alphabet by likelihood ratio, an optimal mechanism can be taken to partition the sorted alphabet into contiguous blocks and apply randomized response to the block label; every extreme point of the joint range is an SPR mechanism, and the f-divergence's additive block decomposition gives a dynamic program.

Key results

• SPR dynamic program matches the Kairouz-Oh-Viswanath staircase LP to numerical precision (≤6.1e-14) for k=6 across 100 Dirichlet pairs and an ε grid in [0,10].
• For k=100, the SPR DP completes the full ε sweep in under 20 seconds on a laptop, whereas the LP has 2^100 variables.
• Theorem gives a closed-form optimal binary generalized randomized-response mechanism for E_γ divergences, with an upper bound attained with equality.

Surprising findings

• The optimal E_γ mechanism is binary and its threshold set does not depend on ε: privacy only privatizes the bit 1{X in S_γ}.

Limitations

• Restricted to simple binary hypothesis testing under pure, non-interactive ε-LDP on finite alphabets.
• Assumes P0, P1 are known exactly.
• DP relies on additive block decomposition of f-divergences; not directly extended to quasi-convex objectives such as Chernoff information.

Experimental setup

Metrics: KL divergence (f-divergence) achieved by mechanism maximum deviation between DP and LP values

Baselines: binary mechanism k-ary randomized response Kairouz-Oh-Viswanath staircase LP

Builds on: staircase mechanisms (Kairouz-Oh-Viswanath) Pensia et al. joint range geometry likelihood-ratio quantizers

Closest papers by meaning

• Minimax Optimal Two-Sample 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)
• Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph (NeurIPS 2025 · similarity 0.89)
• Exactly Minimax-Optimal Locally Differentially Private Sampling (NeurIPS 2024 · similarity 0.87)
• Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.87)
• A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility (AAAI 2024 · similarity 0.87)