Research map / Federated learning and privacy / Differential privacy
Optimal Differential Privacy Composition for Exponential Mechanisms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 exact optimal non-adaptive composition formula (BR OptComp, Theorem 2) instead of black-box DP optimal composition | k-fold composition of epsilon-BR exponential mechanisms (non-adaptive) · Homogeneous epsilon, delta_g=1e-6, eps in {0.01,0.1,1} | number of allowable queries / privacy loss eps_g: about four times more queries than black-box composition | Helped |
| Use exact optimal non-adaptive formula instead of DR19 bound | k-fold composition of epsilon-BR mechanisms · Top-k application, homogeneous case | number of allowable queries: about two times more queries than DR19 | Helped |
| Use adaptive composition bound (MGF / OptKL) instead of DR19 bound | adaptive composition of epsilon-BR mechanisms · Heterogeneous/adaptive, some settings | number of allowable queries: about three times more queries than both optimal DP composition and DR19 in some settings | Helped |
| Model adaptive rather than non-adaptive composition of BR mechanisms (adversary chooses next mechanism from previous outputs) | composition of epsilon-BR mechanisms · Theoretical, k>=4, eps_g in [0,(k-3)eps] | achievable (eps_g, delta) privacy | Hurt |
| Replace black-box DP composition with BR-aware KL-based bound (OptKL) in heterogeneous adaptive composition (ablation) | adaptive heterogeneous composition of BR mechanisms · Figure 1 comparisons | privacy loss eps_g | Helped |
| Use MGF-based bound (Theorem 5) instead of OptKL bound for adaptive heterogeneous composition (ablation) | adaptive heterogeneous composition of BR mechanisms · Figure 1 comparisons | privacy loss eps_g | Helped |
| Apply exact optimal composition to top-k private algorithm | top-k exponential mechanism (Durfee and Rogers 2019) · Figure 1, delta_g=1e-6 | number of rounds / privacy budget: run twice as many rounds as in the original analysis | Helped |
| Account for privacy at range-bounded level (eps-BR) rather than treating exponential mechanism as eps/2-DP-like via sensitivity | single exponential mechanism composition · Figure 1 comparison with eps/2-DP OptComp | privacy loss eps_g | Mixed |
Closest papers by meaning
- Beyond the Calibration Point: Mechanism Comparison in Differential Privacy (ICML 2024 · similarity 0.89)
- 𝑓-Differential Privacy Filters: Validity and Approximate Solutions (NeurIPS 2026 · similarity 0.89)
- The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD (ICLR 2025 · similarity 0.88)
- Privacy Amplification for Matrix Mechanisms (ICLR 2024 · similarity 0.87)
- The Limits of Differential Privacy in Online Learning (NeurIPS 2024 · similarity 0.87)
- Instance-Specific Asymmetric Sensitivity in Differential Privacy (NeurIPS 2024 · similarity 0.87)
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.