Asymptotically optimal private estimation under mean square loss
By Min Ye, Alexander Barg. 2017
18 citations recorded by the source corpus.
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 $\epsilon$ measures the privacy level of a privatization scheme. In our previous work (arXiv:1702.00610), 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^{\epsilon} \ll k$ under both $\ell_2^2$ and $\ell_1$ loss. In other words, for a large number of samples the worst-case estimation loss of our scheme was shown to differ from the optimal value by at most a constant factor. In this paper, we eliminate this gap by showing asymptotic optimality of the proposed scheme and estimator under the $\ell_2^2$ (mean square) loss. More precisely, we show that for any $k$ and $\epsilon,$ the ratio between the worst-case estimation loss of our scheme and the optimal value approaches $1$ as the number of samples tends to infinity.
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Min Ye
- Alexander Barg
- Jayadev Acharya
- Shaowei Wang
- Liusheng Huang
- Yiwen Nie
- Xinyuan Zhang
- Pengzhan Wang
Citations in the corpus
- Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy (2017, background): “Subsequent Work In a follow-up work [16], we showed that for the (2)2 loss, the scheme proposed in this paper is not only order-optimal for the region e k, but also asymptotically optimal for every privacy level.”
- Local Differential Private Data Aggregation for Discrete Distribution Estimation (2019, background): “[39], [40] also induced k-subset mechanism in the context of categorical data distribution estimation, but lacks characterization on its mutual information bound/channel capacity.”