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.
翻译:在本地差异隐私的限制下,我们研究了平均估计$ell_2美元受限制的矢量的问题。虽然文献中存在各种算法,这些算法能够实现这一问题的无现成最佳率,但由于隐藏的常量不同(而且往往很大),这些算法的实际性能可能因隐藏的常量不同而有很大差异。在这项工作中,我们用最小的差异来调查协议设计问题。我们显示,具有优化参数的Priv Unite(Bhowmick等人,2018年)在本地私人随机器大家庭中达到了最佳差异。为了证明这一结果,我们建立了本地随机器的一些属性,并使用了对称性参数参数,使我们能够将最佳随机器写成某种线性程序的最佳优化。这些结构结果应该扩大到其他问题,然后让我们显示最佳随机器属于Priv Unite家族。我们还根据高斯分布开发了一个新的Priv Unif的新变量,这种配置更适合数学分析,并享有同样的最佳保证。这使我们能够在最精确的定值误率上确定一些有用的常值。