Pushing the Boundaries of Private, Large-Scale Query Answering
Pushing the Boundaries of Private, Large-Scale Query Answering
复制标题
DOI：
10.48550/arxiv.2302.04833
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Brendan Avent;A. Korolova
中科院分区：
文献类型：
--
作者：
Brendan Avent;A. Korolova
我们解决的问题，高效和有效地回答大量的敏感数据集上的查询，同时确保差分隐私（DP）。我们分别分析这个问题在两个不同的设置，接地我们的工作在一个国家的最先进的DP机制的大规模查询回答：放松自适应投影（RAP）机制。第一种设置是DP文献中的经典设置，其中所有查询都是预先为机制所知的。在这种情况下，我们确定RAP机制的原始分析中的挑战，然后通过增强的实施和分析来克服它们。然后，我们扩展的RAP机制的能力，能够回答一个更一般和更强大的类的查询（r-的k阈值）比以前考虑的。通过经验评估此类，我们发现该机制能够回答比之前的工作大几个数量级的查询集，并且速度快且实用性高。然后，我们定义了第二种设置，其动机是现实世界的考虑，其定义受到机器学习领域工作的启发。在这种新的设置中，一个机制只给出了部分知识的查询，将在未来提出的，它预计将回答这些未来提出的查询具有很高的效用。我们正式定义了这一设置以及如何衡量一个机制在其中的效用，然后我们全面地实证评估RAP机制在这一新设置中的效用。从这个评估中，我们发现，即使弱的部分知识的未来查询，将构成，该机制是能够有效地和有效地回答任意查询提出的未来。两者合计，从这两个设置的结果推进差分私人大规模查询回答的最新技术水平。
We address the problem of efficiently and effectively answering large numbers of queries on a sensitive dataset while ensuring differential privacy (DP). We separately analyze this problem in two distinct settings, grounding our work in a state-of-the-art DP mechanism for large-scale query answering: the Relaxed Adaptive Projection (RAP) mechanism. The first setting is a classic setting in DP literature where all queries are known to the mechanism in advance. Within this setting, we identify challenges in the RAP mechanism's original analysis, then overcome them with an enhanced implementation and analysis. We then extend the capabilities of the RAP mechanism to be able to answer a more general and powerful class of queries (r-of-k thresholds) than previously considered. Empirically evaluating this class, we find that the mechanism is able to answer orders of magnitude larger sets of queries than prior works, and does so quickly and with high utility. We then define a second setting motivated by real-world considerations and whose definition is inspired by work in the field of machine learning. In this new setting, a mechanism is only given partial knowledge of queries that will be posed in the future, and it is expected to answer these future-posed queries with high utility. We formally define this setting and how to measure a mechanism's utility within it. We then comprehensively empirically evaluate the RAP mechanism's utility within this new setting. From this evaluation, we find that even with weak partial knowledge of the future queries that will be posed, the mechanism is able to efficiently and effectively answer arbitrary queries posed in the future. Taken together, the results from these two settings advance the state of the art on differentially private large-scale query answering.