论文标题
用广义高斯机制私下回答计数查询
Privately Answering Counting Queries with Generalized Gaussian Mechanisms
论文作者
论文摘要
我们考虑回答$ k $计数（即灵敏度1）的问题，以查询具有$（ε，δ）$差异隐私的数据库。我们提供了一种机制，即如果查询的真实答案是向量$ d $，则用$ \ ell_ \ ell_ \ infty $ -Error保证答案$ \ tilde {d} $答案： $ \ MATHCAL {E} \ left [|| \ tilde {d} -d || _ \ infty \ right] = o \ left（\ frac {\ frac {\ sqrt {k \ log \ log \ log \ log log k log k \ log k \ yright（1/Δ）}} $右）。 这将$ \ ell_ \ elfty $ -Error上最著名的上限和下限之间的乘法差距从$ o（\ sqrt {\ log \ log \ log k}）$减少到$ o（\ sqrt {\ sqrt {\ log log \ log \ log \ log \ log k}）$。我们的主要技术贡献是对以下形式的机制的分析，用于回答计数查询：示例$ x $从a \ textit {generalized Gaussian}，即与$ \ exp（ - （ - （|| x || x || _p/σ）^p）$和输出$ \ \ \ tilde {dilde {D} $ X $ X $。这个机制家族提供了$ \ ell_1 $和$ \ ell_ \ infty $ -Error保证之间的权衡，并且可能具有独立的利益。对于$ p = o（\ log \ log k）$，此机制已经与以前最佳的$ \ ell_ \ infty $ -error绑定相匹配。我们通过用稀疏的向量机制编写$ p = o（\ log \ log \ log k）$的此机制来得出我们的主要结果，从而概括了Steinke和Ullman的技术。
We consider the problem of answering $k$ counting (i.e. sensitivity-1) queries about a database with $(ε, δ)$-differential privacy. We give a mechanism such that if the true answers to the queries are the vector $d$, the mechanism outputs answers $\tilde{d}$ with the $\ell_\infty$-error guarantee: $$\mathcal{E}\left[||\tilde{d} - d||_\infty\right] = O\left(\frac{\sqrt{k \log \log \log k \log(1/δ)}}ε\right).$$ This reduces the multiplicative gap between the best known upper and lower bounds on $\ell_\infty$-error from $O(\sqrt{\log \log k})$ to $O(\sqrt{\log \log \log k})$. Our main technical contribution is an analysis of the family of mechanisms of the following form for answering counting queries: Sample $x$ from a \textit{Generalized Gaussian}, i.e. with probability proportional to $\exp(-(||x||_p/σ)^p)$, and output $\tilde{d} = d + x$. This family of mechanisms offers a tradeoff between $\ell_1$ and $\ell_\infty$-error guarantees and may be of independent interest. For $p = O(\log \log k)$, this mechanism already matches the previous best known $\ell_\infty$-error bound. We arrive at our main result by composing this mechanism for $p = O(\log \log \log k)$ with the sparse vector mechanism, generalizing a technique of Steinke and Ullman.
