| Autor: |
Sivakanth Gopi, Yin Tat Lee, Lukas Wutschitz |
| Jazyk: |
angličtina |
| Rok vydání: |
2024 |
| Předmět: |
|
| Zdroj: |
The Journal of Privacy and Confidentiality, Vol 14, Iss 1 (2024) |
| Druh dokumentu: |
article |
| ISSN: |
2575-8527 |
| DOI: |
10.29012/jpc.870 |
| Popis: |
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. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
