论文标题
从指数机制，稀疏矢量，嘈杂的最大和相关算法中的免费差距估计值
Free Gap Estimates from the Exponential Mechanism, Sparse Vector, Noisy Max and Related Algorithms
论文作者
论文摘要
私人选择算法，例如指数机制，嘈杂的最大和稀疏向量，用于从一组候选人中选择项目（例如具有大答案的查询），同时控制基础数据中的隐私泄漏。这种算法是更复杂的差异私有算法的构建基础。在本文中，我们表明，这些算法可以免费发布与所选项目和其他候选人之间差距有关的其他信息（即，不需要额外的隐私费用）。此免费差距信息可以提高某些随访计数查询的准确性高达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.
