I'm trying to prove sequential composition of two (or more) approximate differentially private mechanisms.
The only reference I can find is [here] [1], bottom of page 491, top of 492. In particular, I think the presented proof has problem, namely when she says:
If we look at the additive contribution of each of the $\delta$ terms, of which there are T [2 in my example above], we notice that they are only every multiplied by probabilities, which are at most 1.
The problem is the $\delta$ are multiplied by $\exp(\epsilon) P(x_i )$, which can be arbitrarily large. Note, there is also a term $\delta^k$ she seems to be ignoring. This again can be large.
Question 1: What am I misunderstanding with this proof?
I've tried to prove this myself, but come up short. Here's an attempt at a proof:
Let $\chi$ be our universe of datasets, and let $X$, $X' \in \chi$ be two neighboring datasets. I'll try the proof for two mechanisms that are sequential, so the second can depend on the first's output. So let $F: \chi \to \mathbb{R}$ be an $(\epsilon, \delta)$-DP mechanism and let $G: \mathbb{R}\times\chi \to \mathbb{R}$ with $G(r, \cdot)$ $(\epsilon, \delta)$-DP mechanism for any $r\in \mathbb{R}$.
Our goal is to show that $H(X):= [ F(X), G( F(X), X) ] \in \mathbb{R}^2$ is $(2\epsilon, 2\delta)$-DP.
Let $A\subset \mathbb{R}^2$ be measurable. Let $A_1 = $Proj$_1 (A)$. Let $A_r = \{s: (r,s ) \in A\}$.
\begin{align} P(H(X)\in A) &= \int_{A_1} p_{F(X)}(r) P(G(r,X)\in A_r) dr \\ & \leq \int_{A_1} p_{F(X)}(r) [e^\epsilon P(G(r,X')\in A_r) + \delta dr \\ & = e^\epsilon \int_{A_1} p_{F(X)}(r)P(G(r,X')\in A_r) dr + \delta\int_{A_1} p_{F(X)}(r) dr\\ & = e^\epsilon P([ F(X), G(F(X), X')] \in A) + \delta P(F(X) \in A_1) \end{align} Now we apply the same trick to the $P([ F(X), G(F(X), X')] \in A) $ but swap F and G (so we integrate over $s\in A_2 = $Proj$_2(A)$ against G's density $p_{G(F(X),X')}(s)$ times $P(F(X)\in A_s)$. We obtain:
\begin{align} P(H(X)\in A) &\leq e^\epsilon [ e^\epsilon P(H(X') \in A) + P( G( F(X), F(X')) \in A_2 )\delta] + P(F(X) \in A_1) \delta\\ & = e^{2\epsilon} P(H(X') \in A) + e^{\epsilon} P( G( F(X), F(X')) \in A_2 )\delta + P(F(X) \in A_1) \delta \end{align}
The first term ($e^{2\epsilon} P(H(X') \in A)$) is what we want!
The last term, $P(F(X) \in A_1) \delta \leq \delta$, so that is what we want!
The middle term has the same problem the cited paper has, $e^{\epsilon} P( G( F(X), F(X')) \in A_2 )\delta \leq e^{\epsilon}\delta$, but that may be huge (if we can bound it above by $\delta$ we have the result.
Question 2: How do we fix this proof?
Dwork, Cynthia; Kenthapadi, Krishnaram; McSherry, Frank; Mironov, Ilya; Naor, Moni, Our data, ourselves: privacy via distributed noise generation, Vaudenay, Serge (ed.), Advances in cryptology – EUROCRYPT 2006. 25th annual international conference on the theory and applications of cryptographic techniques, St. Petersburg, Russia, May 28 – June 1, 2006. Proceedings. Berlin: Springer (ISBN 3-540-34546-9/pbk). Lecture Notes in Computer Science 4004, 486-503 (2006). ZBL1140.94336. [1]: https://link.springer.com/content/pdf/10.1007/11761679.pdf?pdf=button