Research map / Federated learning and privacy / Differential privacy
Numerical Composition of Differential Privacy
Sivakanth Gopi, Yin Tat Lee, Lukas Wutschitz
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 |
|---|---|---|---|
| truncate PRV domain at L = Theta(1) using tight tail bound instead of O~(sqrt(k)) | PRV composition algorithm · DP-SGD privacy curve | running time and memory: O~(sqrt(k)) -> O~(1) | Improved |
| proposed algorithm versus prior FFT algorithm of Koskela et al. at aligned accuracy | PRV composition algorithm · DP-SGD sigma=0.8, p=4e-3, eps=1.5, varying steps | runtime | Improved |
| large number of DP-SGD steps (beyond 2,000) with the prior method | prior FFT algorithm of Koskela et al. · DP-SGD, sigma=0.8, p=4e-3 | numerical stability: unstable beyond 2,000 steps | Hurt |
| number of discretisation points needed for convergence: proposed vs prior method | PRV composition algorithm · p=4e-3, sigma=0.8, eps=1.5, k=1000 | error of delta vs number of discretisation points | Improved |
| compare error bounds at the same mesh size 8e-4 for k = 10, 100, 1000 | PRV composition algorithm vs prior method · p=1e-2, sigma=0.8 | width of delta error bounds: prior method reasonable at small k, worse at k=1000 | Mixed |
| use PRV composition bounds versus GDP and RDP accountants | DP-SGD privacy accounting · DP-SGD privacy curve | privacy curve bounds | Improved |
| validate against exact analytical Gaussian curve at p=1 | PRV composition algorithm · p=1 (Gaussian mechanism) | sandwich of true delta(eps): delta_error 10^-10 | Improved |
| push delta below floating point resolution | PRV composition algorithm · p=1 analytical comparison, ~10^4 discretization points | bound meaningfulness: fails for delta < 2 x 10^-11 | Hurt |
| analysis via coupling approximation instead of convolution stability | error analysis · runtime dependence on delta_error | runtime dependence: 1/delta_error -> sqrt(log(1/delta_error)) | Improved |
Closest papers by meaning
- The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD (ICLR 2025 · similarity 0.90)
- Purifying Approximate Differential Privacy with Randomized Post-processing (NeurIPS 2025 · similarity 0.89)
- 𝑓-Differential Privacy Filters: Validity and Approximate Solutions (NeurIPS 2026 · similarity 0.89)
- Provable Privacy with Non-Private Pre-Processing (ICML 2024 · similarity 0.88)
- Auditing $f$-differential privacy in one run (ICML 2025 · similarity 0.88)
- Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothness (ICLR 2025 · 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.
