引理 KL-Divergence（差分隱私）
我正在研究差分隱私，但我再次陷入了引理的證明中。這是：
- $ D_{\infty}^\delta(Y||Z) \leq \epsilon $ 當且僅當存在隨機變數 $ Y’ $ 這樣 $ \Delta(Y,Y’) \leq \delta $ 和 $ D_\infty(Y||Z) \leq \epsilon $ .
我在理解反向證明時遇到了問題。
定義：
是 $ Y, Z $ 兩個隨機變數。
- $ \Delta (Y,Z) \overset{def}{=} \underset{S}{max} \ \ \ | \Pr[Y\in S]-\Pr[Z\in S]| $
- $ D_{\infty}(Y||Z)=\underset{S\subseteq Supp(Y)}{max}\Big[ln\frac{\Pr[Y\in S]}{\Pr[Z \in S]}\Big] $ , 這是兩個分佈之間的 KL-Divergence $ Y,Z $
- $ 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] $
證明：
假設 $ D_{\infty}^\delta(Y||Z) \leq \epsilon $ . 海 $ S={y:\Pr[Y=y] > e^\epsilon \cdot \Pr[Z=y]} $ . 然後
$$ \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*} $$
（直到這裡我才明白）
此外，如果我們讓 $ T={y:\Pr[Y=y] \leq \Pr[Z=y]} $ ， 然後 ：
$$ \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*} $$
我不明白為什麼： $$ \sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) = \sum _{y \notin T}(\Pr[Y=y]-\Pr[Z=Y]) $$
這樣我們就可以得到 $ Y’ $ 從 $ Y $ 通過降低機率 $ S $ 並提高機率 $ T $ 為了滿足：
- 對所有人 $ y\in S $ , $ \Pr[Y’=y]=e^\epsilon \cdot \Pr[Z=y] < \Pr[Y=y]] $
- 對所有人 $ y \in T $ , $ \Pr[Y=y]\leq \Pr[Y’=y]\leq \Pr[Z=y] $
- 對所有人 $ y\notin S \cup T $ , $ \Pr[Y’=y]=\Pr[Y=y] \leq e^{\epsilon} \cdot \Pr[Z=y] $
然後 $ D_{\infty}^\delta(Y’||Z) \leq \epsilon $ 通過檢查
參考資料： Dwork, C. & Roth, A. (2014)。差分隱私的算法基礎。理論電腦科學的基礎和趨勢，第 45 頁。
我不明白為什麼：
$$ \sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) = \sum _{y \notin T}(\Pr[Y=y]-\Pr[Z=y]) $$
那麼域被劃分為 $ T $ 及其補語。因此，兩個機率分佈的差值在整個域上的和為零。
$$ \sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) +\sum _{y \notin T}(\Pr[Z=y]-\Pr[Y=y])=0, $$ 但是現在您可以將第二項移到右側並獲得要求的方程。