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]) \ \ \ (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.

| cite | improve this answer | |
  • $\begingroup$ Thanks for the quick answer, Thomas. It makes sense. Yeah, that is not the KL divergence, but is similar (The Expression). $\endgroup$ – Miguel Gutierrez Jul 2 at 5:07

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.