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.


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]$


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.

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

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])$$

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.

  • $\begingroup$ That makes sense, thanks for the quick answer kodlu. $\endgroup$ Jul 2 '20 at 2:37
  • 1
    $\begingroup$ @kelalaka thanks, I actually prefer $\mathbb{P}$ usually but just used what the OP wrote without thinking... $\endgroup$
    – kodlu
    Jul 2 '20 at 22:09

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.