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 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. (2020) 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.

By admin