Title: 

Geometrizing rates of convergence under local differential privacy



Abstract:

One of the many new challenges for statistical inference in the information age
is the increasing concern of data privacy protection. A particularly fruitful
approach to data protection is the concept of `local differential privacy'
(Dwork et al. (2), Evfimievski et al. (3)). Here, the idea is that each data 
providing individual releases only a randomly perturbed version of its original
data. Such a randomization (or privatization) mechanism is said to provide
$\alpha$-local differential privacy if its log-likelihood-ratio under any pair
of hypothetical true data values is uniformly bounded by some pre-specified
privacy level $\alpha$. This privacy protection protocol has already found
its way into applications and is prominently used, e.g., by Apple Inc. (1).

In this talk, we discuss the impact of an $\alpha$-local differential privacy
guarantee on the quality of statistical inference, in a minimax framework. In 
this setup, the objective is not only to come up with an optimal estimation
procedure that efficiently recovers information from the privatized
observations, but also to devise a privatization mechanism that best
facilitates subsequent estimation while respecting the required privacy
provisions. In the context of estimating linear functionals of the unknown
true data generating distribution, we characterize the minimax rate of private
estimation and provide a general construction for minimax rate optimal
privatization mechanisms. Our analysis also allows for a quantification of the
price in statistical accuracy that has to be paid for achieving
$\alpha$-local differential privacy. This price appears to be highly problem
dependent.



References:

Apple Inc. privacy policy.
https://images.apple.com/privacy/docs/Differential_Privacy_Overview.pdf

Dwork, C., F. McSherry, K. Nissim, and A. Smith (2006). Calibrating noise to
sensitivity in private data analysis. In S. Halevi and T. Rabin (Eds.), Theory
of Cryptography, Lecture Notes in Computer Science, pp. 265--284. Springer.

Evfimievski, A., J.~Gehrke, and R.~Srikant (2003). Limiting privacy breaches in
privacy preserving data mining. In Proceedings of the twenty-second ACM
SIGMOD-SIGACT-SIGART symposium on Principles of database systems,
pp. 211--222. ACM.