Research map / Federated learning and privacy / Differential privacy
Purifying Approximate Differential Privacy with Randomized Post-processing
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.
Proposes "purification," converting (ε,δ)-approximate DP mechanisms into pure DP via uniform mixing plus Laplace post-processing, and applies it to DP-ERM, PTR, mode release, linear regression, query release, and lower bounds.
Problem
Approximate DP is often used because it enables utility gains and composition/PTR tools unavailable to pure DP; the paper asks whether approximate DP mechanisms can be converted into efficient pure DP mechanisms with near-optimal utility.
Approach
Mix the approximate-DP output with a small uniform distribution over a bounded convex set so the TV distance to a hypothetical indistinguishable pair converts into an infinity-Wasserstein bound, then add Laplace noise calibrated to that bound to obtain pure DP via randomized post-processing.
Key results
- Purified DP-SGD gives 2ε-pure DP with excess risk Õ(CLd/(nε)) for convex losses, matching the exponential mechanism's rate with runtime Õ(n²ε^{3/2}+d) versus the exponential mechanism's higher cost.
- Pure DP mode release achieves 2ε-DP with a gap requirement of Ω(log|X| log(log|X|/ε)/ε), matching the Laplace histogram bound up to a log log|X| factor.
- Lower bound via purification: any (ε,δ)-DP mean estimator has error Ω̃(√(d log(1/δ))/(εn)) on some dataset, with probability at least 1/4.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Purify Noisy-SGD | Noisy-SGD · DP-ERM | excess empirical risk: $\frac{\sqrt{d\log (1/\delta)} L\|\mathcal{C}\|_2}{n\varepsilon}$ -> $\frac{d L\|\mathcal{C}\|_2}{n\varepsilon}$ | Mixed |
| Purify Noisy-SGD | Noisy-SGD · DP-ERM (SC) | excess empirical risk: $\frac{d\log (1/\delta) L^2}{\lambda n^2\varepsilon^2 }$ -> $\frac{d^2 L^2}{\lambda n^2\varepsilon^2}$ | Mixed |
| Purify DP-Frank-Wolfe | DP-Frank-Wolfe · DP-ERM (ℓ1) | excess empirical risk: $\frac{(\log d)^{2/3}(\log (1/\delta))^{1/3}}{(n\varepsilon)^{2/3}}$ -> $\sqrt{\frac{\log d}{n\varepsilon}}$ | Mixed |
| Purify PTR-type mechanism | PTR-type mechanism · Bounding Δ_local | utility bound: $\frac{d^{1/2}(\Delta_{\mathrm{local}} + \log(1/\delta)/\varepsilon)}{\varepsilon}$ -> $\frac{d^{1/2}\Delta_{\mathrm{loc | Mixed |
| Purify Distance to Instability | Distance to Instability · Mode Release | utility bound: $\frac{\log(1/\delta)}{\varepsilon}$ -> $\frac{\log|\mathcal{\mathcal{X}}|}{\varepsilon}$ | Mixed |
| Purify AdaSSP | AdaSSP · Linear Regression | utility bound: $\min\{\frac{\sqrt{d\log(1/\delta)}}{n\varepsilon}, \frac{d\log(1/\delta)}{\lambda_{\min}n^2 \varepsilon^2}\}$ -> $\min\ | Mixed |
| Purify MWEM | MWEM · Query Release | utility bound: $\frac{(\log k)^{1/2} ( d \log(1/\delta))^{1/4} }{\sqrt{n\varepsilon}}$ -> $\frac{(\log k)^{1/3} d^{1/3} }{(n\varepsilon | Mixed |
| Replace Laplace Noisy GD with purified DP-SGD | DP-ERM · DP-ERM, ℓ2-Lipschitz convex | utility: $\nicefrac{d^{1/2}}{(n\varepsilon)^{1/2}}$ -> $\nicefrac{d}{n\varepsilon}$ | Helped |
| Use purified DP-SGD instead of the exponential mechanism | DP-ERM · DP-ERM, ℓ2-Lipschitz convex | runtime: $d^4n^3 \vee d^3 n^4 \varepsilon$ -> $n^2\varepsilon^{3/2} + d$ | Helped |
Surprising findings
- Pure-DP mechanisms can match or beat approximate DP utility for low-dimensional private histograms, where the Laplace mechanism has smaller variance than the Gaussian mechanism except when δ is too large.
Limitations
- For finite output spaces the utility bound incurs an extra log log|Y| factor compared to prior work.
- Purification of high-dimensional outputs introduces an extra Õ(d) factor through the Laplace noise scale, which can degrade utility for dimension-independent algorithms.
Experimental setup
Metrics: excess empirical risk mean squared error expected l_infinity error expected l_1 error
Baselines: Noisy-SGD exponential mechanism DP-Frank-Wolfe AdaSSP MWEM Small Database mechanism Laplace histogram
Builds on: Noisy-SGD DP-Frank-Wolfe MWEM AdaSSP ASAP
Closest papers by meaning
- Provable Privacy with Non-Private Pre-Processing (ICML 2024 · similarity 0.89)
- 𝑓-Differential Privacy Filters: Validity and Approximate Solutions (NeurIPS 2026 · similarity 0.89)
- Auditing $f$-differential privacy in one run (ICML 2025 · similarity 0.88)
- The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD (ICLR 2025 · similarity 0.88)
- Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy (ICLR 2024 · similarity 0.88)
- Instance-Specific Asymmetric Sensitivity in Differential Privacy (NeurIPS 2024 · 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.