Event
CCSP Seminar: Alexander Barg, "Optimal locally private estimation under $\ell_p$ loss for $1 \leq p"
Thursday, February 28, 2019
5:00 p.m.-6:30 p.m.
2168 A.V. Williams Bldg.
Ajaykrishnan Nageswaran
301 405 3661
ajayk@umd.edu
http://www.ece.umd.edu/seminars/ccsp/
Communication, Control and Signal Processing Seminar
Optimal locally private estimation under $\ell_p$ loss for $1 \leq p \leq 2$
Professor Alexander Barg
Electrical and Computer Engineering and
the Institute for Systems Research
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 $\epsilon$ measures the privacy level of a privatization scheme. Recently, 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$ (mean square) and $\ell_1$ loss.
In this talk, we sharpen this result by showing asymptotic optimality of the proposed scheme under the $\ell_p$ loss for all $1 \leq p \leq 2$. More precisely, we show that for any $p \in [1,2]$ and any $k$ and $\epsilon$, the ratio between the worst-case $\ell_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 $\ell_p, p \geq 1$. Joint work with Min Ye (Princeton).
