# 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$$.
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 advanced 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.