Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy

By Min Ye, Alexander Barg. 2017

205 citations recorded by the source corpus.

We consider the minimax estimation problem of a discrete distribution with support size <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> under privacy constraints. A privatization scheme is applied to each raw sample independently, and we need to estimate the distribution of the raw samples from the privatized samples. A positive number <inline-formula> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula> measures the privacy level of a privatization scheme. For a given <inline-formula> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula>, we consider the problem of constructing optimal privatization schemes with <inline-formula> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula>-privacy level, i.e., schemes that minimize the expected estimation loss for the worst-case distribution. Two schemes known in the literature provide order optimal performance in the high privacy regime where <inline-formula> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula> is very close to 0, and in the low privacy regime where <inline-formula> <tex-math notation="LaTeX">$e^{\epsilon }\approx k$ </tex-math></inline-formula>, respectively. In this paper, we propose a new family of schemes which substantially improve the performance of the existing schemes in the medium privacy regime when <inline-formula> <tex-math notation="LaTeX">$1\ll e^{\epsilon } \ll k$ </tex-math></inline-formula>. More concretely, we prove that when <inline-formula> <tex-math notation="LaTeX">$3.8 < \epsilon <\ln (k/9) $ </tex-math></inline-formula>, our schemes reduce the expected estimation loss by 50% under <inline-formula> <tex-math notation="LaTeX">$\ell _{2}^{2}$ </tex-math></inline-formula> metric and by 30% under <inline-formula> <tex-math notation="LaTeX">$\ell _{1}$ </tex-math></inline-formula> metric over the existing schemes. We also prove a lower bound for the region <inline-formula> <tex-math notation="LaTeX">$e^{\epsilon } \ll k$ </tex-math></inline-formula>, which implies that our schemes are order optimal in this regime.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, 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 Electrical and Electronic Engineering

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, ”
Learning discrete distributions: user vs item-level privacy (2020, background): “…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], and with communication constraints [Barnes…”
Federated Heavy Hitters Discovery with Differential Privacy (2019, background): “…et al., 2015; Xu et al., 2016; Zhou and Lin, 2018; Kairouz et al., 2016; Wang et al., 2017; Bassily et al., 2017; Acharya et al., 2018; Ye and Barg, 2018; Avent et al., 2017; Bun et al., 2018; Cormode et al., 2018), and some recent works combine FL with central DP (Geyer et al., 2017;…”
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 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”
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters (2019, methodology): “To build toward constant communication private-coin distribution estimation schemes, recall that the known optimal distribution estimation schemes [26, 31, 32, 33] are all symmetric, and require Ω(log k ) communication bits per message.”
Lower Bounds for Locally Private Estimation via Communication Complexity (2019, background): “(2018), Rohde and Steinberger (2018), and Duchi and Ruan (2018), or at most logarithmic in dimension (Ye and Barg, 2018); given the promise of privacy amplification in local settings (Erlingsson et al.”
Local Private Hypothesis Testing: Chi-Square Tests (2017, background): “Other related and notable works in the local privacy model include Pastore and Gastpar (2016); Kairouz et al. (2016); Ye and Barg (2017)”
Lower Bounds for Learning Distributions under Communication Constraints via Fisher Information (2019, background): “…et al. (2013) for a general treatment of estimation problems under locally differentially private (LDP) constraints, while optimal schemes (and lower bounds) for estimating discrete distributions are proposed in Kairouz et al. (2016); Wang et al. (2016); Ye and Barg (2018); Acharya et al. (2019c).”
Test without Trust: Optimal Locally Private Distribution Testing (2018, background): “Indeed, note that the problem of learning the unknown k-ary distribution up to an accuracy of γ in total variation distance in the locally private setting has received a lot of attention, and its optimal sample complexity is known to be Θ(k2/(γ2ε2)); see [16, 19, 35, 26, 5].”
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].”
On the Power of Multiple Anonymous Messages (2019, unknown): “Some works [100,69] have established tight lower bounds for locally diﬀerentially private distribution estimation in the weak privacy setting with loss instead given by either (cid:96) 1 or 22 .”
Local Differential Private Data Aggregation for Discrete Distribution Estimation (2019, background): “It should be note that concurrent work [38],”
Unified lower bounds for interactive high-dimensional estimation under information constraints (2020, background): “For ̺ > 1 (low-privacy regime), our bound matches the upper bound for the noninteractive case, established in [33, 5], showing that even in this lowprivacy regime interactivity cannot lead to better rates, except maybe up to constant factors.”