# Purifying Approximate Differential Privacy with Randomized Post-processing

arXiv: https://arxiv.org/abs/2503.21071 · HTML: https://mlsanity.com/paper/2503.21071/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 70 references that are in the map.
- First posted on arXiv 27 Mar 2025.

## Builds on (most cited first, 26 of 26)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Subsampled R'enyi Differential Privacy and Analytical Moments Accountant](https://mlsanity.com/paper/1808.00087/) (2018)
- [Unlocking High-Accuracy Differentially Private Image Classification through Scale](https://mlsanity.com/paper/2204.13650/) (2022)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [Privacy Amplification by Iteration](https://mlsanity.com/paper/1808.06651/) (2018)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain](https://mlsanity.com/paper/1803.02596/) (2018)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [On the Theory and Practice of Privacy-Preserving Bayesian Data Analysis](https://mlsanity.com/paper/1603.07294/) (2016)
- [Make Up Your Mind: The Price of Online Queries in Differential Privacy](https://mlsanity.com/paper/1604.04618/) (2016)
- [Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometry](https://mlsanity.com/paper/1411.5417/) (2014)
- [Differentially Private Empirical Risk Minimization with Input Perturbation](https://mlsanity.com/paper/1710.07425/) (2017)
- [Faster Differentially Private Convex Optimization via Second-Order Methods](https://mlsanity.com/paper/2305.13209/) (2023)
- [Improving the Privacy and Practicality of Objective Perturbation for Differentially Private Linear Learners](https://mlsanity.com/paper/2401.00583/) (2023)
- [Differentially Private Coordinate Descent for Composite Empirical Risk Minimization](https://mlsanity.com/paper/2110.11688/) (2021)
- [Sampling from Log-Concave Distributions with Infinity-Distance Guarantees](https://mlsanity.com/paper/2111.04089/) (2021)
- [An end-to-end Differentially Private Latent Dirichlet Allocation Using a Spectral Algorithm](https://mlsanity.com/paper/1805.10341/) (2018)
- [Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy](https://mlsanity.com/paper/2310.14661/) (2023)
- [Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2410.05880/) (2024)
- [Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimization](https://mlsanity.com/paper/2204.01585/) (2022)

## Built on by (most cited first, 2 of 2)

- [Multi-View Graph Feature Propagation for Privacy Preservation and Feature Sparsity](https://mlsanity.com/paper/2510.11347/) (2025)
- [Optimal Rates for Pure varepsilon-Differentially Private Stochastic Convex Optimization with Heavy Tails](https://mlsanity.com/paper/2604.06492/) (2026)

## Abstract (arXiv)

We propose a framework to convert (varepsilon, δ)-approximate Differential Privacy (DP) mechanisms into (varepsilon', 0)-pure DP mechanisms under certain conditions, a process we call ``purification.'' This algorithmic technique leverages randomized post-processing with calibrated noise to eliminate the δ parameter while achieving near-optimal privacy-utility tradeoff for pure DP. It enables a new design strategy for pure DP algorithms: first run an approximate DP algorithm with certain conditions, and then purify. This approach allows one to leverage techniques such as strong composition and propose-test-release that require δ>0 in designing pure-DP methods with δ=0. We apply this framework in various settings, including Differentially Private Empirical Risk Minimization (DP-ERM), stability-based release, and query release tasks. To the best of our knowledge, this is the first work with a statistically and computationally efficient reduction from approximate DP to pure DP. Finally, we illustrate the use of this reduction for proving lower bounds under approximate DP constraints with explicit dependence in δ, avoiding the sophisticated fingerprinting code construction.