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.
翻译:我们给出了一种快速算法, 以最佳的方式将隐私保障分为不同的私人(DP)算法, 从而达到任意的准确性。 我们的方法基于隐私损失随机变量的概念, 以量化DP算法的隐私损失。 我们的算法需要运行的时间和记忆来接近由自己构成的 $k$ 的 DP 算法的隐私曲线 $\ tilde{O} (\\ sqrt{k}}) 。 这比Koskela et al. (202020) 之前的最佳方法有所改进, 前者需要$\ tilde_ Omega} (k ⁇ 1.5}) 运行时间。 我们通过精确计算 Abadi 等人 (2016) 的 DP- SGD 算法的隐私损失来展示我们的算法的效用, 并显示我们的算法比先前的工作加快了几级的隐私计算速度, 同时保持类似的精确性 。