论文标题
私人查询通过约翰逊 - 林登斯特劳斯转型发布
Private Query Release via the Johnson-Lindenstrauss Transform
论文作者
论文摘要
我们介绍了一种基于约翰逊·林登斯特劳斯引理的统计查询的新方法，以释放具有不同隐私的统计查询。关键想法是将查询答案随机投影到一个较低的维空间，以便将任何两个矢量之间的距离之间的距离保留到添加误差。然后，我们使用简单的噪声机制回答投影的查询，并将答案提升到原始维度。使用这种方法，我们首次给出了纯粹的私人机制，具有最佳情况下最坏情况的样本复杂性，在平均错误下，以回答$ n $的宇宙的$ k $ Queries的工作量。作为其他应用，我们给出了第一个纯粹的私人有效机制，具有最佳样品复杂性，用于计算有界的高维分布的协方差，并用于回答2向边际查询。我们还表明，直到对错误的依赖性，我们机制的变体对于每个给定的查询工作负载几乎是最佳的。
We introduce a new method for releasing answers to statistical queries with differential privacy, based on the Johnson-Lindenstrauss lemma. The key idea is to randomly project the query answers to a lower dimensional space so that the distance between any two vectors of feasible query answers is preserved up to an additive error. Then we answer the projected queries using a simple noise-adding mechanism, and lift the answers up to the original dimension. Using this method, we give, for the first time, purely differentially private mechanisms with optimal worst case sample complexity under average error for answering a workload of $k$ queries over a universe of size $N$. As other applications, we give the first purely private efficient mechanisms with optimal sample complexity for computing the covariance of a bounded high-dimensional distribution, and for answering 2-way marginal queries. We also show that, up to the dependence on the error, a variant of our mechanism is nearly optimal for every given query workload.
