Course:CPSC522/Differential Privacy

Introduction to Differential Privacy

Principal Author: Yilin Yang
Collaborators:

Abstract

As we rely more and more on technology, data safety issues nowadays have become more and more prevalent. In light of this unprecedented amount of data used to train models, how do we protect users/data from malicious actors who want to infer this information? An obvious choice will be to choose to omit sensitive features in the dataset, or only report averaged results, however as Dwork et al. has pointed out, these "protection" methods are too naive. Unsurprisingly, even simple attacks are very effective: For two datasets that record voter information and healthcare information while omitting the name, using natural joins is enough to connect two datasets and learn more about an individual, as addresses (or a combination of information) are unique to a very small set of people. Therefore, it's not difficult for adversarial users to obtain critical information. In fact, one of the most famous machine learning competitions, the Netflix recommendation system competition, was subject to privacy risks using the natural join as shown here. Such attacks are so simple in fact that even curious users can pull them off accidentally, and they facilitate the need for a gold standard privacy notion. In this page, we introduce the gold standard privacy notion of Differential Privacy (DP). DP is mathematically guaranteed to preserve privacy and is widely deployed in the industry by tech companies such as Apple, Google, and Facebook. It is even used in the 2020 US census to protect individual privacy. We will follow the notations by Dwork et al. who first introduced DP. We will begin with a formal definition of privacy and DP. We will then introduce a mechanism that can be used to achieve DP, we will then talk about DP properties and finally introduce approximate DP and its mechanisms. We will also beifly go over Rényi DP as a more recent development in DP.

Builds on

As DP is a mathematical guarantee, Probability is the main foundation. However, understanding Rényi Divergence is recommended for the last section.

Related Pages

The Algorithmic Foundations of Differential Privacy by Dwork et al. should be your go-to for most theory DP related.

Programming Differential Privacy is a much simpler overview that goes into implementation more than theory.

CS 860 - Algorithms for Private Data Analysis by Gautam Kamath has very good insight into the more dense proofs of DP, I highly recommend!

Hopefully, all of these along with this Wiki page can provide some well-needed insight into my previous page:

MDP for Differentially Private Reinforcement Learning

For those interested in the 2020 US Census, the blog post by Simson Garfinkel offers excellent insight.

Definition of Privacy and Differential Privacy

Before we introduce Differential Privacy, it is important to formally define privacy as it greatly changes our method of preserving privacy: if the goal is to not leak any information about the population, then every statistical/machine learning method that aims to preserve this notion of privacy cannot be of any use to analysts. However, if we define privacy as protection for members that participated in the training dataset so that there is no incurred risk for participating in the training process, then as ML researchers we can still obtain statistically significant knowledge of the population. We will use this definition of privacy, more formally:

Definition of Privacy:

Data Privacy aims to preserve the sensitive information of participants from malicious individuals while allowing data analysts to conduct statistically significant inferences of the data.

Definition of Differential Privacy

Following the definition by Dwork et al., for some $\varepsilon \geq 0$, A mechanism ${\mathcal {M}}$ is called $\varepsilon$-DP if and only if it satisfies the equation:

$$\Pr[{\mathcal {M}}({\mathcal {D}})\in S]\leq e^{\epsilon }\cdot \Pr[{\mathcal {M}}({\mathcal {D'}})\in S]$$

for all neighboring datasets ${\mathcal {D}}$ and ${\mathcal {D'}}$and for all possible sets of the mechanism's output $S$.

Here, datasets are considered neighboring if they differ by only 1 entry, and a mechanism ${\mathcal {M}}$ is any function that satisfies DP.

The DP definition essentially implies that the mechanism ${\mathcal {M}}$ cannot be deterministic and must have multiple outputs given some input, and the output for ${\mathcal {M}}({\mathcal {D}})$ and ${\mathcal {M}}({\mathcal {D'}})$ should be very similar to each other. This ensures that the adversary cannot infer whether or not a specific individual has partaken in the dataset, thereby protecting the user and its sensitive information. To make this clearer:

Example of the Differential Privacy Definition, here neighboring datasets have approximately the same output.

$\varepsilon$ here is also known as the privacy budget or privacy parameter, the larger $\varepsilon$ is the less private ${\mathcal {M}}$ becomes as there is more difference in the output for ${\mathcal {M}}({\mathcal {D}})$ and ${\mathcal {M}}({\mathcal {D'}})$. However it should be noted that the exact nature of $\varepsilon$ is not fully understood, in other words, how do we choose $\varepsilon$ in practice? Even companies like Google, Apple, and Facebook who actively deploy DP models to preserve their users' privacy will typically choose an empirical value (or so they claim). In most cases, $\varepsilon$ should be 1 or smaller, and $\varepsilon$ greater than 10 offers little to no privacy.

With the definition in hand, how does a function become a DP mechanism ${\mathcal {M}}$? At a high level, DP can be achieved by injecting noise into a sensitive portion of the training procedure. This noise acts as a privacy barrier that obscures the 1-to-1 relationship of input and output, making any information past the privacy wall "sanitized". This barrier does not need setup such as in a database denying costly access restrictions like in databases as this added noise will make the results of such a query useless for malicious actors. Naturally, injecting noise will degrade the performance of an ML model, and researchers need to balance the tradeoff between protection and performance. In the next section, we will look at the Laplace Mechanism, a classic $\varepsilon$-DP mechanism achieved by adding controlled Laplace noise.

Laplace Mechanism

Before we introduce the Laplace mechanism, we must define the sensitivity considered in the Laplace Mechanism:

Definition 1: Following the definition by , for any given function $f(x):{\mathcal {D}}^{n}\rightarrow \mathbb {R} ^{k}$, the sensitivity of the function $f$ is:

$$\Delta _{f}=\max _{{\mathcal {D}},{\mathcal {D'}}}||f(D)-f(D')||_{1},$$

Where once again ${\mathcal {D}}$ and ${\mathcal {D'}}$ are neighboring datasets.

This sensitivity is called the $l_{1}$-sensitivity. There are multiple definitions of sensitivity, and they are used to scale the DP noise to the magnitude of change when 1 data point is changed in the dataset. Thus ensuring our DP noise is on the correct scale. Now, we can introduce the Laplace Mechanism:

Theorem 1: For a function $f(x):{\mathcal {D}}^{n}\rightarrow \mathbb {R} ^{k}$, the mechanism ${\mathcal {M}}$ satisfies $\varepsilon$-DP:

$${\mathcal {M}}(x)=f(x)+{\text{Lap}}({\frac {\Delta _{f}}{\varepsilon }})$$

Where Lap is the laplace distribution with paramters 0 and ${\frac {\Delta _{f}}{\varepsilon }}$. For the proof of such mechanism ${\mathcal {M}}$ satisfies $\varepsilon$-DP, please see Theorem 4 of Gautam's Lecture notes.

The typical noise addition for functions to achieve DP. A larger sensitivity will require more DP noise.

Laplace Mechanism Application: Counting Queries

One of the most classic examples of using the Laplace Mechanism to privatize the counting query result. The counting query in a database are queries that ask the question: "How many data points in the dataset have property/feature A?" In this case, the system will go through each data point and generate an indicator value and sum it up with a function say $f$. As each data point can change this sum by at most 1, the sensitivity of $f$ should be 1. Thus an $\varepsilon$-DP algorithmn for the counting queries is $f({\mathcal {D}})+{\text{Lap}}(1/\varepsilon )$. The returned mechanism will have an error of $O(1/\varepsilon )$ and is independent of the dataset size.

There are many other use cases for the Laplace Mechanism, including privatizing histogram queries. In the next section, we will showcase the useful properties of DP.

Important Properties of Differential Privacy

DP is a popular choice of privatization not only because of its intuitive mechanisms, but also the convenient properties that follow from the DP definition. Here we will introduce the three most commonly used DP properties in research: post-processing, (basic) composition, and group privacy. We will include the proof as they are simple, but the proofs are largely inspired by Gautam's Lecture notes.

Post-Processing

Post-Processing is one of the most important qualities of DP, as it essentially guarantees any downstream task will not "un-DP" sensitive data that has been privatized.

Theorem 2: Let a mechanism ${\mathcal {M}}:{\mathcal {D}}^{n}\rightarrow {\mathcal {Y}}$ be $\varepsilon$-DP, and let ${\mathcal {F}}:{\mathcal {Y}}\rightarrow {\mathcal {Z}}$ be a randomized mapping algorthim, then ${\mathcal {F}}\ \circ \ {\mathcal {M}}$ is $\varepsilon$-DP.

Proof. As ${\mathcal {F}}$ is randomized, it can be considered as some distribution of deterministic functions, say $f$. Thus for any neighbouring datasets ${\mathcal {D}}$ and ${\mathcal {D'}}$ and output $S\subseteq {\mathcal {Z}}$:

$${\begin{aligned}\Pr[{\mathcal {F}}({\mathcal {M}}({\mathcal {D}}))\in S]&=\mathbb {E} _{f\sim {\mathcal {F}}}[\Pr[{\mathcal {M}}({\mathcal {D}})\in f^{-1}(S)]]\\&\leq \mathbb {E} _{f\sim {\mathcal {F}}}[e^{\varepsilon }\cdot \Pr[{\mathcal {M}}({\mathcal {D'}})\in f^{-1}(S)]]&&({\text{DP defintion}})\\&=e^{\varepsilon }\cdot \Pr[{\mathcal {F}}({\mathcal {M}}({\mathcal {D'}}))\in S]\\&&&\Box \end{aligned}}$$

(Basic) Composition

Another important property of DP is composition, in the case where we run k DP algorithms on the same dataset, how do we aggregate/compose the privacy budget of these k mechanisms?

Theorem 3: Let $\mathbf {\mathcal {M}} =[{\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{k}]$ be a scequence of k $\varepsilon$-DP mechanisms, then ${\mathcal {M}}$ is $k\varepsilon$-DP.

Proof. For any neighbouring datasets ${\mathcal {D}}$ and ${\mathcal {D'}}$ and output sequence $S=[S_{1},\dots ,S_{k}]$:

$${\begin{aligned}{\frac {\Pr[{\mathcal {M}}({\mathcal {D}})=S]}{\Pr[{\mathcal {M}}({\mathcal {D'}})=S]}}&=\prod _{i=1}^{k}{\frac {\Pr[{\mathcal {M}}_{i}({\mathcal {D}})=S_{i}|[{\mathcal {M}}_{1}({\mathcal {D}}),\dots ,{\mathcal {M}}_{i-1}({\mathcal {D}})]=[S_{1},\dots ,S_{i-1}]]}{\Pr[{\mathcal {M}}_{i}({\mathcal {D}})=S_{i}|[{\mathcal {M}}_{1}({\mathcal {D'}}),\dots ,{\mathcal {M}}_{i-1}({\mathcal {D'}})]=[S_{1},\dots ,S_{i-1}]]}}\\&\leq \prod _{i=1}^{k}e^{\varepsilon }\\&=e^{k\varepsilon }\\&&&\Box \end{aligned}}$$

This is called basic composition because this budget bound is not the tightest, more recently there is the advanced composition which improves this bound to $O({\sqrt {k}})\varepsilon$-DP rather than the current $k\varepsilon$-DP. We will introduce the advanced composition later when we discuss approximate DP.

Group Privacy

Last but not least, we can extend the neighboring dataset definition to datasets that differ by $k$ entries, this is called group privacy. Similar to the DP definition:

Theorem 4: Let a mechanism ${\mathcal {M}}:{\mathcal {D}}^{n}\rightarrow {\mathcal {Y}}$ be $\varepsilon$-DP, thus for all datasets ${\mathcal {D}}$ and ${\mathcal {D'}}$ that differ by $k$ data points, and for all possible sets of the mechanism's output $S$.

$$\Pr[{\mathcal {M}}({\mathcal {D}})\in S]\leq e^{k\epsilon }\cdot \Pr[{\mathcal {M}}({\mathcal {D'}})\in S]$$

Proof. Defining ${\mathcal {D}}_{0}={\mathcal {D}}$ , ${\mathcal {D}}_{k}={\mathcal {D'}}$, and the sequence from ${\mathcal {D}}_{0},\dots ,{\mathcal {D}}_{k}$ as a sequence of neighboring datasets, for all possible sets of the mechanism's output $S$, we have:

$${\begin{aligned}\Pr[{\mathcal {M}}({\mathcal {D}}_{0})\in S]&\leq e^{\epsilon }\cdot \Pr[{\mathcal {M}}({\mathcal {D}}_{1})\in S]\\&\leq e^{2\epsilon }\cdot \Pr[{\mathcal {M}}({\mathcal {D}}_{2})\in S]\\&\dots \\&\leq e^{k\epsilon }\cdot \Pr[{\mathcal {M}}({\mathcal {D}}_{k})\in S]\\&&&\Box \end{aligned}}$$

Thus we have learned the three most important properties that help DP to be an intuitive way of adding privacy protection, in practice however $\varepsilon$-DP is a rather strong guarantee, in the next section, we will talk about the more widely used Approximate DP as it is known to give a better utility-privacy tradeoff.

Approximate Differential Privacy

Similar to $\varepsilon$-DP, we introduce a relaxation of this guarantee called approximate DP:

Definition 2: Following the definition by Dwork et al. , for some $\varepsilon ,\delta \geq 0$, A mechanism ${\mathcal {M}}$ is called $(\varepsilon ,\delta )$-DP if and only if it satisfies the equation:

$$\Pr[{\mathcal {M}}({\mathcal {D}})\in S]\leq e^{\epsilon }\cdot \Pr[{\mathcal {M}}({\mathcal {D'}})\in S]+\delta$$

for all neighboring datasets ${\mathcal {D}}$ and ${\mathcal {D'}}$and for all possible sets of the mechanism's output $S$.

Here, the only difference from $\varepsilon$-DP is the addition of $\delta$. $\delta$ is called the failure probability, we can summarize its behaviour into two cases:

• With a probability of $1-\delta$, we have $\varepsilon$-DP: $\Pr[{\mathcal {M}}({\mathcal {D}})\in S]\leq e^{\epsilon }\cdot \Pr[{\mathcal {M}}({\mathcal {D'}})\in S]$.
• With a probability of $\delta$, we get no privacy guarantee!

At first glance, this seems like a very scary definition, as there's a possibility that this algorithm will fail and leak sensitive data! Therefore in practice, this failure probability will be very small. Although it is still not enough to satisfy some DP purists (nothing ever does anyways), In the following sections we will see $(\varepsilon ,\delta )$-DP mechanism that fail gracefully, and instead of releasing a sensitive dataset when it fails, instead they release the sensitive data with a weaker DP guarantee.

Gaussian Mechanism

Before we introduce the Gaussian mechanism, similar to the Laplace Mechanism we must define the sensitivity considered:

Definition 3: For a function $f(x):{\mathcal {D}}^{n}\rightarrow \mathbb {R} ^{k}$, the sensitivity of $f$ is:

$$\Delta _{f}=\max _{{\mathcal {D}},{\mathcal {D'}}}||f(D)-f(D')||_{2},$$

Where once again ${\mathcal {D}}$ and ${\mathcal {D'}}$ are neighboring datasets.

This sensitivity is called the $l_{2}$-sensitivity. Now, we can introduce the Gaussian Mechanism:

Theorem 5: For a function $f(x):{\mathcal {D}}^{n}\rightarrow \mathbb {R} ^{k}$, the mechanism ${\mathcal {M}}$ satisfies $(\varepsilon ,\delta )$-DP:

$${\mathcal {M}}(x)=f(x)+{\mathcal {N}}(0,\sigma ^{2}\Delta _{f}^{2}\mathbf {I} _{p})$$

The (privacy) parameter $\sigma$ for a single privacy release satisfies the following inequality: $\sigma \geq {\sqrt {2\log(1.25/\delta )}}/\epsilon$ hold for $\epsilon \leq 1$.

For the proof of such mechanism ${\mathcal {M}}$ satisfies $(\varepsilon ,\delta )$-DP, please see Theorem 6 of Gautam's Lecture notes. In the following section we will outline the properties that Approximate DP has.

Important Properties of Approximate Differential Privacy

Similar to the properties in $\varepsilon$-DP, Approximate DP also offers such useful properties. Here, as some proofs are dense we will only state the results, those who are interested in the details can refer to the works by Dwork et al. and Vadhan .

Post-Processing

The post-processing property still holds, and the proof is pretty straightforward as you replace the DP definition with the approximate DP definition:

Theorem 6: Let a mechanism ${\mathcal {M}}:{\mathcal {D}}^{n}\rightarrow {\mathcal {Y}}$ be $\varepsilon$-DP, and let ${\mathcal {F}}:{\mathcal {Y}}\rightarrow {\mathcal {Z}}$ be a randomized mapping algorthimn, then ${\mathcal {F}}\ \circ \ {\mathcal {M}}$ is $(\varepsilon ,\delta )$-DP.

Basic Composition

Theorem 7: Let $\mathbf {\mathcal {M}} =[{\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{k}]$ be a sequence of k $(\varepsilon ,\delta )$-DP mechanisms, where each Mechanism ${\mathcal {M}}_{i}$ is $(\varepsilon _{i},\delta _{i})$-DP then ${\mathcal {M}}$ is $(\sum _{i=1}^{k}\varepsilon _{i},\sum _{i=1}^{k}\delta _{i})$-DP.

Advanced Composition

As stated previously, if we used Advanced Composition, we can improve the aggregated/composed privacy budget of DP algorithms.

Theorem 8: Let $\mathbf {\mathcal {M}} =[{\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{k}]$ be a sequence of k $(\varepsilon ,\delta )$-DP mechanisms, where each Mechanism ${\mathcal {M}}_{i}$ has the same privacy parameters $\varepsilon _{i}=\varepsilon$ and $\delta _{i}=\delta$. then ${\mathcal {M}}$'s is $(\varepsilon {\sqrt {8k\ln(1/\delta ')}},k\delta +\delta ')$-DP.

Here $\delta '>0$, and it's a value that can be manually changed and provides a relationship between the composed ${\tilde {\varepsilon }}=\varepsilon {\sqrt {8k\ln(1/\delta ')}}$ and ${\tilde {\delta }}=k\delta +\delta '$. The exact proof of this bound is detailed in the paper by Dwork et al. But the intuition can be found in Gautam's DP Lecture 6 . Notice that Approximate DP is equivalent to DP when $\delta =0$, this bound holds for both DP definitions. This which improves the privacy parameter ${\tilde {\varepsilon }}$ to $O({\sqrt {k}})\varepsilon$ rather than the $k\varepsilon$ in basic composition.

Group Privacy

Last but not least, we also have group privacy in Approximate DP:

Theorem 9: Let a mechanism ${\mathcal {M}}:{\mathcal {D}}^{n}\rightarrow {\mathcal {Y}}$ be $(\varepsilon ,\delta )$-DP, thus for all datasets ${\mathcal {D}}$ and ${\mathcal {D'}}$ that differ by $k$ data points, and for all possible sets of the mechanism's output $S$.

$$\Pr[{\mathcal {M}}({\mathcal {D}})\in S]\leq e^{k\epsilon }\cdot \Pr[{\mathcal {M}}({\mathcal {D'}})\in S]+ke^{(k-1)\varepsilon }\delta$$

Here, the $\delta$ has an additional factor of $e^{(k-1)\varepsilon }$.

Failure Probability $\delta$ in the Gaussian Mechanism

We mentioned in the previous section how the Gaussian Mechanism is not $\varepsilon$-DP, instead with failure probability $\delta$, it is a graceful failure with a weaker DP guarantee.

In other words, with probability $\delta$, the Gaussian Mechanism satisfies $t\varepsilon$-DP instead, for some value $t$.

As for what this value $t$ is, the proof Theorm 6 of Gautam's Lecture notes provides a more detailed explaination.

Finally, we have talked about the most common properties in DP and approximate DP, and why it is widely recognized in both academics and industry as the gold standard privacy notion. In the next section, we will look at a more up-to-date Approximate DP method, Rényi Differential Privacy.

Rényi Differential Privacy

In statistics, there are many divergence metrics used to compare probability distributions. As the DP definition is essentially a probability distribution comparison, researchers have thought of applying these metrics to the DP definition in hopes of improving the bounds of the DP properties stated previously. These metrics, such as the max divergence, KL divergence, and Rényi divergence have sparked variants of DP as they can be directly transformed back to the original DP definition. Here, we will look at the most widely used Rényi Differential Privacy (RDP), we will begin by introducing the definition of the Rényi Divergence:

Definition 4: For two probability distributions ${\mathcal {P}}$ and ${\mathcal {Q}}$, the Rényi Divergence is defined as:

$$D_{\alpha }({\mathcal {P}}\ ||\ {\mathcal {Q}})={\frac {1}{\alpha -1}}\log {\big (}\sum _{i=1}^{n}{\mathcal {p}}_{i}^{\alpha }q_{i}^{1-\alpha }{\big )}$$

When $\alpha \rightarrow 1$, this is the KL-divergence and when $\alpha \rightarrow \infty$ we can recover the $\varepsilon$-DP definition (This is just pure mathematics). We can use Rényi Divergence at various other $\alpha$ to have a better relaxation of DP while avoiding the failure probability in Approximate DP. We now formally introduce RDP which is first proposed by Mironov :

Definition 5: A mechanism ${\mathcal {M}}$ is called $(\alpha ,{\bar {\epsilon }})$-RDP if and only if it satisfies the equation:

$$D_{\alpha }({\mathcal {M}}({\mathcal {D}})\ ||\ {\mathcal {M}}({\mathcal {D'}}))\leq {\bar {\epsilon }}$$

for all neighboring datasets ${\mathcal {D}}$ and ${\mathcal {D'}}$. Here ${\bar {\epsilon }}$ should be differentiated from the $\varepsilon$ in the DP definitions.

The relationship between $(\alpha ,{\bar {\epsilon }})$-RDP and $(\varepsilon ,\delta )$-DP are as follows:

Theorem 10: Let a mechanism ${\mathcal {M}}:{\mathcal {D}}^{n}\rightarrow {\mathcal {Y}}$ be $(\alpha ,{\bar {\epsilon }})$-RDP, then for some $\delta >0$, ${\mathcal {M}}$ is $(\varepsilon ,\delta )$-DP where $\varepsilon ={\bar {\epsilon }}+{\frac {\log(1/\delta )}{\alpha -1}}$.

Here, the $\delta$ can once again be manually changed by the data scientists but a small value might be more sensible. One of the most mechanism that achieves $(\alpha ,{\bar {\epsilon }})$-RDP is, once again, the Gaussian Mechanism:

Theorem 11: For a function $f(x):{\mathcal {D}}^{n}\rightarrow \mathbb {R} ^{k}$, the mechanism ${\mathcal {M}}$ satisfies $(\varepsilon ,\delta )$-DP:

$${\mathcal {M}}(x)=f(x)+{\mathcal {N}}(0,{\frac {\Delta _{f}^{2}\alpha }{2{\bar {\epsilon }}}})$$

One of the biggest advantage in using this RDP Gaussian Mechanism is that the composition can be tight, without the need for advanced composition:

RDP Composition

Theorem 12: Let $\mathbf {\mathcal {M}} =[{\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{k}]$ be a sequence of k $(\alpha ,{\bar {\epsilon }})$-RDP mechanisms, where each Mechanism ${\mathcal {M}}_{i}$ is $(\alpha ,{\bar {\epsilon }}_{i})$-RDP then ${\mathcal {M}}$ is $(\alpha ,\sum _{i=1}^{k}{\bar {\epsilon }}_{i})$-RDP.

This bound is particularly powerful as even transforming it back to the original definition of $(\varepsilon ,\delta )$-DP we get a much better privacy cost than advanced composition. Consequently, RDP has been used in Goggle's TensorFlow Privacy package for privacy accounting.

Conclusion

In this Wiki page, we provide a comprehensive overview and introduction to DP, a gold standard notion of privacy. We carefully defined privacy and showcased how DP is a powerful mathematical guarantee of this notion of privacy. There are many DP variants and mechanisms not introduced as it is far beyond the scope of this course, however, I highly recommend checking out Zero-Concentrated Differential Privacy by Bun and Steinke as well as many DP papers in machine learning conferences as there are active researchers from all over the world who are in active pursuit of closing the gap between DP and non-DP settings. Ultimately, if DP doesn't degrade the performance, it can be trivial to deploy and privacy in ML will be achieved.

Annotated Bibliography

Put your annotated bibliography here. Add links where appropriate.