Research map / Federated learning and privacy / Differential privacy
Extremal Mechanisms for Local Differential Privacy
Peter Kairouz, Sewoong Oh, Pramod Viswanath
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 |
|---|---|---|---|
| use binary or randomized response mechanism instead of geometric noise mechanism | local differential privacy mechanism · KL divergence, |X|=6, 100 random instances | normalized KL divergence | Improved |
| use randomized response in the high privacy regime instead of the optimal staircase mechanism | randomized response mechanism · KL divergence, |X|=6 | KL divergence relative to optimal: as bad as 10% of the optimal one | Hurt |
| use binary mechanism in the low privacy regime instead of the optimal staircase mechanism | binary mechanism · KL divergence, |X|=6 | KL divergence relative to optimal: as bad as 25% of the optimal one | Hurt |
| pick the better of binary and randomized response per instance | binary and randomized response mechanisms · KL divergence, |X| in {3,4,6,12} | fraction of optimal KL divergence: at least 70% for |X| = 6 (and 55% for |X| = 12) | Improved |
| use randomized response in the high privacy regime instead of the optimal mechanism | randomized response mechanism · Mutual information, |X|=6 | mutual information relative to optimal: as bad as 35% of the optimal one | Hurt |
| use binary mechanism in the low privacy regime instead of the optimal mechanism | binary mechanism · Mutual information, |X|=6 | mutual information relative to optimal: as bad as 40% of the optimal one | Hurt |
| pick the better of binary and randomized response per instance | binary and randomized response mechanisms · Mutual information, |X| in {3,4,6,12} | fraction of optimal mutual information: at least 75% for |X| = 6 (and 65% for |X| = 12) | Improved |
Closest papers by meaning
- Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms (NeurIPS 2020 · similarity 0.92)
- Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.90)
- Instance-Specific Asymmetric Sensitivity in Differential Privacy (NeurIPS 2024 · similarity 0.89)
- Beyond the Calibration Point: Mechanism Comparison in Differential Privacy (ICML 2024 · similarity 0.89)
- Exactly Minimax-Optimal Locally Differentially Private Sampling (NeurIPS 2024 · similarity 0.89)
- Auditing $f$-differential privacy in one run (ICML 2025 · 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.
