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 算法的隐私损失来展示我们的算法的效用, 并显示我们的算法比先前的工作加快了几级的隐私计算速度, 同时保持类似的精确性 。

0
下载
关闭预览

相关内容

机器学习系统设计系统评估标准
专知会员服务
25+阅读 · 2021年4月2日
【AAAI2021】记忆门控循环网络
专知会员服务
48+阅读 · 2020年12月28日
专知会员服务
52+阅读 · 2020年9月7日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【干货书】数值计算C编程,319页pdf,Numerical C
专知会员服务
67+阅读 · 2020年4月7日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
经典回顾 | Collaborative Metric Learning
机器学习与推荐算法
6+阅读 · 2020年9月18日
已删除
将门创投
11+阅读 · 2019年8月13日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年7月28日
VIP会员
相关VIP内容
专知会员服务
25+阅读 · 2021年4月2日
【AAAI2021】记忆门控循环网络
专知会员服务
48+阅读 · 2020年12月28日
专知会员服务
52+阅读 · 2020年9月7日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【干货书】数值计算C编程,319页pdf,Numerical C
专知会员服务
67+阅读 · 2020年4月7日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
相关资讯
经典回顾 | Collaborative Metric Learning
机器学习与推荐算法
6+阅读 · 2020年9月18日
已删除
将门创投
11+阅读 · 2019年8月13日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
9+阅读 · 2018年12月28日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员