# Interpretation of advanced composition theorem of differential privacy

In "The Algorithmic Foundations of Differential Privacy" book, Advanced Decomposition Theorem (Thm 3.20) is stated as follows:

For all "$$\epsilon, \delta, \delta' \geq 0$$, the class of ($$\epsilon,\delta$$)-differentially private mechanisms satisfies ($$\epsilon',k\delta+\delta'$$)-differential privacy under $$k$$-fold adaptive composition for:

$$\epsilon'=\sqrt{2k\ln{(1/\delta')}}\epsilon +k\epsilon(\exp(\epsilon)-1)$$

I have two questions related to this theorem:

1. If the all private mechanism of interest are $$(\epsilon,0)$$-differentially private, and in my understanding $$\delta'$$ is a tuning parameter, can't we have $$\delta'=0$$? Isn't that theorem a better composition than the basic decomposition in which $$\epsilon$$'s and $$\delta$$'s adds up? In the basic decomposition theorem, if all the mechanisms are $$(\epsilon,0)$$-differentially private, then we can have $$(k\epsilon,0)$$-differentially private composition.
2. On page 52 of the same book (just after Example 3.7), it is said that:

So how many queries can we answer with non-trivial accuracy? On a database of size $$n$$ let us say the accuracy is non-trivial if the error is of order $$o(n)$$. Theorem 3.20 says that for fixed values of $$\epsilon$$ and $$\delta$$, it is possible to answer close to $$n^2$$ counting queries with non-trivial accuracy. Similarly, one can answer close to n queries while still having noise $$o(\sqrt{n})$$ — that is, noise less than the sampling error.

I didn't understand how Theorem 3.20 says that. How do we measure the error here, and how the theorem is used to conclude this?

Consider the composition of $$k$$ algorithms each of which is $$(\varepsilon,0)$$-differentially private. We want to calculate parameters $$\varepsilon'$$ and $$\delta'$$ such that that the composition of these algorithms satisfies $$(\varepsilon',\delta')$$-differential privacy.

The comparison is between advanced composition $$\varepsilon' = \sqrt{2k\log(1/\delta)}\varepsilon + k \varepsilon (e^\varepsilon-1)$$ and basic composition $$\varepsilon' = k \varepsilon$$.

There is no way to say that one of these expressions is universally better than the other, as it depends on the parameter settings. However, we can argue that for some realistic parameter settings the first is better than the second.

What do I mean by realistic parameter settings? Let's say that the number of queries is fairly large (e.g., $$k = 10^5$$) and the final privacy parameters are not too big (e.g., $$\varepsilon' = 1$$ and $$\delta'=10^{-6}$$).

Then for basic composition we need $$\varepsilon = \varepsilon'/k = 10^{-5}$$. For advanced composition the calculation is a bit messier, but we can calculate that $$\varepsilon=58 \times 10^{-5}$$ suffices. In other words, advanced composition saves a factor of $$58$$ over basic composition. The improvement becomes more dramatic as $$k$$ increases.

Asymptotically, if we think of $$\varepsilon'$$ and $$\delta'$$ fixed but $$k$$ becoming larger, we see that basic composition requires $$\varepsilon \approx 1/k$$, while advanced composition requires $$\varepsilon \approx 1/\sqrt{k}$$. (I'm dropping all non-relevant terms and constants here.) This is the advantage of advanced composition.

• Hi Thomas, how did you calculate the advanced composition $\varepsilon$?. – Miguel Gutierrez Jul 14 at 17:22
• @MiguelGutierrez This is Theorem 3.20 in the Dwork-Roth textbook and originally appears as Theorem 3.3 in the Dwork-Rothblum-Vadhan paper. – Thomas Jul 15 at 4:12
• Yes, I mean your example. I am using corollary after this theorem (In Dwork-Roth textbook) and didn't get that result. How do you calculate the advance composition in your example which is $58 \times 10^{-5}$? I am just a little confused. – Miguel Gutierrez Jul 15 at 4:22
• Thank you @Thomas. The second question is still not clear to me. It seems the error measure and $\epsilon'$ are equivalent, but I don't understand why. Also if we have a noise $o(\sqrt{n})$, why can we answer $n$ queries this time? – oicrisah Jul 28 at 14:21

By allowing a slack in $$\tilde \delta$$, one can get a higher privacy of $$\tilde \epsilon = O(k \epsilon^2 + \sqrt{k}\epsilon)$$, compared with the basic composition $$\tilde \epsilon = O(k\epsilon)$$. That's the advantage of advanced composition theorem.

Of course when $$\tilde \delta$$ close to 0 it is very likely that advanced composition guarantee will be larger than the basic composition guarantee. And it makes sense since the advantage of advanced composition theorem comes from the slack of $$\tilde \delta$$, which is insignificant when $$\tilde \delta = 0$$.

• Thanks Piggy! Do you have an idea about the second question? So how the theorem relates with the number of queries we can answer? – oicrisah Jul 29 at 9:37