INTERACTIVE VERSUS NONINTERACTIVE LOCALLY DIFFERENTIALLY PRIVATE ESTIMATION: TWO ELBOWS FOR THE QUADRATIC FUNCTIONAL

• 成果类型: Article
• 署名作者: Butucea, Cristina; Rohde, Angelika; Steinberger, Lukas
• 署名单位: Institut Polytechnique de Paris; ENSAE Paris; University of Freiburg; University of Vienna
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/22-AOS2254
• 发表日期: 2023
• 页码: 464-486
• 关键词: Adaptive Estimation; CONVERGENCE; inequalities; rates; ORDER; sharp

摘要

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 noninteractive 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 noninteractive procedure in terms of min-imax rate of estimation.In particular, in the noninteractive scenario we identify an elbow in the minimax rate at s = 34, whereas in the sequentially interactive scenario the elbow is at s = 21. This is markedly different from both, the case of direct observations, where the elbow is well known to be at s = 41, as well as from the case where Laplace noise is added to the original data, where an elbow at s = 94 is obtained.We also provide adaptive estimators that achieve the optimal rate up to log-factors, we draw connections to nonparametric 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 pri-vate, but interactive, mechanism improves over the simple noninteractive one is also of great importance for practical implementations of local differential privacy.