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%。我们从对这些算法的仔细隐私分析中获得这些结果。基于这一分析,我们进一步提议新的混合算法,可以动态地节省额外的隐私预算。