Numerical Composition of Differential Privacy
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 algor...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Labor Dynamics Institute
2024-02-01
|
| Series: | The Journal of Privacy and Confidentiality |
| Subjects: | |
| Online Access: | https://journalprivacyconfidentiality.org/index.php/jpc/article/view/870 |
| Summary: | 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.
|
|---|---|
| ISSN: | 2575-8527 |