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

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

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

### Corollary

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*}$$

Proof:

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.

• 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? – arcaynia Jul 14 at 18:39
• I am struggling to understand why the value of the epsilon. I thought the proof shows why the value of epsilon, – Miguel Gutierrez Jul 14 at 18:52
• 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 – arcaynia Jul 14 at 19:02
• 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 – arcaynia Jul 14 at 19:03
• @arcaynia you may want to turn your comment into an answer – kodlu Jul 15 at 5:55