Optimal locally private estimation under _p loss for 1 p 2

Abstract

We consider the minimax estimation problem of a discrete distribution with support size k under locally differential privacy constraints. A privatization scheme is applied to each raw sample independently, and we need to estimate the distribution of the raw samples from the privatized samples. A positive number measures the privacy level of a privatization scheme. In our previous work (IEEE Trans. Inform. Theory, 2018), we proposed a family of new privatization schemes and the corresponding estimator. We also proved that our scheme and estimator are order optimal in the regime e^ k under both _2^2 (mean square) and _1 loss. In this paper, we sharpen this result by showing asymptotic optimality of the proposed scheme under the _p^p loss for all 1 p 2. More precisely, we show that for any p[1,2] and any k and , the ratio between the worst-case _p^p estimation loss of our scheme and the optimal value approaches 1 as the number of samples tends to infinity. The lower bound on the minimax risk of private estimation that we establish as a part of the proof is valid for any loss function _p^p, p 1.

Tasks

Reproductions