Mutual Information Optimally Local Private Discrete Distribution Estimation

By Shaowei Wang, Liusheng Huang, Pengzhan Wang, Yiwen Nie, Hongli Xu, Wei Yang, Xiangyang Li, Chunming Qiao. 2016

100 citations recorded by the source corpus.

Consider statistical learning (e.g. discrete distribution estimation) with local $\epsilon$-differential privacy, which preserves each data provider's privacy locally, we aim to optimize statistical data utility under the privacy constraints. Specifically, we study maximizing mutual information between a provider's data and its private view, and give the exact mutual information bound along with an attainable mechanism: $k$-subset mechanism as results. The mutual information optimal mechanism randomly outputs a size $k$ subset of the original data domain with delicate probability assignment, where $k$ varies with the privacy level $\epsilon$ and the data domain size $d$. After analysing the limitations of existing local private mechanisms from mutual information perspective, we propose an efficient implementation of the $k$-subset mechanism for discrete distribution estimation, and show its optimality guarantees over existing approaches.

Subfields: Artificial Intelligence

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

Citations in the corpus

Breaking the Communication-Privacy-Accuracy Trilemma (2020, background): “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].”
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.”
Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy (2017, background): “At the same time, [14] does not i clude a detailed analysis of the existing schemes and the new proposal in the medium privacy regime.”
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters (2019, methodology): “Distribution estimation under ε-LDP has been well studied in the past few years (Duchi et al., 2013a; Erlingsson et al., 2014; Wang et al., 2016; Kairouz et al., 2016; Ye & Barg, 2018; Acharya et al., 2019; Bassily, 2019).”
Optimal schemes for discrete distribution estimation under local differential privacy (2017, background): “[14] under the name of k-subset mechanisms.”
Answering Multi-Dimensional Analytical Queries under Local Differential Privacy (2019, background): “, finding heavy hitters [4, 6, 36], frequent itemset mining [29, 37], and histogram estimation [24, 34, 38].”
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 Testing of Identity and Closeness of Discrete Distributions (2017, background): “There has been a line of research for statistical testing and estimation problems under the notion of local differential privacy [57, 28, 34, 50, 40, 58, 63, 6, 53, 1].”
Asymptotically optimal private estimation under mean square loss (2017, background): “This lower bound implies that the schemes and the estimators proposed in [12], [13] are order optimal in this regime.”
Consistent and Accurate Frequency Oracles under Local Differential Privacy (2019, methodology): “Subset Selection [33, 38] method reports a randomly selected subset of a fixed size k .”
Lossless Compression of Efficient Private Local Randomizers (2021, methodology): “, 2014) and also by a closely-related Subset Selection algorithm (Wang et al., 2016; Ye & Barg, 2018).”
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).”
Differentially Private Assouad, Fano, and Le Cam (2020, methodology): “Several estimation tasks have also been considered under the distributed notion of local diﬀerential privacy, e.g., [War65, KLN + 11, EPK14, DJW13, KBR16, WHW + 16, YB18, GR18, ACT19, ASZ19, AS19, ACFT19, She17].”
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].”
Locally Differentially Private Heavy Hitter Identification (2017, background): “More sophisticated frequency estimators have been studied before [2], [6], [16], [34], [35], [39].”