The Sparse Vector Technique, Revisited
The Sparse Vector Technique, Revisited
复制标题
重新审视稀疏矢量技术
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Uri Stemmer
中科院分区：
文献类型：
--
作者：
Haim Kaplan;Y. Mansour;Uri Stemmer
我们重新审视了差异隐私文献中最基本和最广泛的技术之一 - 稀疏向量技术[Dwork等，Stoc 2009]。宽松地说，这项技术使我们能够私下测试给定查询的值是否接近我们期望的（W.R.T.输入数据库），只要我们的值是无限数量的查询，只要它们的值是确实接近我们的期望。在第一次不是这种情况之后，该过程停止了。我们对稀疏向量技术进行了修改，该技术允许进行更微调的隐私分析。结果，在某些情况下，即使在查询价值不符合我们的期望之后，我们仍可以继续测试查询的过程。
我们通过将其应用于较量的热门人物问题来证明我们的技术：在每个时间步骤中，每个n个用户都会获得新的输入，而任务是私下确定所有当前的重型击球手。也就是说，按时第一步，目标是识别所有数据元素X，以使许多用户具有X作为当前输入。我们为此问题提供了一种算法，可以改善使用现有技术可以获得的错误。具体而言，我们算法的错误取决于单人用户将重击作为输入的最大次数，而不是存在重击的总数。
We revisit one of the most basic and widely applicable techniques in the literature of differential privacy - the sparse vector technique [Dwork et al., STOC 2009]. Loosely speaking, this technique allows us to privately test whether the value of a given query is close to what we expect it would be (w.r.t. the input database), where we are allowed to test an unbounded number of queries as long as their value is indeed close to what we expected. After the first time in which this is not the case, the process halts. We present a modification to the sparse vector technique that allows for a more fine-tuned privacy analysis. As a result, in some cases we are able to continue with the process of testing queries even after the first time in which the value of the query did not meet our expectations.
We demonstrate our technique by applying it to the shifting-heavy-hitters problem: On every time step, each of n users gets a new input, and the task is to privately identify all the current heavy-hitters. That is, on time step i, the goal is to identify all data elements x such that many of the users have x as their current input. We present an algorithm for this problem with improved error guarantees over what can be obtained using existing techniques. Specifically, the error of our algorithm depends on the maximal number of times that a singe user holds a heavy-hitter as input, rather than the total number of times in which a heavy-hitter exists.
DOI：
10.1145/2688073.2688100
发表时间：
2014-02
期刊：
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science
影响因子：
--
作者：
Avrim Blum;Jamie Morgenstern;Ankit Sharma;Adam D. Smith
通讯作者：
Avrim Blum;Jamie Morgenstern;Ankit Sharma;Adam D. Smith
在不可知 PAC 模型中私下回答分类查询
DOI：
--
发表时间：
2020
期刊：
The 31st International Conference on Algorithmic Learning Theory
影响因子：
--
作者：
Nandi, Anupama;Bassily, Raef
通讯作者：
Bassily, Raef