Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacy

We consider the minimax estimation problem of a discrete distribution with support size k under 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. For a given ε, we consider the problem of constructing optimal privatization schemes with ε-privacy level, i.e., schemes that minimize the expected estimation loss for the worst-case distribution. Two schemes in the literature provide order optimal performance in the high privacy regime where ε is very close to 0, and in the low privacy regime where eε≈ k, respectively. In this paper, we propose a new family of schemes which substantially improve the performance of the existing schemes in the medium privacy regime when 1ll eε ll k. More concretely, we prove that when 3.8 < ε <ln(k/9) , our schemes reduce the expected estimation loss by 50% under ℓ22 metric and by 30% under ℓ1 metric over the existing schemes. We also prove a lower bound for the region eε ll k, which implies that our schemes are order optimal in this regime.