Research map / Federated learning and privacy / Differential privacy
Exactly Minimax-Optimal Locally Differentially Private Sampling
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.
Characterizes the exact minimax worst-case f-divergence privacy-utility trade-off for locally differentially private sampling over finite and continuous (bounded-density-ratio) data spaces and gives a universally optimal clipping-based mechanism that beats the KL-projection baseline.
Problem
Private sampling under local differential privacy: a client holding a distribution must release a sample whose distribution is close to the original; prior work fixed a reference distribution, giving only locally optimal mechanisms and ambiguous utility. The paper asks for the exact minimax privacy-
Approach
Defines worst-case f-divergence over all epsilon-LDP sampling mechanisms, and shows a clipped-density mechanism (clip of p/r_P to a band [b, b e^eps] times reference) is the f-divergence projection for every f and is minimax optimal, removing dependence on an arbitrary reference distribution.
Key results
- For finite k=10, the proposed mechanism has lower theoretical worst-case f-divergence than the MBDE-based baseline (uniform Q0) for KL, TV and squared Hellinger across epsilon in {0.1,0.5,1,2,5}, with a significant gap for epsilon in [0.5,2].
- On 1D Gaussian mixtures (N=100, K=10), the proposed mechanism yields much lower empirical worst-case f-divergence than the baseline for all tested f-divergences and epsilon.
- Exact minimax worst-case f-divergence is characterized as (1-r1)/(r2-r1) f(r2) + (r2-1)/(r2-r1) f(r1), attained universally for all f-divergences.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed minimax-optimal sampler instead of the baseline with uniform reference distribution | Private sampling over finite space (k=10) · Finite space [k], k=10 | KL divergence | Helped |
| Use the proposed minimax-optimal sampler instead of the baseline with uniform reference distribution | Private sampling over finite space (k=10) · Finite space [k], k=10 | total variation distance | Helped |
| Use the proposed minimax-optimal sampler instead of the baseline with uniform reference distribution | Private sampling over finite space (k=10) · Finite space [k], k=10 | squared Hellinger distance | Helped |
| Use the proposed minimax-optimal sampler instead of MBDE baseline | Private sampling for 1D Gaussian mixtures · 1D Gaussian mixture (100 experiments, K=10) | KL divergence | Helped |
| Use the proposed minimax-optimal sampler instead of MBDE baseline | Private sampling for 1D Gaussian mixtures · 1D Gaussian mixture (100 experiments, K=10) | total variation distance | Helped |
| Use the proposed minimax-optimal sampler instead of MBDE baseline | Private sampling for 1D Gaussian mixtures · 1D Gaussian mixture (100 experiments, K=10) | squared Hellinger distance | Helped |
Surprising findings
- The baseline's closed-form clipping expression can fail to sum to one for some pairs (e.g., point masses), so the original formula is incomplete.
- The optimal mechanism is the f-divergence projection for every f-divergence, not only KL.
Limitations
- Worst-case f-divergence is only a geometry-agnostic utility; Wasserstein-type metrics are not covered.
- Only single-sample-per-client release is analyzed.
- Continuous-case experiments use empirical rather than closed-form utility, and r_P must be found numerically via bisection with approximation error affecting the LDP level.
Experimental setup
Datasets: synthetic Gaussian mixtures in 1D
Benchmarks: finite space k=10 worst-case f-divergence 1D Gaussian mixture empirical worst-case f-divergence
Metrics: worst-case KL divergence worst-case total variation worst-case squared Hellinger empirical maximum f-divergence over 100 mixtures
Baselines: MBDE relative mollifier KL projection
Builds on: Mollified Boosted Density Estimation k-ary randomized response f-divergence data processing inequality
Closest papers by meaning
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.94)
- Privacy Amplification Persists under Unlimited Synthetic Data Release (NeurIPS 2026 · similarity 0.90)
- Privacy Guarantees in Posterior Sampling under Contamination (NeurIPS 2026 · similarity 0.89)
- Privacy without Noisy Gradients: Slicing Mechanism for Generative Model Training (NeurIPS 2024 · similarity 0.89)
- Instance-Optimality for Private KL Distribution Estimation (NeurIPS 2025 · similarity 0.89)
- Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation (NeurIPS 2026 · similarity 0.89)
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.