EFFICIENCY IN LOCAL DIFFERENTIAL PRIVACY

We develop a theory of asymptotic efficiency in regular parametric models when data confidentiality is ensured by local differential privacy (LDP). Even though efficient parameter estimation is a classical and well-studied problem in mathematical statistics, it leads to several nontrivial obstacles that need to be tackled when dealing with the LDP case. Starting from a regular parametric model P = (P theta)theta E Theta, Theta C Rp, for the i.i.d. unobserved sensitive data X 1 , ...,Xn, we establish local asymptotic mixed normality (along subsequences) of the model Q(n)P= (Q(n)P n ) theta theta E Theta generating the sanitized observations Z1,... , Z n , where Q (n) is an arbitrary sequence of sequentially interactive privacy mechanisms. This result readily implies convolution and local asymptotic minimax theorems. In case p = 1, the optimal asymptotic variance is found to be the inverse of the supremal Fisher information supQEQ alpha I theta(QP) E R, where the supremum runs over all alpha-differentially private (marginal) Markov kernels. We present an algorithm for finding a (nearly) optimal privacy mechanism Q and an estimator theta n(Z1, ..., Zn) based on the corresponding sanitized data that achieves this asymptotically optimal variance.