Free Gap Information from the Differentially Private Sparse Vector and Noisy Max Mechanisms
Free Gap Information from the Differentially Private Sparse Vector and Noisy Max Mechanisms
复制标题
DOI：
10.14778/3368289.3368295
复制
发表时间：
2019-11-01
影响因子：
2.5
通讯作者：
Kifer, Daniel
中科院分区：
文献类型：
--
作者：
Ding, Zeyu;Wang, Yuxin;Kifer, Daniel
嘈杂的最大值和稀疏向量是差异隐私的选择算法，并充当更复杂的算法的基础。在本文中，我们表明，这两种算法都可以免费发布其他信息（即，以无额外的隐私费用）。嘈杂的最大值用于返回一组查询之间的近似最大化器。我们证明它也可以免费释放近似最大化器和亚军之间的嘈杂差距。此免费信息可以提高某些后续计数查询的准确性高达50％。稀疏向量用于返回一组大约大于固定阈值的查询。我们表明，它可以自适应地控制其隐私预算（对可能比阈值大得多的查询预算使用更少的预算），以增加其可以处理的查询量。这些结果来自仔细的隐私分析。
Noisy Max and Sparse Vector are selection algorithms for differential privacy and serve as building blocks for more complex algorithms. In this paper we show that both algorithms can release additional information for free (i.e., at no additional privacy cost). Noisy Max is used to return the approximate maximizer among a set of queries. We show that it can also release for free the noisy gap between the approximate maximizer and runner-up. This free information can improve the accuracy of certain subsequent counting queries by up to 50%. Sparse Vector is used to return a set of queries that are approximately larger than a fixed threshold. We show that it can adaptively control its privacy budget (use less budget for queries that are likely to be much larger than the threshold) in order to increase the amount of queries it can process. These results follow from a careful privacy analysis.