Marginal Release Under Local Differential Privacy

By Tejas D. Kulkarni, Graham Cormode, Divesh Srivastava. 2017

144 citations recorded by the source corpus.

Many analysis and machine learning tasks require the availability of marginal statistics on multidimensional datasets while providing strong privacy guarantees for the data subjects. Applications for these statistics range from finding correlations in the data to fitting sophisticated prediction models. In this paper, we provide a set of algorithms for materializing marginal statistics under the strong model of local differential privacy. We prove the first tight theoretical bounds on the accuracy of marginals compiled under each approach, perform empirical evaluation to confirm these bounds, and evaluate them for tasks such as modeling and correlation testing. Our results show that releasing information based on (local) Fourier transformations of the input is preferable to alternatives based directly on (local) marginals.

Subfields: Artificial Intelligence, 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 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, ”
Federated Heavy Hitters Discovery with Differential Privacy (2019, background): “learning, frequent sequence mining, and heavy-hitter discovery both in the central and local models of DP [6, 10, 18, 42, 44, 32, 40, 5, 1, 43, 3, 11, 17], and some recent works combine FL with central DP [29, 39].”
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”
Cryptϵ: Crypto-Assisted Differential Privacy on Untrusted Servers (2019, unknown): “Interesting work has been done in both theCDPmodel [8, 22, 30, 33, 34, 39, 54– 56, 58, 70, 71, 75, 85, 89, 90, 100–102, 104, 105, 107] and the LDP model [13, 32, 42, 44, 91, 95–97, 108].”
Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited (2018, methodology): “All these previous works have considered the central model of differential privacy, and only the recent work [16] studies this problem in the local model, while their methods are based Fourier Transform.”
CALM: Consistent Adaptive Local Marginal for Marginal Release under Local Differential Privacy (2018, methodology): “Two recent papers [11, 31] considered the problem of publishing marginals under LDP. Kulkarni [11] et al. proposed to apply the Fourier Transformation method, which was used in publishing marginals under the centralized DP setting [5].”
On the Power of Multiple Anonymous Messages (2019, unknown): “This improves on a result of Cheu et al. [29, Corollary 32], which gives a lower bound of n “ ω p log 1 { 17 B q for this task.”
Locally Differentially Private Data Collection and Analysis (2019, background): “Current researches focus on many related problems under the LDP model, such as mean/frequency estimation [15, 39, 48], probability distribution estimation [22, 56, 47], heavy hitter identification [5, 41, 8], itemset mining [50], marginal distribution release [12, 60], and empirical risk minimizatio”
Privacy at Scale: Local Differential Privacy in Practice (2018, background): “Instead, taking projections of the data via a Fourier basis allows better reconstructions [8].”
Locally Differentially Private Heavy Hitter Identification (2017, background): “For example, mean estimation [11], [27], frequent itemset mining [29], [37], releasing marginals under LDP [10], [30], [41], key-value pair estimation [40], evolving data monitoring [15], [22], and empirical risk minimization [31], [32].”
Consistent and Accurate Frequency Oracles under Local Differential Privacy (2019, background): “, finding heavy hitters [5–7, 17, 35], frequent itemset mining [27, 36], releasing marginals under LDP [9, 28, 40], keyvalue pair estimation [39], evolving data monitoring [15, 20], and empirical risk minimization [30, 31].”
Answering Multi-Dimensional Analytical Queries under Local Differential Privacy (2019, result): “As shown in Figure 3, [ 2 , 7 ] can be partitioned into 4 intervals in I D (blue ones), and [ 3 , 8 ] partitioned into 2 in I D (green ones).”