论文标题
在当地差异隐私下进行平均估计的最佳算法
Optimal Algorithms for Mean Estimation under Local Differential Privacy
论文作者
论文摘要
我们研究了$ \ ell_2 $结合的向量的平均估计的问题，该矢量受到当地差异隐私的约束。尽管文献具有多种算法，这些算法可以实现此问题的渐近最佳速率，但由于隐藏的常数（并且通常很大），实践中这些算法的性能可能很大。在这项工作中，我们研究了以最小差异设计协议的问题。我们表明，具有优化参数的Privunit（Bhowmick等人，2018年）实现了大型本地私人随机化家族的最佳差异。为了证明这一结果，我们建立了局部随机化器的一些属性，并使用对称参数，使我们能够将最佳随机器写为特定线性程序的优化器。这些结构性结果应扩展到其他问题，然后允许我们证明最佳随机器属于私人家庭。 我们还基于高斯分布开发了一种新的私有化变体，该变体更适合数学分析，并具有相同的最佳保证。这使我们能够在最佳误差的确切常数以及数值估计这些常数上建立几个有用的属性。
We study the problem of mean estimation of $\ell_2$-bounded vectors under the constraint of local differential privacy. While the literature has a variety of algorithms that achieve the asymptotically optimal rates for this problem, the performance of these algorithms in practice can vary significantly due to varying (and often large) hidden constants. In this work, we investigate the question of designing the protocol with the smallest variance. We show that PrivUnit (Bhowmick et al. 2018) with optimized parameters achieves the optimal variance among a large family of locally private randomizers. To prove this result, we establish some properties of local randomizers, and use symmetrization arguments that allow us to write the optimal randomizer as the optimizer of a certain linear program. These structural results, which should extend to other problems, then allow us to show that the optimal randomizer belongs to the PrivUnit family. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees. This allows us to establish several useful properties on the exact constants of the optimal error as well as to numerically estimate these constants.
