Differential Privacy

Introduction

At this year’s Neural Information Processing System Conference (NeurIPS), Google is sponsoring a machine unlearning competition. The goal of this competition is to engage the machine learning community in discussions on how to improve unlearning algorithms and their evaluation. Machine unlearning is a way by which we remove the influence of a training example from a trained machine learning model. As more businesses use deep learning models in their operations, there are growing concerns amongst the public about data privacy and the responsible use of such models. Machine unlearning offers a way for users to opt-out of their data being used by such trained models whilst preserving the privacy of their data.

In this post, I’ll discuss differential privacy which is a related subfield of machine learning that concerns privacy. Some knowledge from differential privacy should give us an idea as to how to approach machine unlearning and how machine unlearning algorithms work.

Differential Privacy

What is differential privacy?

It’s simply a mathematical definition of privacy that provides some privacy preserving guarantees for randomized mechanisms operating on a database. As we will see in the next section, it offers us a way to formally define machine unlearning.

We can think of a randomized mechanism as some mechanism that produces an output, $\xi \sim \mathcal{K}(.)$, with a given probability. This output however is not always the same each time we run it on a given data (Desfontaines, 2018). However if we run $\mathcal{K}$ several times, we will get a distribution for its output with some density, $\text{Pr}[\mathcal{K}(.) \in \mathcal{S}]$.

Suppose we want to protect someone’s anonymity, we can present 2 datasets: $\mathcal{D}^{\prime}$ & $\mathcal{D}$, which differ only by the presence or absence of a single element which is the person whose anonymity we’re trying to protect. For any differentially private mechanism, $\mathcal{K}$, we’re offered some guarantee that its output distribution on both datasets will be so similar that if an adversary were to inspect the distributions over however many runs of $\mathcal{K}$, said adversary will not be able to tell which database our person of interest is in. We can formalize this notion as such

$\text{Pr}[\mathcal{K}(\mathcal{D}) \in \mathcal{S}] \leq e^{\epsilon} \text{Pr}[\mathcal{K}(\mathcal{D}^{\prime}) \in \mathcal{S}] \tag{1}$

The guarantee offered by any randomized mechanism of interest is expressed by the term, $\epsilon$. It quantifies just how different both probability distributions are and as such it acts as a bound on how much privacy is loss were an attack to occur. The smaller the value of $\epsilon$, the stronger the privacy gurantees and vice versa. Typically $\epsilon$ for a given $\mathcal{K}$ is published or publicly known. Depeding on how much privacy is required, one may seek an $\epsilon$ as small as $0.01$ or as large as $\text{ln} 3$ (Dwork, 2008).

Let’s say a terrible event occurs like $\mathcal{K}$ publishes complete records of one or more persons in the dataset…oops! If we can guarantee that such event occurs with a probability $\delta$, then that affects our earlier privacy gurantee. It no longer holds with a probability of $1$ which is every time we run $\mathcal{K}$; it now holds with a probability, $1 - \delta$, whenever $\mathcal{K}$ doesn’t do something catastrophic. We can re-write our previous guarantee as

$\text{Pr}[\mathcal{K}(\mathcal{D}) \in \mathcal{S}] \leq e^{\epsilon} \text{Pr}[\mathcal{K}(\mathcal{D}^{\prime}) \in \mathcal{S}] + \delta \tag{2}$

It is interesting to note that the equation for both types of differential privacy are symmetric. For the above type of differential privacy, we have

$\begin{aligned} e^{-\epsilon} \text{Pr}[\mathcal{K}(\mathcal{D}^{\prime}) \in \mathcal{S}] - \delta &\leq \text{Pr}[\mathcal{K}(\mathcal{D}) \in \mathcal{S}] \leq e^{\epsilon} \text{Pr}[\mathcal{K}(\mathcal{D}^{\prime}) \in \mathcal{S}] + \delta \\ \text{Pr}[\mathcal{K}(\mathcal{D}^{\prime}) \in \mathcal{S}] &\leq e^{\epsilon} \text{Pr}[\mathcal{K}(\mathcal{D}) \in \mathcal{S}] + \delta \tag{3} \end{aligned}$

We can formulate differential privacy in a way that allows us quantify how well an adversary can distinguish between the output of $\mathcal{K}$ on datasets $\mathcal{D}$ and $\mathcal{D}^{\prime}$. Suppose we run $\mathcal{K}$ on either of the datasets and release the output, $\xi$, to an adversary. The adversary has to figure out which dataset $\xi$ came from. Said adversary is faced with the following hyopthesis test:

$\begin{aligned} H_{0} &: \xi \sim \mathcal{K}(\mathcal{D}) \\ H_{1} &: \xi \sim \mathcal{K}(\mathcal{D}^{\prime}) \tag{4} \end{aligned}$

Given $\xi$, our adversary has to decide whether to reject the null hypothesis, $H_{0}$ - in which case they will be accepting the alternative hypothesis, $H_{1}$ - or they can fail to reject it. Doing either can result in a type $\rm I$ error (False Positive) when $H_{0}$ is actually true and in a type $\rm II$ errors (False Negative) when $H_{1}$ is actually true. If our adversary selects a rejection region, $\mathcal{R} \subseteq \mathcal{S}$, for $\xi$ we can characterize the False Positive Rate (FPR) or the probability of making a type $\rm I$ error as

$\begin{aligned} FPR \equiv \text{Pr}[\mathcal{K}(\mathcal{D}) \in \mathcal{R}] \tag{5a} \end{aligned}$

We can also characterize the False Negative Rate (FNR) or the probability of making a type $\rm II$ error as

$\begin{aligned} FNR \equiv \text{Pr}[\mathcal{K}(\mathcal{D}^{\prime}) \in \overline{\mathcal{R}}] \tag{5b} \end{aligned}$

where $\overline{\mathcal{R}}$ is the complement of $\mathcal{R}$ (Kairouz et al., 2015).

This formulation is quite interesting because we can use the number of false positives (FP) and false negatives (FN) made by our adversary to estimate the privacy gurantee, $\epsilon$ for a mechanism $\mathcal{K}$. To see how, let us first consider that the FNR can be expressed in terms of the differential privacy equation as

$\begin{aligned} \text{Pr}[\mathcal{K}(\mathcal{D}) \in \overline{\mathcal{R}}] \leq e^{\epsilon} \text{Pr}[\mathcal{K}(\mathcal{D}^{\prime}) \in \overline{\mathcal{R}}] + \delta \\ 1 - \text{Pr}[\mathcal{K}(\mathcal{D}) \in \mathcal{R}] \leq e^{\epsilon} \text{Pr}[\mathcal{K}(\mathcal{D}^{\prime}) \in \overline{\mathcal{R}}] + \delta \\ 1 - \delta \leq e^{\epsilon} \text{Pr}[\mathcal{K}(\mathcal{D}^{\prime}) \in \overline{\mathcal{R}}] + \text{Pr}[\mathcal{K}(\mathcal{D}) \in \mathcal{R}] \\ 1 - \delta \leq e^{\epsilon} \text{FNR} + \text{FPR} \tag{6} \end{aligned}$

From the above, we have

$\epsilon \geq \text{ln} \left( \frac{1 - \delta - \text{FPR}}{\text{FNR}} \right) \tag{7}$

Considering the expression for FPR as well, we can estimate $\epsilon$ as

$\hat{\epsilon} = \text{max} \left( \text{ln} \frac{1 - \delta - \hat{\text{FPR}}}{\hat{\text{FNR}}}, \text{ln} \frac{1 - \delta - \hat{\text{FNR}}}{\hat{\text{FPR}}}\right) \tag{8}$

where $\hat{\text{FPR}}$ and $\hat{\text{FNR}}$ are estimates to the true FPR and FNR. This approach to estimating $\epsilon$ becomes useful in discussing unlearning algorithms (Evaluation for the NeurIPS Machine Unlearning Competition, 2023).

Conclusion

I’ve briefly discussed differential privacy as they relate to machine unlearning. The important bits are how privacy is offered by randomized mechanism on any pair of adjacent datasets and how the privacy guarantee of a given mechanism can be estimated using the set of false positives and negatives that are generated by an adverserial attack.

If you’re interested in learning more about differential privacy, I invite you to check out (Desfontaines, 2018) which provides a friendly blog series and (Kamath, 2020) which provide a lecture series on the topic.