Numerical Composition of Differential Privacy
Numerical Composition of Differential Privacy
复制标题
DOI：
10.29012/jpc.870
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Sivakanth Gopi;Y. Lee;Lukas Wutschitz
中科院分区：
文献类型：
--
作者：
Sivakanth Gopi;Y. Lee;Lukas Wutschitz
我们给出了一个快速算法，以最佳组合的隐私保证差分隐私（DP）算法的任意精度。该方法基于隐私损失随机变量的概念来量化DP算法的隐私损失，算法逼近一个由自身组成的DP算法的隐私曲线$k$次所需的运行时间和内存为$\tilde{O}（\sqrt{k}）$。这改进了Kobia等人的最佳先验方法。（2021）需要$\tilde{\Omega}（k^{1.5}）$运行时间。我们通过准确计算Abadi et al.（2016）的DP-SGD算法的隐私损失来证明我们算法的实用性，并表明我们的算法与之前的工作相比将隐私计算速度提高了几个数量级，同时保持了类似的准确性。
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.