# Lemma KL-Divergence (Differential Privacy)

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.

1. $$\Delta (Y,Z) \overset{def}{=} \underset{S}{max} \ \ \ | Pr[Y\in S]-Pr[Z\in S]|$$
2. $$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$$
3. $$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]) \ \ \ (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:

1. For all $$y\in S$$, $$Pr[Y'=y]=e^\epsilon \cdot Pr[Z=y] < Pr[Y=y]]$$
2. For all $$y \in T$$, $$Pr[Y=y]\leq Pr[Y'=y]\leq Pr[Z=y]$$
3. 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.

For any set $$T$$, the reason $$\sum_{y\in T}(Pr[Z=y]-Pr[Y=y]) = \sum _{y \notin T}(Pr[Y=y]-Pr[Z=y])$$ is that both $$\Pr[Z=y]$$ and $$\Pr(Y=y)$$ add to 1 over the entire sample, so $$Pr[Y=y]-Pr[Z=y]$$ adds to zero over the entire sample.
So $$\sum_{y\in T}(Pr[Z=y]-Pr[Y=y]) + \sum _{y \notin T}(Pr[Z=y]-Pr[Y=y])=0$$ giving $$\sum_{y\in T}(Pr[Z=y]-Pr[Y=y]) - \sum _{y \notin T}(Pr[Y=y]-Pr[Z=y])=0$$ and $$\sum_{y\in T}(Pr[Z=y]-Pr[Y=y]) = \sum _{y \notin T}(Pr[Y=y]-Pr[Z=y])$$
Incidentally, $$D_\infty(Y||Z)$$ as you have defined it is not the KL-divergence. The KL-divergence is the expected value of the log likelihood ratio, not the supremum.