# 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]) \ \ \ \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:

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.

• just a remark, that is not the standard definition of KL divergence. Jul 2 '20 at 2:17
• Yes, is not the same. Jul 2 '20 at 2:19
• Note: in $\LaTeX$, there is \Pr for $\Pr$. Jul 2 '20 at 19:32

$$\sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) = \sum _{y \notin T}(\Pr[Y=y]-\Pr[Z=y])$$
Well the domain is partitioned into $$T$$ and its complement. So the sum over the full domain of the difference of the two probability distributions is zero.
$$\sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) +\sum _{y \notin T}(\Pr[Z=y]-\Pr[Y=y])=0,$$ but now you can just move the second term to the right hand side and get the claimed equation.
• @kelalaka thanks, I actually prefer $\mathbb{P}$ usually but just used what the OP wrote without thinking... Jul 2 '20 at 22:09