A Statistical Framework for Differential Privacy

By Larry A. Wasserman, Shuheng Zhou. 2008

565 citations recorded by the source corpus.

One goal of statistical privacy research is to construct a data release mechanism that protects individual privacy while preserving information content. An example is a random mechanism that takes an input database X and outputs a random database Z according to a distribution Qn(⋅|X). Differential privacy is a particular privacy requirement developed by computer scientists in which Qn(⋅|X) is required to be insensitive to changes in one data point in X. This makes it difficult to infer from Z whether a given individual is in the original database X. We consider differential privacy from a statistical perspective. We consider several data-release mechanisms that satisfy the differential privacy requirement. We show that it is useful to compare these schemes by computing the rate of convergence of distributions and densities constructed from the released data. We study a general privacy method, called the exponential mechanism, introduced by McSherry and Talwar (2007). We show that the accuracy of this method is intimately linked to the rate at which the probability that the empirical distribution concentrates in a small ball around the true distribution.

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

Protection Against Reconstruction and Its Applications in Private Federated Learning (2018, methodology): “Roughly, a mechanism satisfying inequality (2) guarantees that even if an adversary knows that the initial data is one of x or x′, the adversary cannot distinguish them given an outcome Z (the probability of error must be at least 1/(1 + eε)) [68].”
Learning Anonymized Representations with Adversarial Neural Networks (2018, background): “In the machine learning literature, [Wasserman and Zhou, 2010] and [Chaudhuri et al., 2011] develop differentially private empirical risk minimization algorithms, and [Bassily et al., 2014] and [Wang et al., 2016] study similar statistical and sample complexity of differentially private procedures.”
Collecting Telemetry Data Privately (2017, background): “For alternate interpretations of differential privacy within the framework of hypothesis testing we refer the reader to [20, 7].”
The Composition Theorem for Differential Privacy (2013, background): “Together with Corollary 4, Theorem 5 recovers a well known result: differential privacy is preserved by postprocessing the output [10], [15], [33].”
Crypto-Nets: Neural Networks over Encrypted Data (2014, background): “Another line of work focuses on differential privacy (Chaudhuri et al., 2011; Duchi et al., 2012; Dwork, 2008; Smith, 2011; Wasserman & Zhou, 2010).”
Signal Processing and Machine Learning with Differential Privacy (2013, background): “In particu lar, much of the theory has been developed for data taking discrete values, and there are many challenges raised by con tinuous data, ranging from the implementation of differen tially private algorithms [20] to theoretical foundations [21].”
Privacy Aware Learning (2012, methodology): “Zhou et al. [33] study one such procedure, and nonparametric data releases, such as those Hall et al. [15] study, may also provide insights.”
Differentially Private Empirical Risk Minimization (2009, neutral): “Wasserman and Zhou (2010) provide a more statistical view of differential privacy, and Zhou et al. (2009) provide a technique of generating synthetic data using compression via random linear or affine transformations.”
Minimax Optimal Procedures for Locally Private Estimation (2016, methodology): “More recent work aims to link differential privacy to statistical concerns (Dwork and Lei 2009; Wasserman and Zhou 2010; Hall, Rinaldo, and Wasserman 2012; Smith 2011; Chaudhuri, Monteleoni, and Sarwate 2011; Rubinstein et al. 2012); in particular, researchers have developed algorithms for private…”
Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation (2013, background): “…densities p and q ), the KL-divergence between P and Q is deﬁned by Letting σ ( ) denote the (an appropriate) σ -ﬁeld on X , the total variation distance between the distributions P and Q on X is given by For random vectors X and Y , where X is distributed according to the distribution P and”
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters (2019, background): “Differential Privacy (DP) [9] has emerged as one of the most popular notions of privacy (see [9, 6, 10, 11, 12], references therein, and the recent book [13]).”
The Right Complexity Measure in Locally Private Estimation: It is not the Fisher Information (2018, background): “An equivalent view [56] is that an adversary knowing the data is either x or x′ cannot accurately test, even conditional on the output Z, whether the generating data was x or x’ (the sum of Type I and II errors is at least 1 1+eε ).”
Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle (2015, background): “…and statistical hypothesis testing, and hence fits naturally in the general framework of statistical machine learning, e.g., see (Dwork & Lei, 2009; Wasserman & Zhou, 2010; Smith, 2011; Lei, 2011; Wang et al., 2015), as well as applications involving regression (Chaudhuri et al., 2011; Thakurta &…”
The Large Margin Mechanism for Differentially Private Maximization (2014, background): “There has been a large amount of work on differential privacy for a wide range of statistical and machine learning tasks over the last decade [6, 30, 13, 21, 33, 24, 1]; for overviews, see [18] and [29].”
On the 'Semantics' of Differential Privacy: A Bayesian Formulation (2008, background): “Specifically, fix an -differentially private mechanism A, an i.i.d. distribution on the data x, an index i, and disjoint sets S and T of possible values for the i-th entry xi of x. Wasserman and Zhou [16] show that any hypothesis test (given A(x), and full knowledge of the input product distribution”
Bayesian Differential Privacy through Posterior Sampling (2013, background): “Further results on the accuracy of the exponential mechanism with respect to the Kolmogorov-Smirnov distance are given in (Wasserman and Zhou, 2010), which introduced the concept of privacy as hypothesis testing where an adversary wishes to distinguish two datasets.”
Enabling Privacy-Preserving GWAS in Heterogeneous Human Populations (2016, unknown): “Informally, taking the frequentist’s perspective (Wasserman and Zhou, 2010), one can think of exp ðeÞ as bounding the power-to-significance ratio of any statistical test the adversary might use to determine a participant’s disease status based on e-phenotypically differentially private data.”
Locally differentially-private distribution estimation (2016, background): “More recent work in this spirit in the field of machine learning include [6] and [7].”