The overall DP under the strong composition theorem for k-mechanisms is ($\epsilon \sqrt{k log(1/\delta)}$, k$\delta$) such that each individual mechanism has ($\epsilon, \delta$)-DP.

But what if say, 25% of the total k-mechanisms have $(\epsilon_1, \delta_1)$-DP, while the remaining 75% mechanisms have $(\epsilon_2, \delta_2)$-DP. What would the overall DP be under the rules of strong composition in this case?


1 Answer 1


In this case, you would need to use the optimal composition theorem of Murtagh and Vahdan (see theorem 1.4 of Concurrent Composition of Differential Privacy by Vadhan and Wang for example).

This says that the mechanisms can be combined into an $(\epsilon_g,\delta_g)$ mechanism whenever $\epsilon_g\ge 0$ satisfies $$(1+\exp(\epsilon_1))^{-0.25k}(1+\exp(\epsilon_2))^{-0.75k}\left(\sum_{i=0}^{0.25k}\sum_{j=0}^{0.75k}\binom{0.25 k}i\binom{0.75 k}j\mathrm{max}\left(\exp(i\epsilon_1+j\epsilon_2)-\exp(\epsilon_g+(0.25k-i)\epsilon_1+(0.75k-j)\epsilon_2)\right)\right)\le 1-\frac{1-\delta_g}{(1-\delta_1)^{0.25k}(1-\delta_2)^{0.75k}}.$$


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.