Local differential privacy has recently received increasing attention from the statistics community as a valuable tool to protect the privacy of individual data owners without the need of a trusted third party. Similar to the classical notion of randomized response, the idea is that data owners randomize their true information locally and only release the perturbed data. Many different protocols for such local perturbation procedures can be designed. In most estimation problems studied in the literature so far, however, no significant difference in terms of minimax risk between purely non-interactive protocols and protocols that allow for some amount of interaction between individual data providers could be observed. In this paper we show that for estimating the integrated square of a density, sequentially interactive procedures improve substantially over the best possible non-interactive procedure in terms of minimax rate of estimation. In particular, in the non-interactive scenario we identify an elbow in the minimax rate at $s=\frac34$, whereas in the sequentially interactive scenario the elbow is at $s=\frac12$. This is markedly different from both, the case of direct observations, where the elbow is well known to be at $s=\frac14$, as well as from the case where Laplace noise is added to the original data, where an elbow at $s= \frac94$ is obtained. We also provide adaptive estimators that achieve the optimal rate up to log-factors, we draw connections to non-parametric goodness-of-fit testing and estimation of more general integral functionals and conduct a series of numerical experiments. The fact that a particular locally differentially private, but interactive, mechanism improves over the simple non-interactive one is also of great importance for practical implementations of local differential privacy.
翻译:最近,统计界日益关注当地差异隐私,认为这是保护个人数据拥有者隐私的宝贵工具,不需要信任第三方。类似于随机响应的典型概念,其理念是数据所有者在当地随机随机地发布其真实信息,而只发布受扰动的数据。对于这种本地扰动程序,可以设计许多不同的协议。在迄今为止研究的文献中,大多数小问题在纯非互动协议和协议之间没有明显区别,这些协议允许个人数据提供者进行某种程度的互动。在本文中,我们表明,在估算一个密度的综合正方形时,按顺序互动程序大大改进了可能的最佳的非互动程序,在估算的迷你速率方面,只有发布数据。在非互动情况下,我们确定小通速率的肘值为$z ⁇ frac34美元,而在依次的互动假设中,肘值为$sfrexc12美元。这与直接观测明显不同,在估算一个事实中,手肘是已知的简单正弦数,14的按次互动程序大大改进了最佳的不互动性程序。我们从最初的汇率到最接近的汇率的汇率,也提供了最优的汇率。