Composition of Differential Privacy & Privacy Amplification by Subsampling

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.

Basic Composition

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

Let $M_{1},M_{2},\cdots,M_{k}:\mathcal{X}^{n}\to\mathcal{Y}$ be randomized algorithms. Suppose $M_{j}$ is $\varepsilon_{j}$-DP for each $j\in[k]$. Define $M:\mathcal{X}^{n}\to\mathcal{Y}^{k}$ by $M(x)=(M_{1}(x),M_{2}(x),\cdots,M_{k}(x))$, where each algorithm is run independently. Then $M$ is $\varepsilon$-DP for $\varepsilon=\sum_{j=1}^{k}\varepsilon_{j}$.

If we want to release $k$ values each of sensitivity $1$ (as above) and have the overall release be $\varepsilon$-DP, then, using basic composition, we can add $\mathsf{Laplace}(k/\varepsilon)$ noise to each value. The variance of the noise for each value is $2k^{2}/\varepsilon^{2}$, so the standard deviation is $\sqrt{2}k/\varepsilon$. 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.

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

The limitation of pure $\varepsilon$-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 $(\varepsilon,\delta)$-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.

Privacy Loss Distributions

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

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

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 ($\delta$) to determine what level of low probability events we can ignore.

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 $(\varepsilon,\delta)$-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 §3.1) we will calculate the privacy loss distribution corresponding to the Gaussian mechanism, which is a particularly nice example. In the next subsection (§3.2), we explain how the privacy loss distribution arises naturally via statistical hypothesis testing. To conclude this section (§3.3), we precisely relate the privacy loss back to approximate $(\varepsilon,\delta)$-DP. In the next section (§4), we will use the privacy loss distribution as a tool to analyze composition.

In the context of differential privacy, the distributions $P=M(x)$ and $Q=M(x^{\prime})$ correspond to the outputs of the algorithm $M$ on neighbouring inputs $x,x^{\prime}$. 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^{\prime}$) is more likely given the observed output ($Y\leftarrow M(\cdot)$). If $Z>0$, then the hypothesis $Y\leftarrow P=M(x)$ explains the observed output better than the hypothesis $Y\leftarrow Q=M(x^{\prime})$ 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\to\infty$, then we can be nearly certain that the output came from $P$, rather than $Q$. A very negative privacy loss $Z\ll 0$ means that the observed output $Y\leftarrow P$ strongly supports the wrong hypothesis (i.e., $Y\leftarrow Q$).

As long as the privacy loss distribution is well-defined,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. we can easily express almost all the quantities of interest in terms of it:

for all neighbouring $x,x^{\prime}$. (See Proposition 7.)

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.

Let $P=\mathcal{N}(\mu,\sigma^{2})$ and $Q=\mathcal{N}(\mu^{\prime},\sigma^{2})$. Then $\mathsf{PrivLoss}\left({P}\middle\|{Q}\right)=\mathcal{N}(\rho,2\rho)$ for $\rho=\frac{(\mu-\mu^{\prime})^{2}}{2\sigma^{2}}$.

We have $P(y)=\frac{1}{\sqrt{2\pi\sigma^{2}}}\exp\left(-\frac{(y-\mu)^{2}}{2\sigma^{2}}\right)$ and $Q(y)=\frac{1}{\sqrt{2\pi\sigma^{2}}}\exp\left(-\frac{(y-\mu^{\prime})^{2}}{2\sigma^{2}}\right)$. Thus the log likelihood ratio is

The privacy loss of the Gaussian mechanism is unbounded; thus it does not satisfy pure $\varepsilon$-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.

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^{\prime})$ corresponding to the outputs of the algorithm $M$ on neighbouring inputs $x,x^{\prime}$. 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)\geq Q(Y)$ and otherwise chooses $Q$; the accuracy of this test is

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)\geq 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:

How is this related to the privacy loss distribution? The test statistic $Z=f_{\left.{P}\middle\|{Q}\right.}(Y)$ under the hypothesis $Y\leftarrow P$ is precisely the privacy loss random variable $Z\leftarrow\mathsf{PrivLoss}\left({P}\middle\|{Q}\right)$. Thus the Neyman-Pearson lemma tells us that the privacy loss distribution $\mathsf{PrivLoss}\left({P}\middle\|{Q}\right)$ captures everything we need to know about distinguishing $P$ from $Q$.

Note that the Neyman-Pearson lemma also references the test statistic $f_{\left.{P}\middle\|{Q}\right.}(Y)$ under the hypothesis $Y\leftarrow 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 $\mathsf{PrivLoss}\left({Q}\middle\|{P}\right)$ and this distribution is something we should be able to handle due to the symmetry of differential privacy guarantees.

Fix distributions $P$ and $Q$ on $\mathcal{Y}$ such that the log likelihood ratio $f_{\left.{P}\middle\|{Q}\right.}(y)=\log\left(\frac{P(y)}{Q(y)}\right)$ is well-defined for all $y\in\mathcal{Y}$. Since $f_{\left.{P}\middle\|{Q}\right.}(y)=-f_{\left.{Q}\middle\|{P}\right.}(y)$ for all $y\in\mathcal{Y}$, if $Z\leftarrow\mathsf{PrivLoss}\left({Q}\middle\|{P}\right)$, then $-Z$ follows the distribution of $f_{\left.{P}\middle\|{Q}\right.}(Y)$ under the hypothesis $Y\leftarrow Q$.

Second, if we need to compute an expectation of some function $g$ of $f_{\left.{P}\middle\|{Q}\right.}(Y)$ under the hypothesis $Y\leftarrow Q$, then we can still express this in terms of the privacy loss $\mathsf{PrivLoss}\left({P}\middle\|{Q}\right)$:

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 $(\varepsilon,\delta)$-DP:

Let $P$ and $Q$ be two probability distributions on $\mathcal{Y}$ such that the privacy loss distribution $\mathsf{PrivLoss}\left({P}\middle\|{Q}\right)$ is well-defined. Fix $\varepsilon\geq 0$ and define

For any measurable $S\subset\mathcal{Y}$, we have

This gives the first expression in the result:

The expression $\delta=\sup_{S\subset\mathcal{Y}}P(S)-e^{\varepsilon}\cdot Q(S)$ in Proposition 7 is known as the “hockey stick divergence” and it determines the smallest $\delta$ for a given $\varepsilon$ such that $P(S)\leq e^{\varepsilon}Q(S)+\delta$ for all $S\subset\mathcal{Y}$. If $P=M(x)$ and $Q=M(x^{\prime})$ for arbitrary neighbouring datasets $x,x^{\prime}$, then this expression gives the best approximate $(\varepsilon,\delta)$-DP guarantee.

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

Furthermore, this guarantee is optimal – for every $\varepsilon\geq 0$, there is no $\delta^{\prime}<\delta$ such that $M$ is $(\varepsilon,\delta^{\prime})$-DP for general $q$.

Fix arbitrary neighbouring datasets $x,x^{\prime}\in\mathcal{X}^{n}$ and $S\subset\mathcal{Y}$. Let $\mu=q(x)$ and $\mu^{\prime}=q(x^{\prime})$. Let $P=M(x)=\mathcal{N}(\mu,\sigma^{2})$ and $Q=M(x^{\prime})=\mathcal{N}(\mu^{\prime},\sigma^{2})$. We must show $P(S)\leq e^{\varepsilon}\cdot Q(S)+\delta$ for arbitrary $\varepsilon\geq 0$ and the value $\delta$ given in the result.

By Proposition 3, $\mathsf{PrivLoss}\left({P}\middle\|{Q}\right)=\mathsf{PrivLoss}\left({Q}\middle\|{P}\right)=\mathcal{N}(\rho,2\rho)$, where $\rho=\frac{(\mu-\mu^{\prime})^{2}}{2\sigma^{2}}\leq\rho_{*}=\frac{\Delta^{2}}{2\sigma^{2}}$.

By Proposition 7, we have $P(S)\leq e^{\varepsilon}\cdot Q(S)+\delta$, where

Since $\rho\leq\rho_{*}$ and the above expression is increasing in $\rho$, we can substitute in $\rho_{*}$ as an upper bound.

Optimality follows from the fact that both Propositions 3 and 7 give exact characterizations. Note that we must assume that there exist neighbouring $x,x^{\prime}$ such that $\rho=\rho_{*}$. ∎

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

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:

For each $j\in[k]$, let $P_{j}$ and $Q_{j}$ be distributions on $\mathcal{Y}_{j}$ and assume $\mathsf{PrivLoss}\left({P_{j}}\middle\|{Q_{j}}\right)$ is well defined. Let $P=P_{1}\times P_{2}\times\cdots\times P_{k}$ denote the product distribution on $\mathcal{Y}=\mathcal{Y}_{1}\times\mathcal{Y}_{2}\times\cdots\times\mathcal{Y}_{k}$ obtained by sampling independently from each $P_{j}$. Similarly, let $Q=Q_{1}\times Q_{2}\times\cdots\times Q_{k}$ denote the product distribution on $\mathcal{Y}$ obtained by sampling independently from each $Q_{j}$. Then $\mathsf{PrivLoss}\left({P}\middle\|{Q}\right)$ is the convolution of the distributions $\mathsf{PrivLoss}\left({P_{j}}\middle\|{Q_{j}}\right)$ for all $j\in[k]$. That is, sampling $Z\leftarrow\mathsf{PrivLoss}\left({P}\middle\|{Q}\right)$ is equivalent to $Z=\sum_{j=1}^{k}Z_{j}$ when $Z_{j}\leftarrow\mathsf{PrivLoss}\left({P_{j}}\middle\|{Q_{j}}\right)$ independently for each $j\in[k]$.

For all $y\in\mathcal{Y}$, the log likelihood ratio (Definition 2) satisfies

Since $P$ is a product distribution, sampling $Y\leftarrow P$ is equivalent to sampling $Y_{1}\leftarrow P_{1}$, $Y_{2}\leftarrow P_{2}$, $\cdots$, $Y_{k}\leftarrow P_{k}$ independently.

A sample from the privacy loss distribution $Z\leftarrow\mathsf{PrivLoss}\left({P}\middle\|{Q}\right)$ is given by $Z=f_{\left.{P}\middle\|{Q}\right.}(Y)$ for $Y\leftarrow P$. By the above two facts, this is equivalent to $Z=f_{\left.{P_{1}}\middle\|{Q_{1}}\right.}(Y_{1})+f_{\left.{P_{2}}\middle\|{Q_{2}}\right.}(Y_{2})+\cdots+f_{\left.{P_{k}}\middle\|{Q_{k}}\right.}(Y_{k})$ for $Y_{1}\leftarrow P_{1}$, $Y_{2}\leftarrow P_{2}$, $\cdots$, $Y_{k}\leftarrow P_{k}$ independently. For each $j\in[k]$, sampling $Z_{j}\leftarrow\mathsf{PrivLoss}\left({P_{j}}\middle\|{Q_{j}}\right)$ is given by $Z_{j}=f_{\left.{P_{j}}\middle\|{Q_{j}}\right.}(Y_{j})$ for $Y_{j}\leftarrow P_{j}$. Thus sampling $Z\leftarrow\mathsf{PrivLoss}\left({P}\middle\|{Q}\right)$ is equivalent to $Z=Z_{1}+Z_{2}+\cdots+Z_{k}$ where $Z_{1}\leftarrow\mathsf{PrivLoss}\left({P_{1}}\middle\|{Q_{1}}\right)$, $Z_{2}\leftarrow\mathsf{PrivLoss}\left({P_{2}}\middle\|{Q_{2}}\right)$, $\cdots$, $Z_{k}\leftarrow\mathsf{PrivLoss}\left({P_{k}}\middle\|{Q_{k}}\right)$ are independent. ∎

Theorem 9 is the key to understanding composition of differential privacy. More concretely, we should think of a pair of neighbouring inputs $x,x^{\prime}$ and $k$ algorithms $M_{1},\cdots,M_{k}$. Suppose $M$ is the composition of $M_{1},\cdots,M_{k}$. Then the the differential privacy of $M$ can be expressed in terms of the privacy loss distribution $\mathsf{PrivLoss}\left({M(x)}\middle\|{M(x^{\prime})}\right)$. Theorem 9 allows us to decompose this privacy loss as the sum/convolution of the privacy losses of the constituent algorithms $\mathsf{PrivLoss}\left({M_{j}(x)}\middle\|{M_{j}(x^{\prime})}\right)$ for $j\in[k]$. Thus if we have differential privacy guarantees for each $M_{j}$, this allows us to prove differential privacy guarantees for $M$.

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 $\mathsf{PrivLoss}\left({M(x)}\middle\|{M(x^{\prime})}\right)$ 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 8:

Furthermore, this guarantee is optimal – for every $\varepsilon\geq 0$, there is no $\delta^{\prime}<\delta$ such that $M$ is $(\varepsilon,\delta^{\prime})$-DP for general $q$.

Now both $P$ and $Q$ are product distributions: For $j\in[d]$, let $P_{j}=\mathcal{N}(\mu_{j},\sigma^{2})$ and $Q_{j}=\mathcal{N}(\mu^{\prime}_{j},\sigma^{2})$. Then $P=P_{1}\times P_{2}\times\cdots P_{d}$ and $Q=Q_{1}\times Q_{2}\times\cdots\times Q_{d}$.

By Theorem 9, $\mathsf{PrivLoss}\left({P}\middle\|{Q}\right)=\sum_{j=1}^{d}\mathsf{PrivLoss}\left({P_{j}}\middle\|{Q_{j}}\right)$ and $\mathsf{PrivLoss}\left({Q}\middle\|{P}\right)=\sum_{j=1}^{d}\mathsf{PrivLoss}\left({Q_{j}}\middle\|{P_{j}}\right)$.

By Proposition 3, $\mathsf{PrivLoss}\left({P_{j}}\middle\|{Q_{j}}\right)=\mathsf{PrivLoss}\left({Q_{j}}\middle\|{P_{j}}\right)=\mathcal{N}(\rho_{j},2\rho_{j})$, where $\rho_{j}=\frac{(\mu_{j}-\mu^{\prime}_{j})^{2}}{2\sigma^{2}}$ for all $j\in[d]$.

Thus $\mathsf{PrivLoss}\left({P}\middle\|{Q}\right)=\mathsf{PrivLoss}\left({Q}\middle\|{P}\right)=\sum_{j=1}^{d}\mathcal{N}(\rho_{j},2\rho_{j})=\mathcal{N}(\rho,2\rho)$, where $\rho=\sum_{j=1}^{d}\rho_{j}=\frac{\|\mu-\mu^{\prime}\|_{2}^{2}}{2\sigma^{2}}\leq\rho_{*}=\frac{\Delta^{2}}{2\sigma^{2}}$.

By Proposition 7, we have $P(S)\leq e^{\varepsilon}\cdot Q(S)+\delta$, where

Since $\rho\leq\rho_{*}$ and the above expression is increasing in $\rho$, we can substitute in $\rho_{*}$ as an upper bound.

Optimality follows from the fact that Propositions 3 and 7 and Theorem 9 give exact characterizations. Note that we must assume that there exist neighbouring $x,x^{\prime}$ such that $\rho=\rho_{*}$. ∎

The key to the analysis of Gaussian composition in the proof of Corollary 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 $\varepsilon$-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},\cdots,M_{k}:\mathcal{X}^{n}\to\mathcal{Y}$ each be $\varepsilon$-DP and let $M:\mathcal{X}^{n}\to\mathcal{Y}^{k}$ be the composition of these algorithms. Let $x,x^{\prime}\in\mathcal{X}^{n}$ be neighbouring datasets. For notational convenience, let $P_{j}=M_{j}(x)$ and $Q_{j}=M_{j}(x^{\prime})$ for all $j\in[k]$ and let $P=M(x)=P_{1}\times P_{2}\times\cdots\times P_{k}$ and $Q=M(x^{\prime})=Q_{1}\times Q_{2}\times\cdots\times Q_{k}$.

Our goal is to understand the privacy loss $Z\leftarrow\mathsf{PrivLoss}\left({P}\middle\|{Q}\right)=\mathsf{PrivLoss}\left({M(x)}\middle\|{M(x^{\prime})}\right)$ of the composed algorithm. Theorem 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}\leftarrow\mathsf{PrivLoss}\left({P_{j}}\middle\|{Q_{j}}\right)=\mathsf{PrivLoss}\left({M_{j}(x)}\middle\|{M_{j}(x^{\prime})}\right)$ independently for each $j\in[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.,

Are we done? Can we substitute this approximation into Proposition 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 $(\varepsilon,\delta)$-DP would incur an error of $\delta\geq\Omega(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\geq 0$,

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

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.

Let $M:\mathcal{X}^{n}\to\mathcal{Y}$ be a randomized algorithm. We say that $M$ satisfies $\rho$-concentrated differential privacy ($\rho$-zCDP) if, for all neighbouring inputs $x,x^{\prime}\in\mathcal{X}^{n}$, the privacy loss distribution $\mathsf{PrivLoss}\left({M(x)}\middle\|{M(x^{\prime})}\right)$ is well-defined (see Definition 2) and

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

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

Let $M_{1},M_{2},\cdots,M_{k}:\mathcal{X}^{n}\to\mathcal{Y}$ be randomized algorithms. Suppose $M_{j}$ is $\rho_{j}$-zCDP for each $j\in[k]$. Define $M:\mathcal{X}^{n}\to\mathcal{Y}^{k}$ by $M(x)=(M_{1}(x),M_{2}(x),\cdots,M_{k}(x))$, where each algorithm is run independently. Then $M$ is $\rho$-zCDP for $\rho=\sum_{j=1}^{k}\rho_{j}$.

Fix neighbouring inputs $x,x^{\prime}\in\mathcal{X}^{n}$. By our assumption that each algorithm $M_{j}$ is $\rho_{j}$-zCDP,

By Theorem 9, $Z\leftarrow\mathsf{PrivLoss}\left({M(x)}\middle\|{M(x^{\prime})}\right)$ can be written as $Z=\sum_{j=1}^{k}Z_{j}$, where $Z_{j}\leftarrow\mathsf{PrivLoss}\left({M_{j}(x)}\middle\|{M_{j}(x^{\prime})}\right)$ independently for each $j\in[k]$.

Since $x$ and $x^{\prime}$ were arbitrary, this proves that $M$ satisfies $\rho$-zCDP, as required. ∎

Next we show how to convert from concentrated DP to approximate DP, which applies the tools we developed earlier. (This conversion is fairly tight, but not completely optimal; Asoodeh, Liao, Calmon, Kosut, and Sankar [ALCKS20] give an optimal conversion.)

For any $M:\mathcal{X}^{n}\to\mathcal{Y}$ and any $\varepsilon,t\geq 0$, $M$ satisfies $(\varepsilon,\delta)$-DP with

In particular, if $M$ satisfies $\rho$-zCDP, then $M$ satisfies $(\varepsilon,\delta)$-DP for any $\varepsilon\geq\rho$ with

Let $Z\leftarrow\mathsf{PrivLoss}\left({M(x)}\middle\|{M(x^{\prime})}\right)$. By Proposition 7, it suffices to show

for the value of $\delta$ given in the statement above.

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

We trivially have $0\leq c\cdot\exp(tZ)$ as long as $c>0$. Thus we only need to ensure $1-\exp(\varepsilon-Z)\leq c\cdot\exp(tZ)$. That is, for any value of $t>0$, we can set

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

whence $c\leq\exp(-\varepsilon t)$. Substituting in this upper bound on $c$ and setting $t=(\varepsilon-\rho)/2\rho$ completes the proof ∎

Proposition 14 shows that $\rho$-zCDP implies $(\varepsilon,\delta=\exp(-(\varepsilon-\rho)^{2}/4\rho))$-DP for all $\varepsilon\geq\rho$. Equivalently, $\rho$-zCDP implies $(\varepsilon=\rho+2\sqrt{\rho\cdot\log(1/\delta)},\delta)$-DP for all $\delta>0$. Also, to obtain a given a target $(\varepsilon,\delta)$-DP guarantee, it suffices to have $\rho$-zCDP with

This gives a sufficient condition; tighter bounds can be obtained from Proposition 14. For example, if we add $\mathcal{N}(0,\sigma^{2})$ to a query of sensitivity 1, then, by Lemma 12, to ensure $(\varepsilon,\delta)$-DP it suffices to set $\sigma^{2}=\frac{2}{\varepsilon^{2}}\cdot\left(\log(1/\delta)+\varepsilon\right)$.

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

Suppose $M$ satisfies $\varepsilon$-DP, then $M$ satisfies $\frac{1}{2}\varepsilon^{2}$-zCDP.

The key additional fact is the following consequence of Lemma 6

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

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

If we substitute $t=-1$ into Lemma 17, we have

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

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]:

Let $M_{1},M_{2},\cdots,M_{k}:\mathcal{X}^{n}\to\mathcal{Y}$ be randomized algorithms. Suppose $M_{j}$ is $\varepsilon_{j}$-DP for each $j\in[k]$. Define $M:\mathcal{X}^{n}\to\mathcal{Y}^{k}$ by $M(x)=(M_{1}(x),M_{2}(x),\cdots,M_{k}(x))$, where each algorithm is run independently. Then $M$ is $(\varepsilon,\delta)$-DP for any $\delta>0$ with

By Proposition 16, for each $j\in[k]$, $M_{j}$ satisfies $\rho_{j}$-zCDP with $\rho_{j}=\frac{1}{2}\varepsilon_{j}^{2}$. By composition of concentrated DP (Theorem 13), $M$ satisfies $\rho$-zCDP with $\rho=\sum_{j=1}^{k}\rho_{j}$. Finally, Proposition 14 can convert this concentrated DP guarantee to approximate DP: $M$ satisfies $(\varepsilon,\delta)$-DP for all $\varepsilon\geq\rho$ and $\delta=\exp(-(\varepsilon-\rho)^{2}/4\rho)$. We can rearrange this so that $\delta>0$ is arbitrary and $\varepsilon=\rho+\sqrt{4\rho\log(1/\delta)}$. ∎

Recall that the basic composition theorem (Theorem 1) gives $\delta=0$ and $\varepsilon=\sum_{j=1}^{k}\varepsilon_{j}$. That is, basic composition scales with the 1-norm of the vector $(\varepsilon_{1},\varepsilon_{2},\cdots,\varepsilon_{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 $(\varepsilon,\delta)$-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 $\mathsf{Laplace}(k/\varepsilon)$ noise to each answer. However, using advanced composition, we can answer each query by adding $\mathsf{Laplace}(\sqrt{k/2\rho})$ noise to each answer, where

(per Remark 15). If the privacy parameters $\varepsilon,\delta>0$ are fixed (which implies $\rho$ is fixed) and $k\to\infty$, we can see that asymptotically advanced composition gives noise per query scaling as $\Theta(\sqrt{k})$, while basic composition results in noise scaling as $\Theta(k)$.

2 Adaptive Composition & Postprocessing

Thus far we have only considered non-adaptive composition. That is, we assume that the algorithms $M_{1},M_{2},\cdots,M_{k}$ being composed are independent. More generally, adaptive composition considers the possibility that $M_{j}$ can depend on the outputs of $M_{1},\cdots,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.

Let $M_{1}:\mathcal{X}^{n}\to\mathcal{Y}_{1}$ be $\rho_{1}$-zCDP. Let $M_{2}:\mathcal{X}^{n}\times\mathcal{Y}_{1}\to\mathcal{Y}_{2}$ be such that, for all $y_{1}\in\mathcal{Y}_{1}$, the algorithm $x\mapsto M(x,y_{1})$ is $\rho_{2}$-zCDP. That is, $M_{2}$ is $\rho_{2}$-zCDP in terms of its first argument for any fixed value of the second argument. Define $M:\mathcal{X}^{n}\to\mathcal{Y}_{2}$ by $M(x)=M_{2}(x,M_{1}(x))$. Then $M$ is $(\rho_{1}+\rho_{2})$-zCDP.

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

For now, we make a simplifying technical assumption (which we will justify later): We assume that, given $y_{2}=M(x,y_{1})$, we can determine $y_{1}$. This means we can decompose $f_{\left.{M(x)}\middle\|{M(x^{\prime})}\right.}(y_{2})=f_{\left.{M_{1}(x)}\middle\|{M_{1}(x^{\prime})}\right.}(y_{1})+f_{\left.{M_{2}(x,y_{1})}\middle\|{M_{2}(x^{\prime},y_{1})}\right.}(y_{2})$. Thus

as required. All that remains is to justify our simplifying technical assumption. We can perforce ensure this assumption holds by defining $\hat{M}:\mathcal{X}^{n}\to\mathcal{Y}_{1}\times\mathcal{Y}_{2}$ by $\hat{M}(x)=(y_{1},y_{2})$ where $y_{1}=M_{1}(x)$ and $y_{2}=M_{2}(x,y_{1})$ 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 postprocessing 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 postprocessing property of concentrated DP, which we prove in Lemma 20 and Corollary 21. ∎

Let $\hat{P}$ and $\hat{Q}$ be distributions on $\hat{\mathcal{Y}}$ and let $g:\hat{\mathcal{Y}}\to\mathcal{Y}$ be an arbitrary function. Define $P=g(\hat{P})$ and $Q=g(\hat{Q})$ to be the distributions on $\mathcal{Y}$ obtained by applying $g$ to a function from $\hat{P}$ and $\hat{Q}$ respectively. Then, for all $t\geq 0$,

To generate a sample from $Y\leftarrow Q$, we sample $\hat{Y}\leftarrow\hat{Q}$ and set $Y=g(\hat{Y})$. We consider the reverse process: Given $y\in\mathcal{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\leftarrow 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 Radon-Nikodym derivative of the original distributions ($\hat{P}$ with respect to $\hat{Q}$) via the conditional distribution $\hat{Q}_{y}$.

To see where this identity comes from, write

where the inequality follows from Jensen’s inequality and the convexity of the function $v\mapsto v^{t+1}$. ∎

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

Fix neighbouring inputs $x,x^{\prime}\in\mathcal{X}^{n}$. Let $P=M(x)$, $Q=M(x^{\prime})$, $\hat{P}=\hat{M}(x)$, and $\hat{Q}=\hat{M}(x^{\prime})$. By Lemma 20 and the assumption that $\hat{M}$ is $\rho$-zCDP, for all $t\geq 0$,

which implies that $M$ is also $\rho$-zCDP. ∎

3 Composition of Approximate (ε,δ)𝜀𝛿(\varepsilon,\delta)-DP

Thus far we have only considered the composition of pure DP mechanisms (Theorems 1 & 18) and the Gaussian mechanism (Corollary 10). What about approximate $(\varepsilon,\delta)$-DP?

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

For $j\in[k]$, let $M_{j}:\mathcal{X}^{n}\times\mathcal{Y}_{j-1}\to\mathcal{Y}_{j}$ be randomized algorithms. Suppose $M_{j}$ is $(\varepsilon_{j},\delta_{j})$-DP for each $j\in[k]$. For $j\in[k]$, inductively define $M_{1\cdots j}:\mathcal{X}^{n}\to\mathcal{Y}_{j}$ by $M_{1\cdots j}(x)=M_{j}(x,M_{1\cdots(j-1)}(x))$, where each algorithm is run independently and $M_{1\cdots 0}(x)=y_{0}$ for some fixed $y_{0}\in\mathcal{Y}_{0}$. Then $M_{1\cdots k}$ is $(\varepsilon,\delta)$-DP for any $\delta>\sum_{j=1}^{k}\delta_{j}$ with

where $\delta^{\prime}=\delta-\sum_{j=1}^{k}\delta_{j}$.

Intuitively, if you consider the privacy loss $\mathsf{PrivLoss}\left({M(x)}\middle\|{M(x^{\prime})}\right)$ (where $x,x^{\prime}\in\mathcal{X}^{n}$ are arbitrary neighbouring inputs), then $M$ being $(\varepsilon,\delta)$-DP is equivalent to the privacy loss being in $[-\varepsilon,+\varepsilon]$ with probability at least $1-\delta$; otherwise the privacy loss can be arbitrary (including possibly infinite). Informally, the proof of Theorem 22 uses a union bound to show that with probability at least $1-\sum_{j=1}^{k}\delta_{j}$ all of the privacy losses of the $k$ algorithms are bounded by their respective $\varepsilon_{j}$s. 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.

Let $P$ and $Q$ be probability distributions over $\mathcal{Y}$. Fix $\varepsilon,\delta\geq 0$. Suppose that, for all measurable $S\subset\mathcal{Y}$, we have $P(S)\leq e^{\varepsilon}\cdot Q(S)+\delta$ and $Q(S)\leq e^{\varepsilon}P(S)+\delta$.

Then there exist distributions $P^{\prime},Q^{\prime},P^{\prime\prime},Q^{\prime\prime}$ over $\mathcal{Y}$ with the following properties. We can express $P$ and $Q$ as convex combinations of these distributions, namely $P=(1-\delta)P^{\prime}+\delta P^{\prime\prime}$ and $Q=(1-\delta)Q^{\prime}+\delta Q^{\prime\prime}$. And, for every measurable $S\subset\mathcal{Y}$, we have $e^{-\varepsilon}\cdot Q^{\prime}(S)\leq P^{\prime}(S)\leq e^{\varepsilon}\cdot Q^{\prime}(S)$.

Fix $\varepsilon_{1},\varepsilon_{2}\in[0,\varepsilon]$ to be determined later. Define distributions $P^{\prime}$, $P^{\prime\prime}$, $Q^{\prime}$, and $Q^{\prime\prime}$ as follows.Formally, $P(y)$, $P^{\prime}(y)$, $P^{\prime\prime}(y)$, $Q(y)$, $Q^{\prime}(y)$, and $Q^{\prime\prime}(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. For all points $y\in\mathcal{Y}$,

where $\delta_{1}$ and $\delta_{2}$ are appropriate normalizing constants.

By construction, $(1-\delta_{1})P^{\prime}+\delta_{1}P^{\prime\prime}=P$ and $(1-\delta_{2})Q^{\prime}+\delta_{2}Q^{\prime\prime}=Q$.

If $\delta_{1}=\delta_{2}=\delta$, then we have the appropriate decomposition and, for all $y\in\mathcal{Y}$, we have

as required. If $\delta_{1}=\delta_{2}<\delta$, we can change the decomposition to

and likewise for $Q$, which also yields the result.

It only remains to show that we can ensure that $\delta_{1}=\delta_{2}\leq\delta$ by appropriately setting $\varepsilon_{1},\varepsilon_{2}\in[0,\varepsilon]$. We have

We can extend Lemma 23 to show that any pair of distributions staisfying the $(\varepsilon,\delta)$-DP guarantee can be represented as a postprocessing of $(\varepsilon,\delta)$-DP randomized response:

Let $P$ and $Q$ be probability distributions over $\mathcal{Y}$. Fix $\varepsilon,\delta\geq 0$. Suppose that, for all measurable $S\subset\mathcal{Y}$, we have $P(S)\leq e^{\varepsilon}\cdot Q(S)+\delta$ and $Q(S)\leq e^{\varepsilon}P(S)+\delta$.

Then there exist distributions $A$, $B$, $P^{\prime\prime}$, and $Q^{\prime\prime}$ over $\mathcal{Y}$ such that

By Lemma 23, there exist distributions $P^{\prime},Q^{\prime},P^{\prime\prime},Q^{\prime\prime}$ over $\mathcal{Y}$ such that $P=(1-\delta)P^{\prime}+\delta P^{\prime\prime}$ and $Q=(1-\delta)Q^{\prime}+\delta Q^{\prime\prime}$ and, for every measurable $S\subset\mathcal{Y}$, we have $e^{-\varepsilon}\cdot Q^{\prime}(S)\leq P^{\prime}(S)\leq e^{\varepsilon}\cdot Q^{\prime}(S)$.

If $\varepsilon=0$, let $A=B=P^{\prime}=Q^{\prime}$. Otherwise, let

We can verify that $A$ and $B$ are probability distributions, since, for all $S$, we have $e^{-\varepsilon}\cdot Q^{\prime}(S)\leq P^{\prime}(S)\leq e^{\varepsilon}\cdot Q^{\prime}(S)$, which implies $A(S)\geq 0$ and $B(S)\geq 0$. Also $A(\mathcal{Y})=B(\mathcal{Y})=1$. And we have $\frac{e^{\varepsilon}}{e^{\varepsilon}+1}A+\frac{1}{e^{\varepsilon}+1}B=P^{\prime}$ and $\frac{e^{\varepsilon}}{e^{\varepsilon}+1}B+\frac{1}{e^{\varepsilon}+1}A=Q^{\prime}$, as required ∎

The proof of Theorem 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 23 inductively; this requires cumbersome notation, but is otherwise straightforward.

Fix neighbouring datasets $x,x^{\prime}\in\mathcal{X}^{n}$. We inductively define distributions $P_{j}$ and $Q_{j}$ on $\mathcal{Y}_{0}\times\mathcal{Y}_{1}\times\cdots\times\mathcal{Y}_{j}$ as follows. For $j\in[k]$, $P_{j}=(Y_{0},Y_{1},\cdots,Y_{j-1},M_{j}(x,Y_{j-1}))$, where $(Y_{1},\cdots,Y_{j-1})\leftarrow P_{j-1}$, and $Q_{j}=(Y_{0},Y_{1},\cdots,Y_{j-1},M_{j}(x^{\prime},Y_{j-1}))$, where $(Y_{1},\cdots,Y_{j-1})\leftarrow Q_{j-1}$. We define $P_{0}=Q_{0}$ to be the point mass on $y_{0}$.

We will prove by induction that, for each $j\in[k]$, there exist distributions $P_{j}^{\prime}$, $P_{j}^{\prime\prime}$, $Q_{j}^{\prime}$, and $Q_{j}^{\prime\prime}$ on $\mathcal{Y}_{0}\times\mathcal{Y}_{1}\times\cdots\times\mathcal{Y}_{j}$ such that

where the final inequality holds for the case $\varepsilon=\frac{1}{2}\sum_{j=1}^{k}\varepsilon_{j}^{2}+\sqrt{2\log(1/\delta^{\prime})\sum_{j=1}^{k}\varepsilon_{j}^{2}}$ and requires setting $t=\frac{\varepsilon}{\sum_{j=1}^{k}\varepsilon_{j}^{2}}-\frac{1}{2}=\sqrt{\frac{2\log(1/\delta^{\prime})}{\sum_{j=1}^{k}\varepsilon_{j}^{2}}}$.

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

Fix $j\in[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\leftarrow P_{j-1}$, where $P_{j}|_{Y}:=(Y,M_{j}(x,Y_{j-1}))$. For every $y$, we apply Lemma 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.