论文标题
用于使随机近似算法差异私有的添加噪声机制
Additive Noise Mechanisms for Making Randomized Approximation Algorithms Differentially Private
论文作者
论文摘要
可用数据量的指数增加使得利用它们而不违反用户的隐私是计算机科学的基本问题之一。这个问题已在差异隐私的框架下进行了彻底调查。但是，大多数文献都没有集中在数据量如此之大的设置上，以至于我们甚至无法在非私人设置中计算确切的答案（例如在流设置，sublinear-time设置等）中。这通常可以使在实践中使用差异隐私。 在本文中，我们展示了一种使蒙特卡洛随机近似算法差异化的一般方法。我们只需要假设近似算法的错误$ r $足够集中在$ 0 $左右（例如\ $ \ Mathbb {e} [| r |] $是有限的），并且近似函数的函数具有小的全局敏感性$δ$。具体而言，如果我们具有具有足够浓缩误差的随机近似算法，该误差具有时间/空间/查询复杂性$ t（n，ρ）$，$ρ$是一个准确性参数，我们可以说出具有相同准确性和复杂性$ t（n，θ（θ（）$ $ - $ - $ - differfertial的算法。
The exponential increase in the amount of available data makes taking advantage of them without violating users' privacy one of the fundamental problems of computer science. This question has been investigated thoroughly under the framework of differential privacy. However, most of the literature has not focused on settings where the amount of data is so large that we are not even able to compute the exact answer in the non-private setting (such as in the streaming setting, sublinear-time setting, etc.). This can often make the use of differential privacy unfeasible in practice. In this paper, we show a general approach for making Monte-Carlo randomized approximation algorithms differentially private. We only need to assume the error $R$ of the approximation algorithm is sufficiently concentrated around $0$ (e.g.\ $\mathbb{E}[|R|]$ is bounded) and that the function being approximated has a small global sensitivity $Δ$. Specifically, if we have a randomized approximation algorithm with sufficiently concentrated error which has time/space/query complexity $T(n,ρ)$ with $ρ$ being an accuracy parameter, we can generally speaking get an algorithm with the same accuracy and complexity $T(n,Θ(ερ))$ that is $ε$-differentially private.
