Interactive Versus Non-Interactive Locally Differentially Private Estimation: Two Elbows for the Quadratic Functional

• Activity Number: 120 - Challenges and Recent Advances in Private Data Analysis
• Type: Topic-Contributed
• Date/Time: Monday, August 9, 2021 : 1:30 PM to 3:20 PM
• Sponsor: Section on Nonparametric Statistics
• Author(s): Lukas Steinberger*
• Companies: University of Vienna
• Keywords: local differential privacy; quadratic functional; non-parametric estimation; minimax rate of convergence

Abstract

In the locally differentially private estimation problems studied in the literature so far, 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 talk we show that for estimating the integrated square of a density, sequentially interactive locally differentially private 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 a smoothness of s=3/4, whereas in the sequentially interactive scenario the elbow is at s=1/2. This is markedly different from both, the case of direct observations, where the elbow is well known to be at s=1/4, as well as from the case where Laplace noise is added to the original data, where an elbow at s=9/4 is obtained.