Private selection algorithms, such as the Exponential Mechanism, Noisy Max and Sparse Vector, are used to select items (such as queries with large answers) from a set of candidates, while controlling privacy leakage in the underlying data. Such algorithms serve as building blocks for more complex differentially private algorithms. In this paper we show that these algorithms can release additional information related to the gaps between the selected items and the other candidates for free (i.e., at no additional privacy cost). This free gap information can improve the accuracy of certain follow-up counting queries by up to 66%. We obtain these results from a careful privacy analysis of these algorithms. Based on this analysis, we further propose novel hybrid algorithms that can dynamically save additional privacy budget.


翻译:个人选择算法,如指数机制、 Noisy Max 和 Sparse 矢量器等私人选择算法,用于从一组候选人中选择项目(例如询问并有大量答案),同时控制基础数据中的隐私泄漏。这些算法是更复杂的不同私人算法的构件。在本文中,我们显示这些算法可以免费(即不增加隐私费用)发布与选定项目与其他候选项目之间差距相关的额外信息。这种免费的空白信息可以提高某些后续计数查询的准确性,达到66%。我们从对这些算法的仔细隐私分析中获得这些结果。基于这一分析,我们进一步提议新的混合算法,可以动态地节省额外的隐私预算。

0
下载
关闭预览

相关内容

《计算机信息》杂志发表高质量的论文,扩大了运筹学和计算的范围,寻求有关理论、方法、实验、系统和应用方面的原创研究论文、新颖的调查和教程论文,以及描述新的和有用的软件工具的论文。官网链接:https://pubsonline.informs.org/journal/ijoc
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
已删除
将门创投
10+阅读 · 2018年5月2日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
LibRec 精选:推荐系统9个必备数据集
LibRec智能推荐
6+阅读 · 2018年3月7日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Arxiv
0+阅读 · 2021年1月21日
Arxiv
0+阅读 · 2021年1月20日
VIP会员
相关VIP内容
相关资讯
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
已删除
将门创投
10+阅读 · 2018年5月2日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
LibRec 精选:推荐系统9个必备数据集
LibRec智能推荐
6+阅读 · 2018年3月7日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Top
微信扫码咨询专知VIP会员