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

By Marco Gaboardi, Ryan M. Rogers, Or Sheffet. 2018

50 citations recorded by the source corpus.

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)) ).

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, methodology): “Our protocols use the private learner of [43] for parity functions, a protocol of [8] for answering all threshold queries, a protocol of [16] for heavy hitters, and a protocol of [31] for approximating a quantile.”
The Power of the Hybrid Model for Mean Estimation (2018, background): “However, DP mean estimation of distributions under both the TCM and LM has been studied since the models’ introductions [17, 21, 56], and continues to be actively studied to this day [2, 15, 18, 20, 22, 28, 29, 32, 37, 39–42].”
Differentially Private Confidence Intervals (2020, methodology): “Additionally, Gaboardi et al. [9] give a method for calculating conﬁdence intervals in the more restrictive local diﬀeren-tial privacy setting, in part using the same methods as Karwa and Vadhan.”
Lower Bounds for Locally Private Estimation via Communication Complexity (2019, background): “Most saliently, many of these results only apply in settings in which the privatization scheme is non-adaptive, that is, the scheme remains static for all data contributors except in 1-dimensional problems (Duchi et al., 2018; Ye and Barg, 2018; Gaboardi et al., 2018).”
Differentially Private Nonparametric Hypothesis Testing (2019, methodology): “[13] developed a private one sample t-test under the more restrictive local differential privacy model.”
Locally Differentially Private Data Collection and Analysis (2019, methodology): “Besides, existing local protocols under (ǫ, δ)-LDP [24, 31, 4] mainly focus on the task of mean esti3”
Locally Private Gaussian Estimation (2018, background): “[14] This Work Setting Accuracy α, Round Complexity T Accuracy α, Round Complexity T”
Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message (2021, methodology): “It is also naturally re-lated to mean estimation in distributed models of DP (e.g., Gaboardi et al., 2019).”