Discrete Distribution Estimation under Local Privacy

By Peter Kairouz, Kallista A. Bonawitz, Daniel Ramage. 2016

377 citations recorded by the source corpus.

The collection and analysis of user data drives improvements in the app and web ecosystems, but comes with risks to privacy. This paper examines discrete distribution estimation under local privacy, a setting wherein service providers can learn the distribution of a categorical statistic of interest without collecting the underlying data. We present new mechanisms, including hashed K-ary Randomized Response (KRR), that empirically meet or exceed the utility of existing mechanisms at all privacy levels. New theoretical results demonstrate the order-optimality of KRR and the existing RAPPOR mechanism at different privacy regimes.

Subfields: Artificial Intelligence, 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 Statistics and Probability

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “While LDP protocols are effective at enforcing privacy and have theoretical justifications [156, 135, 136], a number of results have shown that achieving local differential privacy while preserving utility is challenging particularly, especially in high-dimensional data settings [229, 388, 219, 51, ”
The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation (2021, background): “However, it is now well-established that local DP usually leads to a steep hit in accuracy (Kasiviswanathan et al., 2011; Duchi et al., 2013; Kairouz et al., 2016).”
Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs (2020, background): “The challenge is that the traditional privacy approach to the learning problem uses local diﬀerential privacy (LDP) [War65, ESAG04, DJW13, BNO08, KLN + 11], which is known to give poor learning performance [DJW13,KLN + 11,KBR16].”
Learning discrete distributions: user vs item-level privacy (2020, background): “…non-asymptotic convergence rates [Braess and Sauer, 2004, Kamath et al., 2015, Han et al., 2015], with local diﬀerential privacy [Duchi et al., 2013, Kairouz et al., 2016, Acharya et al., 2019a, Ye and Barg, 2018], with global diﬀerential privacy [Diakonikolas et al., 2015, Acharya et al., 2020],…”
Breaking the Communication-Privacy-Accuracy Trilemma (2020, methodology): “If we further assume X are drawn from some discrete distribution p, then the problem falls into distribution estimation under local differential privacy [9], [13], [34], [36], [42], [43], [44], [45], [46] and limited communication [11], [25], [45], [46], [47], [48], [49], [50].”
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, background): “, (Kairouz et al., 2016; Acharya & Sun, 2019; Suresh, 2019)), as private histogram procedures can be used as a black-box to solve important algorithmic problems such as heavy hitters (e.”
The Privacy Blanket of the Shuffle Model (2019, methodology): “This randomizer has been studied and used (in the local model) in several previous works [21, 20, 7].”
Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, background): “Distribution learning under LDP constraints has been studied in [4], [21], [37], [52], [56], all providing sample-optimal schemes with different merits.”
Collecting Telemetry Data Privately (2017, methodology): “KFlip is sub-optimal for small ε [17] but has better performance when ε is Ω(ln k).”
BLENDER: Enabling Local Search with a Hybrid Differential Privacy Model (2017, background): “Moreover, recent work in the LDP model is focused on precisely that problem [13, 34] or very closely related ones of histogram computations [5, 21].”
Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy (2017, background): “As discussed in [12], along with the empirical estimator for the k-RR andk-RAPPOR schemes, there are other estimators, for instance, the normalized es timator and the projected estimator.”
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”
Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication (2018, background): “The k-RR mechanism [45, 31] is an Á-LDP QRR with Z = X = [k], such that”
Generative Adversarial Privacy: A Data-Driven Approach to Information-Theoretic Privacy (2018, background): “For example, learning population level histograms under local DP suﬀers from a stupendous increase in sample complexity by a factor proportional to the size of the dictionary [6, 16, 34].”
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].”