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

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 normal distribution with variance σ. Our algorithms result in a (1-β)-confidence interval for the underlying distribution's mean μ of length tilde Oleft( fracσ √log(frac 1 β)ε√ n right). In addition, our algorithms leverage binary search using local differential privacy for quantile estimation, a result which may be of separate interest. Moreover, we prove a matching lower-bound (up to poly-log factors), showing that any one-shot (each individual is presented with a single query) local differentially private algorithm must return an interval of length Omegaleft( fracσ√log(1/β)ε√nright).