Research map / Federated learning and privacy / Differential privacy
Rényi Pufferfish Privacy: General Additive Noise Mechanisms and Privacy Amplification by Iteration via Shift Reduction Lemmas
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.
Introduces a Rényi-divergence variant of Pufferfish privacy, a general Wasserstein additive-noise mechanism with approximate and p-Wasserstein relaxations, and privacy amplification by iteration for noisy convex SGD via shift reduction lemmas.
Problem
Pufferfish privacy lacks general, tractable additive noise mechanisms compatible with many noise distributions, and it lacks composition guarantees needed for iterative machine learning algorithms such as DP-SGD.
Approach
Defines Rényi Pufferfish privacy and extends the Wasserstein mechanism to any absolutely continuous additive noise via shift reduction lemmas, relaxes the infinity-Wasserstein constraint (delta-approximation and p-Wasserstein/Orlicz shifts), and proves a dataset-dependent privacy amplification by iteration bound for contractive noisy iterations.
Key results
- In Example 2 the approximate GAWM gives sensitivity 1 at delta=3e-3 versus 98 for the GWM.
- On attribute privacy with real datasets, GWM/DAGWM sensitivities are lower than DP sensitivities (e.g., Heart: DP >=100 vs GWM 8; Student Scores: 20 vs 8).
- PABI bound for noisy projected SGD gives a T-independent bound under independent data, recovering DP-SGD results of Feldman et al. (2018).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GWM instead of DP | Attribute privacy mechanisms · Student Scores | sensitivity: 20 -> 8 | Helped |
| Use the Cauchy mechanism instead of GWM | Attribute privacy mechanisms · Student Scores | sensitivity: 8 -> 2.76 | Helped |
| Use GWM instead of DP | Attribute privacy mechanisms · Heart | sensitivity: ≥100 -> 8 | Helped |
| Use the Cauchy mechanism instead of GWM | Attribute privacy mechanisms · Heart | sensitivity: 8 -> 7.80 | Helped |
| Use GWM instead of DP | Attribute privacy mechanisms · Adult | sensitivity: 1 -> 1 | No clear effect |
| Use the Cauchy mechanism instead of GWM | Attribute privacy mechanisms · Adult | sensitivity: 1 -> 0.42 | Helped |
| Use δ-approximation in place of the exact GWM constraint | GWM on the Average salary query · Average salary query | sensitivity: 98 -> 1 | Helped |
| Use the distribution-aware shift constraint instead of the GWM shift constraint | Mechanisms for Example 1 · Counting query with correlation | RPP privacy cost: log(1+ 4/λ²)/(α−1) -> log(1+ (1+3ρ)/λ²)/(α−1) | Helped |
| Analyze noisy gradient descent with independent data points using PABI | Noisy gradient descent · Independent data points | RPP privacy cost: αη²/(2σ²) min(2L, ∥a − b∥ supᵥ∈K Cᵥ)² | Helped |
Limitations
- The infinity-Wasserstein sensitivity can be large for heavy-tailed or rare-value queries, motivating relaxations.
- The general Wasserstein computations are hard in general; closed forms are given only for specific instances.
- Theoretical PABI bound for correlated data grows with the number of steps when data points are correlated.
Experimental setup
Datasets: Student Scores Heart Adult
Metrics: sensitivity
Baselines: Wasserstein mechanism group RDP group differential privacy DP sensitivity-based mechanisms
Builds on: Pufferfish privacy Wasserstein mechanism shift reduction lemma privacy amplification by iteration Rényi differential privacy
Closest papers by meaning
- Shifted Interpolation for Differential Privacy (ICML 2024 · similarity 0.88)
- The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD (ICLR 2025 · similarity 0.88)
- Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation (NeurIPS 2026 · similarity 0.88)
- Privacy Amplification Persists under Unlimited Synthetic Data Release (NeurIPS 2026 · similarity 0.88)
- Privacy Amplification for Matrix Mechanisms (ICLR 2024 · similarity 0.88)
- Optimizing Noise Distributions for Differential Privacy (ICML 2025 · similarity 0.88)
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.