Speaker: Angelika Rohde

 

Title: Estimating functionals under local differential privacy

 

Abstract: 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 classic notion of randomized response, the idea is that data owners randomize their true information locally and only release the perturbed data. We study the problem of estimating a functional of an unknown probability distribution in which the original iid sample is kept private even from the statistician via an local differential privacy constraint. Let Omega denote the modulus of continuity of the functional, with respect to total variation distance. For a large class of loss functions, we show that the privatized minimax risk is equivalent to the loss function applied to Omega(n^{-1/2}) within constants, under regularity conditions that are satisfied, in particular, if the functional is linear and the probability distribution is convex. Our results complement the theory developed by Domoho and Liu (1991) with the nowadays highly relevant case of privatized data. Somewhat surprisingly, the difficulty of the estimation problem in the private case is characterized by Omega, whereas, it is characterized by the Hellinger modulus of continuity if the original data are available. For linear functionals, 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 the last part of the talk, 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.