Free gap estimates from the exponential mechanism, sparse vector, noisy max and related algorithms
Free gap estimates from the exponential mechanism, sparse vector, noisy max and related algorithms
复制标题
来自指数机制、稀疏向量、噪声最大值和相关算法的自由间隙估计
DOI：
10.1007/s00778-022-00728-2
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Kifer, Daniel
中科院分区：
文献类型：
--
作者：
Ding, Zeyu;Wang, Yuxin;Xiao, Yingtai;Wang, Guanhong;Zhang, Danfeng;Kifer, Daniel
私有选择算法，如指数机制，噪声最大和稀疏向量，用于从一组候选项中选择项目（如具有大答案的查询），同时控制底层数据中的隐私泄漏。这样的算法充当更复杂的差异隐私算法的构建块。在本文中，我们表明，这些算法可以释放额外的信息有关的差距之间的选定项目和其他候选人免费（即，没有额外的隐私成本）。这种自由间隙信息可以将某些后续计数查询的准确性提高高达66%。我们从这些算法的仔细隐私分析得到这些结果。基于此分析，我们进一步提出了新的混合算法，可以动态地节省额外的隐私预算。
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.
影响因子：
1.8
作者：
Albarghouthi, Aws;Hsu, Justin
通讯作者：
Hsu, Justin