Numerical Composition of Differential Privacy
Citations Over TimeTop 10% of 2024 papers
Abstract
We give a fast algorithm to optimally compose privacy guarantees of differentially private (DP) algorithms to arbitrary accuracy. Our method is based on the notion of \emph{privacy loss random variables} to quantify the privacy loss of DP algorithms.The running time and memory needed for our algorithm to approximate the privacy curve of a DP algorithm composed with itself $k$ times is $\tilde{O}(\sqrt{k})$. This improves over the best prior method by Koskela et al. (2021) which requires $\tilde{\Omega}(k^{1.5})$ running time. We demonstrate the utility of our algorithm by accurately computing the privacy loss of DP-SGD algorithm of Abadi et al. (2016) and showing that our algorithm speeds up the privacy computations by a few orders of magnitude compared to prior work, while maintaining similar accuracy.
Related Papers
- → Differential Private Noise Adding Mechanism and Its Application on Consensus Algorithm(2020)93 cited
- → Differential private noise adding mechanism: Basic conditions and its application(2017)35 cited
- → Differential Private Noise Adding Mechanism and Its Application on Consensus(2016)4 cited
- Differential Private Noise Adding Mechanism: Fundamental Theory and its Application.(2016)
- Susquehanna Chorale Spring Concert "Roots and Wings"(2017)