Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation

By John C. Duchi, Martin J. Wainwright, Michael I. Jordan. 2013

158 citations recorded by the source corpus.

We provide a detailed study of the estimation of probability distributions---discrete and continuous---in a stringent setting in which data is kept private even from the statistician. We give sharp minimax rates of convergence for estimation in these locally private settings, exhibiting fundamental tradeoffs between privacy and convergence rate, as well as providing tools to allow movement along the privacy-statistical efficiency continuum. One of the consequences of our results is that Warner's classical work on randomized response is an optimal way to perform survey sampling while maintaining privacy of the respondents.

Subfields: Artificial Intelligence, Computer Science Applications, Statistics and Probability, Privacy & Security

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

In Statistics and Probability

In Privacy & Security

Citations in the corpus

Collecting Telemetry Data Privately (2017, methodology): “The single-round LDP mechanism in Duchi et al. [9] sends out a 0-1 random response for each bucket: send 1 with probability eε/2/(eε/2 + 1) if the counter value is in this bucket, with probability 1/(eε/2 + 1) if not.”
Distributed Statistical Machine Learning in Adversarial Settings (2017, background): “Although a variety of privacypreserving solutions have been developed [4, 11], privacy breaches still occur frequently, with recent examples including iCloud leaks of celebrity photos [3] and PRISM surveillance program [2].”
Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy (2017, background): “Existing Results The following two privatization schemes are the most well-known in the literature: the k-ary Randomized Aggregatable Privacy-Preserving Ordinal Response (k-RAPPOR) scheme [8], [9], and the k-ary Randomized Response (k-RR) scheme [10]–[12].”
Discrete Distribution Estimation under Local Privacy (2016, background): “A conditional distribution Q is said to be ε -locally differentially private if for all x , x (cid:48) ∈ X and all E ⊂ Y , we have that where et al., 2013a) .”
Collecting and Analyzing Multidimensional Data with Local Differential Privacy (2019, background): “Various data analytics and machine learning problems have been studied under LDP, such as probability distribution estimation [15], [23], [30], [32], [42], heavy hitter discovery [4], [7], [33], [39], frequent new term discovery [37], frequency estimation [5], [38], frequent itemset mining [40], mar”
Minimax Optimal Procedures for Locally Private Estimation (2016, neutral): “…statistics in a conditional analysis in which the data are treated as fixed (with some exceptions, for example, the articles Beimel, Nissim, and Omri 2008; Smith 2011; Karwa and Slavkovi´c 2016, as well as preliminary extended abstracts of our own work Duchi, Jordan, and Wainwright 2013a, 2013b).”
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters (2019, background): “Distribution estimation is a classical task in the centralized setting, where R observes the true samples X n , and it is known that [28] Distribution estimation under ε -LDP is also well studied in the past few years [29, 15, 30, 31, 32, 33, 34].”
Answering Multi-Dimensional Analytical Queries under Local Differential Privacy (2019, methodology): “…or known to the server ( e.g. , how much time a user spends on a service is Trust model of LDP. Users do not trust the server and require We adopt the local model of differential privacy (LDP) [13], which is also called randomized response model [39], γ -amplification [17], or FRAPP [2]. e.g.”
Mutual Information Optimally Local Private Discrete Distribution Estimation (2016, background): “…privacy guarantee, and achieves plenty of theoretical results or mechanisms characterizing the deﬁnition, both in centralized database setting (e.g. in [21][4][13]) and in the local setting [18] (e.g. in [6][14][16]), where each data provider sanitizes their secret data locally and independently.”
Context-Aware Generative Adversarial Privacy (2017, background): “Thus, training machine learning models on randomized data with DP guarantees often leads to a signiﬁcantly reduced utility and comes with a tremendous hit in sample complexity [16, 17, 18, 25, 31, 35, 36, 40, 53, 70, 74, 80, 81, 82] in the desired leakage regimes.”
Asymptotically optimal private estimation under mean square loss (2017, methodology): “I-A we mentioned several papers that have considered it, viz., [7]–[12], [14].”
Consistent and Accurate Frequency Oracles under Local Differential Privacy (2019, methodology): “Mean estimation is also a building block in LDP, but most of them transform the numerical value to a discrete value using stochastic round, and then apply frequency oracles [10, 12, 13, 25].”
Local Differential Privacy-Based Federated Learning for Internet of Things (2020, background): “[6] introduced alternative mechanisms for LDP.”