Locally Private Gaussian Estimation

By Matthew Joseph, Janardhan Kulkarni, Jieming Mao, Zhiwei Steven Wu. 2018

39 citations recorded by the source corpus.

We study a basic private estimation problem: each of $n$ users draws a single i.i.d. sample from an unknown Gaussian distribution, and the goal is to estimate the mean of this Gaussian distribution while satisfying local differential privacy for each user. Informally, local differential privacy requires that each data point is individually and independently privatized before it is passed to a learning algorithm. Locally private Gaussian estimation is therefore difficult because the data domain is unbounded: users may draw arbitrarily different inputs, but local differential privacy nonetheless mandates that different users have (worst-case) similar privatized output distributions. We provide both adaptive two-round solutions and nonadaptive one-round solutions for locally private Gaussian estimation. We then partially match these upper bounds with an information-theoretic lower bound. This lower bound shows that our accuracy guarantees are tight up to logarithmic factors for all sequentially interactive $(\varepsilon,\delta)$-locally private protocols.

Subfields: Artificial Intelligence, Computer Science Applications

How researchers see this paper

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

In Artificial Intelligence

In Computer Science Applications

Citations in the corpus

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].”
Unified lower bounds for interactive high-dimensional estimation under information constraints (2020, background): “Turning to local privacy, [24] provide upper bounds (as well as some partial lower bounds) for one-dimensional Gaussian mean estimation under LDP under the l2 loss, in the sequentially interactive model.”
Private Hypothesis Selection (2019, background): “There has also been a great deal of work on distribution learning in the local model of diﬀerential privacy [DJW13, WHW + 16, KBR16, ASZ19, DR18, JKMW18, YB18, GRS19].”
Differentially Private Algorithms for Learning Mixtures of Separated Gaussians (2019, background): “There has also been a great deal of work on distribution learning in the local model of differential privacy [29, 65, 45, 2, 30, 44, 67, 37].”
Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation (2019, unknown): “We limit our discussion and study to the central model of differential privacy, though there has also been much work on mean estimation in the local model [21, 19, 11].”
The Role of Interactivity in Local Differential Privacy (2019, background): “[22] and Duchi and Rogers [14] to the fully interactive setting.”
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”
Lower Bounds for Locally Private Estimation via Communication Complexity (2019, background): “(For the one dimensional case, see also [24].”
Private Mean Estimation of Heavy-Tailed Distributions (2020, background): “There has also been some work on locally private mean estimation in the Gaussian case [GRS19, JKMW19].”