1
$\begingroup$

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

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.

$\endgroup$
6
  • 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$ 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
0
$\begingroup$

Turning arcynia's comment into an answer so this question can be marked as fixed: « The very next paragraph of the book explains this: "Note that the above corollary gives a rough guide for how to set $\varepsilon$ to get desired privacy parameters under composition. When one cares about optimizing constants (which one does when dealing with actual implementations), $\varepsilon$ 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$

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.