Locally Private Mean Estimation: $Z$-test and Tight Confidence Intervals

[edit]

Marco Gaboardi, Ryan Rogers, Or Sheffet ;
Proceedings of Machine Learning Research, PMLR 89:2545-2554, 2019.

Abstract

This work provides tight upper- and lower-bounds for the problem of mean estimation under differential privacy in the local-model, when the input is composed of $n$ i.i.d. drawn samples from a Gaussian. Our algorithms result in a $(1-\beta)$-confidence interval for the underlying distribution’s mean of length $O(\sigma *sqrt(log(n/beta)log(1/\beta))/(\epsilon*sqrt(n))$. In addition, our algorithms leverage on binary search using local differential privacy for quantile estimation, a result which may be of separate interest. Moreover, our algorithms have a matching lower-bound, where we prove that any one-shot (each individual is presented with a single query) local differentially private algorithm must return an interval of length $\Omega(\sigma*sqrt(\log(1/\beta))/(\epsilon*sqrt(n)))$.

Related Material