2025/03/27 by Yingyu Lin, Erchi Wang, Lin, Yingyu +5 · 2 citations
Computer Science · Social Sciences · #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Privacy, Security, and Data Protection #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2503.21071
openalex publication_date 2025/03/27 · openalex created_date 2025/10/11 · openalex updated_date 2026/07/28
We propose a framework to convert (ε, δ)-approximate Differential Privacy (DP) mechanisms into (ε', 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.