I have a problem understanding the proof of the corollary of Advanced Composition

Theorem Advanced Composition:

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

\begin{equation*} \varepsilon'= \sqrt{2k\ln(1/\delta')}\varepsilon+k\varepsilon(e^\varepsilon-1) \end{equation*}


Given target privacy parameters $0<\varepsilon'<1$ and $\delta'>0$, to ensure $(\varepsilon',k\delta+\delta')$ cumulative privacy loss over $k$ mechanisms, it suffices that each mechanism is $(\varepsilon,\delta)$-differentially private, where

\begin{equation*} \varepsilon=\frac{\varepsilon'}{2\sqrt{2k \ ln(1/\delta')}} \end{equation*}


The theorem of Advanced Composition tells us the composition will be $(\varepsilon^*,k\delta+\delta')$ for all $\delta'$, where $\varepsilon^*=\sqrt{2k \ln(1/\delta')}\cdot \varepsilon+k\varepsilon^2$. When $\varepsilon'<1$ we have that $\varepsilon^*<\varepsilon'$.

I don't see clearly the connections between the proof and the corollary. I tried using the quadratic formula. I think it, and don't see how they get the $\varepsilon$ from the corollary.

  • 1
    $\begingroup$ Are you struggling to understand why that value of epsilon was chosen in the first place, or why the proof shows that that value of epsilon is sufficient? $\endgroup$ – arcaynia Jul 14 '20 at 18:39
  • $\begingroup$ I am struggling to understand why the value of the epsilon. I thought the proof shows why the value of epsilon, $\endgroup$ – Miguel Gutierrez Jul 14 '20 at 18:52
  • 1
    $\begingroup$ The idea of the proof appears to be to show that the value of epsilon they have selected fulfils the required criteria, rather than explain why they chose that value $\endgroup$ – arcaynia Jul 14 '20 at 19:02
  • 2
    $\begingroup$ The very next paragraph of the book explains this: "Note that the above corollary gives a rough guide for how to set ε to get desired privacy parameters under composition. When one cares about optimizing constants (which one does when dealing with actual implementations), ε can be set more tightly by appealing directly to the composition theorem." That is to say, this value for epsilon does not represent anywhere near a calculated optimal value, but just a fairly good rough guide $\endgroup$ – arcaynia Jul 14 '20 at 19:03
  • $\begingroup$ @arcaynia you may want to turn your comment into an answer $\endgroup$ – kodlu Jul 15 '20 at 5:55

Your Answer

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

Browse other questions tagged or ask your own question.