Buy Print

Differential Privacy in Artificial Intelligence: From, Theory to Practice

Edited by

Author and Other Information

Status:

Available

Emerald Publishing Limited

DOI:

https://doi.org/10.1561/9781638284772

ISBN electronic:

978-1-63828-477-2

ISBN print:

978-1-63828-476-5

Publication date:

2025

Book Chapter

Chapter 3: Composition of Differential Privacy & Privacy Amplification by Subsampling

Thomas Steinke

Search for other works by this author on:

This Site

PubMed

Google Scholar

Author and Other Information

Thomas Steinke

2025

Ferdinando Fioretto and Pascal Van Hentenryck

This work is published under the terms of a non-commercial Creative Commons license (CC BY-NC), which permits use, distribution and reproduction in any medium, provided the original work is properly cited. The license enables reusers to distribute, remix, adapt, and build upon the material in any medium or format for noncommercial purposes only, and only so long as attribution is given to the creator. Further terms may be seen at: Link to the terms of the CC BY-NC license

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License .

Doi:

https://doi.org/10.1561/978-1-63828-477-220251005

Published:

2025

2025

Ferdinando Fioretto and Pascal Van Hentenryck

3.1 Introduction

Our data is subject to many different uses. Many entities will have access to our data, including government agencies, healthcare providers, employers, technology companies, and financial institutions. Those entities will perform many different analyses that involve our data and those analyses will be updated repeatedly over our lifetimes. The greatest risk to privacy is that an attacker will combine multiple pieces of information from the same or different sources and that the combination of these will reveal sensitive details about us. Thus we cannot study privacy leakage in a vacuum; it is important that we can reason about the accumulated privacy leakage over multiple independent analyses.

As a concrete example to keep in mind, consider the following simple differencing attack: Suppose your employer provides healthcare benefits. The employer pays for these benefits and thus may have access to summary statistics like how many employees are currently receiving pre-natal care or currently are being treated for cancer. Your pregnancy or cancer status is highly sensitive information, but intuitively the aggregated count is not sensitive as it is not specific to you. However, this count may be updated on a regular basis and your employer may notice that the count increased on the day you were hired or on the day you took off for a medical appointment. This example shows how multiple pieces of information – the date of your hire or medical appointment, the count before that date, and the count afterwards – can be combined to reveal sensitive information about you, despite each piece of information seeming innocuous on its own. Attacks could combine many different statistics from multiple sources and hence we need to be careful to guard against such attacks, which leads us to differential privacy.

Differential privacy has strong composition properties – if multiple independent analyses are run on our data and each analysis is differentially private on its own, then the combination of these analyses is also differentially private. This property is key to the success of differential privacy. Composition enables building complex differentially private systems out of simple differentially private subroutines. Composition allows the re-use data over time without fear of a catastrophic privacy failure. And, when multiple entities use the data of the same individuals, they do not need to coordinate to prevent an attacker from learning private details of individuals by combining the information released by those entities. To prevent the above differencing attack, we could independently perturb each count to make it differentially private; then taking the difference of two counts would be sufficiently noisy to obscure your pregnancy or cancer status.

Composition is quantitative. The differential privacy guarantee of the overall system will depend on the number of analyses and the privacy parameters that they each satisfy. The exact relationship between these quantities can be complex. There are various composition theorems that give bounds on the overall parameters in terms of the parameters of the parts of the system. In this chapter, we will study several composition theorems (including the relevant proofs) and we will also look at some examples that demonstrate how to apply the composition theorems and why we need them.

Composition theorems provide privacy bounds for a given system. A system designer must use composition theorems to design systems that simultaneously give good privacy and good utility (i.e., good statistical accuracy). This process often called “privacy budgeting” or “privacy accounting.” Intuitively, the system designer has some privacy constraint (i.e., the overall system must satisfy some final privacy guarantee) which can be viewed as analogous to a monetary budget that must be divided amongst the various parts of the system. Composition theorems provide the accounting rules for this budget. Allocating more of the budget to some part of the system makes that part more accurate, but then less budget is available for other parts of the system. Thus the system designer must also make a value judgement about which parts of the system to prioritize.

Overview of the Chapter

This chapter provides an in-depth discussion of composition theorems and privacy amplification techniques in Differential Privacy. It begins by introducing the basic composition theorem in Section 3.2, and examining whether basic composition strategies achieve optimal privacy guarantees. Next, in Section 3.3, it reviews the concept of privacy loss distributions and offers a statistical hypothesis testing perspective to understand approximate Differential Privacy. The chapter then discusses advanced composition via the privacy loss distribution, in Section 3.4, revisiting basic composition and exploring composition through Gaussian approximation. It reviews the notion of Concentrated Differential Privacy, adaptive composition, and post-processing, and examines the composition of approximate Differential Privacy. Then, the chapter focuses on privacy amplification by subsampling, in Section 3.6, covering subsampling techniques for pure and approximate Differential Privacy, the differences between addition/removal and replacement for neighboring datasets, and how subsampling interacts with composition. Here, the concept of Rényi Differential Privacy is introduced, along with analytic bounds for privacy amplification and practical guidance on the use of privacy amplification by subsampling in real-world applications. Finally, the chapter concludes, in Section 3.7, with a reflection on the historical development of the discussed concepts and provides further reading for a deeper understanding of these concepts.

3.2 Basic Composition

The simplest composition theorem is what is known as basic composition. This applies to pure ε-DP (although it can be extended to approximate (ε,δ)-DP). Basic composition says that, if we run k independent ε-DP algorithms, then the composition of these is kε-DP. More generally, we have the following result.

Theorem 3.1 (Basic Composition). Let $M_{1}, M_{2}, \dots, M_{k} : X^{n} \to Y$ be randomized algorithms. Suppose M_j is ε_j-DP for each j ∈ [k]. Define $M : X^{n} \to Y^{k}$ by M(x) = (M₁(x), M₂(x),…,M_k(x)), where each algorithm is run independently. Then M is ε-DP for $ε = \sum_{j = 1}^{k} ε_{j}$ ⁠.

Proof. Fix an arbitrary pair of neighboring datasets $x, x^{'} \in X^{n}$ and output $y \in Y^{k}$ ⁠. To establish that M is ε-DP, we must show that $e^{- ε} \leq \frac{ℙ [M (x) = y]}{ℙ [M (x^{'}) = y]} \leq e^{ε}$ ⁠. By independence, we have

\begin{matrix} \frac{ℙ [M (x) = y]}{ℙ [M (x^{'}) = y]} & = \frac{\prod_{j = 1}^{k} ℙ [M_{j} (x) = y_{j}]}{\prod_{j = 1}^{k} ℙ [M_{j} (x^{'}) = y_{j}]} \\ = \prod_{j = 1}^{k} \frac{ℙ [M_{j} (x) = y_{j}]}{ℙ [M_{j} (x^{'}) = y_{j}]} \leq \prod_{j = 1}^{k} e^{ε_{j}} = e^{\sum_{j = 1}^{k} ε_{j}} = e^{ε}, \end{matrix}

where the inequality follows from the fact that each M_j is ε_j-DP and, hence, $e^{- ε_{j}} \leq \frac{ℙ [M_{j} (x) = y_{j}]}{ℙ [M_{j} (x^{'}) = y_{j}]} \leq e^{ε_{j}}$ ⁠. Similarly, $\prod_{j = 1}^{k} \frac{ℙ [M_{j} (x) = y_{j}]}{ℙ [M_{j} (x^{'}) = y_{j}]} \geq \prod_{j = 1}^{k} e^{- ε_{j}}$ ⁠, which completes the proof.

Basic composition is already a powerful result, despite its simple proof; it establishes the versatility of differential privacy and allows us to begin reasoning about complex systems in terms of their building blocks. For example, suppose we have k functions $\begin{array}{l} f_{1}, \dots, f_{k} : X^{n} \to ℝ \end{array}$ each of sensitivity 1. For each j ∈ [k], we know that adding Laplace (1/ε) noise to the value of f_j(x) satisfies ε-DP. Thus, if we add independent Laplace (1/ε) noise to each value f_j(x) for all j ∈ [k], then basic composition tells us that releasing this vector of k noisy values satisfies kε−DP. If we want the overall system to be ε-DP, then we should add independent Laplace (k/ε) noise to each value f_j(x).

3.2.1 Is Basic Composition Optimal?

If we want to release k values each of sensitivity 1 (as above) and have the overall release be ε-DP, then, using basic composition, we can add Laplace (k/ε) noise to each value. The variance of the noise for each value is 2k²/ε³, so the standard deviation is $\sqrt{2} k / ε$ ⁠. In other words, the scale of the noise must grow linearly with the number of values k if the overall privacy and each value's sensitivity is fixed. It is natural to wonder whether the scale of the Laplace noise can be reduced by improving the basic composition result. We now show that this is not possible.

For each j ∈ [k], let $M_{j} : X^{n} \to ℝ$ be the algorithm that releases f_j(x) with Laplace (k/ε) noise added. Let $M : X^{n} \to ℝ^{k}$ be the composition of these k algorithms. Then M_j is ε/k-DP for each j ∈ [k] and basic composition tells us that M is ε-DP. The question is whether M satisfies a better DP guarantee than this – i.e., does M satisfy ε_*-DP for some ε_* < ε ? Suppose we have neighboring datasets $x, x^{'} \in X^{n}$ such that f_j(x) = f_j(x′) + 1 for each j ∈ [k]. Let y = (a,a,…,a) ∈ ℝ^k for some $a \geq \max_{j = 1}^{k} f_{j} (x)$ ⁠. Then

\begin{matrix} \frac{ℙ [M (x) = y]}{ℙ [M (x^{'}) = y]} & = \frac{\prod_{j = 1}^{k} ℙ [f_{j} (x) + Laplace (k / ε) = y_{j}]}{\prod_{j = 1}^{k} ℙ [f_{j} (x^{'}) + Laplace (k / ε) = y_{j}]} \\ = \prod_{j = 1}^{k} \frac{ℙ [Laplace (k / ε) = y_{j} - f_{j} (x)]}{ℙ [Laplace (k / ε) = y_{j} - f_{j} (x^{'})]} \\ = \prod_{j = 1}^{k} \frac{\frac{ε}{2 k} \exp (- \frac{ε}{k} | y_{j} - f_{j} (x) |)}{\frac{ε}{2 k} \exp (- \frac{ε}{k} | y_{j} - f_{j} (x^{'}) |)} \\ = \prod_{j = 1}^{k} \frac{\exp (- \frac{ε}{k} (y_{j} - f_{j} (x)))}{\exp (- \frac{ε}{k} (y_{j} - f_{j} (x^{'})))} (y_{j} \geq f_{j} (x) and y_{j} \geq f_{j} (x^{'})) \\ = \prod_{j = 1}^{k} \exp (\frac{ε}{k} (f_{j} (x) - f_{j} (x^{'}))) \\ = \exp (\frac{ε}{k} \sum_{j = 1}^{k} (f_{j} (x) - f_{j} (x^{'}))) = e^{ε} . \end{matrix}

This shows that basic composition is optimal. For this example, we cannot prove a better guarantee than what is given by basic composition.

Is there some other way to improve upon basic composition that circumvents this example? Note that we assumed that there are neighboring datasets $x, x^{'} \in X^{n}$ such that f_j(x) = f_j(x′) + 1 for each j ∈ [k]. In some settings, no such worst case datasets exist. In that case, instead of scaling the noise linearly with k, we can scale the Laplace noise according to the ℓ₁ sensitivity $Δ_{1} : = \sup_{\begin{matrix} x, x^{'} \in X^{n} \\ neighboring \end{matrix}} \sum_{j = 1}^{k} | f_{j} (x) - f_{j} (x^{'}) ∣$ ⁠.

Instead of adding assumptions to the problem, we will look more closely at the example above. We showed that there exists some output y ∈ ℝ^d such that $\frac{ℙ [M (x) = y]}{ℙ [M (x^{'}) = y]} = e^{ε}$ ⁠. However, such outputs y are very rare, as we require y_j ≥ max{f_j(x), f_j(x′)} for each j ∈ [k] where y_j = f_j(x)+ Laplace (k/ε). Thus, in order to observe an output y such that the likelihood ratio is maximal, all of the k Laplace noise samples must be positive, which happens with probability 2^−k. The fact that outputs y with maximal likelihood ratio are exceedingly rare turns out to be a general phenomenon and not specific to the example above.

Can we improve on basic composition if we only ask for a high probability bound? That is, instead of demanding $\frac{ℙ [M (x) = y]}{ℙ [M (x^{'}) = y]} \leq e^{ε_{*}}$ for all $y \in Y$ ⁠, we demand $\underset{Y \leftarrow M (x)}{ℙ} [\frac{ℙ [M (x) = Y]}{ℙ [M (x^{'}) = Y]} \leq e^{ε_{*}}] \geq 1 - δ$ for some 0 < δ ≪ 1. Can we prove a better bound ε_* < ε in this relaxed setting? The answer turns out to be yes.

The limitation of pure ε-DP is that events with tiny probability – which are negligible in real-world applications – can dominate the privacy analysis. This motivates us to move to relaxed notions of differential privacy, such as approximate (ε,δ)-DP and concentrated DP, which are less sensitive to low probability events. In particular, these relaxed notions of differential privacy allow us to prove quantitatively better composition theorems. The rest of this chapter develops this direction further.

3.3 Privacy Loss Distributions

Qualitatively, an algorithm $M : X^{n} \to Y$ is differentially private if, for all neighboring datasets $x, x^{'} \in X^{n}$ ⁠, the output distributions M(x) and M(x′) are “indistinguishable” or “close.” The key question is how do we quantify the closeness or indistinguishability of a pair of distributions?

Pure DP (a.k.a. pointwise DP) [DMNS06] uniformly bounds the likelihood ratio $- \frac{ℙ [M (x) = y]}{ℙ [M (x^{'}) = y]} \leq e^{ε}$ for all $y \in Y$ ⁠. As discussed at the end of the section on basic composition (Section 3.2), this can be too strong as the outputs y that maximize this likelihood ratio may be very rare.

We could also consider the total variation distance (a.k.a. statistical distance):

d_{TV} (M (x), M (x^{'})) : = \sup_{S \subset Y} (ℙ [M (x) \in S] - ℙ [M (x^{'}) \in S]) .

Another option would be the KL divergence (a.k.a. relative entropy). Both TV distance and KL divergence turn out to give poor privacy-utility tradeoffs; that is, to rule out bad algorithms M, we must set these parameters very small, but that also rules out all the good algorithms. Intuitively, both TV and KL are not sensitive enough to low-probability bad events (whereas pure DP is too sensitive). We need to introduce a parameter (δ) to determine what level of low probability events we can ignore.

Approximate (ε,δ)-DP [Dwo+06] is a combination of pure ε-DP and δ TV distance. Specifically, M is (ε,δ)-DP if, for all neighboring datasets $x, x^{'} \in X^{n}$ and all measurable $S \subset Y, ℙ [M (x) \in S] \leq e^{ε} \cdot ℙ [M (x^{'}) \in S] + δ$ ⁠. Intuitively, (ε,δ)-DP is like ε-DP except we can ignore events with probability ≤ δ. That is, δ represents a failure probability, so it should be small (e.g., δ ≤ 10⁻⁶), while ε can be larger (e.g., ε ≈ 1); having two parameters with very different values allows us to circumvent the limitations of either pure DP or TV distance as a similarity measure.

All of these options for quantifying indistinguishability can be viewed from the perspective of the privacy loss distribution. The privacy loss distribution also turns out to be essential to the analysis of composition. Approximate (ε,δ)-DP bounds are usually proved via the privacy loss distribution.

We now formally define the privacy loss distribution and relate it to the various quantities we have considered. Then, in Section 3.3.1, we will calculate the privacy loss distribution corresponding to the Gaussian mechanism, which is a particularly nice example. In the next Section 3.3.2, we explain how the privacy loss distribution arises naturally via statistical hypothesis testing. To conclude, in Section 3.3.3, we precisely relate the privacy loss back to approximate (ε,δ)-DP. In the next section (Section 3.4), we will use the privacy loss distribution as a tool to analyze composition.

Definition 3.2 (Privacy Loss Distribution). Let P and Q be two probability distributions on $Y$ ⁠. Define $f_{P ‖ Q} : Y \to ℝ$ by $f_{P ‖ Q} (y) = \log (P (y) / Q (y))$ ⁠.^ⁱThe privacy loss random variable is given by Z = f_P∥Q (Y) for Y ← P. The distribution of Z is denoted PrivLoss (P∥Q).

In the context of differential privacy, the distributions P = M(x) and Q = M(x′) correspond to the outputs of the algorithm M on neighboring inputs x,x′. Successfully distinguishing these distributions corresponds to learning some fact about an individual person's data. The randomness of the privacy loss random variable Z comes from the randomness of the algorithm M (e.g., added noise). Intuitively, the privacy loss tells us which input (x or x′) is more likely given the observed output (Y←M(⋅)). If Z > 0, then the hypothesis Y ← P = M(x) explains the observed output better than the hypothesis Y ← Q = M(x′) and vice versa. The magnitude of the privacy loss Z indicates how strong the evidence for this conclusion is. If Z = 0, both hypotheses explain the output equally well, but, if Z → ∞, then we can be nearly certain that the output came from P, rather than Q. A very negative privacy loss Z ≪ 0 means that the observed output Y ← P strongly supports the wrong hypothesis (i.e., Y ← Q).

As long as the privacy loss distribution is well-defined,^ⁱⁱ we can easily express almost all the quantities of interest in terms of it:

Pure ε-DP of M is equivalent to demanding that $\underset{Z \leftarrow PrivLoss (M (x) ‖ M (x^{'}))}{ℙ} [Z \leq ε] = 1$ for all neighboring x,x′.^ⁱⁱⁱ
The KL divergence is the expectation of the privacy loss: $D_{1} (P ‖ Q) : = \underset{Z \leftarrow PrivLoss (P ‖ Q)}{E} [Z]$ ⁠.^{^iv}
The TV distance is given by
$\begin{matrix} d_{TV} (P, Q) & = \underset{Z \leftarrow PrivLoss (P ‖ Q)}{E} [\max {0, 1 - \exp (- Z)}] \\ = \frac{1}{2} \underset{Z \leftarrow PrivLoss (P ‖ Q)}{E} [| 1 - \exp (- Z) |] . \end{matrix}$
Approximate (ε,δ)-DP of M is implied by $\underset{Z \leftarrow PrivLoss (M (x) ‖ M (x^{'}))}{ℙ} [Z \leq ε] \geq 1 - δ$ for all neighboring x,x′. So we should think of approximate DP as a tail bound on the privacy loss. To be precise, (ε,δ)-DP of M is equivalent to
$\underset{Z \leftarrow PrivLoss (M (x) ‖ M (x^{'}))}{E} [\max {0, 1 - \exp (ε - Z)}] \leq δ,$
for all neighboring x,x′. (See Proposition 3.7.)

3.3.1 Privacy Loss of Gaussian Noise Addition

As an example, we will work out the privacy loss distribution corresponding to the addition of Gaussian noise to a bounded-sensitivity query. This example is particularly clean, as the privacy loss distribution is also a Gaussian, and it will turn out to be central to the story of composition.

Proposition 3.3 (Privacy Loss Distribution of Gaussian). Let $P = N (μ, σ^{2})$ and $Q = N (μ^{'}, σ^{2})$ ⁠. Then $PrivLoss (P ‖ Q) = N (ρ, 2 ρ)$ for $ρ = \frac{{(μ - μ^{'})}^{2}}{2 σ^{2}}$ ⁠.

Proof. We have $P (y) = \frac{1}{\sqrt{2 π σ^{2}}} \exp (- \frac{{(y - μ)}^{2}}{2 σ^{2}})$ and $Q (y) = \frac{1}{\sqrt{2 π σ^{2}}} \exp (- \frac{{(y - μ^{'})}^{2}}{2 σ^{2}})$ ⁠. Thus the log likelihood ratio is

\begin{matrix} f_{P ∥ Q} (y) & = \log (\frac{P (y)}{Q (y)}) \\ = \log (\frac{\frac{1}{\sqrt{2 π σ^{2}}} \exp (- \frac{{(y - μ)}^{2}}{2 σ^{2}})}{\frac{1}{\sqrt{2 π σ^{2}}} \exp (- \frac{{(y - μ^{'})}^{2}}{2 σ^{2}})}) \\ = - \frac{{(y - μ)}^{2}}{2 σ^{2}} + \frac{{(y - μ^{'})}^{2}}{2 σ^{2}} \\ = \frac{(y^{2} - 2 μ^{'} y + μ^{' 2}) - (y^{2} - 2 μ y + μ^{2})}{2 σ^{2}} \\ = \frac{2 (μ - μ^{'}) y - μ^{2} + μ^{' 2}}{2 σ^{2}} \\ = \frac{(μ - μ^{'}) (2 y - μ - μ^{'})}{2 σ^{2}} . \end{matrix}

The log likelihood ratio f_P∥Q is an affine linear function. Thus the privacy loss random variable Z = f_P∥Q (Y) for $Y \leftarrow P = N (μ, σ^{2})$ will also follow a Gaussian distribution. Specifically, $E [Y] = μ$ ⁠, so

E [Z] = \frac{(μ - μ^{'}) (2 E [Y] - μ - μ^{'})}{2 σ^{2}} = \frac{{(μ - μ^{'})}^{2}}{2 σ^{2}} = ρ

and, similarly, $V [Y] = σ^{2}$ ⁠, so

V [Z] = \frac{({(2 (μ - μ^{'}))}^{2}}{{(2 σ^{2})}^{2}} \cdot V [Y] = \frac{{(μ - μ^{'})}^{2}}{σ^{2}} = 2 ρ .

To relate Proposition 3.3 to the standard Gaussian mechanism $M : X^{n} \to ℝ$ ⁠, recall that $M (x) = N (q (x), σ^{2})$ ⁠, where q is a sensitivity-Δ query – i.e., q(x) − q(x′)∣ ≤ Δ for all neighboring datasets $x, x^{'} \in X^{n}$ ⁠. Thus, for neighboring datasets x, x′, we have $PrivLoss (M (x) ‖ M (x^{'})) = N (ρ, 2 ρ)$ for some $ρ \leq \frac{Δ^{2}}{2 σ^{2}}$ ⁠.

The privacy loss of the Gaussian mechanism is unbounded; thus it does not satisfy pure ε-DP. However, the Gaussian distribution is highly concentrated, so we can say that with high probability the privacy loss is not too large. This is the basis of the privacy guarantee of the Gaussian mechanism.

3.3.2 Statistical Hypothesis Testing Perspective

To formally quantify differential privacy, we must measure the closeness or indistinguishability of the distributions P = M(x) and Q = M(x′) corresponding to the outputs of the algorithm M on neighboring inputs x,x′. Distinguishing a pair of distributions is precisely the problem of (simple) hypothesis testing in the field of statistical inference. Thus it is natural to look at hypothesis testing tools to quantify the (in)distinguishability of a pair of distributions.

In the language of hypothesis testing, the two distributions P and Q would be the null hypothesis and the alternate hypothesis, which correspond to a positive or negative example. We are given a sample Y drawn from one of the two distributions and our task is to determine which. Needless to say, there is, in general, no hypothesis test that perfectly distinguishes the two distributions and, when choosing a hypothesis test, we face a non-trivial tradeoff between false positives and false negatives. There are many different ways to measure how good a given hypothesis test is.

For example, we could measure the accuracy of the hypothesis test evenly averaged over the two distributions. In this case, given the sample Y, an optimal test chooses P if P(Y) ≥ Q(Y) and otherwise chooses Q; the accuracy of this test is

\frac{1}{2} \underset{Y \leftarrow P}{ℙ} [P (Y) \geq Q (Y)] + \frac{1}{2} \underset{Y \leftarrow Q}{ℙ} [P (Y) < Q (Y)] = \frac{1}{2} + \frac{1}{2} d_{TV} (P, Q) .

This measure of accuracy thus corresponds to TV distance. The greater the TV distance between the distributions, the more accurate this test is. However, as we mentioned earlier, TV distance does not yield good privacy-utility tradeoffs. Intuitively, the problem is that this hypothesis test doesn't care about how confident we are. That is, the test only asks whether P(Y) ≥ Q(Y), but not how big the difference or ratio is. Hence we want a more refined measure of accuracy that does not count false positives and false negatives equally.

Regardless of how we measure how good the hypothesis test is, there is an optimal test statistic, namely the log likelihood ratio. This test statistic gives a real number and thresholding that value yields a binary hypothesis test; any binary hypothesis test is dominated by some value of the threshold. In other words, the tradeoff between false positives and false negatives reduces to picking a threshold. This remarkable – yet simple – fact is established by the Neyman-Pearson lemma:

Lemma 3.4 (Neyman-Pearson Lemma [NP33]). Fix distributions P and Q on $Y$ and define the log-likelihood ratio test statistic $f_{P ‖ Q} : Y \to ℝ$ by $f_{P ‖ Q} (y) = \log (\frac{P (y)}{Q (y)})$ ⁠. Let $T : Y \to {P, Q}$ be any (possibly randomized) test. Then there exists some t ∈ ℝ such that

\begin{matrix} \underset{Y \leftarrow P}{ℙ} [T (Y) = P] \leq \underset{Y \leftarrow P}{ℙ} [f_{P ‖ Q} (Y) \geq t] a n d \\ \underset{Y \leftarrow Q}{ℙ} [T (Y) = Q] \leq \underset{Y \leftarrow Q}{ℙ} [f_{P ‖ Q} (Y) \leq t] . \end{matrix}

How is this related to the privacy loss distribution? The test statistic Z = f_P∥Q (Y) under the hypothesis Y ← P is precisely the privacy loss random variable Z ← PrivLoss (P∥Q. Thus the Neyman-Pearson lemma tells us that the privacy loss distribution PrivLoss (P∥Q) captures everything we need to know about distinguishing P from Q.

Note that the Neyman-Pearson lemma also references the test statistic f_P∥Q (Y) under the hypothesis Y ← Q. This is fundamentally not that different from the privacy loss. There are two ways we can relate this quantity back to the usual privacy loss: First, we can relate it to PrivLoss (Q∥P) and this distribution is something we should be able to handle due to the symmetry of differential privacy guarantees.

Remark 3.5.Fix distributions P and Q on $Y$ such that the log likelihood ratio $f_{P ‖ Q} (y) = \log (\frac{P (y)}{Q (y)})$ is well-defined for all $y \in Y$ ⁠. Since f_P∥Q (y) = −f_Q∥P (y) for all $y \in Y$ ⁠, if Z ← PrivLoss (Q∥P), then −Z follows the distribution of f_P∥Q (Y) under the hypothesis Y ← Q.

Second, if we need to compute an expectation of some function g of f_P∥Q (Y) under the hypothesis Y ← Q, then we can still express this in terms of the privacy loss PrivLoss (P∥Q) :

Lemma 3.6 (Change of Distribution for Privacy Loss). Fix distributions P and Q on $Y$ such that the log likelihood ratio $f_{P ‖ Q} (y) = \log (\frac{P (y)}{Q (y)})$ is well-defined for all $y \in Y$ ⁠. Let g:ℝ → ℝ be measurable. Then

\underset{Y \leftarrow Q}{E} [g (f_{P ‖ Q} (Y))] = \underset{Z \leftarrow PrivLoss (P ‖ Q)}{E} [g (Z) \cdot e^{- Z}] .

Proof. By the definition of the log likelihood ratio (see Definition 3.2), we have $\underset{Y \leftarrow P}{E} [h (Y)] = \underset{Y \leftarrow Q}{E} [h (Y) \cdot e^{f_{P ‖ Q} (Y)}]$ for all measurable functions h. Setting $h (y) = g (f_{P ‖ Q} (y)) \cdot e^{- f_{P ‖ Q} (y)}$ yields $\underset{Z \leftarrow P r i v L o s s (P ‖ Q)}{E} [g (Z) \cdot e^{- Z}] = \underset{Y \leftarrow P}{E} [h (Y)] = \underset{Y \leftarrow Q}{E} [h (Y) \cdot e^{f_{P ‖ Q} (Y)}] = \underset{Y \leftarrow Q}{E} [g (f_{P ‖ Q} (Y))]$ ⁠, as required. We can also write these expressions out as an integral to obtain a more intuitive proof:

\begin{matrix} \underset{Y \leftarrow Q}{E} [g (f_{P ‖ Q} (Y))] & = \int_{y} g (f_{P ‖ Q} (y)) \cdot Q (y) d y \\ = \int_{Y} g (f_{P ‖ Q} (y)) \cdot \frac{Q (y)}{P (y)} \cdot P (y) d y \\ = \int_{Y} g (f_{P ‖ Q} (y)) \cdot e^{- \log (P (y) / Q (y))} \cdot P (y) d y \\ = \int_{Y} g (f_{P ‖ Q} (y)) \cdot e^{- f_{P ‖ Q} (y)} \cdot P (y) d y \\ = \underset{Y \leftarrow P}{E} [g (f_{P ‖ Q} (Y)) \cdot e^{- f_{P ‖ Q} (Y)}] \\ = \underset{Z \leftarrow PrivLoss (P ‖ Q)}{E} [g (Z) \cdot e^{- Z}] . \end{matrix}

3.3.3 Approximate DP & the Privacy Loss Distribution

So far, in this section, we have defined the privacy loss distribution, given an example, and illustrated that it is a natural quantity to consider that captures essentially everything we need to know about the (in)distinguishability of two distributions. To wrap up this section, we will relate the privacy loss distribution back to the definition of approximate (ε,δ)-DP:

Proposition 3.7 (Conversion from Privacy Loss Distribution to Approximate Differential Privacy). Let P and Q be two probability distributions on $Y$ such that the privacy loss distribution PrivLoss (P∥Q) is well-defined. Fix ε ≥ 0 and define

δ : = \sup_{S \subset Y} P (S) - e^{ε} \cdot Q (S) .

Then

\begin{matrix} δ & = \underset{Z \leftarrow PrivLoss (P ‖ Q)}{ℙ} [Z > ε] - e^{ε} \cdot \underset{Z^{'} \leftarrow PrivLoss (Q ‖ P)}{ℙ} [- Z^{'} > ε] \\ = \underset{Z \leftarrow PrivLoss (P ‖ Q)}{E} [\max {0, 1 - \exp (ε - Z)}] \\ = \int_{ε}^{\infty} e^{ε - Z} \cdot \underset{Z \leftarrow PrivLoss (P ‖ Q)}{ℙ} [Z > z] d z \\ \leq \underset{Z \leftarrow PrivLoss (P ‖ Q)}{ℙ} [Z > ε] . \end{matrix}

Proof. For any measurable $S \subset Y$ ⁠, we have

P (S) - e^{ε} \cdot Q (S) = \int_{Y} I [y \in S] \cdot (P (y) - e^{ε} \cdot Q (y)) d y,

where $I$ denotes the indicator function – it takes the value 1 if the condition is true and 0 otherwise. To maximize this expression, we want y ∈ S whenever P(y)−e^ε. Q(y) > 0 and we want y ∉ S when this is negative. Thus δ = P(S_*) − e^ε⋅Q(S_*) for

S_{*} : = {y \in Y : P (y) - e^{ε} \cdot Q (y) > 0} = {y \in Y : f_{P ‖ Q} (y) > ε} .

Now

P (S_{*}) = \underset{Y \leftarrow P}{ℙ} [f_{P ‖ Q} (Y) > ε] = \underset{Z \leftarrow PrivLoss (P ‖ Q)}{ℙ} [Z > ε],

and, by Remark 3.5,

Q (S_{*}) = \underset{Y \leftarrow Q}{ℙ} [f_{P ‖ Q} (Y) > ε] = \underset{Z^{'} \leftarrow PrivLoss (Q ‖ P)}{ℙ} [- Z^{'} > ε] .

This gives the first expression in the result:

δ = P (S_{*}) - e^{ε} \cdot Q (S_{*}) = \underset{Z \leftarrow PrivLoss (P ‖ Q)}{ℙ} [Z > ε] - e^{ε} \cdot \underset{Z^{'} \leftarrow PrivLoss (Q ‖ P)}{ℙ} [- Z^{'} > ε] .

Alternatively, $P (S_{*}) = \underset{Z \leftarrow PrivLoss (P ‖ Q)}{E} [I [Z > ε]]$ and, by Lemma 3.6,

Q (S_{*}) = \underset{Y \leftarrow Q}{E} [I [f_{P ‖ Q} (Y) > ε]] = \underset{Z \leftarrow PrivLoss (P ‖ Q)}{E} [I [Z > ε] \cdot e^{- Z}],

which yields

δ = P (S_{*}) - e^{ε} \cdot Q (S_{*}) = \underset{Z \leftarrow PrivLoss (P ‖ Q)}{E} [(1 - e^{ε} \cdot e^{- Z}) \cdot I [Z > ε]] .

Note that $(1 - e^{ε} \cdot e^{- z}) \cdot I [z > ε] = \max {0, 1 - e^{ε - z}}$ for all z ∈ ℝ. This produces the second expression in our result.

To obtain the third expression in the result, we apply integration by parts to the second expression: Let $F (z) : = \underset{Z \leftarrow PrivLoss (P ‖ Q)}{ℙ} [Z > z]$ be the complement of the cumulative distribution function of the privacy loss distribution. Then the probability density function of Z evaluated at z is given by the negative derivative, −F′(z).^{^v} Then

\begin{matrix} δ & = \underset{Z \leftarrow PrivLoss (P ‖ Q)}{E} [\max {0, 1 - e^{ε - Z}}] \\ = \int_{ℝ} \max {0, 1 - e^{ε - z}} \cdot (- F^{'} (z)) d z \\ = \int_{ε}^{\infty} (1 - e^{ε - z}) \cdot (- F^{'} (z)) d z \\ = \int_{ε}^{\infty} (\frac{d}{d z} (1 - e^{ε - z}) \cdot (- F (z))) - (0 - e^{ε - z} \cdot (- 1)) \cdot (- F (z)) d z (product rule) \\ = \lim_{z \to \infty} (1 - e^{ε - z}) \cdot (- F (z)) - (1 - e^{ε - ε}) \cdot (- F (ε)) - \int_{ε}^{\infty} e^{ε - z} \cdot (- F (z)) d z (fundamental theorem of calculus) \\ = - \lim_{z \to \infty} \underset{Z \leftarrow PrivLoss (P ‖ Q)}{ℙ} [Z > z] + \int_{ε}^{\infty} e^{ε - z} \cdot \underset{Z \leftarrow PrivLoss (P ‖ Q)}{ℙ} [Z > z] d z . \end{matrix}

If the privacy loss is well-defined, then $\lim_{z \to \infty} \underset{Z \leftarrow PrivLoss (P ‖ Q)}{ℙ} [Z > z] = 0$ ⁠.

The final expression (an upper bound, rather than a tight characterization) is easily obtained from any of the other three expressions. In particular, dropping the second term $- e^{ε} \cdot \underset{Z^{'} \leftarrow PrivLoss (Q ‖ P)}{ℙ} [- Z^{'} > ε] \leq 0$ from the first expression yields the upper bound.

The expression $δ = \sup_{S \subset Y} P (S) - e^{ε} \cdot Q (S)$ in Proposition 3.7 is known as the “hockey stick divergence” and it determines the smallest δ for a given ε such that P(S) ≤ e^εQ(S) + δ for all $s \subset Y$ ⁠. If P = M(x) and Q = M(x′) for arbitrary neighboring datasets x,x′, then this expression gives the best approximate (ε,δ)-DP guarantee.

Proposition 3.7 gives us three equivalent ways to calculate δ, each of which will be useful in different circumstances. To illustrate how to use Proposition 3.7, we combine it with Proposition 3.3 to prove a tight approximate differential privacy guarantee for Gaussian noise addition:

Corollary 3.8 (Tight Approximate Differential Privacy for Univariate Gaussian). Let $q : X^{n} \to ℝ$ be a deterministic function and let $Δ : = \sup_{\begin{matrix} x, x^{'} \in X^{n} \\ neighboring \end{matrix}} ∣ q (x) - q (x^{'}) ∣$ be its sensitivity. Define a randomized algorithm $M : X^{n} \to ℝ$ by $M (x) = N (q (x), σ^{2})$ for some σ² > 0. Then, for any ε ≥ 0, M satisfies (ε, δ)-DP with

δ = \bar{Φ} (\frac{ε - ρ_{*}}{\sqrt{2 ρ_{*}}}) - e^{ε} \cdot \bar{Φ} (\frac{ε + ρ_{*}}{\sqrt{2 ρ_{*}}}),

where ρ_* := Δ²/2σ² and $\bar{Φ} (z) : = \underset{G \leftarrow N (0, 1)}{ℙ} [G > z] = \frac{1}{\sqrt{2 π}} \int_{z}^{\infty} \exp (- t^{2} / 2) d t$ ⁠.

Furthermore, this guarantee is optimal – for every ε ≥ 0, there is no δ′ < δ such that M is (ε, δ′)-DP for general q.

Proof. Fix arbitrary neighboring datasets $x, x^{'} \in X^{n}$ and $S \subset Y$ ⁠. Let μ = q(x) and μ′ = q(x′). Let $P = M (x) = N (μ, σ^{2})$ and $Q = M (x^{'}) = N (μ^{'}, σ^{2})$ ⁠. We must show P(S) ≤ e^ε ⋅ Q(S) + δ for arbitrary ε ≥ 0 and the value δ given in the result.

By Proposition 3.3, $PrivLoss (P ‖ Q) = PrivLoss (Q ‖ P) = N (ρ, 2 ρ)$ ⁠, where $ρ = \frac{{(μ - μ^{'})}^{2}}{2 σ^{2}} \leq ρ_{*} = \frac{Δ^{2}}{2 σ^{2}}$ ⁠.

By Proposition 3.7, we have P(S) ≤ e^ε ⋅ Q(S) + δ, where

\begin{matrix} δ & = \underset{Z \leftarrow PrivLoss (P ‖ Q)}{ℙ} [Z > ε] - e^{ε} \cdot \underset{Z^{'} \leftarrow PrivLoss (Q ‖ P)}{ℙ} [- Z^{'} > ε] \\ = \underset{Z \leftarrow N (ρ, 2 ρ)}{ℙ} [Z > ε] - e^{ε} \cdot \underset{Z^{'} \leftarrow N (ρ, 2 ρ)}{ℙ} [- Z^{'} > ε] \\ = \underset{G \leftarrow N (0, 1)}{ℙ} [ρ + \sqrt{2 ρ} \cdot G > ε] - e^{ε} \cdot \underset{G \leftarrow N (0, 1)}{ℙ} [- ρ + \sqrt{2 ρ} \cdot G > ε] \\ = \underset{G \leftarrow N (0, 1)}{ℙ} [G > \frac{ε - ρ}{\sqrt{2 ρ}}] - e^{ε} \cdot \underset{G \leftarrow N (0, 1)}{ℙ} [G > \frac{ε + ρ}{\sqrt{2 ρ}}] \\ = \bar{Φ} (\frac{ε - ρ}{\sqrt{2 ρ}}) - e^{ε} \cdot \bar{Φ} (\frac{ε + ρ}{\sqrt{2 ρ}}) . \end{matrix}

Since ρ ≤ ρ_* and the above expression is increasing in ρ, we can substitute in ρ_* as an upper bound.

Optimality follows from the fact that both Propositions 3.3 and 3.7 give exact characterizations. Note that we must assume that there exist neighboring x,x′ such that ρ = ρ_*.

The guarantee of Corollary 3.8 is exact, but it is somewhat hard to interpret. We can easily obtain a more interpretable upper bound:

\begin{matrix} δ & = \bar{Φ} (\frac{ε - ρ_{*}}{\sqrt{2 ρ_{*}}}) - e^{ε} \cdot \bar{Φ} (\frac{ε + ρ_{*}}{\sqrt{2 ρ_{*}}}) \\ \leq \bar{Φ} (\frac{ε - ρ_{*}}{\sqrt{2 ρ_{*}}}) = \underset{G \leftarrow N (0, 1)}{ℙ} [G > \frac{ε - ρ_{*}}{\sqrt{2 ρ_{*}}}] \\ \leq \frac{\exp (- \frac{{(ε - ρ_{*})}^{2}}{4 ρ_{*}})}{\max {2, \sqrt{\frac{π}{ρ_{*}}} \cdot (ε - ρ_{*})}} . (assuming ε \geq ρ_{*}) \end{matrix}

3.4 Composition via the Privacy Loss Distribution

The privacy loss distribution captures essentially everything about the (in)distinguishability of a pair of distributions. It is also the key to understanding composition. Suppose we run multiple differentially private algorithms on the same dataset and each has a well-defined privacy loss distribution. The composition of these algorithms corresponds to the convolution of the privacy loss distributions. That is, the privacy loss random variable corresponding to running all of the algorithms independently is equal to the sum of the independent privacy loss random variables of each of the algorithms:

Theorem 3.9 (Composition is Convolution of Privacy Loss Distributions). For each j ∈ [k], let P_j and Q_j be distributions on $Y_{j}$ and assume PrivLoss (P_j∥Q_j) is well defined. Let P = P₁ × P₂ × … × P_k denote the product distribution on $Y = Y_{1} \times Y_{2} \times \dots \times Y_{k}$ obtained by sampling independently from each P_j. Similarly, let Q = Q₁ × Q₂ × … × Q_k denote the product distribution on $Y$ obtained by sampling independently from each Q_j. Then PrivLoss (P∥Q) is the convolution of the distributions PrivLoss (P_j∥Q_j) for all j ∈ [k]. That is, sampling Z ← PrivLoss(P∥Q) is equivalent to $Z = \sum_{j = 1}^{k} Z_{j}$ when Z_j ← PrivLoss(P_j∥Q_j) independently for each j ∈ [k].

Proof. For all $y \in Y$ ⁠, the log likelihood ratio (Definition 3.2) satisfies

\begin{matrix} f_{P ‖ Q} (y) & = \log (\frac{P (y)}{Q (y)}) \\ = \log (\frac{P_{1} (y_{1}) \cdot P_{2} (y_{2}) \dots \dots P_{k} (y_{k})}{Q_{1} (y_{1}) \cdot Q_{2} (y_{2}) \dots \dots Q_{k} (y_{k})}) \\ = \log (\frac{P_{1} (y_{1})}{Q_{1} (y_{1})}) + \log (\frac{P_{2} (y_{2})}{Q_{2} (y_{2})}) + \dots + \log (\frac{P_{k} (y_{k})}{Q_{k} (y_{k})}) \\ = f_{P_{1} ‖ Q_{1}} (y_{1}) + f_{P_{2} ‖ Q_{2}} (y_{2}) + \dots + f_{P_{k} ‖ Q_{k}} (y_{k}) . \end{matrix}

Since P is a product distribution, sampling Y ← P is equivalent to sampling Y₁ ← P₁, Y₂ ← P₂,…, Y_k ← P_k independently.

A sample from the privacy loss distribution Z ← PrivLoss(P∥Q) is given by Z = f_P∥Q (Y) for Y ← P. By the above two facts, this is equivalent to $Z = f_{P_{1} ‖ Q_{1}} (Y_{1}) + f_{P_{2} ‖ Q_{2}} (Y_{2}) + \dots + f_{P_{k} ‖ Q_{k}} (Y_{k})$ for Y₁ ← P₁, Y₂ ← P₂,…, Y_k ← P_k independently. For each j ∈ [k], sampling Z_j ← PrivLoss(P_j∥Q_j) is given by $Z_{j} = f_{P_{j} ‖ Q_{j}} (Y_{j})$ for Y_j ← P_j. Thus sampling Z ← PrivLoss (P∥Q) is equivalent to Z = Z₁ + Z₂ + … + Z_k where Z₁ ← PrivLoss(P₁∥Q₁), Z₂ ← PrivLoss(P₂∥Q₂),…, Z_k ← PrivLoss(P_k∥Q_k) are independent.

Theorem 3.9 is the key to understanding composition of differential privacy. More concretely, we should think of a pair of neighboring inputs x,x′ and k algorithms M₁,…, M_k. Suppose M is the composition of M₁,…, M_k. Then the the differential privacy of M can be expressed in terms of the privacy loss distribution PrivLoss (M(x)∥M(x′)). Theorem 3.9 allows us to decompose this privacy loss as the sum/convolution of the privacy losses of the constituent algorithms PrivLoss (M_j(x)∥M_j(x′)) for j ∈ [k]. Thus if we have differential privacy guarantees for each M_j, this allows us to prove differential privacy guarantees for M.

Basic Composition, Revisited

We can revisit basic composition (Theorem 3.1 in Section 3.2) with the perspective of privacy loss distributions. Suppose $M_{1}, M_{2}, \dots, M_{k} : X^{n} \to Y$ are each ε-DP. Fix neighboring datasets $x, x^{'} \in X^{n}$ ⁠. This means that $\underset{Z_{j} \leftarrow PrivLoss (M_{j} (x) ‖ M_{j} (x^{'}))}{ℙ} [Z_{j} \leq ε] = 1$ for each j ∈ [k]. Now let $M : X^{n} \to Y^{k}$ be the composition of these algorithms. We can express the privacy loss Z ← PrivLoss(M(x)∥M(x′)) as Z = Z₁ + Z₂ + … + Z_k where Z_j ← PrivLoss (M_j(x)∥M_j(x′)) for each j ∈ [k]. Basic composition simply adds up the upper bounds:

Z = Z_{1} + Z_{2} + \dots + Z_{k} \leq ε + ε + \dots + ε = k ε .

This bound is tight if each Z_j is a point mass (i.e., $ℙ [Z_{j} = ε] = 1$ ⁠). However, this is not the case. (It is possible to prove, in general, that $ℙ [Z_{j} = ε] \leq \frac{1}{1 + e^{- ε}}$ ⁠.) The way we will prove better composition bounds is by applying concentration of measure bounds to this sum of independent random variables. That way we can prove that the privacy loss is small with high probability, which yields a better differential privacy guarantee.

Intuitively, we will apply the central limit theorem. The privacy loss random variable of the composed algorithm M can be expressed as the sum of independent bounded random variables. That means the privacy loss distribution PrivLoss (M(x)∥M(x′)) is well-approximated by a Gaussian, which is the information we need to prove a composition theorem. What is left to do is to obtain bounds on the mean and variance of the summands and make this Gaussian approximation precise.

Gaussian Composition

It is instructive to look at composition when each constituent algorithm M_j is the Gaussian noise addition mechanism. In this case the privacy loss distribution is exactly Gaussian and convolutions of Gaussians are also Gaussian. This is the ideal case and our general composition theorem will be an approximation to this ideal.

Specifically, we can prove a multivariate analog of Corollary 3.8:

Corollary 3.10 (Tight Approximate Differential Privacy for Multivariate Gaussian). Let $q : X^{n} \to ℝ^{d}$ be a deterministic function and let $Δ : = \sup_{\begin{matrix} x, x^{'} \in X^{n} \\ n e i g h b o r i n g \end{matrix}} ‖ q (x) - q (x^{'}) ‖_{2}$ be its sensitivity in the 2-norm. Define a randomized algorithm $M : X^{n} \to ℝ^{d}$ by $M (x) = N (q (x), σ^{2} I)$ for some σ² > 0, where I is the identity matrix. Then, for any ε ≥ 0, M satisfies (ε, δ)-DP with

δ = \bar{Φ} (\frac{ε - ρ_{*}}{\sqrt{2 ρ_{*}}}) - e^{ε} \cdot \bar{Φ} (\frac{ε + ρ_{*}}{\sqrt{2 ρ_{*}}}),

where ρ_* := Δ²/2σ²and $\bar{Φ} (z) : = \underset{G \leftarrow N (0, 1)}{ℙ} [G > z] = \frac{1}{\sqrt{2 π}} \int_{z}^{\infty} \exp (- t^{2} / 2) d t$ ⁠.

Furthermore, this guarantee is optimal – for every ε ≥ 0, there is no δ′ < δ such that M is (ε, δ′)-DP for general q.

Proof. Fix arbitrary neighboring datasets $x, x^{'} \in X^{n}$ and $S \subset Y$ ⁠. Let μ = q(x) and μ′ = q(x′) ∈ ℝ^d. Let $P = M (x) = N (μ, σ^{2} I)$ and $Q = M (x^{'}) = N (μ^{'}, σ^{2} I)$ ⁠. We must show P(S) ≤ e^ε⋅Q(S) + δ for arbitrary ε ≥ 0 and the value δ given in the result.

Now both P and Q are product distributions: For j ∈ [d], let $P_{j} = N (μ_{j}, σ^{2})$ and $Q_{j} = N (μ_{j}^{'}, σ^{2})$ ⁠. Then P = P₁ × P₂ × … P_d and Q = Q₁ × Q₂ × …× Q_d.

By Theorem 3.9, $PrivLoss (P ∥ Q) = \sum_{j = 1}^{d} PrivLoss (P_{j} ∥ Q_{j})$ and $PrivLoss (Q ∥ P) = \sum_{j = 1}^{d} PrivLoss (Q_{j} ∥ P_{j})$ ⁠.

By Proposition 3.3, $PrivLoss (P_{j} ∥ Q_{j}) = PrivLoss (Q_{j} ∥ P_{j}) = N (ρ_{j}, 2 ρ_{j})$ ⁠, where $ρ_{j} = \frac{{(μ_{j} - μ_{j}^{'})}^{2}}{2 σ^{2}}$ for all j ∈ [d].

Thus $PrivLoss (P ∥ Q) = PrivLoss (Q ∥ P) = \sum_{j = 1}^{d} N (ρ_{j}, 2 ρ_{j}) = N (ρ, 2 ρ)$ ⁠, where $ρ = \sum_{j = 1}^{d} ρ_{j} = \frac{{‖ μ - μ^{'} ‖}_{2}^{2}}{2 σ^{2}} \leq ρ_{*} = \frac{Δ^{2}}{2 σ^{2}}$ ⁠.

By Proposition 3.7, we have P(S) ≤ e^ε⋅Q(S) + δ, where

\begin{matrix} δ & = \underset{Z \leftarrow PrivLoss (P ‖ Q)}{ℙ} [Z > ε] - e^{ε} \cdot \underset{Z^{'} \leftarrow PrivLoss (Q ‖ P)}{ℙ} [- Z^{'} > ε] \\ = \underset{Z \leftarrow N (ρ, 2 ρ)}{ℙ} [Z > ε] - e^{ε} \cdot \underset{Z^{'} \leftarrow N (ρ, 2 ρ)}{ℙ} [- Z^{'} > ε] \\ = \underset{G \leftarrow N (0, 1)}{ℙ} [ρ + \sqrt{2 ρ} \cdot G > ε] - e^{ε} \cdot \underset{G \leftarrow N (0, 1)}{ℙ} [- ρ + \sqrt{2 ρ} \cdot G > ε] \\ = \underset{G \leftarrow N (0, 1)}{ℙ} [G > \frac{ε - ρ}{\sqrt{2 ρ}}] - e^{ε} \cdot \underset{G \leftarrow N (0, 1)}{ℙ} [G > \frac{ε + ρ}{\sqrt{2 ρ}}] \\ = \bar{Φ} (\frac{ε - ρ}{\sqrt{2 ρ}}) - e^{ε} \cdot \bar{Φ} (\frac{ε + ρ}{\sqrt{2 ρ}}) . \end{matrix}

Since ρ ≤ ρ_* and the above expression is increasing in ρ, we can substitute in ρ_* as an upper bound.

Optimality follows from the fact that Propositions 3.3 and 3.7 and Theorem 3.9 give exact characterizations. Note that we must assume that there exist neighboring x,x′ such that ρ = ρ_*.

The key to the analysis of Gaussian composition in the proof of Corollary 3.10 is that sums of Gaussians are Gaussian. In general, the privacy loss of each component is not Gaussian, but the sum still behaves much like a Gaussian and this observation is the basis for improving the composition analysis.

Composition Via Gaussian Approximation

After analyzing Gaussian composition, our next step is to analyze the composition of k independent ε-DP algorithms. We will use the same tools as we did for Gaussian composition and we will develop a new tool, which is called concentrated differential privacy.

Let $M_{1}, \dots, M_{k} : X^{n} \to Y$ each be ε-DP and let $M : X^{n} \to Y^{k}$ be the composition of these algorithms. Let $x, x^{'} \in X^{n}$ be neighboring datasets. For notational convenience, let P_j = M_j(x) and Q_j = M_j(x′) for all j ∈ [k] and let P = M(x) = P₁ × P₂ × … × P_k and Q = M(x′) = Q₁ × Q₂ × … × Q_k.

For each j ∈ [k], the algorithm M_j satisfies ε-DP, which ensures that the privacy loss random variable Z_j ← PrivLoss(P_j∥Q_j) = PrivLoss(M_j(x)∥M_j(x′)) is supported on the interval [−ε, ε]. The privacy loss being bounded immediately implies a bound on the variance: $V [Z_{j}] \leq E [Z_{j}^{2}] \leq ε^{2}$ ⁠. We also can prove a bound on the expectation: $E [Z_{j}] \leq \frac{1}{2} ε^{2}$ ⁠. We will prove this bound formally later (in Proposition 3.16). For now, we give some intuition: Clearly $E [Z_{j}] \leq ε$ and the only way this can be tight is if Z_j = ε with probability 1. But Z_j = log(P_j(Y_j)/Q_j(Y_j)) for Y_j ← P_j. Thus $E [Z_{j}] = ε$ implies P_j(Y_j) = e^ε ⋅ Q_j(Y_j) with probability 1. This yields a contradiction: $1 = \sum_{y} P_{j} (y) = \sum_{y} e^{ε} \cdot Q_{j} (y) = e^{ε} \cdot 1$ ⁠. Thus we conclude $E [Z_{j}] < ε$ and, with a bit more work, we can obtain the bound $E [Z_{j}] \leq \frac{1}{2} ε^{2}$ from the fact that |Z_j| ≤ ε and $\sum_{y} P_{j} (y) = \sum_{y} Q_{j} (y) = 1$ ⁠.

Our goal is to understand the privacy loss Z ← PrivLoss(P∥Q) = PrivLoss (M(x)∥M(x′)) of the composed algorithm. Theorem 3.9 tells us that this is the convolution of the constituent privacy losses. That is, we can write $Z = \sum_{j = 1}^{k} Z_{j}$ where Z_j ← PrivLoss(P_j∥Q_j) = PrivLoss(M_j(x)∥M_j(x′)) independently for each j ∈ [k].

By independence, we have

E [Z] = \sum_{j = 1}^{k} E [Z_{j}] \leq \frac{1}{2} ε^{2} \cdot k and V [Z] = \sum_{j = 1}^{k} V [Z_{j}] \leq ε^{2} \cdot k .

Since Z can be written as the sum of independent bounded random variables, the central limit theorem tells us that it is well approximated by a Gaussian – i.e.,

PrivLoss (P ‖ Q) = PrivLoss (M (x) ‖ M (x^{'})) \approx N (E [Z], V [Z]) .

Are we done? Can we substitute this approximation into Proposition 3.7 to complete the proof of a better composition theorem? We must make this approximation precise. Unfortunately, the approximation guarantee of the quantitative central limit theorem (a.k.a., the Berry-Esseen Theorem) is not quite strong enough. To be precise, converting the guarantee to approximate (ε,δ)-DP would incur an error of $δ \geq Ω (1 / \sqrt{k})$ ⁠, which is larger than we want.

Our approach is to look at the moment generating function – i.e., the expectation of an exponential function – of the privacy loss distribution. To be precise, we will show that, for all t ≥ 0,

\begin{matrix} \underset{Z \leftarrow PrivLoss (P ‖ Q)}{E} [\exp (t Z)] & = \prod_{j = 1}^{k} \underset{Z_{j} \leftarrow PrivLoss (P_{j} ‖ Q_{j})}{E} [\exp (t Z_{j})] \\ \leq \exp (\frac{1}{2} ε^{2} t (t + 1) \cdot k) \\ = \underset{\tilde{Z} \leftarrow N (\frac{1}{2} ε^{2} k, ε^{2} k)}{E} [\exp (t \tilde{Z})] . \end{matrix}

In other words, rather than attempting to prove a Gaussian approximation, we prove a one-sided bound. Informally, this says that PrivLoss $(P ‖ Q) \leq N (\frac{1}{2} ε^{2} k, ε^{2} k)$ ⁠. The expectation of an exponential function turns out to be a nice way to formalize this inequality, because, if X and Y are independent, then $E [\exp (X + Y)] = E [\exp (X)] \cdot E [\exp (Y)]$ ⁠.

To formalize this approach, we next introduce concentrated differential privacy.

3.4.1 Concentrated Differential Privacy

Concentrated differential privacy [DR16; BS16] is a variant of differential privacy (like pure DP and approximate DP). The main advantage of concentrated DP is that it composes well. Thus we will use it as a tool to prove better composition results.

Definition 3.11 (Concentrated Differential Privacy). Let $M : X^{n} \to Y$ be a randomized algorithm. We say that M satisfies ρ-concentrated differential privacy (ρ−zCDP) if, for all neighboring inputs $x, x^{'} \in X^{n}$ ⁠, the privacy loss distribution PrivLoss (M(x)∥M(x′)) is well-defined (see Definition 3.2) and

\forall t \geq 0 \underset{Z \leftarrow PrivLoss (M (x) ‖ M (x^{'}))}{E} [\exp (t Z)] \leq \exp (t (t + 1) \cdot ρ) .

To contextualize this definition, we begin by showing that the Gaussian mechanism satisfies it.

Lemma 3.12 (Gaussian Mechanism is Concentrated DP). Let $q : X^{n} \to ℝ^{d}$ have sensitivity Δ – that is, ‖q(x)−q(x′)‖₂ ≤ Δ for all neighboring $x, x^{'} \in X^{n}$ ⁠. Let σ > 0. Define a randomized algorithm $M : X^{n} \to ℝ^{d}$ by $M (x) = N (q (x), σ^{2} I_{d})$ ⁠. Then M is ρ-zCDP for $ρ = \frac{Δ^{2}}{2 σ^{2}}$ ⁠.

Proof. Fix neighboring inputs $x, x^{'} \in X^{n}$ and t ≥ 0. By Proposition 3.3, for each j ∈ [d], $PrivLoss (M {(x)}_{j} ‖ M {(x^{'})}_{j}) = N ({\hat{ρ}}_{j}, 2 {\hat{ρ}}_{j})$ for ${\hat{ρ}}_{j} = \frac{{(q {(x)}_{j} - q {(x^{'})}_{j})}^{2}}{2 σ^{2}}$ ⁠. By Theorem 3.9, $PrivLoss (M (x) ‖ M (x^{'})) = \sum_{j = 1}^{d} N ({\hat{ρ}}_{j}, 2 {\hat{ρ}}_{j}) = N (\hat{ρ}, 2 \hat{ρ})$ for $\hat{ρ} = \sum_{j = 1}^{d} {\hat{ρ}}_{j} = \frac{{‖ q (x) - q (x^{'}) ‖}_{2}^{2}}{2 σ^{2}} \leq ρ$ ⁠. Thus $\underset{Z \leftarrow PrivLoss (M (x) ‖ M (x^{'}))}{E} [\exp (t Z)] = \exp (t (t + 1) \hat{ρ}) \leq \exp (t (t + 1) ρ)$ ⁠, as required.

To analyze the composition of k independent ε-DP algorithms, we will prove three results: (i) Pure ε-DP implies $\frac{1}{2} ε^{2}$ -zCDP. (ii) The composition of k independent $\frac{1}{2} ε^{2}$ -zCDP algorithms satisfies $\frac{1}{2} ε^{2} k$ -zCDP. (iii) $\frac{1}{2} ε^{2} k$ -zCDP implies approximate (ε′,δ)-DP with δ ∈ (0,1) arbitrary and $ε^{'} = ε \cdot \sqrt{2 k \log (1 / δ)} + \frac{1}{2} ε^{2} k$ ⁠. We begin with composition, as this is the raison d'être for concentrated DP:

Theorem 3.13 (Composition for Concentrated Differential Privacy). Let $M_{1}, M_{2}, \dots, M_{k} : X^{n} \to Y$ be randomized algorithms. Suppose M_j is ρ_j−zCDP for each j ∈ [k]. Define $M : X^{n} \to Y^{k}$ by M(x) = (M₁(x),M₂(x),…, M_k(x)), where each algorithm is run independently. Then M is ρ−zCDP for $ρ = \sum_{j = 1}^{k} ρ_{j}$ ⁠.

Proof. Fix neighboring inputs $x, x^{'} \in X^{n}$ ⁠. By our assumption that each algorithm M_j is ρ_j-zCDP,

\forall t \geq 0 \underset{Z_{j} \leftarrow PrivLoss (M_{j} (x) ‖ M_{j} (x^{'}))}{E} [\exp (t Z_{j})] \leq \exp (t (t + 1) \cdot ρ_{j}) .

By Theorem 3.9, Z ← PrivLoss(M(x)∥M(x′)) can be written as $Z = \sum_{j = 1}^{k} Z_{j}$ ⁠, where Z_j ← PrivLoss(M_j(x)∥M_j(x′)) independently for each j ∈ [k].

Thus, for any t ≥ 0, we have

\begin{matrix} \underset{Z \leftarrow PrivLoss (M (x) ‖ M (x^{'}))}{E} [\exp (t Z)] & = \underset{\forall j \in [k] Z_{j} \leftarrow \underset{independent}{PrivLoss} (M_{j} (x) ‖ M_{j} (x^{'}))}{E} [\exp (t \sum_{j = 1}^{k} Z_{j})] \\ = \prod_{j = 1}^{k} \underset{Z_{j} \leftarrow PrivLoss (M_{j} (x) ‖ M_{j} (x^{'}))}{E} [\exp (t Z_{j})] \\ \leq \prod_{j = 1}^{k} \exp (t (t + 1) \cdot ρ_{j}) \\ = \exp (t (t + 1) \cdot \sum_{j = 1}^{k} ρ_{j}) \\ = \exp (t (t + 1) \cdot ρ) . \end{matrix}

Since x and x′ were arbitrary, this proves that M satisfies ρ-zCDP, as required.

Next we show how to convert from concentrated DP to approximate DP, which applies the tools we developed earlier.

Proposition 3.14 (Conversion from Concentrated DP to Approximate DP). For any $M : X^{n} \to Y$ and any ε, t ≥ 0, M satisfies (ε,δ)-DP with

\begin{matrix} δ & = \underset{\sup_{\begin{matrix} x, x^{'} \in X^{n} \\ neighboring \end{matrix}} Z \leftarrow PrivLoss (M (x) ‖ M (x^{'}))}{E} [\exp (t Z)] \cdot \frac{\exp (- ε t)}{t + 1} \cdot {(1 - \frac{1}{t + 1})}^{t} \\ \leq \underset{\sup_{\begin{matrix} x, x^{'} \in X^{n} \\ neighboring \end{matrix}} Z \leftarrow PrivLoss (M (x) ‖ M (x^{'}))}{E} [\exp (t (Z - ε))] . \end{matrix}

In particular, if M satisfies ρ−zCDP, then M satisfies (ε, δ)−DP for any ε ≥ ρ with

\begin{matrix} δ & = \inf_{t > 0} \exp (t (t + 1) ρ - ε t) \cdot \frac{1}{t + 1} \cdot {(1 - \frac{1}{t + 1})}^{t} \\ \leq \exp (- {(ε - ρ)}^{2} / 4 ρ) . \end{matrix}

Proof. Fix arbitrary neighboring inputs x,x′. Fix ε,t ≥ 0. We must show that for all S we have $ℙ [M (x) \in S] \leq e^{ε} \cdot ℙ [M (x^{'}) \in S] + δ$ for the value of δ given in the statement above.

Let Z ← PrivLoss(M(x)∥M(x′)). By Proposition 3.7, it suffices to show

E [\max {0, 1 - \exp (ε - Z)}] \leq δ,

for the value of δ given in the statement above.

Let c > 0 be a constant such that, with probability 1,

\max {0, 1 - \exp (ε - Z)} \leq c \cdot \exp (t Z) .

Taking expectations of both sides we have $E [\max {0, 1 - \exp (ε - Z)}] \leq c \cdot E [\exp (t Z)]$ ⁠, which is the kind of bound we need. It only remains to identify the appropriate value of c to obtain the desired bound.

We trivially have 0 ≤ c ⋅ exp(tZ) as long as c > 0. Thus we only need to ensure 1 − exp(ε − Z) ≤ c ⋅ exp(tZ). That is, for any value of t > 0, we can set

\begin{matrix} c & = \sup_{z \in ℝ} \frac{1 - \exp (ε - z)}{\exp (t z)} \\ = \sup_{z \in ℝ} \exp (- t z) - \exp (ε - (t + 1) z) \\ = \frac{\exp (- ε t)}{t + 1} \cdot {(1 - \frac{1}{t + 1})}^{t}, \end{matrix}

where the final equality follows from using calculus to determine that z = ε + log(1 + 1/t) is the optimal value of z. Thus $E [\max {0, 1 - \exp (ε - Z)}] \leq E [\exp (t Z)] \cdot \frac{\exp (- ε t)}{t + 1} \cdot {(1 - \frac{1}{t + 1})}^{t}$ ⁠, which proves the first part of the statement.

Now assume M is ρ-zCDP. Thus

\forall t \geq 0 E [\exp (t Z)] \leq \exp (t (t + 1) \cdot ρ),

which immediately yields the equality in the second part of the statement.

To obtain the inequality in the second part of the statement, we observe that

\max {0, 1 - \exp (ε - Z)} \leq I [Z > ε] \leq \exp (t (Z - ε)),

whence c ≤ exp(−εt). Substituting in this upper bound on c and setting t = (ε − ρ)/2ρ completes the proof

Remark 3.15.Proposition 3.14 shows that ρ-zCDP implies (ε,δ = exp(−(ε − ρ)²/4ρ))-DP for all ε ≥ ρ. Equivalently, ρ-zCDP implies $(ε = ρ + 2 \sqrt{ρ \cdot \log (1 / δ)}, δ)$ -DP for all δ > 0. Also, to obtain a given a target (ε,δ)-DP guarantee, it suffices to have ρ-zCDP with

\frac{ε^{2}}{4 \log (1 / δ) + 4 ε} \leq ρ = {(\sqrt{\log (1 / δ) + ε} - \sqrt{\log (1 / δ)})}^{2} \leq \frac{ε^{2}}{4 \log (1 / δ)} .

This gives a sufficient condition; tighter bounds can be obtained from Proposition 3.14.

The final piece of the puzzle is the conversion from pure DP to concentrated DP.

Proposition 3.16.Suppose M satisfies ε-DP, then M satisfies $\frac{1}{2} ε^{2} - z C D P$ ⁠.

Proof. Fix neighboring inputs x,x′. Let Z ← PrivLoss(M(x)∥M(x′)). By our ε-DP assumption, Z is supported on the interval [−ε, +ε]. Our task is to prove that $E [\exp (t Z)] \leq \exp (\frac{1}{2} ε^{2} t (t + 1))$ for all t > 0.

The key additional fact is the following consequence of Lemma 3.6

\begin{matrix} \underset{Z \leftarrow PrivLoss (P ‖ Q)}{E} [e^{- Z}] & = \underset{Y \leftarrow P}{E} [e^{- f_{P ‖ Q} (Y)}] \\ = \underset{Y \leftarrow Q}{E} [e^{f_{P ‖ Q} (Y)} \cdot e^{- f_{P ‖ Q} (Y)}] = \underset{Y \leftarrow Q}{E} [1] = 1. \end{matrix}

We can write this out as an integral to make it clear:

\begin{matrix} \underset{Z \leftarrow PrivLoss (P ‖ Q)}{E} [\exp (- Z)] & = \underset{Y \leftarrow P}{E} [\exp (- f_{P ‖ Q} (Y))] \\ = \underset{Y \leftarrow P}{E} [\exp (- \log (P (Y) / Q (Y)))] \\ = \underset{Y \leftarrow P}{E} [\frac{Q (Y)}{P (Y)}] \\ = \int_{Y} \frac{Q (y)}{P (y)} P (y) d y \\ = \int_{Y} Q (y) d y \\ =1 . \end{matrix}

The combination of these two facts −Z ∈ [−ε, ε] and $E [\exp (- Z)] = 1$ is all we need to know about Z to prove the result. The technical ingredient is Hoeffding's lemma [Hoe63]:

Lemma 3.17 (Hoeffding's lemma). Let Z be a random variable supported on the interval [−ε, +ε]. Then for all $t \in ℝ, E [\exp (t Z)] \leq \exp (t E [Z] + t^{2} ε^{2} / 2)$ ⁠.

Proof. To simplify things, we can assume without loss of generality that Z is supported on the discrete set {−ε, +ε}. To prove this claim, let $\tilde{Z} \in {- ε, + ε}$ be a randomized rounding of Z. That is, $\underset{\tilde{Z}}{E} [\tilde{Z} ∣ Z = z] = z$ for all z ∈ [−ε, +ε]. By Jensen's inequality, since exp(tz) is a convex function of z ∈ ℝ for any fixed t ∈ ℝ, we have

\underset{Z}{E} [\exp (t Z)] = \underset{Z}{E} [\exp (t \underset{\tilde{Z}}{E} [\tilde{Z} ∣ Z])] \leq \underset{Z}{E} [\underset{\tilde{Z}}{E} [\exp (t \tilde{Z}) ∣ Z]] = \underset{\tilde{Z}}{E} [\exp (t \tilde{Z})] .

Note that $E [\tilde{Z}] = E [Z]$ ⁠. Thus it suffices to prove $E [\exp (t \tilde{Z})] \leq \exp (t E [\tilde{Z}] + \frac{1}{2} ε^{2} t^{2})$ for all t ∈ ℝ.

The final step in the proof is some calculus: Let $p : = ℙ [\tilde{Z} = ε] = 1 - ℙ [\tilde{Z} = - ε]$ ⁠. Then $E [Z] = E [\tilde{Z}] = ε p - ε (1 - p) = ε (2 p - 1)$ ⁠. Define f : ℝ → ℝ by

f (t) : = \log E [\exp (t \tilde{Z})] = \log (p \cdot e^{t ε} + (1 - p) \cdot e^{- t ε}) = \log (1 - p + p \cdot e^{2 t ε}) - t ε .

For all t ∈ ℝ,

f^{'} (t) = \frac{2 ε p \cdot e^{2 t ε}}{1 - p + p \cdot e^{2 t ε}} - ε,

and

\begin{matrix} f^{''} (t) & = \frac{{(2 ε)}^{2} p \cdot e^{2 t ε} \cdot (1 - p + p \cdot e^{2 t ε}) - {(2 ε p \cdot e^{2 t ε})}^{2}}{{(1 - p + p \cdot e^{2 t ε})}^{2}} \\ = {(2 ε)}^{2} \cdot \frac{p \cdot e^{2 t ε}}{1 - p + p \cdot e^{2 t ε}} \cdot (1 - \frac{p \cdot e^{2 t ε}}{1 - p + p \cdot e^{2 t ε}}) \\ = {(2 ε)}^{2} \cdot x \cdot (1 - x) \leq {(2 ε)}^{2} \cdot \frac{1}{4} = ε^{2} . \end{matrix}

The final line sets $x = \frac{p \cdot e^{2 t ε}}{1 - p + p \cdot e^{2 t ε}}$ and uses the fact that the function x ⋅ (1 − x) is maximized at $x = \frac{1}{2}$ ⁠.

Note that f(0) = 0 and $f^{'} (0) = 2 ε p - ε = E [\tilde{Z}] = E [Z]$ ⁠. By the fundamental theorem of calculus, for all t ∈ ℝ,

\begin{array}{l} f (t) = f (0) + f^{'} (0) \cdot t + \int_{0}^{t} \int_{0}^{s} f^{''} (r) d r d s \leq 0 + E [Z] \cdot t \\ + \int_{0}^{t} \int_{0}^{s} ε^{2} d r d s = E [Z] \cdot t + \frac{1}{2} ε^{2} t^{2} . \end{array}

This proves the lemma, as $E [\exp (t Z)] \leq E [\exp (t \tilde{Z})] = \exp (f (t)) \leq (\exp (E [Z] . t + \frac{1}{2} ε^{2} t^{2})$ ⁠.

If we substitute t = −1 into Lemma 3.17, we have

1 = E [\exp (- Z)] \leq \exp (- E [Z] + \frac{1}{2} ε^{2}),

which rearranges to $E [Z] \leq \frac{1}{2} ε^{2}$ ⁠.

Substituting this bound on the expectation back into Lemma 3.17 yields the result: For all t > 0, we have

E [\exp (t Z)] \leq \exp (t \cdot E [Z] + \frac{1}{2} ε^{2} t^{2}) \leq \exp (\frac{1}{2} ε^{2} t (t + 1)) .

Combining these three results lets us prove what is known as the advanced composition theorem where we start with each individual algorithm satisfying pure DP [DRV10]:

Theorem 3.18 (Advanced Composition Starting with Pure DP). Let $M_{1}, M_{2}, \dots, M_{k} : X^{n} \to Y$ be randomized algorithms. Suppose M_j is ε_j-DP for each j ∈ [k]. Define $M : X^{n} \to Y^{k}$ by M(x) = (M₁(x),M₂(x),…, M_k(x)), where each algorithm is run independently. Then M is (ε, δ)-DP for any δ > 0 with

ε = \frac{1}{2} \sum_{j = 1}^{k} ε_{j}^{2} + \sqrt{2 \log (1 / δ) \sum_{j = 1}^{k} ε_{j}^{2}} .

Proof of Theorem 3.18. By Proposition 3.16, for each j ∈ [k], M_j satisfies ρ_j-zCDP with $ρ_{j} = \frac{1}{2} ε_{j}^{2}$ ⁠. By composition of concentrated DP (Theorem 3.13), M satisfies ρ-zCDP with $ρ = \sum_{j = 1}^{k} ρ_{j}$ ⁠. Finally, Proposition 3.14 can convert this concentrated DP guarantee to approximate DP: M satisfies (ε,δ)-DP for all ε ≥ ρ and δ = exp(−(ε−ρ)²/4ρ). We can rearrange this so that δ > 0 is arbitrary and $ε = ρ + \sqrt{4 ρ \log (1 / δ)}$ ⁠.

Comparison of different composition bounds. We compose k independent 0.1-DP algorithms to obtain a (ε,10⁻⁶)-DP guarantee. Theorem 3.1 – basic composition gives ε = k⋅0.1. For comparison, we have advanced composition (Theorem 3.18), an optimal bound [KOV15], and Concentrated DP (CDP) with the improved conversion from Proposition 3.14. For comparison, we also consider composing the Gaussian mechanism using Corollary 3.10, where the Gaussian noise is scaled to have the same variance as Laplace noise would have to attain 0.1-DP.

Figure 3.1

Plot comparing basic, advanced, optimal, C D P, and Gaussian composition bounds, showing epsilon versus number of compositions k for repeated 0 point 1 D P mechanisms.

View large Download slide

Comparison of different composition bounds. We compose k independent 0.1-DP algorithms to obtain a (ε,10⁻⁶)-DP guarantee. Theorem 3.1 – basic composition gives ε = k⋅0.1. For comparison, we have advanced composition (Theorem 3.18), an optimal bound [KOV15], and Concentrated DP (CDP) with the improved conversion from Proposition 3.14. For comparison, we also consider composing the Gaussian mechanism using Corollary 3.10, where the Gaussian noise is scaled to have the same variance as Laplace noise would have to attain 0.1-DP.

Recall that the basic composition theorem (Theorem 3.1) gives δ = 0 and $ε = \sum_{j = 1}^{k} ε_{j}$ ⁠. That is, basic composition scales with the 1-norm of the vector (ε₁,ε₂,…, ε_k), whereas advanced composition scales with the 2 -norm of this vector (and the squared 2 -norm). Neither bound strictly dominates the other. However, asymptotically (in a sense we will make precise in the next paragraph) advanced composition dominates basic composition.

Suppose we have a fixed (ε,δ)-DP guarantee for the entire system and we must answer k queries of sensitivity 1. Using basic composition, we can answer each query by adding Laplace (k/ε) noise to each answer. However, using advanced composition, we can answer each query by adding Laplace $(\sqrt{k / 2 ρ})$ noise to each answer,

where

ρ \geq \frac{ε^{2}}{4 \log (1 / δ) + 4 ε},

(per Remark 3.15). If the privacy parameters ε,δ > 0 are fixed (which implies ρ is fixed) and k → ∞, we can see that asymptotically advanced composition gives noise per query scaling as $Θ (\sqrt{k})$ ⁠, while basic composition results in noise scaling as Θ(k).

3.4.2 Adaptive Composition & Post-processing

Thus far we have only considered non-adaptive composition. That is, we assume that the algorithms M₁,M₂,…, M_k being composed are independent. More generally, adaptive composition considers the possibility that M_j can depend on the outputs of M₁,…, M_j−1. This kind of dependence arises very often, either in an iterative algorithm, or an interactive system where a human chooses analyses to perform sequentially. Fortunately, adaptive composition is easy to deal with.

Proposition 3.19 (Adaptive Composition of Concentrated DP). Let $M_{1} : X^{n} \to Y_{1}$ be ρ₁−zCDP. Let $M_{2} : X^{n} \times Y_{1} \to Y_{2}$ be such that, for all $y_{1} \in Y_{1}$ ⁠, the algorithm x ↦ M(x,y₁) is ρ₂−zCDP. That is, M₂is ρ₂−zCDP in terms of its first argument for any fixed value of the second argument. Define $M : X^{n} \to Y_{2}$ by M(x) = M₂(x,M₁(x)). Then M is (ρ₁ + ρ₂)-zCDP.

Proposition 3.19 only considers the composition of two algorithms, but it can be extended to k algorithms by induction.

Proof. Fix neighboring inputs $x, x^{'} \in X^{n}$ ⁠. Fix t ≥ 0. Let Z ← PrivLoss (M(x)∥M(x′)). We must prove $E [\exp (t Z)] \leq \exp (t (t + 1) (ρ_{1} + ρ_{2}))$ ⁠.

For non-adaptive composition, we could write Z = Z₁ + Z₂ where Z₁ ← PrivLoss(M₁(x) ∥ M₁(x′)) and Z₂ ← PrivLoss(M₂(x) ∥ M₂(x′)) are independent. However, we cannot do this in the adaptive case – the two privacy losses are not independent. Instead, we use the fact that, conditioned on the value of the first privacy loss Z₁, the privacy loss Z₂ still satisfies the bound on the moment generating function. That is, for all z₁, we have $E [\exp (t Z_{2}) ∣ Z_{1} = z_{1}] \leq \exp (t (t + 1) ρ_{2})$ ⁠. To make this argument precise, we must expand out the relevant definitions.

For now, we make a simplifying technical assumption (which we will justify later): We assume that, given y₂ = M(x,y₁), we can determine y₁. This means we can decompose $f_{M (x) ‖ M (x^{'})} (y_{2}) = f_{M_{1} (x) ‖ M_{1} (x^{'})} (y_{1}) + f_{M_{2} (x, y_{1}) ‖ M_{2} (x^{'}, y_{1})} (y_{2})$ ⁠. Thus

\begin{array}{l} \underset{Z \leftarrow P r i v L o s s (M (x) ‖ M (x^{'}))}{E} [\exp (t Z)] \\ = \underset{Y \leftarrow M_{2} (x, M_{1} (x))}{E} [\exp (t \cdot f_{M (x) ‖ M (x^{'})} (Y))] \\ = \underset{Y_{1} \leftarrow M_{1} (x)}{E} [\underset{Y_{2} \leftarrow M_{2} (x, Y_{1})}{E} [e x p (t \cdot (f_{M_{1} (x) ‖ M_{1} (x^{'})} (Y_{1}) \\ + f_{M_{2} (x, Y_{1}) ‖ M_{2} (x^{'}, Y_{1})} (Y_{2})))]] \\ = \underset{Y_{1} \leftarrow M_{1} (x)}{E} [\exp (t \cdot f_{M_{1} (x) ‖ M_{1} (x^{'})} (Y_{1})) \\ \cdot \underset{Y_{2} \leftarrow M_{2} (x, Y_{1})}{E} [\exp (t \cdot f_{M_{2} (x, Y_{1}) ‖ M_{2} (x^{'}, Y_{1})} (Y_{2}))]] \\ \leq \underset{Y_{1} \leftarrow M_{1} (x)}{E} [\exp (t \cdot f_{M_{1} (x) ‖ M_{1} (x^{'})} (Y_{1}))] \\ \cdot \sup_{y_{1}} \underset{Y_{2} \leftarrow M_{2} (x, y_{1})}{E} [\exp (t \cdot f_{M_{2} (x, y_{1}) ‖ M_{2} (x^{'}, y_{1})} (Y_{2}))] \\ = \underset{Z_{1} \leftarrow P r i v L o s s (M_{1} (x) ‖ M_{1} (x^{'}))}{E} [\exp (t \cdot Z_{1})] \\ \cdot \sup_{y_{1}} \underset{Z_{2} \leftarrow P r i v L o s s (M_{2} (x, y_{1}) ‖ M_{2} (x^{'}, y_{2}))}{E} [\exp (t \cdot Z_{2})] \\ \leq \exp (t (t + 1) ρ_{1}) \cdot \exp (t (t + 1) ρ_{2}) \\ = \exp (t (t + 1) (ρ_{1} + ρ_{2}))), \end{array}

as required. All that remains is to justify our simplifying technical assumption. We can perforce ensure this assumption holds by defining $\hat{M} : X^{n} \to Y_{1} \times Y_{2}$ by $\hat{M} (x) = (y_{1}, y_{2})$ where y₁ = M₁(x) and y₂ = M₂(x,y₁) and proving the theorem for $\hat{M}$ in lieu of M. Since the output of $\hat{M}$ includes both outputs, rather than just the last output, the above decomposition works. The result holds in general because M is a post-processing of $\hat{M}$ ⁠. That is, we can obtain M(x) by running $\hat{M} (x)$ and discarding the first part of the output. Intuitively, discarding part of the output cannot hurt privacy. Formally, this is the post-processing property of concentrated DP, which we prove in Lemma 3.20 and Corollary 3.21.

Lemma 3.20 (Post-processing for Concentrated DP). Let $\hat{P}$ and $\hat{Q}$ be distributions on $\hat{Y}$ and let $g : \hat{Y} \to Y$ be an arbitrary function. Define $P = g (\hat{P})$ and $Q = g (\hat{Q})$ to be the distributions on $Y$ obtained by applying g to a function from $\hat{P}$ and $\hat{Q}$ respectively. Then, for all t ≥ 0,

\underset{Z \leftarrow PrivLoss (P ‖ Q)}{E} [\exp (t Z)] \leq \underset{\hat{Z} \leftarrow PrivLoss (\hat{P} ‖ \hat{Q})}{E} [\exp (t \hat{Z})] .

Proof. To generate a sample from Y ← Q, we sample $\hat{Y} \leftarrow \hat{Q}$ and set $Y = g (\hat{Y})$ ⁠. We consider the reverse process: Given $y \in Y$ ⁠, define ${\hat{Q}}_{y}$ to be the conditional distribution of $\hat{Y} \leftarrow \hat{Q}$ conditioned on $g (\hat{Y}) = y$ ⁠. That is, ${\hat{Q}}_{y}$ is a distribution such that we can generate a sample $\hat{Y} \leftarrow \hat{Q}$ by first sampling Y ← Q and then sampling $\hat{Y} \leftarrow {\hat{Q}}_{Y}$ ⁠. Note that if g is an injective function, then ${\hat{Q}}_{y}$ is a point mass.

We have the following key identity. Formally, this relates the Radon-Nikodym derivative of the postprocessed distributions (P with respect to Q) to the RadonNikodym derivative of the original distributions (⁠ $\hat{P}$ with respect to $\hat{Q}$ ⁠) via the conditional distribution ${\hat{Q}}_{y}$ ⁠.

\forall y \in Y \frac{P (y)}{Q (y)} = \underset{\hat{Y} \leftarrow {\hat{Q}}_{y}}{E} [\frac{\hat{P} (\hat{Y})}{\hat{Q} (\hat{Y})}] .

To see where this identity comes from, write

\begin{matrix} \underset{\hat{Y} \leftarrow {\hat{Q}}_{y}}{E} [\frac{\hat{P} (\hat{Y})}{\hat{Q} (\hat{Y})}] & = \int_{{\hat{y} : g (\hat{y}) = y}} \frac{\hat{P} (\hat{y})}{\hat{Q} (\hat{y})} \cdot {\hat{Q}}_{y} (\hat{y}) d \hat{y} \\ = \int_{{\hat{y} : g (\hat{y}) = y}} \frac{\hat{P} (\hat{y})}{\hat{Q} (\hat{y})} \cdot \frac{\hat{Q} (\hat{y})}{\int_{{\tilde{y} : g (\tilde{y}) = y}} \hat{Q} (\tilde{y}) d \tilde{y}} d \hat{y} \\ = \frac{\int_{{\hat{y} : g (\hat{y}) = y}} \hat{P} (\hat{y}) d \hat{y}}{\int_{{\tilde{y} : g (\tilde{y}) = y}} \hat{Q} (\tilde{y}) d \tilde{y}} \\ = \frac{P (y)}{Q (y)} . \end{matrix}

Finally, we have

\begin{matrix} \underset{Z \leftarrow PrivLoss (P ‖ Q)}{E} [\exp (t Z)] & = \underset{Y \leftarrow P}{E} [\exp (t \cdot f_{P ‖ Q} (Y))] \\ = \underset{Y \leftarrow Q}{E} [\exp ((t + 1) \cdot f_{P ‖ Q} (Y))] (Lemma 3 .6) \\ = \underset{Y \leftarrow Q}{E} [{(\frac{P (Y)}{Q (Y)})}^{t + 1}] \\ = \underset{Y \leftarrow Q}{E} [{(\underset{\hat{Y} \leftarrow {\hat{Q}}_{Y}}{E} [\frac{\hat{P} (\hat{Y})}{\hat{Q} (\hat{Y})}])}^{t + 1}] \\ \leq \underset{Y \leftarrow Q}{E} [\underset{\hat{Y} \leftarrow {\hat{Q}}_{Y}}{E} [{(\frac{\hat{P} (\hat{Y})}{\hat{Q} (\hat{Y})})}^{t + 1}]] (Jensen) \\ = \underset{\hat{Y} \leftarrow \hat{Q}}{E} [{(\frac{\hat{P} (\hat{Y})}{\hat{Q} (\hat{Y})})}^{t + 1}] \\ = \underset{\hat{Y} \leftarrow \hat{Q}}{E} [\exp ((t + 1) \cdot f_{\hat{P} ‖ \hat{Q}} (\hat{Y}))] \\ = \underset{\hat{Y} \leftarrow \hat{P}}{E} [\exp (t \cdot f_{\hat{P}} ‖ \hat{Q} (\hat{Y}))] (Lemma 3.6) \\ = \underset{\hat{Z} \leftarrow PrivLoss (\hat{P} ‖ \hat{Q})}{E} [\exp (t \hat{Z})], \end{matrix}

where the inequality follows from Jensen's inequality and the convexity of the function v ↦ v^t+1.

Corollary 3.21.Let $\hat{M} : X^{n} \to \hat{Y}$ satisfy ρ-zCDP. Let $g : \hat{Y} \to Y$ be an arbitrary function. Define $M : X^{n} \to Y$ by $M (x) = g (\hat{M} (x))$ ⁠. Then M is also ρ-zCDP.

Proof. Fix neighboring inputs $x, x^{'} \in X^{n}$ ⁠. Let $P = M (x), Q = M (x^{'}), \hat{P} = \hat{M} (x)$ ⁠, and $\hat{Q} = \hat{M} (x^{'})$ ⁠. By Lemma 3.20 and the assumption that $\hat{M}$ is ρ-zCDP, for all t ≥ 0,

\begin{matrix} \underset{Z \leftarrow PrivLoss (M (x) ‖ M (x^{'}))}{E} [\exp (t Z)] & = \underset{Z \leftarrow PrivLoss (P ‖ Q)}{E} [\exp (t Z)] \\ \leq \underset{\hat{Z} \leftarrow PrivLoss (\hat{P} ‖ \hat{Q})}{E} [\exp (t \hat{Z})] \\ = \underset{\hat{Z} \leftarrow PrivLoss (\hat{M} (x) ‖ \hat{M} (x^{'}))}{E} [\exp (t \hat{Z})] \\ \leq \exp (t (t + 1) ρ), \end{matrix}

which implies that M is also ρ-zCDP.

3.4.3 Composition of Approximate (ε,δ)-DP

Thus far we have only considered the composition of pure DP mechanisms (Theorems 3.1 & 3.18) and the Gaussian mechanism (Corollary 3.10). What about approximate (ε,δ)-DP?

We have the following result which extends Theorems 3.1 & 3.18 to approximate DP and to adaptive composition.

Theorem 3.22 (Advanced Composition Starting with Approximate DP). For j ∈ [k], let $M_{j} : X^{n} \times Y_{j - 1} \to Y_{j}$ be randomized algorithms. Suppose M_j is (ε_j, δ_j)−DP for each j ∈ [k]. For j ∈ [k], inductively define $M_{1 \dots j} : X^{n} \to Y_{j}$ by $M_{1 \dots j} (x) = M_{j} (x, M_{1 \dots (j - 1)} (x))$ ⁠, where each algorithm is run independently and M_1…0 (x) = y₀for some fixed $y_{0} \in Y_{0}$ ⁠. Then M_1…kis (ε, δ)-DP for any $δ > \sum_{j = 1}^{k} δ_{j}$ with

ε = \min {\sum_{j = 1}^{k} ε_{j}, \frac{1}{2} \sum_{j = 1}^{k} ε_{j}^{2} + \sqrt{2 \log (1 / δ^{'}) \sum_{j = 1}^{k} ε_{j}^{2}}},

where $δ^{'} = δ - \sum_{j = 1}^{k} δ_{j}$ ⁠.

Intuitively, if you consider the privacy loss PrivLoss (M(x)∥M(x′)) (where $x, x^{'} \in X^{n}$ are arbitrary neighboring inputs), then M being (ε,δ)-DP is equivalent to the privacy loss being in [−ε, +ε] with probability at least 1 − δ; otherwise the privacy loss can be arbitrary (including possibly infinite). Informally, the proof of Theorem 3.22 uses a union bound to show that with probability at least $1 - \sum_{j = 1}^{k} δ_{j}$ all of the privacy losses of the k algorithms are bounded by their respective ε_js. Once we condition on this event, the proof proceeds as before.

Formally, rather than reasoning about possibly infinite privacy losses, we use the following decomposition result.

Lemma 3.23.Let P and Q be probability distributions over $Y$ ⁠. Fix ε, δ ≥ 0. Suppose that, for all measurable $S \subset Y$ ⁠, we have P(S) ≤ e^ε ⋅ Q(S) + δ and Q(S) ≤ e^εP(S) + δ.

Then there exist distributions P′, Q′, P″, Q″ over $Y$ with the following properties. We can express P and Q as convex combinations of these distributions, namely P = (1 − δ) P′ + δP″ and Q = (1 − δ)Q′ + δQ″. And, for every measurable $S \subset Y$ ⁠, we have e^−ε ⋅ Q′ (S) ≤ P′ (S) ≤ e^ε ⋅ Q′ (S).

Proof. Fix ε₁,ε₂ ∈ [0, ε] to be determined later. Define distributions P′, P″, Q′, and Q″ as follows.^{^vi} For all points $y \in Y$ ⁠,

\begin{matrix} P^{'} (y) & = \frac{\min {P (y), e^{ε_{1}} \cdot Q (y)}}{1 - δ_{1}} \\ P^{''} (y) & = \frac{P (y) - (1 - δ_{1}) P^{'} (y)}{δ_{1}} = \frac{\max {0, P (y) - e^{ε_{1}} \cdot Q (y)}}{δ_{1}} \\ Q^{'} (y) & = \frac{\min {Q (y), e^{ε_{2}} \cdot P (y)}}{1 - δ_{2}} \\ Q^{''} (y) & = \frac{Q (y) - (1 - δ_{2}) Q^{'} (y)}{δ_{2}} = \frac{\max {0, Q (y) - e^{ε_{2}} \cdot P (y)}}{δ_{2}}, \end{matrix}

where δ₁ and δ₂ are appropriate normalizing constants.

By construction, (1 − δ₁)P′ + δ₁P″ = P and (1 − δ₂) Q′ + δ₂Q″ = Q.

If δ₁ = δ₂ = δ, then we have the appropriate decomposition and, for all $y \in Y$ ⁠, we have

e^{- ε} \leq e^{- ε_{2}} \leq \frac{P^{'} (y)}{Q^{'} (y)} = \frac{\min {P (y), e^{ε_{1}} \cdot Q (y)}}{\min {Q (y), e^{ε_{2}} \cdot P (y)}} \leq e^{ε_{1}} \leq e^{ε},

as required. If δ₁ = δ₂ < δ, we can change the decomposition to $P = (1 - δ) P^{'} + (δ - δ_{1}) P^{'} + (1 - δ_{1}) P^{''} = (1 - δ) P^{'} + δ \cdot (\frac{δ - δ_{1}}{δ} P^{'} + \frac{δ_{1}}{δ} P^{''})$ ⁠, and likewise for Q, which also yields the result.

It only remains to show that we can ensure that δ₁ = δ₂ ≤ δ by appropriately setting ε₁,ε₂ ∈ [0, ε]. We have

δ_{1} = \int_{Y} \max {0, P (y) - e^{ε_{1}} \cdot Q (y)} d y = \int_{S} P (y) - e^{ε_{1}} \cdot Q (y) d y = P (S) - e^{ε_{1}} Q (S),

where $S = {y \in Y : P (y) \geq e^{ε_{1}} \cdot Q (y)}$ ⁠. If ε₁ = ε, then δ₁ ≤ δ by the assumptions of the Lemma. If ε₁ = 0, then δ₁ = d_TV (P,Q). By decreasing ε₁, we continuously increase δ₁. Thus we can pick ε₁ ∈ [0, ε] such that δ₁ = min{δ,d_TV (P,Q)}. Similarly, we can pick ε₂ ∈ [0, ε], such that δ₂ = min{δ, d_TV (P,Q)}.

The proof of Theorem 3.22 is, unfortunately, quite technical. Most of the steps are the same as we have seen in the pure DP case. The only novelty is applying the decomposition of Lemma 3.23 inductively; this requires cumbersome notation, but is otherwise straightforward.

Proof of Theorem 3.22. Fix neighboring datasets $x, x^{'} \in X^{n}$ ⁠. We inductively define distributions P_j and Q_j on $Y_{0} \times Y_{1} \times \dots \times Y_{j}$ as follows. For j ∈ [k], P_j = (Y₀,Y₁,…, Y_j−1, M_j(x,Y_j−1)), where (Y₁,…, Y_j−1) ← P_j−1, and Q_j = (Y₀,Y₁,…, Y_j−1, M_j(x′,Y_j−1)), where (Y₁,…, Y_j−1) ← Q_j−1. We define P₀ = Q₀ to be the point mass on y₀.

We will prove by induction that, for each j ∈ [k], there exist distributions $\begin{array}{l} P_{j}^{'} \end{array}$ ⁠, $P_{j}^{''}$ ⁠, $Q_{j}^{'}$ and $Q_{j}^{''}$ on $Y_{0} \times Y_{1} \times \dots \times Y_{j}$ such that

P_{j} = \prod_{ℓ = 1}^{j} (1 - δ_{ℓ}) P_{j}^{'} + (1 - \prod_{ℓ = 1}^{j} (1 - δ_{ℓ})) P_{j}^{''}

and

Q_{j} = \prod_{ℓ = 1}^{j} (1 - δ_{ℓ}) Q_{j}^{'} + (1 - \prod_{ℓ = 1}^{j} (1 - δ_{ℓ})) Q_{j}^{''}

and, for all t ≥ 0,

\underset{Z_{j}^{'} \leftarrow PrivLoss (P_{j}^{'} ‖ Q_{j}^{'})}{E} [\exp (t Z_{j}^{'})] \leq \exp (\frac{t (t + 1)}{2} \sum_{ℓ = 1}^{j} ε_{ℓ}^{2})

and, for all measurable $S \subset Y_{0} \times Y_{1} \times \dots \times Y_{j}, P_{j}^{'} (S) \leq \exp (\sum_{ℓ = 1}^{j} ε_{ℓ}) \cdot Q_{j}^{'} (S) S \subset Y_{k}$ ⁠.

Before proving the inductive claim, we show that it suffices to prove the result. Fix an arbitrary measurable $S \subset Y_{k}$ and let $\tilde{S} = Y_{0} \times Y_{1} \times \dots \times Y_{k - 1} \times S$ ⁠. We have

\begin{matrix} ℙ [M (x) \in S] & = P_{k} (\tilde{S}) (Postprocessing) \\ \prod_{ℓ = 1}^{k} (1 - δ_{ℓ}) P_{k}^{'} (\tilde{S}) + (1 - \prod_{ℓ = 1}^{k} (1 - δ_{ℓ})) P_{k}^{''} (\tilde{S}) \\ \leq \prod_{ℓ = 1}^{k} (1 - δ_{ℓ}) P_{k}^{'} (\tilde{S}) + \sum_{j = 1}^{k} δ_{j} (P_{k}^{''} (\tilde{S}) \leq 1 and 1 - \prod_{ℓ = 1}^{k} (1 - δ_{ℓ}) \leq \sum_{j = 1}^{k} δ_{j}) \\ \leq \prod_{ℓ = 1}^{k} (1 - δ_{ℓ}) (e^{ε} \cdot Q_{k}^{'} (\tilde{S}) + δ^{'}) + \sum_{j = 1}^{k} δ_{j} (*) \\ \leq e^{ε} \cdot \prod_{ℓ = 1}^{k} (1 - δ_{ℓ}) \cdot Q_{k}^{'} (\tilde{S}) + δ \\ \leq e^{ε} \cdot Q_{k} (\tilde{S}) + δ (Q_{k} = \prod_{ℓ = 1}^{k} (1 - δ_{ℓ}) Q_{k}^{'} + (1 - \prod_{ℓ = 1}^{k} (1 - δ_{ℓ})) Q_{k}^{''}) \\ = e^{ε} \cdot ℙ [M (x^{'}) \in S] + δ . \end{matrix}

The inequality $P_{k}^{'} (\tilde{S}) \leq e^{ε} \cdot Q_{k}^{'} (\tilde{S}) + δ^{'} (*)$ follows the proof we have seen before. Our inductive conclusion includes a pure DP result – $P_{j}^{'} (\tilde{S}) \leq \exp (\sum_{ℓ = 1}^{j} ε_{ℓ}) \cdot Q_{j}^{'} (\tilde{S})$ and a concentrated DP result – for all t ≥ 0, we have $\underset{Z_{j}^{'} \leftarrow PrivLoss (P_{j}^{'} ‖ Q_{j}^{'})}{E} [\exp (t Z_{j}^{'})] \leq \exp (\frac{t (t + 1)}{2} \sum_{ℓ = 1}^{j} ε_{ℓ}^{2})$ ⁠, which implies

\begin{matrix} P_{k}^{'} (\tilde{S}) & \leq e^{ε} \cdot Q_{k}^{'} (\tilde{S}) + \underset{Z_{k}^{'} \leftarrow PrivLoss (P_{k}^{'} ‖ Q_{k}^{'})}{ℙ} [Z_{k}^{'} > ε] (Proposition 3 .7) \\ \leq e^{ε} \cdot Q_{k}^{'} (\tilde{S}) + \underset{Z_{k}^{'} \leftarrow PrivLoss (P_{k}^{'} ‖ Q_{k}^{'})}{E} [\exp (t (Z_{k}^{'} - ε))] (I [Z_{k}^{'} > ε] \leq \exp (t (Z_{k}^{'} - ε))) \\ \leq e^{ε} \cdot Q_{k}^{'} (\tilde{S}) + \exp (\frac{t (t + 1)}{2} \sum_{j = 1}^{k} ε_{j}^{2}) \cdot \exp (- t ε) (Induction conclusion) \\ \leq e^{ε} \cdot Q_{k}^{'} (\tilde{S}) + δ^{'}, \end{matrix}

where the final inequality holds for the case $ε = \frac{1}{2} \sum_{j = 1}^{k} ε_{j}^{2} + \sqrt{2 \log (1 / δ^{'}) \sum_{j = 1}^{k} ε_{j}^{2}}$ and requires setting $t = \frac{ε}{\sum_{j = 1}^{k} ε_{j}^{2}} - \frac{1}{2} = \sqrt{\frac{2 \log (1 / δ^{'})}{\sum_{j = 1}^{k} ε_{j}^{2}}}$ ⁠.

It only remains for us to perform the induction. The base case (j = 0) is trivial.

Fix j ∈ [k] and assume the induction hypothesis holds for j − 1. The distribution P_j is defined as a mixture (i.e., convex combination) of P_j|Y for Y ← P_j−1, where P_j|Y := (Y, M_j(x, Y_j−1)). For every y, we apply Lemma 3.23 to the conditional distribution P_j|y and then we take the convex combination of these decompositions to obtain a decomposition of P_j. Of course, we must also decompose Q_j at the same time.

For each $y \in Y_{0} \times Y_{1} \times \dots Y_{j - 1}$ ⁠, the conditional distributions satisfy ${\forall S P_{j} |}_{y} (S) \leq {e^{ε_{j}} Q_{j} |}_{y} (S) + δ_{j}$ and vice versa. Thus Lemma 3.23 allows us to decompose the conditional distributions P_j|Y and Q_j|Y as ${P_{j} |}_{y} = {(1 - δ_{j}) P_{j}^{'} |}_{y} + {δ_{j} P_{j}^{''} |}_{y}$ and ${Q_{j} |}_{y} = {(1 - δ_{j}) Q_{j}^{'} |}_{y} + {δ_{j} Q_{j}^{''} |}_{y}$ where ${e^{- ε_{j}} \cdot Q_{j}^{'} |}_{y} (S) \leq {P_{j}^{'} |}_{y} (S) \leq {e^{ε_{j}} \cdot Q_{j}^{'} |}_{y} (S)$ for all S. This gives us the desired decomposition:

\begin{array}{l} P_{j} & = \underset{Y \leftarrow P_{j - 1}}{E} [P_{j} |_{Y}] \\ = \underset{Y \leftarrow P_{j - 1}}{E} [(1 - δ_{j}) P_{j}^{'} |_{Y} + δ_{j} P_{j}^{''} |_{Y}] \\ = \prod_{ℓ = 1}^{j - 1} (1 - δ_{ℓ}) \underset{Y \leftarrow P_{j - 1}^{'}}{E} [(1 - δ_{j}) P_{j}^{'} |_{Y} + δ_{j} P_{j}^{''} |_{Y}] + (1 - \prod_{ℓ = 1}^{j - 1} (1 - δ_{ℓ})) \\ \times \underset{Y \leftarrow P_{j - 1}^{''}}{E} [(1 - δ_{j}) P_{j}^{'} |_{Y} + δ_{j} P_{j}^{''} |_{Y}] \\ = \prod_{ℓ = 1}^{j} (1 - δ_{ℓ}) \underset{Y \leftarrow P_{j - 1}^{'}}{E} [P_{j}^{'} |_{Y}] + δ_{j} \prod_{ℓ = 1}^{j - 1} (1 - δ_{ℓ}) \underset{Y \leftarrow P_{j - 1}^{'}}{E} [P_{j}^{''} |_{Y}] \\ + (1 - \prod_{ℓ = 1}^{j - 1} (1 - δ_{ℓ})) (1 - δ_{j}) \underset{Y \leftarrow P_{j - 1}^{''}}{E} [P_{j}^{'} |_{Y}] \\ + (1 - \prod_{ℓ = 1}^{j - 1} (1 - δ_{ℓ})) δ_{j} \underset{Y \leftarrow P_{j - 1}^{''}}{E} [P_{j}^{''} |_{Y}] . \end{array}

Thus we define the new decomposition as $P_{j}^{'} = {P_{j}^{'} |}_{Y}$ for $Y \leftarrow P_{j - 1}^{'}$ and $Q_{j}^{'} = {Q_{j}^{'} |}_{Y}$ for $Y \leftarrow Q_{j - 1}^{'}$ ⁠. The “weight” of $P_{j}^{'}$ is the product of the weight of $P_{j - 1}^{'}$ (i.e., $\prod_{ℓ = 1}^{j - 1} (1 - δ_{ℓ})$ ⁠) and the weight of ${P_{j}^{'} |}_{Y}$ (i.e., 1−δ_j), as required. The remaining parts of the decomposition are combined to define $P_{j}^{''} = and Q_{j}^{''}$ ⁠; note that $P_{j}^{''}$ includes both ${P_{j}^{'} |}_{Y}$ for $Y \leftarrow P_{j - 1}^{''}$ and ${P_{j}^{''} |}_{Y}$ for Y ← P_j−1. It is easy to verify that this decomposition satisfies the requirements of the induction:

\begin{array}{l} \underset{Z_{j}^{'} \leftarrow P r i v L o s s (P_{j}^{'} ‖ Q_{j}^{'})}{E} [\exp (t Z_{j}^{'})] \\ = \underset{Y_{j}^{'} \leftarrow P_{j}^{'}}{E} [\exp (t \cdot f_{P_{j}^{'}} ‖ Q_{j}^{'} (Y_{j}^{'}))] \\ = \underset{Y_{j - 1}^{'} \leftarrow P_{j - 1}^{'}}{E} [\underset{Y_{j}^{'} \leftarrow P_{j}^{'} ∣ Y_{j - 1}}{E} [\exp (t \cdot (f_{P_{j - 1}^{'}} ‖ Q_{j - 1}^{'} (Y_{j - 1}^{'}) + f_{P_{j}^{'} |_{Y_{j - 1}}} ‖ Q_{j}^{'} |_{Y_{j - 1}} (Y_{j}^{'})))]] \\ = \underset{Y_{j - 1}^{'} \leftarrow P_{j - 1}^{'}}{E} [\exp (t \cdot f_{P_{j - 1}^{'}} ‖ Q_{j - 1}^{'} (Y_{j - 1}^{'})) \\ \cdot \underset{Y_{j}^{'} \leftarrow P_{j}^{'} |_{j - 1}}{E} [\exp (t \cdot f_{P_{j}^{'} ∣ Y_{j - 1}} ‖ Q_{j}^{'} |_{j - 1} (Y_{j}^{'}))]] \\ = \underset{Y_{j - 1}^{'} \leftarrow P_{j - 1}^{'}}{E} [\exp (t \cdot f_{P_{j - 1}^{'}} ‖ Q_{j - 1}^{'} (Y_{j - 1}^{'})) \\ \cdot \underset{Z_{j}^{'} \leftarrow P r i v L o s s (P_{j}^{'} | Y_{j - 1} ‖ Q_{j}^{'} | Y_{j - 1})}{E} [\exp (t \cdot Z_{j}^{'})]] \\ \leq \underset{Y_{j - 1}^{'} \leftarrow P_{j - 1}^{'}}{E} [\exp (t \cdot f_{P_{j - 1}^{'}} ‖ Q_{j - 1}^{'} (Y_{j - 1}^{'})) \cdot \exp (t (t + 1) \frac{1}{2} ε_{j}^{2})] (P r o p o s i t i o n 3.16 & | Z_{j}^{'} | \leq ε_{j}) \\ \leq \exp (\frac{t (t + 1)}{2} \sum_{ℓ = 1}^{j - 1} ε_{ℓ}^{2}) \cdot \exp (t (t + 1) \frac{1}{2} ε_{j}^{2}) (I n d u c t i o n h y p o t h e s i s) \\ = \exp (\frac{t (t + 1)}{2} \sum_{ℓ = 1}^{j} ε_{ℓ}^{2}) . \end{array}

And, for pure DP, we have $P_{j}^{'} (S) = \underset{Y_{j - 1}^{'} \leftarrow P_{j - 1}^{'}}{E} [{P_{j}^{'} |}_{Y_{j - 1}} (S)] \leq \underset{Y_{j - 1}^{'} \leftarrow P_{j - 1}^{'}}{E} [e^{ε_{j}} {Q_{j}^{'} |}_{j - 1} (S)] \leq \exp (\sum_{ℓ = 1}^{j - 1} ε_{ℓ}) \cdot \underset{Y_{j - 1}^{'} \leftarrow Q_{j - 1}^{'}}{E} [{e^{ε_{j}} Q_{j}^{'} |}_{Y_{j - 1}} (S)] = \exp (\sum_{ℓ = 1}^{j} ε_{ℓ})$ ⁠. $Q_{j}^{'} (S)$ for all measurable S.

3.5 Asymptotic Optimality of Composition

Is the advanced composition theorem optimal? That is, could we prove a result that is stronger? This is an important question, but we first need to think about what optimality even means. Recall that, in Section 3.2.1, we proved that basic composition is optimal, but then we showed that we could do better by relaxing the requirement from pure DP to approximate DP or concentrated DP. To prove asymptotic optimality of advanced composition, we will show that no algorithm can provide better accuracy than advanced composition gives (except for constant factors) subject to approximate DP. Furthermore, we will see that the analysis is not specific to approximate DP.

Combining advanced composition (Theorem 3.18 or 3.22) with Laplace noise addition shows that we can answer k bounded sensitivity queries (e.g., counting queries) with noise scale $Θ (\sqrt{k / ρ})$ for each query, where ρ only depends on the privacy parameters, e.g., ρ = Θ(ε²/log(1/δ)) for (ε,δ)-DP. (Gaussian noise addition also gives the same asymptotics, per Corollary 3.10.)

We can prove that this asymptotics – average error per query $Ω (\sqrt{k})$ – is optimal. Formally, we have the following result.

Theorem 3.24 (Negative Result for Error of Private Mean Estimation). Let $X = {0, 1}^{k}$ and $Y = {[0, 1]}^{k}$ ⁠. Let $M : X^{n} \to Y$ satisfy (ε, δ)-DP. If δ ≤ 1/100n and k ≥ 200(e^ε − 1)²n, then there exists some $x \in X^{n}$ such that

\sqrt{E [\frac{1}{k} ‖ M (x) - \bar{x} ‖_{2}^{2}]} \geq \min {\frac{\sqrt{k}}{16 \cdot n \cdot (e^{ε} - 1)}, \frac{1}{10}},

where $\bar{x} = \frac{1}{n} \sum_{i = 1}^{n} x_{i} \in {[0, 1]}^{k}$ is the mean of input dataset.

Theorem 3.24 shows that any DP algorithm answering k queries must have error per query scaling with $Ω (\sqrt{k})$ ⁠, which matches the guarantees of the advanced composition theorem. We briefly remark on some of the properties of this theorem:

First, M could just output $\frac{1}{2}$ for each coordinate; this is trivially private and has root mean square error at most $\frac{1}{2}$ ⁠. The theorem must apply to such an algorithm too, which is the fundamental reason why the lower bound in the conclusion of Theorem 3.24 cannot be larger than a constant $\frac{1}{10}$ ⁠.

Second, the assumption δ ≤ 1/100n is also necessary, up to constant factors. If δ ≫ 1/n, then M could sample nδ of the inputs and return the sample mean. This would be (0, δ)-DP and would give accuracy $\sqrt{E [\frac{1}{k} ‖ M (x) - \bar{x} ‖_{2}^{2}]} \leq \frac{1}{\sqrt{n δ}} ≪ 1$ ⁠. Note that the advanced composition theorem includes a $\sqrt{\log (1 / δ)}$ term. It is possible to extend the negative results to include such a term too [SU15] (see also Lemma 2.3.6 of Bun [Bun16]), but we do not do this here for simplicity.

Third, the assumption k ≥ 200(e^ε − 1)²n is not really necessary; it is an artifact of our analysis. If k ≪ ε²n, then the privacy error is lower than the sampling error (if we think of x as consisting of n samples from some distribution). A different analysis is possible in this case.

Fourth, Theorem 3.24 has e^ε − 1 in the denominator, where our positive results have ε. For small ε, we have e^ε − 1 ≈ ε. But, for large ε, there is an exponential difference. Surprisingly, this is inherent; by using discrete noise [CKS20] in place of continuous Laplace noise it is possible to improve the positive results to yield this asymptotic behavior. However, we are generally not interested in the large ε setting.

Finally, fifth, this theorem is not merely an esoteric impossibility result. It corresponds to realistic attacks, which are known as “tracing attacks” [DSSU17] or “membership inference attacks” [SSSS17], which are the subject of Chapter 5 of this book.

Proof of Theorem 3.24. The theorem guarantees that there exists a specific input x on which M has high error. In general, x must depend on M. To prove this we show that, for a random input from a carefully chosen distribution, any M must have high error. It follows that for each specific M there must exist some fixed input with high error.

For p ∈ [0, 1]^k, let $D_{p}$ be the product distribution over {0, 1}^k with mean p. Our random input $X \in X^{n}$ will consist of n independent draws from $D_{p}$ ⁠. Furthermore, we select the mean parameter randomly too. That is, P ∈ [0, 1]^d is uniformly random and X consists of n conditionally independent draws from $D_{P}$ ⁠.

We analyze the quantity

Z : = \sum_{i = 1}^{n} 〈 M (X) - P, X_{i} - P 〉 .

Applying Lemma 3.25 with $f (x) = E [M {(X)}_{j} ∣ X_{j} = x]$ and summing over the coordinates j ∈ [k] shows that

\begin{matrix} \underset{P \leftarrow Uniform ({[0, 1]}^{k}) X \leftarrow D_{P}^{n}}{E} [Z + ‖ M (X) - \bar{X} ‖_{2}^{2}] \\ = \sum_{j = 1}^{k} \underset{P \leftarrow Uniform ([0, 1] k) X \leftarrow D_{P}^{n}}{E} [(M {(X)}_{j} - P_{j}) \cdot \sum_{i = 1}^{n} (X_{i, j} - P_{j})] \geq \frac{k}{12} . \end{matrix}

Denoting $α^{2} k = E [‖ M (X) - \bar{X} ‖_{2}^{2}]$ ⁠, we have $E [Z] \geq \frac{k}{12} - α^{2} k$ ⁠. Intuitively, Z measures the total correlation between the output of M and its inputs. What Lemma 3.25 shows is that, if M is accurate – i.e., $E [‖ M (X) - \bar{X} ‖_{2}^{2}] \leq o (k)$ – then this correlation must be large.

The punchline of the proof is that we show that differential privacy means the correlation must be small, which conflicts with the fact that we have proven it must be large. Ergo, we will obtain the desired impossibility result.

For i ∈ [n], define

Z_{i} = 〈 M (X) - P, X_{i} - P 〉,

so that $Z = \sum_{i = 1}^{n} Z_{i}$ ⁠. Let X₀ be a fresh sample from $D_{P}$ that is (conditionally) independent from X₁,…, X_n. Let M(X₀,X_−i) denote running M on the dataset X where X_i has been replaced by X₀ and define

{\tilde{Z}}_{i} = 〈 M (X_{0}, X_{- i}) - P, X_{i} - P 〉 .

By differential privacy, M(X₀,X_−i) is indistinguishable from M(X), even if we condition on X₀, X₁,…, X_n. Thus the distributions of ${\tilde{Z}}_{i}$ and Z_i are also indistinguishable.

Since M(X₀,X_−i) and X_i are independent (conditioned on P) and $E [X_{i} - P] = \vec{0}, E [{\tilde{Z}}_{i}] = 0$ and

\begin{matrix} \underset{P, X, M}{E} [{\tilde{Z}}_{i}^{2}] & = \sum_{j = 1}^{k} \underset{P}{E} [P_{j} (1 - P_{j}) \cdot \underset{X, M}{E} [{(M {(X_{0}, X_{- i})}_{j} - P_{j})}^{2}]] \\ \leq \frac{1}{4} \underset{P, X, M}{E} [‖ M (X) - P ‖_{2}^{2}] . \end{matrix}

Now $E [‖ M (X) - P ‖_{2}^{2}] \leq 2 E [‖ M (X) - \bar{X} ‖_{2}^{2}] + 2 E [‖ \bar{X} - P ‖_{2}^{2}] \leq 2 α^{2} k + \frac{k}{3 n}$ ⁠.^{^vii}

Lemma 3.26, $| Z_{i} | \leq k, | {\tilde{Z}}_{i} | \leq k$ ⁠, and $E [| {\tilde{Z}}_{i} |] \leq \sqrt{E [{\tilde{Z}}_{i}^{2}]}$ (i.e., Jensen's inequality) gives

E [Z_{i}] \leq E [{\tilde{Z}}_{i}] + (e^{ε} - 1) E [| {\tilde{Z}}_{i} |] + 2 δ k \leq \frac{e^{ε} - 1}{2} \sqrt{2 α^{2} k + \frac{k}{3 n}} + 2 δ k .

Putting things together, we have

\frac{k}{12} - α^{2} k \leq E [Z] = \sum_{i = 1}^{n} E [Z_{i}] \leq n \cdot (\frac{e^{ε} - 1}{2} \sqrt{2 α^{2} k + \frac{k}{3 n}} + 2 δ k) .

Ignoring terms that are (hopefully) low order, this is $Ω (k) \leq O (n \cdot ε \sqrt{α^{2} k})$ ⁠, which rearranges to $α = \sqrt{E [\frac{1}{k} ‖ M (X) - \bar{X} ‖_{2}^{2}]} \geq Ω (\frac{\sqrt{k}}{n ε})$ ⁠, which is the desired asymptotic result. To be precise, this rearranges to

α \geq \sqrt{{(\frac{1}{6} - 2 α^{2} - 4 n δ)}^{2} \cdot \frac{k}{2 n^{2} \cdot {(e^{ε} - 1)}^{2}} - \frac{1}{6 n}} .

If α ≤ 1/10 and δ ≤ 1/100n, then $\frac{1}{6} - 2 α^{2} - 4 n δ \geq \frac{1}{10}$ ⁠. If k ≥ 200(e^ε − 1)²n, then ${(\frac{1}{10})}^{2} \cdot \frac{k}{2 n^{2} {(e^{ε} - 1)}^{2}} \geq \frac{1}{n}$ ⁠. If all three of these conditions hold, then

\sqrt{E [\frac{1}{k} ‖ M (X) - \bar{X} ‖_{2}^{2}]} = α \geq \sqrt{\frac{k}{200 \cdot n^{2} \cdot {(e^{ε} - 1)}^{2}} (1 - \frac{1}{6})} \geq \frac{\sqrt{k}}{16 n (e^{ε} - 1)} .

Hence, if δ ≤ 1/100n and k ≥ 200(e^ε − 1)²n, then either α > 1/10 or $α \geq \sqrt{k} / 16 n (e^{ε} - 1)$ ⁠, as required.

Now we prove the two lemma that were used to prove Theorem 3.24. We begin with the lemma showing that the correlation Z must be large if M is accurate.

The lemma only contemplates one coordinate and then we sum over the k coordinates in the proof of Theorem 3.24. That is, the function f in the theorem is simply one coordinate of M and we average out the randomness of M and the other coordinates.

Lemma 3.25.Let f: {0,1}^d → [0,1] be an arbitrary function. Let P ∈ [0, 1] be uniformly random and, conditioned on P, let X₁,…, X_n ∈ {0, 1} be independent with $E [X_{i}] = P$ for each i ∈ [n]. Then

\underset{X, P}{E} [(f (X) - P) \cdot \sum_{i = 1}^{n} (X_{i} - P)] + \underset{P}{E} [\underset{X}{E} {[f (X) - \bar{X}]}^{2}] \geq \frac{1}{12} .

By Jensen's inequality $\underset{P}{E} [\underset{X}{E} {[f (X) - \bar{X}]}^{2}] \leq \underset{P, X}{E} [{(f (X) - \bar{X})}^{2}]$ ⁠. Thus

\underset{X, P}{E} [(f (X) - P) \cdot \sum_{i = 1}^{n} (X_{i} - P) + {(f (X) - \bar{X})}^{2}] \geq \frac{1}{12} .

To gain some intuition for the lemma statement, suppose $f (x) = \bar{x} = \frac{1}{n} \sum_{i = 1}^{n} x_{i}$ ⁠. Then

\begin{matrix} E [(f (X) - P, X_{i} - P)] & = E [(\bar{X} - P) \cdot (\sum_{i = 1}^{n} X_{i} - P)] \\ = \frac{1}{n} \sum_{i = 1}^{n} E [{(X_{i} - P)}^{2}] = \frac{1}{6} . \end{matrix}

The constant $\frac{1}{6} = \int_{0}^{1} p (1 - p) d p$ in this example is slightly better than the constant $\frac{1}{12}$ in the general result. However, if $f (x) = \frac{1}{2}$ is a constant function, then the constant is tight, as $\underset{P}{E} [\underset{X}{E} {[f (X) - \bar{X}]}^{2}] = \underset{P}{E} [{(\frac{1}{2} - P)}^{2}] = \frac{1}{12}$ ⁠.

Proof of Lemma 3.25. Define g:[0,1] → [0,1] by $g (p) = \underset{X \leftarrow D_{p}^{n}}{E} [f (X)]$ ⁠, where $D_{p}^{n}$ denotes the product distribution over {0, 1}ⁿ with each coordinate having mean p. Then

\begin{matrix} g^{'} (p) & = \frac{d}{d p X \leftarrow D_{p}^{n}} [f (X)] \\ = \sum_{x \in {0, 1}^{n}} f (x) \frac{d}{d p} \prod_{ℓ = 1}^{n} (x_{ℓ} \cdot p + (1 - x_{ℓ}) \cdot (1 - p)) \\ = \sum_{x \in {0, 1}^{n}} f (x) \prod_{ℓ = 1}^{n} (x_{ℓ} \cdot p + (1 - x_{ℓ}) \cdot (1 - p)) \sum_{i = 1}^{n} \frac{\frac{d}{d p} (p x_{i} \cdot p + (1 - x_{i}) \cdot (1 - p))}{x_{i} \cdot p + (1 - x_{i}) \cdot (1 - p)} (Product rule) \\ = \sum_{x \in {0, 1}^{n}} f (x) \prod_{ℓ = 1}^{n} (x_{ℓ} \cdot p + (1 - x_{ℓ}) \cdot (1 - p)) \sum_{i = 1}^{n} \frac{2 x_{i} - 1}{x_{i} \cdot p + (1 - x_{i}) \cdot (1 - p)} \\ = \sum_{x \in {0, 1}^{n}} f (x) \prod_{ℓ = 1}^{n} (x_{ℓ} \cdot p + (1 - x_{ℓ}) \cdot (1 - p)) \sum_{i = 1}^{n} \frac{x_{i} - p}{p (1 - p)} \\ = \underset{X \leftarrow D_{p}^{n}}{E} [f (X) \cdot \sum_{i = 1}^{n} \frac{X_{i} - p}{p (1 - p)}] . \end{matrix}

Now we apply integration by parts to this derivative:

\begin{matrix} \underset{P \leftarrow [0, 1]}{E} [\underset{X \leftarrow D_{P}^{n}}{E} [f (X) \cdot \sum_{i = 1}^{n} (X_{i} - P)]] \\ = \int_{0}^{1} g^{'} (p) \cdot p (1 - p) d p \\ = \int_{0}^{1} (\frac{d}{d p} g (p) \cdot p (1 - p)) - g (p) \cdot (1 - 2 p) d p \\ = g (1) \cdot 1 (1 - 1) - g (0) \cdot 0 (1 - 0) + \int_{0}^{1} g (p) \cdot (2 p - 1) d p \\ = 2 \underset{P \leftarrow [0, 1]}{E} [g (P) \cdot (P - \frac{1}{2})] . \end{matrix}

Using the fact that $\underset{P \leftarrow [0, 1]}{E} [P - \frac{1}{2}] = 0$ and $\underset{X \leftarrow D_{p}^{n}}{E} [X_{i} - p] = 0$ ⁠, we can center these expressions:

\begin{matrix} \underset{\begin{matrix} P \leftarrow [0, 1] \\ X \leftarrow D_{P}^{n} \end{matrix}}{E} [(f (X) - P) \cdot \sum_{i = 1}^{n} (X_{i} - P)] \\ = 2 \underset{P \leftarrow [0, 1]}{E} [(g (P) - \frac{1}{2}) \cdot (P - \frac{1}{2})] \\ = \underset{P \leftarrow [0, 1]}{E} [{(g (P) - \frac{1}{2})}^{2} + {(P - \frac{1}{2})}^{2} - {((g (P) - \frac{1}{2}) - (P - \frac{1}{2}))}^{2}] \\ \geq \underset{P \leftarrow [0, 1]}{E} [0 + {(P - \frac{1}{2})}^{2} - {(g (P) - P)}^{2}] \\ = \frac{1}{12} - \underset{P \leftarrow [0, 1]}{E} [{(g (P) - P)}^{2}] \\ = \frac{1}{12} - \underset{P \leftarrow [0, 1]}{E} [\underset{X \leftarrow D_{P}^{n}}{E} {[f (X) - \bar{X}]}^{2}] . \end{matrix}

Lemma 3.26.Let X and Y be random variables supported on [−Δ, Δ] satisfying $ℙ [X \in S] \leq e^{ε} \cdot ℙ [Y \in S] + δ$ and $ℙ [Y \in S] \leq e^{ε} \cdot ℙ [X \in S] + δ$ for all measurable S. Then

E [X] \leq E [Y] + (e^{ε} - 1) E [| Y |] + 2 δ Δ .

Proof.

\begin{matrix} E [X] & = \int_{0}^{Δ} ℙ [X > t] - ℙ [X < - t] d t \\ \leq \int_{0}^{Δ} e^{ε} \cdot ℙ [Y > t] + δ - e^{- ε} \cdot (ℙ [Y < - t] - δ) d t \\ = \int_{0}^{Δ} (ℙ [Y > t] - ℙ [Y < - t]) + (e^{ε} - 1) \cdot ℙ [Y > t] + (1 - e^{- ε}) \cdot ℙ [Y < - t] + (1 + e^{- ε}) δ d t \\ = E [Y] + (e^{ε} - 1) E [\max {0, Y}] + (1 - e^{- ε}) E [\max {0, - Y}] + (1 + e^{- ε}) δ Δ \\ \leq E [Y] + (e^{ε} - 1) E [| Y |] + 2 δ Δ, \end{matrix}

as 1 − e^−ε ≤ e^ε − 1 and 1 + e^−ε ≤ 2.

Remark 3.27.The only part of the proof of Theorem 3.24 that uses differential privacy is Lemma 3.26. Thus, if we were to consider a different definition of differential privacy, as long as an analog of Lemma 3.26 holds for this alternative definition, an analog of Theorem 3.24 would still apply. That is to say, this negative result is robust to our choice of privacy definition (unlike the the negative result in Section 3.2.1).

3.6 Privacy Amplification by Subsampling

Thus far we have considered the composition of Gaussian mechanisms, and generic mechanisms satisfying pure or approximate DP. We now turn our attention to subsampled privacy mechanisms. These mechanisms introduce some additional quirks into the picture, which will force us to develop new tools.

The premise of privacy amplification by subsampling is that we run a DP algorithm on some random subset of the data. The subset introduces additional uncertainty, which benefits privacy. In particular, there is some probability that your data is not included in the analysis, which can only enhance your privacy. Furthermore, a potential attacker does not know whether or not your data was dropped; this uncertainty can benefit your privacy even when your data is included. Privacy amplification by subsampling theorems make this intuition precise.

Subsampling arises naturally. We often would like to collect the data of the entire population, but this is impractical. Thus we collect the data of a subset of the population and use statistical methods to generalize from this sample to the entire population. In particular, in deep learning applications, we will use stochastic gradient descent. That is, we choose a random subset of our training data (called a minibatch) and compute the gradient of the loss function with respect to this subset, rather than the entire dataset. This method reduces the computational cost for training. If we want to make deep learning differentially private, then we will add noise to the gradients and we should exploit privacy amplification by subsampling to analyze the privacy properties of this algorithm.

In this section we will analyze subsampling precisely and we will show how it interacts with composition.

3.6.1 Subsampling for Pure or Approximate DP

We begin by analyzing privacy amplification by subsampling under pure or approximate differential privacy. This is a relatively simple result, but it will be instructive as we later attempt to derive more precise bounds.

Theorem 3.28 (Privacy Amplification by Subsampling for Approximate DP). Let U ⊂ [n] be a random subset. For a dataset $x \in X^{n}$ ⁠, let $x_{U} \in X^{n}$ denote the entries of x indexed by U. That is, (x_U)_i = x_i if i ∈ U and (x_U)_i = ⊥ if i ∉ U, where $⊥ \in X$ is some null value.

Assume that, for all i ∈ [n], we can define U_−i ⊂ [n] \ {i} such that the following two conditions hold.

For all $x \in X^{n}$ and i ∈ [d], x_U and $^{x} U_{- i}$ are always neighboring datasets.
For all i ∈ [n], the marginal distribution of U_−i conditioned on i ∈ U is equal to the marginal distribution of U conditioned on i ∉ U.

Let $M : X^{n} \to Y$ satisfy (ε, δ)-DP. Define $M^{U} : X^{n} \to Y$ by M^U(x) = M(x_U).

Let $p = \max_{i \in [n]} \underset{U}{ℙ} [i \in U]$ ⁠. Then M^U is (ε′, δ′)-DP for ε′ = log(1+p(e^ε−1)) and δ′ = p ⋅ δ.

For small values of ε, we have ε′ = log(1 + p(e^ε − 1)) ≈ p ⋅ ε. More precisely, ε′ = log(1 + p(e^ε − 1)) ≤ p ⋅ (e^ε − 1) and, for ε ≤ 1, we have e^ε − 1 ≤ ε + ε² ≤ 2ε.

The technical assumption about U in the theorem statement is satisfied by many natural subsampling distributions: If U is a uniformly random subset of [n] of a fixed size m, then U_−i can be obtained by replacing i with a a uniformly random element that is not in U. If U is Poisson subsampled – i.e., each i ∈ [n] is independently included in U with probability p – then, by independence, we can simply remove i, namely U_−i = U∖{i}.

The technical assumption should be thought of as an independence assumption. For example, it rules out distributions of the form $\underset{U}{ℙ} [U = [n]] = p$ and $ℙ [U = \emptyset] = 1 - p$ ⁠, which do not yield meaningful privacy amplification.

Proof of Theorem 3.28. Fix neighboring inputs $x, x^{'} \in X^{n}$ and some measurable $S \subset Y$ ⁠. Let i ∈ [n] be the index on which they differ (i.e., $x_{j} = x_{j}^{'}$ for all j ∈ [n] \ {i}) and let $p_{i} = \underset{U}{ℙ} [i \in U]$ ⁠. We have

\begin{array}{l} \underset{M^{U}}{ℙ} [M^{U} (x) \in S] & = \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}) \in S]] \\ = (1 - p_{i}) \cdot \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}) \in S] ∣ i \notin U] \\ + p_{i} \cdot \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}) \in S] ∣ i \in U] \\ = (1 - p_{i}) \cdot \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}^{'}) \in S] ∣ i \notin U] \\ + p_{i} \cdot \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}) \in S] ∣ i \in U] \\ = (1 - p_{i}) \cdot a + p_{i} \cdot b, \\ \underset{M^{U}}{ℙ} [M^{U} (x^{'}) \in S] & = (1 - p_{i}) \cdot \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}^{'}) \in S] ∣ i \notin U] \\ + p_{i} \cdot \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}^{'}) \in S] ∣ i \in U] \\ = (1 - p_{i}) \cdot a + p_{i} \cdot b^{'}, \end{array}

where $a = \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}) \in S] ∣ i \notin U] = \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}^{'}) \in S] ∣ i \notin U], b = \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}) \in S] ∣ i \in U]$ ⁠, and $b^{'} = \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}^{'}) \in S] ∣ i \in U]$ ⁠.

Note that x_U and $x_{U}^{'}$ are always neighboring datasets. And, if i ∉ U, then $x_{U} = x_{U}^{'}$ ⁠. Since M is (ε, δ)-DP, we have $\underset{M}{ℙ} [M (x_{U}) \in S] \leq e^{ε} \cdot \underset{M}{ℙ} [M (x_{U}^{'}) \in S] + δ$ for all values of U; thus

\begin{matrix} b & = \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}) \in S] ∣ i \in U] \leq \underset{U}{E} [e^{ε} \cdot \underset{M}{ℙ} [M (x_{U}^{'}) \in S] + δ ∣ i \in U] \\ = e^{ε} \cdot b^{'} + δ . \end{matrix}

However, this inequality alone is not sufficient to prove the claim. We also need to show that b ≤ e^ε ⋅ a + δ. Using our technical assumption, we have

\begin{matrix} b & = \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}) \in S] ∣ i \in U] \\ \leq \frac{E}{U} [e^{ε} \cdot \underset{M}{ℙ} [M (x_{U_{- i}}) \in S] + δ ∣ i \in U] (x_{U_{- i}} is a neighbour of x_{U}) \\ = \underset{U}{E} [e^{ε} \cdot \underset{M}{ℙ} [M (x_{U}) \in S] + δ ∣ i \notin U] ({U_{- i} |}_{i \in U} has the same distribution as {U |}_{i \notin U}) \\ = e^{ε} \cdot a + δ . \end{matrix}

Now we can complete the proof: For any λ ∈ [0, 1],

\begin{matrix} \underset{M^{U}}{ℙ} [M^{U} (x) \in S] & = (1 - p_{i}) \cdot a + p_{i} \cdot b \\ \leq (1 - p_{i}) \cdot a + p_{i} \cdot ((1 - λ) \cdot (e^{ε} \cdot a + δ) + λ \cdot (e^{ε} \cdot b^{'} + δ)) \\ = (1 - p_{i} + e^{ε} \cdot (1 - λ) \cdot p_{i}) \cdot a + p_{i} \cdot e^{ε} \cdot λ \cdot b^{'} + p_{i} \cdot δ . \end{matrix}

Set λ = p_i + (1 − p_i) ⋅ e^−ε to obtain

\begin{matrix} \underset{M^{U}}{ℙ} [M^{U} (x) \in S] & \leq (1 - p_{i} + e^{ε} \cdot (1 - λ) \cdot p_{i}) \cdot a + p_{i} \cdot e^{ε} \cdot λ \cdot b^{'} + p_{i} \cdot δ \\ = (1 + p_{i} \cdot (e^{ε} - 1)) \cdot ((1 - p_{i}) \cdot a + p_{i} \cdot b^{'}) + p_{i} \cdot δ \\ = (1 + p_{i} \cdot (e^{ε} - 1)) \cdot \underset{M^{U}}{ℙ} [M_{U} (x^{'}) \in S] + p_{i} \cdot δ \\ \leq e^{ε^{'}} \cdot \underset{M^{U}}{ℙ} [M_{U} (x^{'}) \in S] + δ^{'} . \end{matrix}

Theorem 3.28 is tight: Consider an algorithm M : {0, 1, ⊥}ⁿ → {0, 1} that sums its input (excluding ⟂ values) and performs randomized response on whether or not the sum is 0.^{^viii} That is, if y ∈ {0, 1, ⊥}ⁿ satisfies $\sum_{i : y_{i} \neq ⊥} y_{i} = 0$ ⁠, then $ℙ [M (y) = 0] = \frac{e^{ε}}{e^{ε} = 1}$ and $ℙ [M (y) = 1] = \frac{1}{e^{ε} = 1}$ and, if y ∈ {0, 1, ⊥}ⁿ satisfies $\sum_{i : y_{i} \neq ⊥} y_{i} > 0$ ⁠, then $ℙ [M (y) = 1] = \frac{e^{ε}}{e^{ε} = 1}$ and $ℙ [M (y) = 0] = \frac{1}{e^{ε} - 1}$ ⁠. This algorithm satisfies ε-DP.

Let U ⊂ [n] be random and let M^U : {0, 1}ⁿ → {0,1} be as in Theorem 3.28. Consider neighboring datasets x = (0,0,…, 0) and x′ = (1,0,0,…, 0). We have

\begin{matrix} ℙ [M^{U} (x) = 0] = \frac{e^{ε}}{e^{ε} + 1}, \\ ℙ [M^{U} (x) = 1] = \frac{1}{e^{ε} + 1}, \\ ℙ [M^{U} (x^{'}) = 1] = \frac{ℙ [1 \in U] \cdot e^{ε} + ℙ [1 \notin U]}{e^{ε} + 1}, \\ ℙ [M^{U} (x^{'}) = 0] = \frac{ℙ [1 \in U] + ℙ [1 \notin U] \cdot e^{ε}}{e^{ε} + 1}, \\ e^{ε^{'}} \geq \frac{ℙ [M^{U} (x^{'}) = 1]}{ℙ [M^{U} (x) = 1]} = 1 + ℙ [1 \in U] \cdot (e^{ε} - 1), \end{matrix}

where ε′ is the pure DP parameter satisfied by M^U. We can assume without loss of generality that $p = \max_{i} ℙ [i \in U] = ℙ [1 \in U]$ ⁠. Thus this bound matches the guarantee of Theorem 3.28. (This example can be extended to approximate DP too.)

3.6.2 Addition or Removal versus Replacement for Neighboring Datasets

For this discussion of subsampling, we need to be careful about what it means for datasets to be neighboring. There are three common definitions of what qualifies as neighboring datasets: (i) addition or removal of one person's data, (ii) replacement of one person's data, or (iii) both. Each of these three options is a reasonable choice. Work on differential privacy often glosses over this choice – often the choice is irrelevant. But it becomes relevant if we want sharp analyses of privacy amplification by subsampling.

For the discussion of composition so far in this chapter, it does not matter at all how we define neighboring datasets, as long as we are consistent. In general, it only matters slightly which we choose: A replacement can be accomplished by a combination of a removal and an addition. Thus, by group privacy, if the algorithm is (ε, δ)-DP with respect to addition or removal, then it is (2ε, (1 + e^ε)δ)-DP with respect to replacement. Conversely, we can simulate a removal or addition by replacing the record with a “null” value (⟂ in the formalism of Theorem 3.28). Thus DP with respect to replacement entails DP with respect to addition or removal with the same parameters, unless the semantics of the algorithm forbids null values.

This subtlety already arises in Theorem 3.28. Let's take a close look at the technical assumption: Theorem 3.28 assumes that, for all i ∈ [n], we can define U_−i ⊂ [n] \ {i} such that the following two conditions hold.

For all $x \in X^{n}$ and i ∈ [d], x_U and $^{x} U_{- i}$ are always neighboring datasets.
For all i ∈ [n], the marginal distribution of U_−i conditioned on i ∈ U is equal to the marginal distribution of U conditioned on i ∉ U.

Suppose U ⊂ [n] is a uniformly random subset of a fixed size |U| = m. Then we would define U_−i to be U with i replaced by a uniformly random element that is not already in U. Thus, for x_U and $^{x} U_{- i}$ to be neighboring datasets, our neighboring relation must allow replacement, not just addition or removal.

However, if U corresponds to Poisson subsampling (i.e., each i ∈ [n] is included in U independently with probability p), then U_−i would just correspond to removing i. In that case, for x_U and $^{x} U_{- i}$ to be neighboring datasets, our neighboring relation must allow addition and removal.

It turns out to be easier to work with Poisson subsampling and assuming the neighboring relation is addition or removal. In this case, the proof of Theorem 3.28 simplifies to the following.

Proof of Theorem 3.28 for the special case of Poisson sampling and addition or removal. Let U ⊂ [n] independently include each element with probability p. Let $x, x^{'} \in X^{n}$ be neighboring datasets in terms of addition or removal. Without loss of generality, assume x′ is x with x_i removed (or, rather, replaced by $x_{i}^{'} = ⊥$ ⁠).^{^ix} For any measurable $S \subset Y$ ⁠,

\begin{matrix} \underset{M^{U}}{ℙ} [M^{U} (x) \in S] & = \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}) \in S]] \\ = (1 - p) \cdot \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}) \in S] ∣ i \notin U] + p \cdot \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}) \in S] ∣ i \in U] \\ = (1 - p) \cdot \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}^{'}) \in S] ∣ i \notin U] + p \cdot \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}) \in S] ∣ i \in U] \\ = (1 - p) \cdot \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}^{'}) \in S]] + p \cdot \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}) \in S] ∣ i \in U] \\ \leq (1 - p) \cdot \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}^{'}) \in S]] + p \cdot \underset{U}{E} [e^{ε} \cdot \underset{M}{ℙ} [M (x_{U}^{'}) \in S] + δ ∣ i \in U] \\ = (1 - p) \cdot \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}^{'}) \in S]] + p \cdot \underset{U}{E} [e^{ε} \cdot \underset{M}{ℙ} [M (x_{U}^{'}) \in S] + δ] \\ = (1 - p + p \cdot e^{ε}) \cdot \underset{M^{U}}{ℙ} [M^{U} (x^{'}) \in S] + p \cdot δ \end{matrix}

and, by the same calculation,

\begin{array}{l} \underset{M^{U}}{ℙ} [M^{U} (x) \in S] & = (1 - p) \cdot \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}^{'}) \in S]] \\ + p \cdot \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}) \in S] ∣ i \in U] \\ \geq (1 - p) \cdot \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}^{'}) \in S]] \\ + p \cdot \underset{U}{E} [e^{- ε} \cdot (\underset{M}{ℙ} [M (x_{U}^{'}) \in S] - δ) ∣ i \in U] \\ = (1 - p + p \cdot e^{- ε}) \cdot \underset{M^{U}}{ℙ} [M^{U} (x^{'}) \in S] - p \cdot e^{- ε} \cdot δ \\ \geq \frac{1}{1 - p + p \cdot e^{ε}} \cdot (\underset{M^{U}}{ℙ} [M^{U} (x^{'}) \in S] - p \cdot δ) . (Lemma 3.35) \end{array}

The key step in the proof is the equality $\underset{U}{E} [\underset{M}{ℙ} [M (x_{U}^{'}) \in S] ∣ i \notin U] = \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}^{'}) \in S] ∣ i \in U] = \underset{U}{E} [\underset{M}{ℙ} [M (x_{U}^{'}) \in S]]$ ⁠. This holds because $x_{i}^{'} = ⊥$ so whether or not i ∈ U is irrelevant for $x_{U}^{'}$ ⁠, and because the event i ∈ U is independent from U \ {i}.

For the rest of this section, we will restrict our attention to Poisson subsampling and assume that the neighboring relation corresponds to addition or removal of one individual's data.

3.6.3 Subsampling & Composition

How does composition work with subsampling? Of course, we can combine the advanced composition theorem (Theorem 3.22) with our privacy amplification by subsampling result (Theorem 3.28). However, it turns out this is not the best way to analyze many realistic systems.

Consider the following algorithm (which arises in differentially private deep learning applications). Let $x \in X^{n}$ be the private input. Iteratively, for t = 1,…, T, we pick some function $q_{t} : X^{n} \to ℝ^{d}$ and randomly sample a subset U_t ⊂ [n]; then we reveal $N (q_{t} (x_{U_{t}}), σ^{2} I_{d})$ ⁠.

This algorithm interleaves composition with privacy amplification by subsampling. That is, we combine multivariate Gaussian noise addition (which is a form of composition over the d coordinates) with subsampling and then we compose over the T iterations.

We can use Corollary 3.10 to show that releasing $N (q_{t} (x), σ^{2} I_{d})$ satisfies (ε₀, δ₀)-DP for $ε_{0} = O (\sqrt{\frac{Δ_{2}^{2}}{σ^{2}} \log (1 / δ_{0})})$ ⁠, where $Δ_{2} = \sup_{\begin{matrix} x, x^{'} \in X^{n} \\ neighboring \end{matrix}} ‖ q_{t} (x) - q_{t} (x^{'}) ‖_{2}$ is the sensitivity of q_t. Then we can use Theorem 3.28 to show that, if U_t is a Poisson sample which contains each element with probability p, then $N (q_{t} (x_{U_{t}}), σ^{2} I_{d})$ is (ε₁, δ₁)-DP where $ε_{1} = \log (1 + p \cdot (e^{ε_{0}} - 1)) = O (p \cdot ε_{0})$ and δ₁ = p ⋅ δ₀. Finally, Theorem 3.22 tells us that the composition over T iterations satisfies (ε,δ)-DP with $ε = O (ε_{1} \cdot \sqrt{T \log (1 / δ_{2})}))$ and δ = δ₂ + T ⋅ δ₁. Overall, we have

ε = O (\frac{Δ_{2}}{σ} \cdot p \cdot \sqrt{T} \cdot \log (T / δ)) .

This result is asymptotically suboptimal because we have picked up two $\sqrt{\log (1 / δ)}$ terms. We obtained one from the Gaussian noise addition (Corollary 3.10) and another from the composition (Theorem 3.22). Both arise from bounding the tails of the privacy loss distribution. This is redundant; we should only need to bound the tails of the privacy loss distribution once.

Intuitively, we started with a Gaussian privacy loss; then we applied a tail bound to obtain a (ε₀,δ₀)-DP guarantee to which we applied the subsampling theorem; and then we converted this back into a concentrated DP guarantee to apply advanced composition and finally we applied a tail bound to convert this back to (ε,δ)-DP.

We are going to avoid this redundancy by analyzing privacy amplification by subsampling directly in terms of the privacy loss distribution, rather than needing to go via approximate DP. To do so, we need to introduce a new tool.

3.6.4 Rényi Differential Privacy

Rényi differential privacy was introduced by Mironov [Mir17] and was motivated by analyzing privacy amplification by subsampling interleaved with composition, which arises in differentially private deep learning [Aba+16].

Definition 3.29 (Rényi Differential Privacy). Let $M : X^{n} \to Y$ be a randomized algorithm. We say that M satisfies (α, ε)-Rényi differential privacy ((α, ε)RDP) if, for all neighboring inputs $x, x^{'} \in X^{n}$ ⁠, the privacy loss distribution PrivLoss (M(x)∥M(x′)) is well-defined (see Definition 3.2) and

\underset{Z \leftarrow PrivLoss (M (x) ‖ M (x^{'}))}{E} [\exp ((α - 1) Z)] \leq \exp ((α - 1) \cdot ε) .

Rényi DP is closely related to concentrated DP (Definition 3.11). Specifically, ρ-zCDP is equivalent to satisfying (α, α ⋅ ρ)-RDP for all α ∈ (1, ∞). Rényi DP inherits the nice composition properties of concentrated DP:

Lemma 3.30.Let $M_{1} : X^{n} \to Y_{1}$ be (α, ε₁)-RDP. Let $M_{2} : X^{n} \times Y_{1} \to Y_{2}$ be such that, for all y₁ ∈ Y₁, the algorithm x ↦ M(x,y₁) is (α,ε₂)-RDP. Define $M : X^{n} \to Y_{2}$ by M(x) = M₂(x, M₁(x)). Then M is (α, ε₁ + ε₂)-RDP.

The proof of Lemma 3.30 is identical to that of Proposition 3.19. Note that, while the ε parameter adds up, the α parameter does not change. More generally, composing an (α₁,ε₁)-RDP algorithm with an (α₂,ε₂)-RDP algorithm yields (min{α₁,α₂ },ε₁+ε₂)-RDP.

It is helpful to think of ε in (α, ε)-RDP as a function of α, rather than a single number. This function can encode a rich variety of privacy guarantees. (Concentrated DP corresponds to a linear function.) In particular, it allows us to more precisely represent the kinds of guarantees obtained by subsampling.

Concentrated DP corresponds to the privacy loss being subgaussian (i.e., ρ-zCDP implies $\underset{Z \leftarrow PrivLoss (M (x) ‖ M (x^{'}))}{ℙ} [Z > \tilde{ε}] \leq \exp (- {(\tilde{ε} - ρ)}^{2} / 4 ρ)$ for all $\tilde{ε} \geq ρ$ and all neighboring inputs x and x′), whereas Rényi DP corresponds to the privacy loss being subexponential (i.e., (α, ε)-RDP implies $\underset{Z \leftarrow PrivLoss (M (x) ‖ M (x^{'}))}{ℙ} [Z > \tilde{ε}] \leq \exp (- (α - 1) (\tilde{ε} - ε)))$ ⁠. That is, Rényi DP is more appropriate for analyzing privacy loss distributions with slightly heavier tails than Gaussian. In contrast, pure DP corresponds to the privacy loss being bounded (i.e., ε-DP implies $\underset{Z \leftarrow PrivLoss (M (x) ‖ M (x^{'}))}{ℙ} [Z > ε] = 0$ ⁠). So we can view concentrated DP as a relaxation of pure DP and, in turn, Rényi DP is a relaxation of concentrated DP.

Rényi DP is typically formulated in terms of Rényi divergences [Rén61], which were studied in the information theory literature long before differential privacy was discovered.

Definition 3.31 (Rényi Divergences). Let P and Q be distributions over $Y$ ⁠.^{^x}For α ∈ (1, ∞), define

\begin{matrix} D_{α} (P ‖ Q) & = \frac{1}{α - 1} \log \underset{Z \leftarrow PrivLoss (P ‖ Q)}{E} [\exp ((α - 1) Z)] \\ = \frac{1}{α - 1} \log \underset{Y \leftarrow P}{E} [{(\frac{P (Y)}{Q (Y)})}^{α - 1}] \\ = \frac{1}{α - 1} \log \underset{Y \leftarrow Q}{E} [{(\frac{P (Y)}{Q (Y)})}^{α}] . \end{matrix}

Also, define

\begin{matrix} D_{1} (P ‖ Q) & = \lim_{α \to 1} D_{α} (P ‖ Q) \\ = \underset{Z \leftarrow PrivLoss (P ‖ Q)}{E} [Z] \\ = \underset{Y \leftarrow P}{E} [\log (\frac{P (Y)}{Q (Y)})], \\ D_{\infty} (P ‖ Q) & = \lim_{α \to \infty} D_{α} (P ‖ Q) \\ = \sup {\log (\frac{P (S)}{Q (S)}) : S \subset Y, Q (S) > 0} . \end{matrix}

Thus an equivalent definition of M satisfying (α, ε)-RDP is that D_α (M(x)∥M(x′)) ≤ ε for all neighboring x,x′.

We now state several key properties of Rényi divergences; most of these are properties we have proved earlier, but we now restate them in a new language.

Lemma 3.32.Let P, Q be probability distributions over $Y$ with a common sigmaalgebra such that P is absolutely continuous with respect to Q.

Post-processing (a.k.a. data processing inequality) & non-negativity: Let $f : Y \to Z$ be a measurable function. Let f(P) denote the distribution on $Z$ obtained by applying f to a sample from P; define f(Q) similarly. Then 0 ≤ D_α (f(P)∥f(Q)) ≤ D_α (P∥Q) for all α ∈ [1, ∞].
Composition: If P = P′ × P″ and Q = Q′ × Q″ are product distributions, then D_α (P∥Q) = D_α (P′ ∥ Q′) + D_α (P″ ∥ Q″) for all α ∈ [1, ∞].
More generally, suppose P and Q are distributions on $Y = Y^{'} \times Y^{''}$ ⁠. Let P′ and Q′ be the marginal distributions on $Y^{'}$ induced by P and Q respectively. For $y^{'} \in Y^{'}$ ⁠, let $P_{y^{'}}^{''}$ and $Q_{y^{'}}^{''}$ ⁠, be the conditional distributions on $Y^{''}$ induced by P and Q respectively. That is, we can generate a sample Y = (Y′, Y″) ← P by first sampling Y′ ← P′ and then sampling $Y^{''} \leftarrow P_{Y^{'}}^{''}$ and similarly for Q. Then $D_{α} (P ‖ Q) \leq D_{α} (P^{'} ‖ Q^{'}) + \sup_{y^{'} \in Y^{'}} D_{α} (P_{y^{'}}^{''} ‖ Q_{y^{'}}^{''})$ for all α ∈ [1, ∞].
Monotonicity: For all $1 \leq α \leq α^{'} \leq \infty, D_{α} (P ‖ Q) \leq D_{α^{'}} (P ‖ Q)$ ⁠.
Gaussian divergence: For all μ, μ′, σ ∈ ℝ with σ > 0 and all α ∈ [1, ∞),
$D_{α} (N (μ, σ^{2}) ‖ N (μ^{'}, σ^{2})) = α \cdot \frac{{(μ - μ^{'})}^{2}}{2 σ^{2}} .$
Pure DP to Concentrated DP: For all α ∈ [1, ∞),
$D_{α} (P ‖ Q) \leq \frac{α}{8} \cdot {(D_{\infty} (P ‖ Q) + D_{\infty} (Q ‖ P))}^{2} .$
Quasi-convexity: Let P′ and Q′ be probability distributions over $Y$ such that P′ is absolutely continuous with respect to Q′. For s ∈ [0, 1], let (1 − s) ⋅ P + s ⋅ P′ denote the convex combination of the distributions P and P′ with weighting s. For all α ∈ (1, ∞) and all s ∈ [0,1],
$\begin{array}{l} D_{α} ((1 - s) ∣ \cdot P + s \cdot P^{'} ‖ (1 - s) \cdot Q + s \cdot Q^{'}) \\ \leq \frac{1}{α - 1} \log ((1 - s) \cdot \exp ((α - 1) D_{α} (P ‖ Q)) \\ + s \cdot \exp ((α - 1) D_{α} (P^{'} ‖ Q^{'}))) \\ \leq \max {D_{α} (P ‖ Q), D_{α} (P^{'} ‖ Q^{'})} \end{array}$
and D₁((1−s) ⋅ P + s ⋅ P′∥(1 − s) ⋅ Q + s ⋅ Q′) ≤ (1 − s) ⋅ D₁(P∥Q) + s ⋅ D₁(P′∥Q′).
Triangle-like inequality (a.k.a. group privacy): Let R be a distribution on $Y$ and assume that Q is absolutely continuous with respect to R. For all 1 < α < α′ < ∞,
$D_{α} (P ‖ R) \leq \frac{α^{'}}{α^{'} - 1} \cdot D_{α \cdot \frac{α^{'} - 1}{α^{'} - α}} (P ‖ Q) + D_{α^{'}} (Q ‖ R) .$
In particular, if D_α (P∥Q) ≤ ρ₁ ⋅ α and D_α (Q∥R) ≤ ρ₂ ⋅ α for all α ∈ (1, ∞), then $D_{α} (P ‖ R) \leq {(\sqrt{ρ_{1}} + \sqrt{ρ_{2}})}^{2} \cdot α$ for all α ∈ (1, ∞).
Conversion to approximate DP: For all measurable $S \subset Y$ ⁠, all α ∈ (1, ∞), and all $\tilde{ε} \geq D_{α} (P ‖ Q)$ ⁠,
$\begin{matrix} P (S) & \leq e^{\tilde{ε}} \cdot Q (S) + e^{- (α - 1) (\tilde{ε} - D_{α} (P ‖ Q))} \cdot \frac{1}{α} \cdot {(1 - \frac{1}{α})}^{α - 1} \\ \leq e^{\tilde{ε}} \cdot Q (S) + e^{- (α - 1) (\tilde{ε} - D_{α} (P ‖ Q))} . \end{matrix}$

Proof. 1. Post-processing (a.k.a. data processing inequality) & non-negativity: See Lemma 3.20. Non-negativity follows from setting f to be a constant function and noting that the divergence between two point masses is zero.
2. Composition: See Proposition 3.19.
3. Monotonicity: Let 1 < α ≤ α′ < ∞. (The cases where α = 1 and α′ = ∞ follow from continuity.) Let $f (x) = x^{\frac{α^{'} - 1}{α - 1}}$ ⁠. Then f is convex and, by Jensen's inequality,
$\begin{matrix} e^{(α^{'} - 1) D_{α} (P ‖ Q)} & = f (\underset{Y \leftarrow P}{E} [{(\frac{P (Y)}{Q (Y)})}^{α - 1}]) \\ \leq \underset{Y \leftarrow P}{E} [f ({(\frac{P (Y)}{Q (Y)})}^{α - 1})] = e^{(α^{'} - 1) D_{α^{'}} (P ‖ Q)}, \end{matrix}$
which implies $D_{α} (P ‖ Q) \leq D_{α^{'}} (P ‖ Q)$ ⁠.
4. Gaussian divergence: See Lemma 3.12.
5. Pure DP to Concentrated DP: See Proposition 3.16.
6. Quasi-convexity: See Lemma B. 6 of Bun and Steinke [BS16].
7. Triangle-like inequality (a.k.a. group privacy): Let α ∈ (1,∞). Let p, q ∈ (1, ∞) satisfy $\frac{1}{p} + \frac{1}{q} = 1$ ⁠. By Hölder's inequality,
$\begin{matrix} e^{(α - 1) D_{α} (P ‖ R)} & = \underset{Y \leftarrow P}{E} [{(\frac{P (Y)}{R (Y)})}^{α - 1}] = \underset{Y \leftarrow R}{E} [{(\frac{P (Y)}{R (Y)})}^{α}] \\ = \underset{Y \leftarrow Q}{E} [\frac{P (Y)}{Q (Y)} \cdot {(\frac{P (Y)}{Q (Y)} \cdot \frac{Q (Y)}{R (Y)})}^{α - 1}] \\ = \underset{Y \leftarrow Q}{E} [{(\frac{P (Y)}{Q (Y)})}^{α} \cdot {(\frac{Q (Y)}{R (Y)})}^{α - 1}] \\ \leq \underset{Y \leftarrow Q}{E} {[{(\frac{P (Y)}{Q (Y)})}^{α p}]}^{1 / p} \cdot \underset{Y \leftarrow Q}{E} {[{(\frac{Q (Y)}{R (Y)})}^{(α - 1) q}]}^{1 / q} \\ = e^{\frac{α p - 1}{p}} D_{α p} (P ‖ Q) \cdot e^{\frac{(α - 1) q}{q}} D_{(α - 1) q + 1} (Q ‖ R) . \end{matrix}$
This rearranges to
$\begin{matrix} D_{α} (P ‖ R) & \leq \frac{α p - 1}{(α - 1) p} D_{α p} (P ‖ Q) + D_{(α - 1) q + 1} (Q ‖ R) \\ = (1 + \frac{1}{(α - 1) q}) \cdot D_{α p} (P ‖ Q) + D_{(α - 1) q + 1} (Q ‖ R) \\ = \frac{α^{'}}{α^{'} - 1} \cdot D_{α \cdot \frac{α^{'} - 1}{α^{'} - α}} (P ‖ Q) + D_{α^{'}} (Q ‖ R), \end{matrix}$
where the final equality sets $p = \frac{α^{'} - 1}{α^{'} - α}$ and $q = \frac{α^{'} - 1}{α - 1}$
Now assume D_α (P∥Q) ≤ ρ₁ ⋅ α and D_α (Q∥R) ≤ ρ₂ ⋅ α for all α ∈ (1, ∞). Then
$\begin{matrix} D_{α} (P ‖ R) & \leq \inf_{α^{'} > α} \frac{α^{'}}{α^{'} - 1} \cdot D_{α \cdot \frac{α^{'} - 1}{α^{'} - α}} (P ‖ Q) + D_{α^{'}} (Q ‖ R) \\ \leq \inf_{α^{'} > α} \frac{α^{'}}{α^{'} - 1} \cdot α \cdot \frac{α^{'} - 1}{α^{'} - α} \cdot ρ_{1} + α^{'} \cdot ρ_{2} \\ = \inf_{x > 0} α \cdot \frac{x + 1}{x} \cdot ρ_{1} + α \cdot (x + 1) \cdot ρ_{2} (Reparameterize α^{'} = (x + 1) \cdot α) \\ = α \cdot \inf_{x > 0} ρ_{1} + ρ_{2} + \frac{1}{x} ρ_{1} + x \cdot ρ_{2} \\ = α \cdot (ρ_{1} + ρ_{2} + 2 \sqrt{ρ_{1} \cdot ρ_{2}}) (x = \sqrt{ρ_{1} / ρ_{2}}) \\ = α \cdot {(\sqrt{ρ_{1}} + \sqrt{ρ_{2}})}^{2} . \end{matrix}$
8. Conversion to approximate DP: See Proposition 3.14.

3.6.5 Sharp Privacy Amplification by Poisson Subsampling for Rényi DP

Now we analyze privacy amplification by subsampling under Rényi DP. We start with a Rényi DP guarantee and we obtain an amplified Rényi DP guarantee. The goal is to obtain a sharp analysis that avoids converting to approximate DP and back.

For mathematical simplicity, we restrict our attention to Poisson subsampling and assume that neighboring datasets correspond to addition or removal of one person's data.

Theorem 3.33 (Tight Privacy Amplification by Subsampling for Rényi DP). Let U ⊂ [n] be a random set that contains each element independently with probability p. For $x \in X^{n}$ let $x_{U} \in X^{n}$ be given by ${(x_{U})}_{i} = x_{i}$ if i ∈ U and ${(x_{U})}_{i} = ⊥$ if i ∉ U, where $⊥ \in X$ is some fixed value.

Let $ε : ℕ_{\geq 2} \to ℝ \cup {\infty}$ be a function. Let $M : X^{n} \to Y$ satisfy (α, ε(α))-RDP for all $α \in ℕ_{\geq 2}$ with respect to addition or removal – i.e., $x, x^{'} \in X^{n}$ are neighboring if, for some i ∈ [n], we have x_i = ⊥ or $x_{i}^{'} = ⊥$ ⁠, and $\forall j \neq i x_{j} = x_{j}^{'}$ ⁠.

Define $M^{U} : X^{n} \to Y$ by M^U (x) = M(x_U). Then M^U satisfies $(α, ε_{p}^{'} (α)) - R D P$ -RDP for all $α \in ℕ_{\geq 2}$ where

\begin{matrix} ε_{p}^{'} (α) = & \frac{1}{α - 1} \log ({(1 - p)}^{α - 1} (1 + (α - 1) p) \\ + \sum_{k = 2}^{α} (\begin{matrix} α \\ k \end{matrix}) {(1 - p)}^{α - k} p^{k} \cdot e^{(k - 1) ε (k)}) . \end{matrix}

Note that (1 − p)^α−1(1 + (α − 1)p) ≤ 1. It is easy to see from the proof that this analysis is tight. That is, if the assumption that M satisfies (α, ε(α))-RDP for all α is tight for some fixed pair of neighboring inputs, then the conclusion that M^U satisfies $(α, ε_{p}^{'} (α))$ -RDP is also tight.

Theorem 3.33 only considers Rényi DP with orders $α \in ℕ_{\geq 2} = {2, 3, 4, \dots}$ ⁠. This restriction arises because the proof uses a binomial expansion, which only works for integer exponents. In certain cases, it is possible to obtain an expression all α ∈ (1, ∞) using an infinite binomial series [MTZ19]. In general, we can use Monotonicity (part 3 of Lemma 3.32) to bound non-integer α, namely for all α ∈ (1, ∞), M^U satisfies $(α, ε_{p}^{'} (α))$ -RDP.

Proof of Theorem 3.33. Fix neighboring datasets $x, x^{'} \in X^{n}$ ⁠. Without loss of generality, assume that x′ is x with one element removed – i.e., $\exists i \in [n] (x_{i}^{'} = ⊥) \land (\forall j \in [n] \ {i} x_{j} = x_{j}^{'})$ ⁠. Fix this i.

Let $Q = M (x_{U}^{'}) = M^{U} (x^{'})$ ⁠. Let $P = {M (x_{U}) |}_{i \in U}$ be the conditional distribution of M(x_U) with i ∈ U. Note that ${M (x_{U}) |}_{i \notin U} = Q$ because $x_{U} = x_{U}^{'}$ when i ∉ U and the event i ∈ U is independent from U \ {i}. (This is where we use the Poisson subsampling assumption.)

Thus we can express the distribution of M^U (x) as a convex combination: M(x_U) = p ⋅ P + (1 − p) ⋅ Q, since $p = ℙ [i \in U]$ ⁠.

For all $α \in ℕ_{\geq 2}, M$ is assumed to be (α,ε(α))-RDP, so we have D_α (P∥Q) ≤ ε(α) and D_α (Q∥P) ≤ ε(α).

To complete the proof we must show that

D_{α} (p \cdot P + (1 - p) \cdot Q ‖ Q) \leq ε_{p}^{'} (α)

and

D_{α} (Q ‖ p \cdot P + (1 - p) \cdot Q) \leq ε_{p}^{'} (α)

for all $α \in ℕ_{\geq 2}$ ⁠.

Fix $α \in ℕ_{\geq 2}$ ⁠. We have

\begin{matrix} e^{(α - 1) D_{α} (p \cdot P + (1 - p) \cdot Q ‖ Q)} & = \underset{Y \leftarrow Q}{E} [{(\frac{p \cdot P (Y) + (1 - p) \cdot Q (Y)}{Q (Y)})}^{α}] \\ = \underset{Y \leftarrow Q}{E} [{(1 - p + p \cdot \frac{P (Y)}{Q (Y)})}^{α}] \\ = \underset{Y \leftarrow Q}{E} [\sum_{k = 0}^{α} (\begin{matrix} α \\ k \end{matrix}) {(1 - p)}^{α - k} p^{k} {(\frac{P (Y)}{Q (Y)})}^{k}] (Binomial expansion) \\ = \sum_{k = 0}^{α} \underset{k}{α} (\begin{matrix} α \\ k \end{matrix}) {(1 - p)}^{α - k} p^{k} \underset{Y \leftarrow Q}{E} [{(\frac{P (Y)}{Q (Y)})}^{k}] \\ = {(1 - p)}^{α} + α {(1 - p)}^{α - 1} p + \sum_{k = 2}^{α} (\begin{matrix} α \\ k \end{matrix}) {(1 - p)}^{α - k} p^{k} \cdot e^{(k - 1) D_{k} (P ‖ Q)} (\underset{Y \leftarrow Q}{E} [\frac{P (Y)}{Q (Y)}] = 1) \\ \leq {(1 - p)}^{α - 1} (1 + (α - 1) p) + \sum_{k = 2}^{α} (\begin{matrix} α \\ k \end{matrix}) {(1 - p)}^{α - k} p^{k} \cdot e^{(k - 1) ε (k)} (D_{k} (P ‖ Q) \leq ε (k)) \\ = e^{(α - 1) ε_{p}^{'} (α)} . \end{matrix}

Note that ${(1 - p)}^{α - 1} (1 + (α - 1) p) \leq {(e^{- p})}^{α - 1} e^{(α - 1) p} = 1$ ⁠.

An identical calculation shows that

D_{α} (p \cdot Q + (1 - p) \cdot P ‖ P) \leq ε_{p}^{'} (α) .

Finally, Theorem 3.34 gives

D_{α} (Q ‖ p P + (1 - p) Q) \leq \max {\begin{matrix} D_{α} (p P + (1 - p) Q ‖ Q), \\ D_{α} (p Q + (1 - p) P ‖ P) \end{matrix}} \leq ε_{p}^{'} (α) .

The following result shows that, in terms of subsampling for Rényi DP, it suffices to analyze one side of the add/remove neighboring relation.

Theorem 3.34.Let P and Q be probability distributions that are absolutely continuous with respect to each other. Let p ∈ [0,1] and α ∈ (1, ∞). Set $λ = \frac{(2 α - 1) p}{(2 α - 1) p + 3 (1 - p)}$ ⁠. Then

\begin{matrix} e^{(α - 1) D_{α} (Q ‖ p P + (1 - p) Q)} & \leq (1 - λ) \cdot e^{(α - 1) D_{α} (p P + (1 - p) Q ‖ Q)} \\ + λ \cdot e^{(α - 1) D_{α} (p Q + (1 - p) P ‖ P)} . \end{matrix}

Since λ ∈ [0,1], this implies

D_{α} (Q ‖ p P + (1 - p) Q) \leq \max {\begin{matrix} D_{α} (p P + (1 - p) Q ‖ Q), \\ D_{α} (p Q + (1 - p) P ‖ P) \end{matrix}} .

Proof. Define f : (0, ∞) → ℝ by

f (x) = (1 - λ) {(1 - p + p \cdot x)}^{α} + λ \cdot x \cdot {(1 - p + \frac{p}{x})}^{α} - {(1 - p + p \cdot x)}^{1 - α} .

We have

\begin{matrix} (1 - λ) \cdot e^{(α - 1) D_{α} (p P + (1 - p) Q ‖ Q)} + λ \cdot e^{(α - 1) D_{α} (p Q + (1 - p) P ‖ P)} - e^{(α - 1) D_{α} (Q ‖ p P + (1 - p) Q)} \\ = (1 - λ) \cdot \underset{Y \leftarrow Q}{E} [{(\frac{p P (Y) + (1 - p) Q (Y)}{Q (Y)})}^{α}] + λ \cdot \underset{Y \leftarrow P}{E} [{(\frac{p Q (Y) + (1 - p) P (Y)}{P (Y)})}^{α}] - \underset{Y \leftarrow Q}{E} [{(\frac{Q (Y)}{p P (Y) + (1 - p) Q (Y)})}^{α - 1}] \\ = (1 - λ) \cdot \underset{Y \leftarrow Q}{E} [{(p \frac{P (Y)}{Q (Y)} + (1 - p))}^{α}] + λ \cdot \underset{Y \leftarrow P}{E} [{(p {(\frac{P (Y)}{Q (Y)})}^{- 1} + 1 - p)}^{α}] - \underset{Y \leftarrow Q}{E} [{(p \frac{P (Y)}{Q (Y)} + (1 - p))}^{1 - α}] \\ = (1 - λ) \cdot \underset{Y \leftarrow Q}{E} [{(p \frac{P (Y)}{Q (Y)} + (1 - p))}^{α}] + λ \cdot \underset{Y \leftarrow Q}{E} [\frac{P (Y)}{Q (Y)} \cdot {(p {(\frac{P (Y)}{Q (Y)})}^{- 1} + 1 - p)}^{α}] - \underset{Y \leftarrow Q}{E} [{(p \frac{P (Y)}{Q (Y)} + (1 - p))}^{1 - α}] (For any g, \underset{Y \leftarrow Q}{E} [\frac{P (Y)}{Q (Y)} g (Y)] = \underset{Y \leftarrow P}{E} [g (Y)]) \\ = \underset{Y \leftarrow Q}{E} [(1 - λ) \cdot {(1 - p + p \cdot \frac{P (Y)}{Q (Y)})}^{α} + λ \cdot \frac{P (Y)}{Q (Y)} \cdot {(1 - p + \frac{p}{\frac{P (Y)}{Q (Y)}})}^{α} - {(1 - p + p \cdot \frac{P (Y)}{Q (Y)})}^{1 - α}] \\ = \underset{X}{E} [f (X)], \end{matrix}

where $X = \frac{P (Y)}{Q (Y)}$ for Y ← Q. Thus our objective is to show that $\underset{X}{E} [f (X)] \geq 0.$ ⁠.^{^xi}

We claim that f is convex. Convexity implies f(x) ≥ f(1) + f′ (1) ⋅ (x − 1) for all x ∈ (0, ∞). Since f(1) = 0 and $E [X] = \underset{Y \leftarrow Q}{E} [\frac{P (Y)}{Q (Y)}] = 1$ ⁠, this implies $E [f (X)] \geq f (1) + f^{'} (1) E [X - 1] = 0$ ⁠, as required.

It only remains to prove that f is convex. We have, for all x > 0,

\begin{matrix} f (x) & = (1 - λ) {(1 - p + p \cdot x)}^{α} + λ \cdot x \cdot {(1 - p + \frac{p}{x})}^{α} - {(1 - p + p \cdot x)}^{1 - α} \\ f^{'} (x) & = (1 - λ) α p {(1 - p + p \cdot x)}^{α - 1} + λ \cdot {(1 - p + \frac{p}{x})}^{α} - λ α \frac{p}{x} {(1 - p + \frac{p}{x})}^{α - 1} + (α - 1) p {(1 - p + p \cdot x)}^{- α} \\ f^{''} (x) & = (1 - λ) α (α - 1) p^{2} {(1 - p + p \cdot x)}^{α - 2} - λ α \frac{p}{x^{2}} {(1 - p + \frac{p}{x})}^{α - 1} + λ α \frac{p}{x^{2}} {(1 - p + \frac{p}{x})}^{α - 1} + λ α (α - 1) \frac{p^{2}}{x^{3}} {(1 - p + \frac{p}{x})}^{α - 2} - α (α - 1) p^{2} {(1 - p + p \cdot x)}^{- α - 1} \\ = α (α - 1) p^{2} ((1 - λ) {(1 - p + p x)}^{α - 2} + λ \frac{1}{x^{3}} {(1 - p + \frac{p}{x})}^{α - 2} - {(1 - p + p x)}^{- α - 1}) \\ = \frac{α (α - 1) p^{2}}{{(1 - p + p x)}^{α + 1}} ((1 - λ) {(1 - p + p x)}^{2 α - 1} + λ \frac{1}{x^{3}} {(1 - p + \frac{p}{x})}^{α - 2} \cdot {(1 - p + p x)}^{α + 1} - 1) \\ = \frac{α (α - 1) p^{2}}{{(1 - p + p x)}^{α + 1}} ((1 - λ) {(1 - p + p x)}^{2 α - 1} + λ {(\frac{1 - p + p x}{x})}^{3} \cdot {(1 - p + \frac{p}{x})}^{α - 2} \cdot {(1 - p + p x)}^{α - 2} - 1) \\ \geq \frac{α (α - 1) p^{2}}{{(1 - p + p x)}^{α + 1}} \times ((1 - λ) {(1 - p + p x)}^{2 α - 1} + λ {(\frac{1 - p + p x}{x})}^{3} \cdot 1 - 1) (Lemma 3 .35) \\ = \frac{α (α - 1) p^{2}}{{(1 - p + p x)}^{α + 1}} {(\begin{matrix} 3 (1 - p) {(1 - p + p x)}^{2 α - 1} \\ + (2 α - 1) p {(\frac{1 - p}{x} + p)}^{3} \\ \frac{- 3 (1 - p) - (2 α - 1) p}{3 (1 - p) + (2 α - 1) p} \end{matrix})}_{(λ = \frac{(2 α - 1) p}{(2 α - 1) p + 3 (1 - p)})} \\ \geq 0 (Lemma 3 .36) \end{matrix}

We now give the auxiliary lemmata used in the proof of Theorem 3.34.

Lemma 3.35.For all p ∈ [0,1] and x ∈ (0, ∞),

\frac{1}{1 - p + p / x} \leq 1 - p + p \cdot x .

Proof. Let f(t) = t+1/t. Then f′ (t) = 1 − 1/t² and f″(t) = 2/t³ > 0 for all t > 0. Thus f′(t) = 0 ⟺ t = 1 and f(x) ≥ f(1) = 2. Now

\begin{matrix} (1 - p + p \cdot x) \cdot (1 - p + p / x) & = p^{2} + {(1 - p)}^{2} + p (1 - p) (x + 1 / x) \\ \geq p^{2} + {(1 - p)}^{2} + p (1 - p) \cdot 2 \\ = {(p + (1 - p))}^{2} = 1. \end{matrix}

Rearranging yields the result.

Lemma 3.36.For all v ≥ 1, p ∈ [0,1], and x ∈ (0, ∞),

3 (1 - p) {(1 - p + p x)}^{v} + v p {(\frac{1 - p}{x} + p)}^{3} \geq 3 (1 - p) + v p .

Proof. Define f : (0, ∞) → ℝ by

f (x) = 3 (1 - p) {(1 - p + p x)}^{v} + v p {(\frac{1 - p}{x} + p)}^{3} .

Our goal is to prove that f(x) ≥ f(1) = 3(1 − p) + vp for all x ∈ (0, ∞). It suffices to prove that f is convex and that f′(1) = 0. We have

f^{'} (x) = 3 v p (1 - p) ({(1 - p + p x)}^{v - 1} - \frac{1}{x^{2}} {(\frac{1 - p}{x} + p)}^{2}),

f^{''} (x) = 3 v p (1 - p) ((v - 1) p {(1 - p + p x)}^{v - 2} + \frac{2}{x^{3}} \cdot {(\frac{1 - p}{x} + p)}^{2} + \frac{2}{x^{2}} \cdot \frac{1 - p}{x^{2}} \cdot (\frac{1 - p}{x} + p)) .

From these expressions, it is easy to see that f′(1) = 0 and f″(x) ≥ 0 for all x ∈ (0,∞).

3.6.6 Analytic Rényi DP Bound for Privacy Amplification by Poisson Subsampling

Theorem 3.33 gives a tight RDP bound for privacy amplification by Poisson subsampling. However, the bound is in the form of a series. This is adequate for numerical purposes, but it is helpful for our understanding to have a simpler closed-form expression.

In this subsection we will provide a simpler expression and attempt to build some understanding of how privacy amplification by subsampling applies to Rényi DP.

Comparison of Rényi divergence guarantees for Poisson subsampling – i.e., including each person with probability p = 0.05. The unamplified algorithm satisfies 0.5-zCDP. The exact bound is given by Theorem 3.33. For comparison, we have the analytic upper bound from Proposition 3.40 as well as the behavior in the limit given by Proposition 3.41.

Figure 3.2

Plot of R D P bounds for Poisson subsampling, showing curves labeled exact, unamplified, analytic, and limit versus Renyi order alpha.

View large Download slide

Comparison of Rényi divergence guarantees for Poisson subsampling – i.e., including each person with probability p = 0.05. The unamplified algorithm satisfies 0.5-zCDP. The exact bound is given by Theorem 3.33. For comparison, we have the analytic upper bound from Proposition 3.40 as well as the behavior in the limit given by Proposition 3.41.

Theorem 3.37 (Asymptotic Privacy Amplification by Subsampling for Rényi DP). Let p ∈ [0,1/2] and ρ ∈ (0,1]. Define $ω = \min {\frac{\log (1 / p)}{4 ρ}, 1 + p^{- 1 / 4}}$ ⁠. Assume $ω \geq 3 + 2 \frac{\log (1 / ρ)}{\log (1 / p)}$ ⁠.

Let $M : X^{n} \to Y$ satisfy ρ-zCDP with respect to addition or removal.^{^xii}

Define $M^{U} : X^{n} \to Y$ by M^U(x) = M(x_U), where U ⊂ [n] be a random set that contains each element independently with probability p and, for $x \in X^{n}, x_{U} \in X^{n}$ is given by (x_U)_i = x_i if i ∈ U and (x_U)_i = ⊥ if i ∉ U.

Then M^U satisfies (α,10p²ρα)-RDP for all α ∈ (1, ω).

There are many caveats in the statement of Theorem 3.37, but the high level message is that Poisson subsampling a p fraction of the dataset amplifies ρ-zCDP to something like O(p² ⋅ ρ)-zCDP. We will discuss these caveats in a moment, but, ignoring these caveats and the constant factor in the guarantee, this is exactly the kind of guarantee we would hope for.

Consider the following example, which illustrates what kind guarantee we would hope for. Suppose we have a query $q : X \to [0, 1]$ and a sensitive dataset $x \in X^{n}$ and our goal is to estimate $q (x) : = \frac{1}{n} \sum_{i}^{n} q (x_{i})$ ⁠. We could release a sample from $N (q (x), σ^{2})$ ⁠, which satisfies $\frac{1}{2 n^{2} σ^{2}}$ -zCDP and has mean squared error σ². However, perhaps due to computational constraints, we might instead select a random p fraction U ⊂ [n] and instead release a sample from $M^{U} (x) = N (\frac{1}{p^{n}} \sum_{i \in U} q (x_{i}), σ^{2})$ ⁠. We can calculate that the mean squared error of this algorithm is at most $σ^{2} + \frac{1 - p}{p n}$ ⁠. Without amplification this satisfies $(ρ = \frac{1}{2 p^{2} n^{2} σ^{2}})$ -zCDP. With amplification, Theorem 3.37 tells us that this satisfies (α, O(p² ⋅ ρ)) RDP for α not too large. Now $p^{2} \cdot ρ = \frac{1}{2 n^{2} σ^{2}}$ is exactly the guarantee that we obtained by simply evaluating q on the entire dataset and avoiding subsampling. We cannot hope to do better than this.

The constant factor of 10 in the theorem can be improved, but a constant factor loss is the price we pay for having a simpler expression; if we want tight constants we should apply Theorem 3.33.

The main caveat in Theorem 3.37 is the requirement that $α \leq ω \leq \frac{\log (1 / p)}{4 ρ}$ ⁠. This is necessary, as the (α, ε(α))-RDP guarantee qualitatively changes when α ≥ O(log(1/p)/ρ). It changes from ε(α) = O(p²ρα) to ε(α) = ρα−O(log(1/p)). To see why this is inherent, consider the following lower bound. For all p ∈ [0,1], all α ∈ (1, ∞), and all absolutely continuous probability distributions P and Q, we have

\begin{matrix} e^{(α - 1) D_{α} (p P + (1 - p) Q ‖ Q)} & = \underset{Y \leftarrow Q}{E} [{(1 - p + p \cdot \frac{P (Y)}{Q (Y)})}^{α}] \\ \geq \underset{Y \leftarrow Q}{E} [{(p \cdot \frac{P (Y)}{Q (Y)})}^{α}] = p^{α} \cdot e^{(α - 1) D_{α} (P ‖ Q)} . \end{matrix}

Thus $D_{α} (p P + (1 - p) Q ‖ Q) \geq D_{α} (P ‖ Q) - \frac{α}{α - 1} \log (1 / p)$ ⁠. This tells us that, for large α, we cannot have more than an additive improvement in the RDP guarantee, whereas for small α we have a multiplicative improvement. Proposition 3.41 shows that this lower bound is tight.

We now proceed to prove Theorem 3.37.

Lemma 3.38.Let α ∈ (1, ∞), p ∈ [0, 1 − e⁻¹], and x ∈ [0, ∞). If either α ≤ 2 or α > 2 and $p x \leq \max {p, \frac{1 - p}{α - 2}}$ ⁠, then

{(1 - p + p \cdot x)}^{α} \leq 1 + α p (x - 1) + \frac{e}{2} α (α - 1) p^{2} {(x - 1)}^{2} .

Proof. We assume p > 0. Otherwise the result is trivial.

Define f : (0, ∞) → ℝ by

f (x) = {(1 - p + p x)}^{α} .

For all x ∈ [0,∞), we have

\begin{matrix} f^{'} (x) & = α p {(1 - p + p x)}^{α - 1}, \\ f^{''} (x) & = α (α - 1) p^{2} {(1 - p + p x)}^{α - 2}, \\ f^{'''} (x) & = α (α - 1) (α - 2) p^{3} {(1 - p + p x)}^{α - 3} . \end{matrix}

By Taylor's theorem, for all x ∈ [0,∞), there exists ξ_x ∈ [min{1,x},max{1,x}] such that

\begin{matrix} f (x) & = f (1) + f^{'} (1) (x - 1) + \frac{1}{2} f^{''} (ξ_{x}) {(x - 1)}^{2} \\ = 1 + α p (x - 1) + \frac{1}{2} f^{''} (ξ_{x}) {(x - 1)}^{2} . \end{matrix}

To complete the proof is suffices to show that f″ (ξ) ≤ e ⋅ α(α−1)p² in two cases: First, for all ξ ∈ [0, ∞) assuming α ≤ 2. Second, for all $ξ \in [0, \max {1, \frac{1 - p}{p} \frac{1}{α - 2}}]$ assuming α > 2. (Note that, $ξ_{x} \in [0, \max {1, \frac{1 - p}{p} \frac{1}{α - 2}}]$ is implied by the assumptions $p x \leq \max {p, \frac{1 - p}{α - 2}}$ and p > 0.)

First, suppose α ≤ 2. Then f″′)(x) ≤ 0 for all x ∈ [0, ∞). Thus f″ is decreasing (or constant) and, for all ξ ∈ [0, ∞), we have

\begin{matrix} f^{''} (ξ) & \leq f^{''} (0) \\ = α (α - 1) p^{2} {(1 - p)}^{α - 2} \\ \leq α (α - 1) p^{2} \frac{1}{1 - p} (α > 1) \\ \leq α (α - 1) p^{2} \cdot e . (p \leq 1 - e^{- 1}) \end{matrix}

Second, assume α > 2 and $p x \leq \max {p, \frac{1 - p}{α - 2}}$ ⁠, which implies $ξ_{x} \leq \max {1, \frac{1 - p}{p} \frac{1}{α - 2}}$ ⁠.

We have f″′(x) > 0 for all x ∈ [0, ∞). Thus f″ is increasing and, for all $ξ \in [0, \max {1, \frac{1 - p}{p} \frac{1}{α - 2}}]$ ⁠, we have

\begin{matrix} f^{''} (ξ) & \leq f^{''} (\max {1, \frac{1 - p}{p} \frac{1}{α - 2}}) \\ = α (α - 1) p^{2} {(1 - p + p \cdot \max {1, \frac{1 - p}{p} \frac{1}{α - 2}})}^{α - 2} \\ = α (α - 1) p^{2} \max {1, {(1 - p)}^{α - 2} \cdot {(1 + \frac{1}{α - 2})}^{α - 2}} \\ \leq α (α - 1) p^{2} \max {1, {(1 - p)}^{0} \cdot {(e^{\frac{1}{α - 2}})}^{α - 2}} \\ = α (α - 1) p^{2} \cdot e . \end{matrix}

Lemma 3.39.Let α, ω ∈ (1, ∞) with α ≤ ω, p ∈ [0,1−e⁻¹ ], and x ∈ [0, ∞). Then

{(1 - p + p \cdot x)}^{α} \leq 1 + α p (x - 1) + \frac{e}{2} α (α - 1) p^{2} {(x - 1)}^{2} + {((α - 1) p x)}^{ω} .

Proof. We can assume p > 0, as otherwise the result is trivial.

If α ≤ 2 or if α > 2 and $x \leq \max {1, \frac{1 - p}{p} \frac{1}{α - 2}}$ ⁠, then the result follows from Lemma 3.38, as ((α−1)px)^ω ≥ 0.

Thus we assume α > 2 and $x \geq \max {1, \frac{1 - p}{p} \frac{1}{α - 2}}$ ⁠.

Since x ≥ 1, we have $α p (x - 1) + \frac{e}{2} α (α - 1) p^{2} {(x - 1)}^{2} \geq 0$ ⁠. Therefore it suffices to prove that (1 − p + px)^α ≤ ((α − 1)px)^ω.

The assumption x ≥ 1 implies 1 − p + px ≥ 1 and, hence, that (1 − p + px)^α ≤ (1 − p + px)^ω, as we have α ≤ ω. The assumption $x \geq \frac{1 - p}{p} \frac{1}{α - 2}$ rearranges to 1 − p ≤ px(α − 2), which implies 1 − p + px ≤ (α − 1)px and, hence, (1 − p + px)^ω ≤ ((α − 1)px)^ω, as required.

Proposition 3.40 (Analytic Privacy Amplification by Subsampling for Rényi Divergence). Let P and Q be probability distributions with P absolutely continuous with respect to Q. Let p ∈ [0, 1 − e⁻¹] and α, ω ∈ (1, ∞) with α ≤ ω. Then

\begin{array}{l} D_{α} (p P + (1 - p) Q ‖ Q) \\ \begin{array}{l} \leq \frac{1}{α - 1} \log (1 + \frac{e}{2} α (α - 1) p^{2} (e^{D_{2} (P ‖ Q)} - 1) \\ + {((α - 1) p)}^{ω} \cdot e^{(ω - 1) D_{ω} (P ‖ Q)}) \\ \leq α \cdot \frac{e}{2} \cdot p^{2} \cdot (e^{D_{2} (P ‖ Q)} - 1) + p \cdot {((α - 1) \cdot p \cdot e^{D_{ω} (P ‖ Q)})}^{ω - 1} . \end{array} \end{array}

Proof. We have

\begin{array}{l} e^{(α - 1) D_{α} (p P + (1 - p) Q ‖ Q)} \\ = \underset{Y \leftarrow Q}{E} [{(\frac{p \cdot P (Y) + (1 - p) \cdot Q (Y)}{Q (Y)})}^{α}] \\ = \underset{Y \leftarrow Q}{E} [{(1 - p + p \cdot \frac{P (Y)}{Q (Y)})}^{α}] \\ \leq \underset{Y \leftarrow Q}{E} [1 + α p (\frac{P (Y)}{Q (Y)} - 1) + \frac{e}{2} α (α - 1) p^{2} {(\frac{P (Y)}{Q (Y)} - 1)}^{2} \\ + {((α - 1) p \frac{P (Y)}{Q (Y)})}^{ω}] (Lemma 3 .39) \\ = 1 + α p (1 - 1) + \frac{e}{2} α (α - 1) p^{2} (e^{D_{2} (P ‖ Q)} - 1) \\ + {((α - 1) p)}^{ω} \cdot e^{(ω - 1) D_{ω} (P ‖ Q)} . \end{array}

The second inequality in the result follows from the fact that log(1 + u) ≤ u for all u > −1.

We also have the following simpler result that provides better bounds when the Rényi order α is large.

Proposition 3.41.Let P and Q be probability distributions with P absolutely continuous with respect to Q. Let p ∈ [0,1] and α ∈ (1, ∞). Then

\begin{array}{l} D_{α} (p P + (1 - p) Q ‖ Q) \\ \leq \frac{α}{α - 1} \log (1 - p + p \cdot e^{(1 - 1 / α) D_{α} (P ‖ Q)}) \\ = D_{α} (P ‖ Q) - \frac{α}{α - 1} \log (1 / p) + \frac{α}{α - 1} \log (1 + \frac{1 - p}{p} \cdot e^{- \frac{α - 1}{α} D_{α} (P ‖ Q)}) \\ \leq D_{α} (P ‖ Q) - \frac{α}{α - 1} \log (1 / p) + \frac{α}{α - 1} \cdot \frac{1 - p}{p} \cdot e^{- \frac{α - 1}{α} D_{α} (P ‖ Q)} \end{array}

Proof. We assume 0 < p < 1, as the result is immediate otherwise. By Jensen's inequality and the convexity of v ↦ v^α, for all x ∈ [0, ∞) and all λ ∈ (0, 1),

{(1 - p + p x)}^{α} = {((1 - λ) \cdot \frac{1 - p}{1 - λ} + λ \cdot \frac{p x}{λ})}^{α} \leq (1 - λ) \cdot {(\frac{1 - p}{1 - λ})}^{α} + λ \cdot {(\frac{p x}{λ})}^{α} .

Now, for all λ ∈ (0,1), we have

\begin{matrix} e^{(α - 1) D_{α} (p P + (1 - p) Q ‖ Q)} & = \underset{Y \leftarrow Q}{E} [{(1 - p + p \frac{P (Y)}{Q (Y)})}^{α}] \\ \leq \underset{Y \leftarrow Q}{E} [(1 - λ) \cdot {(\frac{1 - p}{1 - λ})}^{α} + λ \cdot {(\frac{p}{λ} \cdot \frac{P (Y)}{Q (Y)})}^{α}] \\ = {(1 - λ)}^{1 - α} \cdot {(1 - p)}^{α} + λ^{1 - α} \cdot p^{α} \cdot e^{(α - 1) D_{α} (P ‖ Q)} . \end{matrix}

We can choose λ to minimize this expression. It turns out to be optimal to set $λ = \frac{1}{1 + \frac{1 - p}{p} \cdot e^{- (1 - 1 / α) D_{α} (P ‖ Q)}}$ ⁠. Now we have

\begin{array}{l} e^{(α - 1) D_{α} (p P + (1 - p) Q ‖ Q)} \\ \leq {(1 - λ)}^{1 - α} \cdot {(1 - p)}^{α} + λ^{1 - α} \cdot p^{α} \cdot e^{(α - 1) D_{α} (P ‖ Q)} \\ = {(1 + \frac{p}{1 - p} e^{(1 - 1 / α) D_{α} (P ‖ Q)})}^{α - 1} \cdot {(1 - p)}^{α} \\ + {(1 + \frac{1 - p}{p} \cdot e^{- (1 - 1 / α) D_{α} (P ‖ Q)})}^{α - 1} \cdot p^{α} \cdot e^{(α - 1) D_{α} (P ‖ Q)} \\ = {(1 - p + p \cdot e^{(1 - 1 / α) D_{α} (P ‖ Q)})}^{α - 1} \cdot (1 - p) \\ + {(p + (1 - p) \cdot e^{- (1 - 1 / α) D_{α} (P ‖ Q)})}^{α - 1} \cdot p \cdot e^{(α - 1) D_{α} (P ‖ Q)} \\ = {(1 - p + p \cdot e^{(1 - 1 / α) D_{α} (P ‖ Q)})}^{α - 1} \cdot (1 - p) \\ + {(p \cdot e^{(1 - 1 / α) D_{α} (P ‖ Q)} + (1 - p))}^{α - 1} \cdot p \cdot e^{(1 - 1 / α) D_{α} (P ‖ Q)} \\ = {(1 - p + p \cdot e^{(1 - 1 / α) D_{α} (P ‖ Q)})}^{α} \cdot \end{array}

Rearranging yields the result.

Proof of Theorem 3.37. Fix neighboring inputs $x, x^{'} \in X^{n}$ ⁠. Fix some α ∈ (1, ω) with $ω = \min {\frac{\log (1 / p)}{4 ρ}, 1 + p^{- 1 / 4}} \geq 3 + 2 \frac{\log (1 / ρ)}{\log (1 / p)}$ ⁠.

Without loss of generality x′ is x with some element removed. That is, we can fix some i ∈ [n] such that $x_{i}^{'} = ⊥$ and $x_{j}^{'} = x_{j}$ for all j≠i.

Let $P = {M (x_{U}) |}_{i \in U}$ and let $Q = {M (x_{U}) |}_{i \notin U}$ ⁠. Then M^U (x) = M(x_U) = pP+(1−p)Q. Also M(x′) = Q

Thus we must prove that D_α (pP+(1−p)Q∥Q) ≤ 10p²ρα and D_α (Q∥pP+(1−p)Q) ≤ 10p²ρα. Since M is assumed to be ρ-zCDP, we have $D_{α^{'}} (P ‖ Q) \leq ρ α^{'}$ and $D_{α^{'}} (Q ‖ P) \leq ρ α^{'}$ for all α′ ∈ (1, ∞).

By Proposition 3.40,

\begin{array}{l} D_{α} (p P + (1 - p) Q ‖ Q) & \leq α \cdot \frac{e}{2} \cdot p^{2} \cdot (e^{D_{2} (P ‖ Q)} - 1) \\ + p \cdot {((α - 1) \cdot p \cdot e^{D_{ω} (P ‖ Q)})}^{ω - 1} \\ \leq α \cdot \frac{e}{2} \cdot p^{2} \cdot (e^{2 ρ} - 1) + p \cdot {((α - 1) \cdot p \cdot e^{ω ρ})}^{ω - 1} \\ \leq α \cdot \frac{e}{2} \cdot p^{2} \cdot (e^{2 ρ} - 1) + p \cdot {(p^{- 1 / 4} \cdot p \cdot p^{- 1 / 4})}^{ω - 1} (α \leq ω = \min {1 + p^{- 1 / 4}, \log (1 / p) / 4 ρ}) \\ = α \cdot \frac{e}{2} \cdot p^{2} \cdot (e^{2 ρ} - 1) + p^{\frac{1 + ω}{2}} \\ \leq α \cdot \frac{e}{2} \cdot p^{2} \cdot (e^{2 ρ} - 1) + p^{2} \cdot ρ (ω \geq 3 + 2 \log (1 / ρ) / \log (1 / p)) \\ = α \cdot p^{2} \cdot ρ \cdot (\frac{e}{2} \cdot \frac{e^{2 ρ} - 1}{ρ} + \frac{1}{α}) \\ \leq α \cdot p^{2} \cdot ρ \cdot 10. (ρ \in (0, 1) a n d α \in (1, ω)) \end{array}

Symmetrically, we have D_α (pQ+(1 − p)P∥P) ≤ α ⋅ p² ⋅ ρ ⋅ 10. By Theorem 3.34,

D_{α} (Q ‖ p P + (1 - p) Q) \leq \max {\begin{array}{l} D_{α} (p P + (1 - p) Q ‖ Q) \\ D_{α} (p Q + (1 - p) P ‖ P) \end{array}} \leq α \cdot p^{2} \cdot ρ \cdot 10.

3.6.7 How to Use Privacy Amplification by Subsampling

The most common use case for privacy amplification by subsampling is analyzing noisy stochastic gradient descent. That is, we repeatedly sample a small subset of the data, compute a function on this subset, and add Gaussian noise. To be precise, let $x \in X^{n}$ be the private input. Iteratively, for t = 1,…, T, we pick some function $q_{t} : X^{n} \to ℝ^{d}$ and randomly sample a subset U_t ⊂ [n]; then we reveal $N (q_{t} (x_{U_{t}}), σ^{2} I_{d})$ ⁠.

The addition of Gaussian noise satisfies concentrated DP. Specifically, Lemma 3.12 shows that releasing $N (q_{t} (x), σ^{2} I_{d})$ satisfies $\frac{Δ_{2}^{2}}{2 σ^{2}}$ -zCDP, where $Δ_{2} = \sup_{\begin{matrix} x, x^{'} \in X^{n} \\ neighboring \end{matrix}} {‖ q_{t} (x) - q_{t} (x^{'}) ‖}_{2}$ is the sensitivity of q_t. We can thus apply Theorem 3.33 to obtain a tight Rényi DP guarantee for $N (q_{t} (x_{U_{t}}), σ^{2} I_{d})$ ⁠, where U_t is a Poisson sample. Finally, we can apply the composition property of Rényi DP (Lemma 3.30) over the T rounds and we can convert this final Rényi DP guarantee to approximate DP using Proposition 3.14. This is how differentially private deep learning is analyzed in practice by libraries such as TensorFlow Privacy [Goo18; McM+18].

We can also obtain an asymptotic analysis: Theorem 3.37 shows that $N (q_{t} (x_{U_{t}}), σ^{2} I_{d})$ with U_t ⊂ [n] including each element independently with probability p satisfies $(α, 5 α p^{2} Δ_{2}^{2} / σ^{2})$ -RDP for all α ∈ (1, ω). Composition over T rounds yields $(α, 5 α T p^{2} Δ_{2}^{2} / σ^{2})$ -RDP for all α ∈ (1, ω), which implies (ε, δ)-DP for all δ > 0 and

ε = O (\frac{Δ_{2}}{σ} \cdot p \cdot \sqrt{T \cdot \log (1 / δ)}) .

This bound is directly comparable to the bound from Section 3.6.3, which was derived by converting back and forth between concentrated DP and approximate DP. The difference is that here we have a $\sqrt{\log (1 / δ)}$ whereas there we had a log(T/δ) term. This is the asymptotic improvement obtained by keeping the analysis within RDP. This asymptotic improvement also translates into a significant improvement in practice.

We have only analyzed Poisson subsampling, where the size of the sample is random. (Specifically, it follows a binomial distribution.) Naturally, other subsampling schemes may arise in practice. In particular, a fixed size sample is common. As discussed in Section 3.6.2, this corresponds to neighboring datasets allowing the replacement of one individual's data, rather than addition or removal. In terms of Rényi divergences, we must analyze $D_{α} (p P + (1 - p) Q ‖ p P^{'} + (1 - p) Q)$ ⁠, whereas addition and removal correspond to D_α (pP+(1−p)Q∥Q) and $D_{α} (Q ‖ p P^{'} + (1 - p) Q)$ ⁠. However, we can apply group privacy (part 7 of Lemma 3.32) to reduce the analysis to the case we have already analyzed: For all α′ > α, we have

\begin{array}{l} D_{α} (p P + (1 - p) Q ‖ p P^{'} + (1 - p) Q) \\ \leq \frac{α^{'}}{α^{'} - 1} \cdot D_{α \cdot \frac{α^{'} - 1}{α^{'} - α}} (p P + (1 - p) Q ‖ Q) + D_{α^{'}} (Q ‖ p P^{'} + (1 - p) Q) . \end{array}

3.7 Concluding Remarks

Composition

Differential privacy (specifically, pure DP) was introduced by Dwork, McSherry, Nissim, and Smith [DMNS06].^{^xiii} The original paper gives a form of basic composition (Theorem 3.1), but does not state it in full generality; rather it states a result specific to Laplace noise addition. Approximate DP was introduced by Dwork, Kenthapadi, McSherry, Mironov, and Naor [Dwo+06] and this work gave a more general statement of the basic composition result, as well as an analysis of the Gaussian mechanism (although not as tight as Corollary 3.8). The tight analysis of the Gaussian mechanism (Corollaries 3.8 & 3.10) is due to Balle and Wang [BW18].

The advanced composition theorem (Theorem 3.22) was proved by Dwork, Rothblum, and Vadhan [DRV10]. ^{^xiv} The key concepts of privacy loss distributions and concentrated DP were implicit in this proof, but they were only made explicit in a separate paper by Dwork and Rothblum [DR16]. Bun and Steinke [BS16] refined the notion of concentrated DP and presented the definition that we use here (Definition 3.11).

Kairouz, Oh, and Viswanathan [KOV15] proved an optimal composition theorem for approximate differential privacy. Specifically, the k-fold composition of (ε,δ)-differential privacy satisfies (ε′,δ′)-differential privacy if and only if

\frac{1}{{(1 + e^{ε})}^{k}} \sum_{ℓ = 0}^{k} (\begin{matrix} k \\ ℓ \end{matrix}) \cdot e^{ℓ ε} \cdot \max {0, 1 - e^{ε^{'} - (2 ℓ - k) ε}} \leq 1 - \frac{1 - δ^{'}}{{(1 - δ)}^{k}} .

This expression is rather complex, but the proof is relatively intuitive. The key insight is that we can reduce the analysis to the k-fold composition of a specific worst-case (ε,δ)-DP mechanism. With probability δ, this mechanism has infinite privacy loss. With probability $(1 - δ) \cdot \frac{e^{ε}}{1 + e^{ε}}$ ⁠, it has privacy loss ε. And, with probability $(1 - δ) \cdot \frac{1}{1 + e^{ε}}$ ⁠, it has privacy loss −ε. The privacy loss of the k-fold composition is the convolution of k of these privacy losses. Thus, with probability 1 − (1 − δ)^k the privacy loss of the composition is infinite. Otherwise – i.e., with probability (1 − δ)^k – the privacy loss has a shifted binomial distribution. Namely, for all ℓ ∈ [k] ∪ {0},

ℙ [Z = ε \cdot ℓ - ε \cdot (k - ℓ)] = {(1 - δ)}^{k} \cdot (\begin{matrix} k \\ ℓ \end{matrix}) \cdot {(\frac{e^{ε}}{e^{ε} + 1})}^{ℓ} \cdot {(\frac{1}{e^{ε} + 1})}^{k - ℓ},

where Z is the privacy loss of the k-fold composition of the worst-case (ε,δ)-DP mechanism. Applying Proposition 3.7 to this distribution yields the expression for the optimal composition theorem.

Kairouz, Oh, and Viswanathan [KOV15] also considered heterogeneous optimal composition. That is, the composition of k mechanisms where each mechanism j ∈ [k] has a different (ε_j,δ_j)-DP guarantee. However, the expression becomes more complicated. Intuitively, this is because the privacy loss distribution can be supported on 2^k points in the heterogeneous case, whereas, in the homogeneous case, it is supported on only k+1 points. Thus it takes exponential time to compute the privacy loss distribution. To be precise, Murtagh and Vadhan [MV16] showed that exactly computing the optimal composition is #P-complete, even if δ_j = 0 for each j ∈ [k]. However, Murtagh and Vadhan also showed that the optimal composition theorem could be approximated to arbitrary precision in polynomial time.

Although these composition results [KOV15; MV16] are optimal, they are limited in that they begin by assuming some (ε_j,δ_j)-DP guarantees about the algorithms being composed. However, we usually know more about the algorithms being composed than simply these two parameters. For example, we may know that the algorithms being composed are Gaussian noise addition. Incorporating this additional information allows us to prove even better bounds than optimal composition. This was the main impetus for the development of concentrated DP and Rényi DP, which we have discussed.

A recent line of work [MM18; KJH20; KJPH21; KH21; GLW21; DRS19; ZDW22; CKS20; GKKM22] has explored optimal composition guarantees whilst incorporating additional information about the mechanisms being composed. To make these computations efficient they consider the (discrete) Fourier transform of the privacy loss.^{^xv} That is, where concentrated DP and Rényi DP consider the moment generating function of the privacy loss $\underset{Z \leftarrow PrivLoss (M (x) ‖ M (x^{'}))}{E} [\exp (t Z)]$ ⁠, these works look at the characteristic function $\underset{Z \leftarrow PrivLoss (M (x) ‖ M (x^{'}))}{E} [\exp (i t Z)]$ ⁠, where i² = −1. These methods provide composition guarantees which are arbitrarily close to optimal, which are thus better than what is attainable via concentrated DP or Rényi DP.

The optimality of advanced composition (Theorem 3.24) is due to Bun, Ullman, and Vadhan [BUV14]. We present the analysis following Kamath and Ullman [KU20].

The composition results we have presented all assume that the privacy parameters of the algorithms being composed (i.e., (ε_j,δ_j) for j ∈ [k] in the language of Theorem 3.22) are fixed. It is natural to consider the setting where these parameters are chosen adaptively [RRUV16] – i.e., (ε_j,δ_j) could depend on the output of M_j−1. For the most part, the composition results carry over seamlessly to the setting of adaptively-chosen privacy parameters. In particular, for Concentrated or Rényi DP, as long as the sum of the adaptively-chosen privacy parameters remains bounded, we attain privacy with that bound [FZ21]. Another extension is “concurrent composition” [VW21], which applies when an adversary may simultaneously access multiple interactive DP systems. Fortunately, the standard composition results readily extend to this setting [VZ22; Lyu22].

Privacy Amplification by Subsampling

The first explicit statement of differential privacy amplification by subsampling was in a blog post by Smith [Smi09], although it appeared implicitly earlier [Kas+11] and the privacy effects of sampling on its own had also been studied [CM06].

For approximate DP, Balle, Barthe, and Gaborardi [BBG18] provide a thorough analysis of privacy amplification by subsampling (cf. Theorem 3.28). They present tight results for Poisson sampling (i.e., including each element independently), sampling a subset of a fixed size (without replacement), and also sampling with replacement, which means a person's data may appear multiple times in the subsampled dataset.

As discussed in Sections 3.6.3 and 3.6.7, subsampling arises in differentially private versions of stochastic gradient descent [CMS11; BST14]. Abadi, Chu, Goodfellow, McMahan, Mironov, Talwar, and Zhang [Aba+16] applied this in the context of deep learning. To obtain better analyses, they developed the “Moments Accountant” – i.e., Rényi DP (although the connection to Rényi divergences was only made later [Mir17; BS16]).

Abadi et al. [Aba+16] obtained asymptotic Rényi DP bounds for the Poisson subsampled Gaussian mechanism, but they used numerical integration for their implementation. Mironov, Talwar, and Zhang [MTZ19] improved these asymptotic results and gave a better numerical method for exact computation (cf. Theorem 3.33); our presentation in Section 3.6.5 largely follows theirs. Bun, Dwork, Rothblum, and Steinke [BDRS18] prove asymptotic Rényi DP bounds for Poisson subsampling applied to a concentrated DP mechanism (cf. Theorem 3.37). Zhu and Wang [ZW19] gave generic Rényi DP bounds for Poisson subsampling.^{^xvi}

Moving away from Poisson subsampling, Wang, Balle, and Kasiviswanathan [WBK19] provide Rényi DP results for sampling a fixed-size set without replacement.

Koskela, Jälkö, and Honkela [KJH20] provide expressions for the privacy loss distribution of the subsampled Gaussian (under both Poisson subsampling and sampling a fixed size set with or without replacement) which can be numerically integrated to obtain optimal composition results.

Closely related to privacy amplification by subsampling is privacy amplification by shuffling[Bit+17; Erl+19; Che+19; BBGN19; FMT21; FMT22]. Privacy amplification by shuffling is usually presented in terms of local differential privacy [Kas+11]. That is, there are n individuals who independently generate random messages that satisfy local ε-DP. Those messages are then “shuffled” so that the potential adversary/attacker cannot identify which message originated from which individual. The additional randomness of the shuffling amplifies the privacy to $(O (ε \cdot \sqrt{\frac{\log (1 / δ)}{n}}), δ)$ -DP.

Intuitively, shuffling is similar to subsampling with composition. Suppose we repeatedly sample one individual uniformly at random and perform an ε-DP computation on their data and the number of repetitions is equal to the number of individuals n. We can analyze this as subsampling a 1/n fraction (fixed size set) composed n times. Privacy amplification by subsampling (Theorem 3.28) says each repetition is ε′-DP for $ε^{'} = \log (1 + \frac{1}{n} (e^{ε} - 1)) = O (ε / n)$ ⁠. Advanced composition (Theorem 3.18) over the n repetitions yields (ε″,δ)-DP for $ε^{''} = O (\sqrt{n \log (1 / δ)} \cdot ε^{'}) = O (ε \cdot \sqrt{\frac{\log (1 / δ)}{n}})$ ⁠.

In contrast, for shuffling, we sample without replacement, so no individual is sampled more than once. This means the samples are not independent, so we cannot appeal to the subsampling plus composition analysis. Nevertheless, this intuition leads to the correct result.

Notes

The function f_P∥Q is called the log likelihood ratio of P with respect to Q. Formally, f_P∥Q is the natural logarithm of the Radon-Nikodym derivative of P with respect to Q. This function is defined by the property that $P (S) = \underset{Y \leftarrow P}{E} [I [Y \in S]] = \underset{Y \leftarrow Q}{E} [e^{f_{P ‖ Q} (Y)} \cdot I [Y \in S]]$ for all measurable $S \subset Y$ ⁠. For this to exist, we must assume that P and Q have the same sigma-algebra and that P is absolutely continuous with respect to Q and vice versa – i.e., $\forall S \subset Y Q (S) = 0 \Leftrightarrow P (S) = 0$ ⁠.

The privacy loss distribution is not well-defined if absolute continuity fails to hold. Intuitively, this corresponds to the privacy loss being infinite. We can extend most of these definitions to allow for an infinite privacy loss. For simplicity, we do not delve into these issues.

iii

Note that, by the symmetry of the neighboring relation (i.e., if x,x′ are neighboring datasets then x′,x are also neighbors), we also have $\underset{Z \leftarrow PrivLoss (M (x) ‖ M (x^{'}))}{ℙ} [Z \geq - ε] = 1$ as a consequence of $\underset{Z^{'} \leftarrow PrivLoss (M (x^{'}) ‖ M (x))}{ℙ} [Z^{'} \leq ε] = 1$ ⁠.

The expectation of the privacy loss is always non-negative. Intuitively, this is because we take the expectation of the log likelihood ratio f_P∥Q(Y) with respect to Y ← P – i.e., the true answer is P, so on average the log likelihood ratio should point towards the correct answer.

In general, the privacy loss may not be continuous – i.e., F may not be differentiable. Nevertheless, the final result still holds in this case.

Formally, P(y),P′ (y),P″ (y),Q(y),Q′ (y), and Q″ (y) denote the Radon-Nikodym derivative of these distributions with respect to some base measure – usually either the counting measure (in which case these quantities are probability mass functions) or Lebesgue measure (in which case these quantities are probability density functions) – in any case, we can take P + Q to be the base measure.

vii

$E [‖ \bar{X} - P ‖_{2}^{2}] = \sum_{j = 1}^{k} \underset{P_{j} \leftarrow Uniform ([0, 1])}{E} [\underset{Y_{j} \leftarrow Binomial (n, P_{j})}{E} [{(\frac{1}{n} Y_{j} - P_{j})}^{2}]] = k \cdot \int_{0}^{1} \frac{p (1 - p)}{n} d p = \frac{k}{6 n}$ ⁠.

viii

Alternatively (and equivalently), consider an algorithm that adds discrete Laplace noise to the sum of its non-null inputs.

To be formal, we assume $⊥ \in X$ is a null value that is equivalent to removing the item. In particular, for $x \in X^{n}$ and U ⊂ [n] we can define $x_{U} \in X^{n}$ such that ${(x_{U})}_{i} = x_{i}$ if i ∈ U and ${(x_{U})}_{i} = ⊥$ if i ∈ [n] \ U.

We make the usual measure theoretic disclaimers: We assume the P and Q have the same sigma-algebra. We assume P is absolutely continuous with respect to Q – i.e., ∀SQ(S) = 0⟹P(S) = 0 – so that the Radon-Nikodym derivative is well-defined; we denote the Radon-Nikodym derivative of P with respect to Q evaluated at y by P(y)/Q(y). More generally, if the absolute continuity assumption does not hold, then we define D_α (P∥Q) = ∞ for all α ∈ [1,∞].

Note that we assume P and Q are absolutely continuous with respect to each other – i.e., ∀SP(S) = 0 ⟺ Q(S) = 0. This ensures that the Radon-Nikodym derivative $\frac{P (y)}{Q (y)}$ is well-defined and, further that $\underset{Y \leftarrow Q}{ℙ} [\frac{P (Y)}{Q (Y)} \leq 0] = 0$ ⁠. Thus the function f need only be defined on (0,∞).

xii

I.e., $x, x^{'} \in X^{n}$ are neighboring if, for some i ∈ [n], we have x_i = ⊥ or $x_{i}^{'} = ⊥$ ⁠, and $\forall j \neq i x_{j} = x_{j}^{'}$ ⁠, where $⊥ \in X$ is some fixed value.

xiii

The name “differential privacy” does not appear in the original paper. It is attributed to Michael Schroeder [DMNS17] and first appeared in a talk by Dwork [Dwo06].

xiv

The original proof showed that the k-fold composition of (ε,δ)-DP algorithms satisfies (ε′,kδ + δ′)-DP with δ′ > 0 arbitrary and $ε^{'} = k ε (e^{ε} - 1) + ε \cdot \sqrt{2 k \log (1 / δ^{'})}$ ⁠. The first term kε(e^ε−1) is slightly worse than Theorem 3.22, which gives $\frac{1}{2} k ε^{2}$ instead.

To apply a discrete Fourier transform, we must first discretize the privacy loss distribution, e.g., by rounding it to a grid. The choice of discretization determines the tightness of the final guarantee, and the computational complexity of computing it.

xvi

Mironov, Talwar, and Zhang [MTZ19] and Zhu and Wang [ZW19] both provide analogs of Theorem 3.34. However, to the best of our knowledge, Theorem 3.34 is novel.

References

[Aba+16]

Abadi

Chu

Goodfellow

H. B.

McMahan

Mironov

Talwar

, and

Zhang

. “Deep Learning with Differential Privacy”. In:

Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. CCS ’16

Vienna, Austria

Association for Computing Machinery

2016

, pp.

308

–

318

. ISBN: 9781450341394. URL: https://doi.org/10.1145/2976749.2978318

(cit. on pp. 126, 147)

Google Scholar

[BBG18]

Balle

Barthe

, and

Gaboardi

. “Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences”. In:

Advances in Neural Information Processing Systems

. Ed. by

Bengio

Wallach

Larochelle

Grauman

Cesa-Bianchi

, and

Garnett

. Vol.

Curran Associates, Inc

2018

. URL: https://proceedings.neurips.cc/paper/2018/file/3b5020bb891119b9f5130f1fea9bd773-Paper.pdf

(cit. on p. 147)

Google Scholar

[BBGN19]

Balle

Bell

Gascón

, and

Nissim

. “The Privacy Blanket of the Shuffle Model”. In:

Advances in Cryptology – CRYPTO 2019

. Ed. by

Boldyreva

and

Micciancio

Cham

Springer International Publishing

2019

, pp.

638

–

667

. ISBN: 978-3-03026951-7. URL: https://arxiv.org/abs/1903.02837

(cit. on p. 148)

Google Scholar

[BDRS18]

Bun

Dwork

G. N.

Rothblum

, and

Steinke

. “Composable and Versatile Privacy via Truncated CDP”. In:

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2018

Los Angeles, CA, USA

Association for Computing Machinery

2018

, pp.

–

. ISBN: 9781450355599. URL: https://doi.org/10.1145/3188745.3188946

(cit. on p. 147)

Google Scholar

[Bit+17]

Bittau

Ú.

Erlingsson

Maniatis

Mironov

Raghunathan

Lie

Rudominer

Kode

Tinnes

, and

Seefeld

. “

Prochlo: Strong privacy for analytics in the crowd

”. In:

Proceedings of the 26th symposium on operating systems principles

2017

, pp.

441

–

459

(cit. on p. 148)

Google Scholar

[BS16]

Bun

and

Steinke

. “Concentrated differential privacy: Simplifications, extensions, and lower bounds”. In:

Theory of Cryptography Conference

Springer

2016

, pp.

635

–

658

. URL: https://arxiv.org/abs/1605.02065

(cit. on pp. 96, 129, 145, 147)

Google Scholar

[BST14]

Bassily

Smith

, and

Thakurta

. “Private empirical risk minimization: Efficient algorithms and tight error bounds”. In:

2014 IEEE 55th annual symposium on foundations of computer science

IEEE

2014

, pp.

464

–

473

(cit. on p. 147)

Google Scholar

[Bun16]

M. M.

Bun

. “

New Separations in the Complexity of Differential Privacy

”.

PhD thesis

2016

(cit. on p. 113)

Google Scholar

[BUV14]

Bun

Ullman

, and

Vadhan

. “Fingerprinting Codes and the Price of Approximate Differential Privacy”. In:

Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing. STOC ’14

New York, New York

Association for Computing Machinery

2014

, pp.

–

. ISBN: 9781450327107. URL: https://arxiv.org/abs/1311.3158

(cit. on p. 146)

Google Scholar

[BW18]

Balle

and

Y.-X.

Wang

. “Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising”. In:

International Conference on Machine Learning

PMLR

2018

, pp.

394

–

403

(cit. on p. 145)

Google Scholar

[Che+19]

Cheu

Smith

Ullman

Zeber

, and

Zhilyaev

. “Distributed differential privacy via shuffling”. In:

Annual International Conference on the Theory and Applications of Cryptographic Techniques

Springer

2019

, pp.

375

–

403

. URL: https://arxiv.org/abs/1808.01394

(cit. on p. 148)

Google Scholar

[CKS20]

C. L.

Canonne

Kamath

, and

Steinke

. “

The discrete gaussian for differential privacy

”. In:

Advances in Neural Information Processing Systems

(

2020

), pp.

15676

–

15688

. URL: https://journalprivacyconfidentiality.org/index.php/jpc/article/view/784

(cit. on pp. 113, 146)

Google Scholar

[CM06]

Chaudhuri

and

Mishra

. “When Random Sampling Preserves Privacy”. In:

Proceedings of the 26th Annual International Conference on Advances in Cryptology. CRYPTO’06

Santa Barbara, California

Springer-Verlag

2006

, pp.

198

–

213

. ISBN: 3540374329. URL: https://doi.org/10.1007/11818175_12

(cit. on p. 147)

Google Scholar

[CMS11]

Chaudhuri

Monteleoni

, and

A. D.

Sarwate

. “

Differentially Private Empirical Risk Minimization

”. In:

J. Mach. Learn. Res. 12.null

(

July

2011

), pp.

1069

–

1109

. ISSN: 1532-4435

(cit. on p. 147)

Google Scholar

[DMNS06]

Dwork

McSherry

Nissim

, and

Smith

. “Calibrating noise to sensitivity in private data analysis”. In:

Theory of cryptography conference

Springer

2006

, pp.

265

–

284

(cit. on pp. 82, 144)

Google Scholar

[DMNS17]

Dwork

McSherry

Nissim

, and

Smith

. “

Calibrating Noise to Sensitivity in Private Data Analysis

”. In:

Journal of Privacy and Confidentiality

(

May

2017

), pp.

–

. URL: https://journalprivacyconfidentiality.org/index.php/jpc/article/view/405

(cit. on p. 144)

Google Scholar

[DR16]

Dwork

and

G. N.

Rothblum

. “

Concentrated differential privacy

”. In:

arXiv preprint arXiv:1603.01887

(

2016

). URL: https://arxiv.org/abs/1603.01887

(cit. on pp. 96, 145)

Google Scholar

[DRS19]

Dong

Roth

, and

W. J.

. “

Gaussian differential privacy

”. In:

arXiv preprint arXiv:1905.02383

(

2019

)

(cit. on p. 146)

Google Scholar

[DRV10]

Dwork

G. N.

Rothblum

, and

Vadhan

. “Boosting and differential privacy”. In:

2010 IEEE 51st Annual Symposium on Foundations of Computer Science

IEEE

2010

, pp.

–

(cit. on pp. 101, 145)

Google Scholar

[DSSU17]

Dwork

Smith

Steinke

, and

Ullman

. “

Exposed!a survey of attacks on private data

”. In:

Annu. Rev. Stat. Appl

(

2017

), pp.

–

(cit. on p. 113)

Google Scholar

[Dwo+06]

Dwork

Kenthapadi

McSherry

Mironov

, and

Naor

. “Our data, ourselves: Privacy via distributed noise generation”. In:

Annual International Conference on the Theory and Applications of Cryptographic Techniques

Springer

2006

, pp.

486

–

503

(cit. on pp. 82, 145)

Google Scholar

[Dwo06]

Dwork

. “Differential Privacy”. In:

Automata, Languages and Programming

. Ed. by

Bugliesi

Preneel

Sassone

, and

Wegener

Berlin, Heidelberg

Springer Berlin Heidelberg

2006

, pp.

–

. ISBN: 978-3-540-35908-1

(cit. on p. 144)

Google Scholar

[Erl+19]

Ú.

Erlingsson

Feldman

Mironov

Raghunathan

Talwar

, and

Thakurta

. “

Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity

”. In:

Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

2019

, pp.

2468

–

2479

. eprint: https://epubs.siam.org/doi/pdf/10.1137/1.9781611975482.151. URL: https://epubs.siam.org/doi/abs/10.1137/1.9781611975482.151

(cit. on p. 148)

Google Scholar

[FMT21]

Feldman

McMillan

, and

Talwar

. “

Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling

”. In:

2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)

2021

, pp.

954

–

964

. URL: https://arxiv.org/abs/2012.12803

(cit. on p. 148)

Google Scholar

[FMT22]

Feldman

McMillan

, and

Talwar

. “

Stronger Privacy Amplification by Shuffling for R\’enyi and Approximate Differential Privacy

”. In:

arXiv preprint arXiv:2208.04591

(

2022

). URL: https://arxiv.org/abs/2208.04591

(cit. on p. 148)

Google Scholar

[FZ21]

Feldman

and

Zrnic

. “Individual Privacy Accounting via a Rényi Filter”. In:

Advances in Neural Information Processing Systems

. Ed. by

Ranzato

Beygelzimer

Dauphin

Liang

, and

J. W.

Vaughan

. Vol.

Curran Associates, Inc

2021

, pp.

28080

–

28091

. URL: https://proceedings.neurips.cc/paper/2021/file/ec7f346604f518906d35ef0492709f78-Paper.pdf

(cit. on p. 147)

Google Scholar

[GKKM22]

Ghazi

Kamath

Kumar

, and

Manurangsi

. “Faster Privacy Accounting via Evolving Discretization”. In:

International Conference on Machine Learning

PMLR

2022

, pp.

7470

–

7483

(cit. on p. 146)

Google Scholar

[GLW21]

Gopi

Y. T.

Lee

, and

Wutschitz

. “Numerical Composition of Differential Privacy”. In:

Advances in Neural Information Processing Systems

. Ed. by

Ranzato

Beygelzimer

Dauphin

Liang

, and

J. W.

Vaughan

. Vol.

Curran Associates, Inc

2021

, pp.

11631

–

11642

. URL: https://proceedings.neurips.cc/paper/2021/file/6097d8f3714205740f30debe1166744e-Paper.pdf

(cit. on p. 146)

Google Scholar

[Goo18]

Google

TensorFlow Privacy Library

. https://github.com/tensorflow/privacy & https://github.com/google/differential-privacy.

2018

(cit. on p. 143)

[Hoe63]

Hoeffding

. “

Probability for sums of bounded random variables

”. In:

J. Am. Stat. Assoc

(

1963

)

(cit. on p. 100)

Google Scholar

[Kas+11]

S. P.

Kasiviswanathan

H. K.

Lee

Nissim

Raskhodnikova

, and

Smith

. “

What Can We Learn Privately?

” In:

SIAM Journal on Computing

(

2011

), pp.

793

–

826

. eprint: https://doi.org/10.1137/090756090. URL: https://doi.org/10.1137/090756090

(cit. on pp. 147, 148)

Google Scholar

[KH21]

Koskela

and

Honkela

. “

Computing differential privacy guarantees for heterogeneous compositions using fft

”. In:

arXiv preprint arXiv:2102.12412

(

2021

)

(cit. on p. 146)

Google Scholar

[KJH20]

Koskela

Jälkö

, and

Honkela

. “Computing Tight Differential Privacy Guarantees Using FFT”. In:

Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics

. Ed. by

Chiappa

and

Calandra

. Vol.

108

Proceedings of Machine Learning Research

PMLR

Aug

2020

, pp.

2560

–

2569

. URL: https://proceedings.mlr.press/v108/koskela20b.html

(cit. on pp. 146, 147)

Google Scholar

[KJPH21]

Koskela

Jälkö

Prediger

, and

Honkela

. “Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT”. In:

Proceedings of The 24th International Conference on Artificial Intelligence and Statistics

. Ed. by

Banerjee

and

Fukumizu

. Vol.

130

Proceedings of Machine Learning Research

PMLR

Apr

2021

, pp.

3358

–

3366

. URL: https://proceedings.mlr.press/v130/koskela21a.html

(cit. on p. 146)

Google Scholar

[KOV15]

Kairouz

, and

Viswanath

. “The composition theorem for differential privacy”. In:

International conference on machine learning

PMLR

2015

, pp.

1376

–

1385

(cit. on pp. 102, 145, 146)

Google Scholar

[KU20]

Kamath

and

Ullman

. “

A primer on private statistics

”. In:

arXiv preprint arXiv:2005.00010

(

2020

). URL: https://arxiv.org/abs/2005.00010

(cit. on p. 146)

Google Scholar

[Lyu22]

Lyu

. “

Composition Theorems for Interactive Differential Privacy

”. In:

arXiv preprint arXiv:2207.09397

(

2022

)

(cit. on p. 147)

Google Scholar

[McM+18]

H. B.

McMahan

Andrew

Erlingsson

Chien

Mironov

Papernot

, and

Kairouz

. “

A general approach to adding differential privacy to iterative training procedures

”. In:

arXiv preprint arXiv:1812.06210

(

2018

)

(cit. on p. 143)

Google Scholar

[Mir17]

Mironov

. “Rényi differential privacy”. In:

2017 IEEE 30th computer security foundations symposium (CSF)

IEEE

2017

, pp.

263

–

275

(cit. on pp. 126, 147)

Google Scholar

[MM18]

Meiser

and

Mohammadi

. “Tight on Budget? Tight Bounds for r-Fold Approximate Differential Privacy”. In:

Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. CCS ’18

Toronto, Canada

Association for Computing Machinery

2018

, pp.

247

–

264

. ISBN: 9781450356930. URL: https://doi.org/10.1145/3243734.3243765

(cit. on p. 146)

Google Scholar

[MTZ19]

Mironov

Talwar

, and

Zhang

. “

R\’enyi differential privacy of the sampled gaussian mechanism

”. In:

arXiv preprint arXiv:1908.10530

(

2019

)

(cit. on pp. 131, 147)

Google Scholar

[MV16]

Murtagh

and

Vadhan

. “The complexity of computing the optimal composition of differential privacy”. In:

Theory of Cryptography Conference

Springer

2016

, pp.

157

–

175

(cit. on p. 146)

Google Scholar

[NP33]

Neyman

and

E. S.

Pearson

. “

IX. On the problem of the most efficient tests of statistical hypotheses

”. In:

Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character

231

694-706

(

1933

), pp.

289

–

337

(cit. on p. 86)

Google Scholar

[Rén61]

Rényi

. “On measures of entropy and information”. In:

Proceedings of the fourth Berkeley symposium on mathematical statistics and probability

. Vol.

547

–

561

Berkeley, California, USA

1961

. URL: https://projecteuclid.org/proceedings/berkeley-symposium-on-mathematical-statistics-and-probability/Proceedings-of-the-Fourth-Berkeley-Symposium-on-Mathematical-Statistics-and/Chapter/On-Measures-of-Entropy-and-Information/bsmsp/1200512181

(cit. on p. 127)

Google Scholar

[RRUV16]

Rogers

Roth

Ullman

, and

Vadhan

. “Privacy Odometers and Filters: Pay-as-You-Go Composition”. In:

Proceedings of the 30th International Conference on Neural Information Processing Systems. NIPS’16

Barcelona, Spain

Curran Associates Inc

2016

, pp.

1929

–

1937

. ISBN: 9781510838819

(cit. on p. 146)

Google Scholar

[Smi09]

Smith

Differential privacy and the secrecy of the sample

. https://adamdsmith.wordpress.com/2009/09/02/sample-secrecy/.

2009

(cit. on p. 147)

[SSSS17]

Shokri

Stronati

Song

, and

Shmatikov

. “Membership inference attacks against machine learning models”. In:

2017 IEEE symposium on security and privacy (SP)

IEEE

2017

, pp.

–

(cit. on p. 113)

Google Scholar

[SU15]

Steinke

and

Ullman

. “

Between pure and approximate differential privacy

”. In:

arXiv preprint arXiv:1501.06095

(

2015

)

(cit. on p. 113)

Google Scholar

[VW21]

Vadhan

and

Wang

. “Concurrent Composition of Differential Privacy”. In:

Theory of Cryptography Conference

Springer

2021

, pp.

582

–

604

(cit. on p. 147)

Google Scholar

[VZ22]

Vadhan

and

Zhang

. “

Concurrent Composition Theorems for all Standard Variants of Differential Privacy

”. In:

arXiv preprint arXiv:2207.08335

(

2022

)

(cit. on p. 147)

Google Scholar

[WBK19]

Y.-X.

Wang

Balle

, and

S. P.

Kasiviswanathan

. “Subsampled Renyi Differential Privacy and Analytical Moments Accountant”. In:

Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics

. Ed. by

Chaudhuri

and

Sugiyama

. Vol.

Proceedings of Machine Learning Research

PMLR

Apr

2019

, pp.

1226

–

1235

. URL: https://proceedings.mlr.press/v89/wang19b.html

(cit. on p. 147)

Google Scholar

[ZDW22]

Zhu

Dong

, and

Y.-X.

Wang

. “Optimal Accounting of Differential Privacy via Characteristic Function”. In:

Proceedings of The 25th International Conference on Artificial Intelligence and Statistics

. Ed. by

Camps-Valls

F. J. R.

Ruiz

, and

Valera

. Vol.

151

Proceedings of Machine Learning Research

PMLR

Mar

2022

, pp.

4782

–

4817

. URL: https://proceedings.mlr.press/v151/zhu22c.html

(cit. on p. 146)

Google Scholar

[ZW19]

Zhu

and

Y.-X.

Wang

. “Poission Subsampled Rényi Differential Privacy”. In:

Proceedings of the 36th International Conference on Machine Learning

. Ed. by

Chaudhuri

and

Salakhutdinov

. Vol.

Proceedings of Machine Learning Research

PMLR

June

2019

, pp.

7634

–

7642

. URL: https://proceedings.mlr.press/v97/zhu19c.html

(cit. on p. 147)

Google Scholar

Chapter 3: Composition of Differential Privacy & Privacy Amplification by Subsampling

3.1 Introduction

Overview of the Chapter

3.2 Basic Composition

3.2.1 Is Basic Composition Optimal?

3.3 Privacy Loss Distributions

3.3.1 Privacy Loss of Gaussian Noise Addition

3.3.2 Statistical Hypothesis Testing Perspective

3.3.3 Approximate DP & the Privacy Loss Distribution

3.4 Composition via the Privacy Loss Distribution

Basic Composition, Revisited

Gaussian Composition

Composition Via Gaussian Approximation

3.4.1 Concentrated Differential Privacy

3.4.2 Adaptive Composition & Post-processing

3.4.3 Composition of Approximate (ε,δ)-DP

3.5 Asymptotic Optimality of Composition

3.6 Privacy Amplification by Subsampling

3.6.1 Subsampling for Pure or Approximate DP

3.6.2 Addition or Removal versus Replacement for Neighboring Datasets

3.6.3 Subsampling & Composition

3.6.4 Rényi Differential Privacy

3.6.5 Sharp Privacy Amplification by Poisson Subsampling for Rényi DP

3.6.6 Analytic Rényi DP Bound for Privacy Amplification by Poisson Subsampling

3.6.7 How to Use Privacy Amplification by Subsampling

3.7 Concluding Remarks

Composition

Privacy Amplification by Subsampling

Notes

References

Related Topics

Email alerts

Related Book Content

Related Articles

Recommended for you

Sharing Unavailable