I am studying differential privacy and I got stuck again in proof of a lemma. Which is:
- $D_{\infty}^\delta(Y||Z) \leq \epsilon$ if and only if there exists a random variable $Y'$ such that $\Delta(Y,Y') \leq \delta$ and $D_\infty(Y||Z) \leq \epsilon $.
I have a problem understanding the reverse proof.
Definitions:
Be $Y, Z$ two random variables.
- $\Delta (Y,Z) \overset{def}{=} \underset{S}{max} \ \ \ | \Pr[Y\in S]-\Pr[Z\in S]|$
- $D_{\infty}(Y||Z)=\underset{S\subseteq Supp(Y)}{max}\Big[ln\frac{\Pr[Y\in S]}{\Pr[Z \in S]}\Big]$, which is the KL-Divergence between two distributions $Y,Z$
- $D_{\infty}^\delta(Y||Z)=\underset{S\subseteq Supp(Y):\Pr[Y\in S]\geq \delta}{max}\Big[ln\frac{\Pr[Y\in S]-\delta}{\Pr[Z \in S]}\Big]$
Proof:
Suppose that $D_{\infty}^\delta(Y||Z) \leq \epsilon$. Sea $S=\{y:\Pr[Y=y] > e^\epsilon \cdot \Pr[Z=y]\}$. Then
\begin{equation*} \sum_{y \in S}(\Pr[Y=y]-e^\epsilon \cdot \Pr[Z=y]) = \Pr[Y \in S]-e^\epsilon \cdot \Pr[Z \in S] \leq \delta \end{equation*}
(I understand until here)
Moreover, if we let $T=\{y:\Pr[Y=y] \leq \Pr[Z=y]\}$, then :
\begin{equation*} \begin{split} \sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) &= \sum _{y \notin T}(\Pr[Y=y]-\Pr[Z=Y]) \ \ \ \text{//I got stuck here} \\ & \geq \sum _{y \in S}(\Pr[Y=y]-\Pr[Z=Y])\\ & \geq \sum _{y \in S}(\Pr[Y=y] > e^\epsilon \cdot \Pr[Z=y]) \end{split} \end{equation*}
I don't' understand why: $$\sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) = \sum _{y \notin T}(\Pr[Y=y]-\Pr[Z=Y])$$
Thus we can obtain $Y'$ from $Y$ by lowering the probabilities on $S$ and raising the probabilities on $T$ To satisfy:
- For all $y\in S$, $\Pr[Y'=y]=e^\epsilon \cdot \Pr[Z=y] < \Pr[Y=y]]$
- For all $y \in T$, $\Pr[Y=y]\leq \Pr[Y'=y]\leq \Pr[Z=y]$
- For all $y\notin S \cup T$, $\Pr[Y'=y]=\Pr[Y=y] \leq e^{\epsilon} \cdot \Pr[Z=y]$
Then $D_{\infty}^\delta(Y'||Z) \leq \epsilon$ by inspection
Reference: Dwork, C. & Roth, A. (2014). The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science, page 45.
\Pr
for $\Pr$. $\endgroup$