3
$\begingroup$

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.

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

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ That makes sense, thanks for the quick answer kodlu. $\endgroup$ Jul 2, 2020 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, 2020 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.