Differential Privacy (DP) is often divided into two tiers: "pure" $\epsilon$-DP and "approximate" $(\epsilon, \delta)$-DP. While pure DP offers a rigorous guarantee for every possible outcome, approximate DP allows for a tiny probability ($\delta$) of a catastrophic privacy failure. Because approximate DP is more flexible—allowing for techniques like advanced composition and the Gaussian mechanism—it has become the industry standard.
However, a growing body of research suggests that the gap between these two tiers is narrower than once thought. By using "purification" techniques, researchers are finding ways to transform approximate, noisy, or one-sided privacy guarantees into the gold standard of pure differential privacy without sacrificing utility.
The Intuition of Purification
The core idea behind purification is that the "slack" in an approximate privacy guarantee is often an artifact of how we measure privacy, rather than a fundamental limit of the data. If an algorithm is $(\epsilon, \delta)$-private, it means there is a small set of outcomes where the privacy loss exceeds $\epsilon$.
As Yingyu Lin, Erchi Wang, Yian Ma, and Yu-Xiang Wang demonstrate in Purifying Approximate Differential Privacy with Randomized Post-processing, we can "smooth out" these problematic outcomes. By taking the output of an approximate mechanism and mixing it with a controlled amount of uniform and Laplace noise, we can effectively mask the $\delta$ risk. This post-processing step ensures that the final output satisfies pure $\epsilon$-DP, allowing us to use flexible "approximate-only" tools like Propose-Test-Release while maintaining strict privacy bounds.
This isn't just a theoretical curiosity. Mark Bun, Jelani Nelson, and Uri Stemmer proved in Heavy Hitters and the Structure of Local Privacy that for non-interactive protocols, approximate local privacy offers no accuracy advantage over pure privacy. Any protocol with a small failure probability can be converted into a strictly private one with nearly identical accuracy.
Restoring Exactness in Private Sampling
A similar challenge exists in Bayesian inference. When we use Markov Chain Monte Carlo (MCMC) to sample from a sensitive posterior distribution, we often add noise to the gradients or likelihoods to satisfy DP. This noise usually biases the sampler, meaning it no longer converges to the true target distribution.
To fix this, researchers use a form of "mathematical purification" to restore the sampler's exactness. In DP-Fast MH: Private, Fast, and Accurate Metropolis-Hastings for Large-Scale Bayesian Inference, Wanrong Zhang and Ruqi Zhang introduce a correction term. By subtracting half of the injected noise variance from the log-acceptance ratio, they maintain the "reversibility" of the Markov chain. This ensures the algorithm converges to the exact posterior despite the privacy-preserving noise.
When the sampler itself is only an approximation (e.g., it hasn't fully converged), Yingyu Lin and colleagues propose the ASAP (Approximate SAmple Perturbation) mechanism in Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy. ASAP adds a secondary layer of noise proportional to the maximum possible approximation error ($W_\infty$ distance). This noise "purifies" the approximate sample, restoring pure DP guarantees by masking the discrepancy between the approximate and ideal distributions.
Symmetrizing One-Sided Privacy
Purification also applies to the direction of privacy. Some algorithms are naturally "one-sided"—they protect the privacy of adding an element but not removing it.
In Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization, Badih Ghazi, Pasin Manurangsi, and their co-authors use Poisson subsampling as a purification tool. This technique symmetrizes the privacy guarantee, transforming one-sided additive DP into standard two-sided pure DP. This allows combinatorial algorithms for problems like Set Cover to achieve the same accuracy as approximate-DP versions while meeting the stricter pure-DP standard.
Why It Works: The Power of Post-Processing
The recurring theme across these papers—from Steven Lee's work on Optimal Pure Differentially Private Sparse Histograms to Clement Louis Canonne's Lemmas of Differential Privacy—is that privacy is a property of the distribution of outputs.
If an algorithm's output distribution is "almost" right (approximate DP) or "almost" target-aligned (biased MCMC), we can often apply a randomized transformation to the output to fix the distribution. Because differential privacy is immune to post-processing, these transformations can strengthen the privacy guarantee or restore statistical exactness without needing to access the original sensitive data again. This shift suggests that the "utility gap" between approximate and pure privacy is not a fundamental law of information theory, but rather a challenge of algorithmic design that purification is beginning to solve.