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 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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