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?


2 Answers 2


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.

  • $\begingroup$ Hi Thomas, how did you calculate the advanced composition $\varepsilon$?. $\endgroup$ Commented Jul 14, 2020 at 17:22
  • 1
    $\begingroup$ @MiguelGutierrez This is Theorem 3.20 in the Dwork-Roth textbook and originally appears as Theorem 3.3 in the Dwork-Rothblum-Vadhan paper. $\endgroup$
    – Thomas
    Commented Jul 15, 2020 at 4:12
  • $\begingroup$ 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. $\endgroup$ Commented Jul 15, 2020 at 4:22
  • $\begingroup$ 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? $\endgroup$
    – oicrisah
    Commented Jul 28, 2020 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.