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

Marco Gaboardi, Ryan Rogers, Or Sheffet
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, 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)))$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-gaboardi19a, title = {Locally Private Mean Estimation: $Z$-test and Tight Confidence Intervals}, author = {Gaboardi, Marco and Rogers, Ryan and Sheffet, Or}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {2545--2554}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/gaboardi19a/gaboardi19a.pdf}, url = {https://proceedings.mlr.press/v89/gaboardi19a.html}, 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)))$.} }
Endnote
%0 Conference Paper %T Locally Private Mean Estimation: $Z$-test and Tight Confidence Intervals %A Marco Gaboardi %A Ryan Rogers %A Or Sheffet %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-gaboardi19a %I PMLR %P 2545--2554 %U https://proceedings.mlr.press/v89/gaboardi19a.html %V 89 %X 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)))$.
APA
Gaboardi, M., Rogers, R. & Sheffet, O.. (2019). Locally Private Mean Estimation: $Z$-test and Tight Confidence Intervals. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:2545-2554 Available from https://proceedings.mlr.press/v89/gaboardi19a.html.

Related Material