# Optimal locally private estimation under ℓp loss for 1≤ p≤ 2

arXiv: https://arxiv.org/abs/1810.07283 · HTML: https://mlsanity.com/paper/1810.07283/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2018.

## Built on by (most cited first, 1 of 1)

- [Private Frequency Estimation via Projective Geometry](https://mlsanity.com/paper/2203.00194/) (2022)

## Abstract (arXiv)

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ε ll k under both ℓ22 (mean square) and ℓ1 loss. In this paper, we sharpen this result by showing asymptotic optimality of the proposed scheme under the ℓpp 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 ℓpp 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 ℓpp, p≥ 1.