Purifying Approximate Differential Privacy with Randomized Post-processing
This work addresses a foundational challenge in privacy-preserving machine learning by providing a novel framework to eliminate the δ parameter, which is crucial for applications requiring strict privacy guarantees without relying on complex constructions like fingerprinting codes.
The paper tackles the problem of converting approximate differential privacy mechanisms into pure differential privacy mechanisms, achieving a statistically and computationally efficient reduction that enables new design strategies for pure DP algorithms with near-optimal privacy-utility tradeoffs.
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.