Optimal schemes for discrete distribution estimation under local differential privacy
Min Ye, Alexander Barg · 2017
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 want to find the optimal privatization scheme which minimizes the expected estimation loss for the worst-case distribution. Two schemes in the literature provide order optimal performance in the high-privacy regime when ϵ is very close to 0, and in the low-privacy regime when 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 1 ≪ eϵ≪ k. More concretely, we prove that when 3.822metric and 30% under ℓ1metric over the existing schemes. We also prove a tight lower bound for the whole region eϵ≪ k, which implies that our schemes are order optimal in this regime.