差分隱私

study

差分隱私 §

1. 定義 §

在接觸資料與設計機制（加雜訊的演算法）前，根據法規、效能需求、風險容忍度等，制定定義（數學標準），規定查詢任務在任何單一資料的改變時，輸出的改變要維持在某個可嚴格量化的界線內。

例如 $ϵ$-DP，其數學標準為任何一筆資料的變動，造成輸出機率改變的倍數上限須小於 $e^{ϵ}$。

2. 分析 §

根據不同種類的查詢任務，例如連續數值、離散選擇、機器學習梯度，量化單一資料變動對輸出的最大可能改變。

在傳統數值查詢中，查詢函數的全局敏感度 $\Delta q$，代表資料庫增加或減少任意一筆資料時，輸出值最大可能改變多少。

極端事件的有無會造成輸出機率有較大的改變，防範極端事件需加入更多雜訊，從而降低模型效能，放寬定義雖能減少雜訊，卻會削弱隱私保護，有更精確的衡量方式嗎？

在模型訓練的初期和後期，單一資料變動對輸出的影響也有很大的差異，初期影響較大，後期影響較小，若始終用一致的最壞情況來衡量，會消耗過多不必要的隱私預算，有更精確的衡量方式嗎？

3. 構造 §

結合步驟 1 訂定的界線與步驟 2 評估的單一資料最大影響力，設計機制，抵銷資料變動帶來的影響，進而滿足定義。

不同的機制可以滿足同一個定義，取決於資料型態與應用場景。若目標是達到純 $ϵ$-DP，即利用 $ϵ$ 與 $\Delta q$ 來設計，面對數值型查詢時可以使用拉普拉斯機制，面對是非題調查時可以使用隨機響應機制，面對從多個選項中選出一個最佳解時可以使用指數機制。

4. 證明 §

機制設計完後，必須提出嚴格的數學證明，以確立該機制能提供的隱私保護下界。例如，寫出該機制在相鄰資料集下的機率密度函數比值，透過推導消去變數，最終證明該比值恆 $\le e^{ϵ}$，即可宣告其符合純 $ϵ$-DP。

此外，同一個機制可套用不同的定義框架來進行評估。以高斯機制為例，因其機率分佈的尾部無限延伸，在極端情況下會打破純 $ϵ$-DP 的嚴格界線，但若使用 $(ϵ,\delta )$-DP 框架，便可將這種隱私保證被打破的極端風險控制在極微小的機率 $\delta$ 之下，或者利用 RDP 框架來精確量化其整體的隱私預算消耗。

總結 §

第 1 步與第 4 步屬於純數學與理論範疇，它們確保了定義的嚴謹性，不與具體資料綁定。第 2 步與第 3 步屬於工程實作範疇，根據不同的應用場景與資料型態，分析影響力並注入特定雜訊。

定義提供了檢驗安全性的框架，而機制是針對特定問題所提出的解決方案

拉普拉斯機制 Laplace Mechanism §

高斯機制 Gaussian Mechanism §

$M(x)=f(x)+Y$

• $f(x)$：查詢函數，要保護的對象
• $Y\sim \mathcal{N}(0,{\sigma }^2)$
• $f_Y(y)=\frac{1}{\sqrt{2\pi {\sigma }^2}}\exp \left(-\frac{y^2}{2{\sigma }^2}\right)$

敏感度 §

• $L_1$ 敏感度 (${\Delta }_{1}f$)
  • ${\Delta }_{1}f={\max }_{D,D^{\prime }}{\sum }_{i=1}^d|f(D{)}_i-f(D^{\prime }{)}_i|$
  • 將所有維度的變化量取絕對值後相加
• $L_2$ 敏感度 (${\Delta }_{2}f$)
  • ${\Delta }_{2}f={\max }_{D,D^{\prime }}\sqrt{{\sum }_{i=1}^d(f(D{)}_i-f(D^{\prime }{)}_i{)}^2}$
  • 將所有維度的變化量平方相加後開根號

純差分隱私 §

$Pr[f(D)\in S]\le e^{ϵ}Pr[f(D^{\prime })\in S]$

• $D,D^{\prime }$：相差一筆資料，稱為相鄰資料集
• $f$：一個隨機機制（演算法），將輸入資料集映射為一個機率分佈
• $S$：$f$ 的輸出空間中的一個子集
• $Pr[f(D)\in S]$：當輸入為資料集 $D$ 時，$f$ 輸出結果落在 $S$ 內的機率
• $ϵ$：隱私預算，大於零的實數，控制隱私保護強度
  • $ϵ$ 越小，$e^{ϵ}$ 越接近 1，表示這筆資料的有無對輸出結果的影響越小，隱私保護越強
• $e^{ϵ}$：機率變化的乘法上限
  • 當 $ϵ$ 很小（例如 $0.1$）時，$e^{0.1}\approx 1.105$，表示單一個體資料的變動，最多只能讓輸出某特定結果的機率增加約 10.5%
• $D$ 與 $D^{\prime }$ 可以互換，實際的上下界為：

$$\begin{gathered} \{\begin{array}{l}Pr[f(D)\in S]\le e^{ϵ}Pr[f(D^{\prime })\in S]\\ e^{-ϵ}Pr[f(D^{\prime })\in S]\le Pr[f(D)\in S]\end{array} \\ ⟹e^{-ϵ}Pr[f(D^{\prime })\in S]\le Pr[f(D)\in S]\le e^{ϵ}Pr[f(D^{\prime })\in S] \end{gathered}$$

近似差分隱私 §

$Pr[f(D)\in S]\le e^{ϵ}Pr[f(D^{\prime })\in S]+\delta$

• 純 $ϵ$-DP 要求，對於所有可能的輸出結果 $S$，機率的變化比例都不能超過 $e^{ϵ}$，但在機率分佈尾部，兩個相近的機率分佈的機率都很低，比值可能非常大，使不等式不成立
• $\delta$：容錯機率，忽略發生機率極低的尾部事件
• 有兩種情況：
  • $Pr[f(D^{\prime })\in S]$ 和 $Pr[f(D)\in S]$ 的機率很小，未滿足純差分隱私的要求，不過加上 $\delta$ 後仍然滿足近似差分隱私，因為兩者皆仍大於零，依然無法 100% 確定某筆資料的有無
  • $Pr[f(D^{\prime })\in S]$ 降至零，加上 $\delta$ 後仍然滿足近似差分隱私，但可確定某筆資料的有無
• $\delta$ 必須設定得非常小，通常標準為 $\delta \ll 1/N$

近似差分隱私的挑戰 §

高斯機制的機率密度函數尾部會導致純 $ϵ$-DP 不成立，而 $(ϵ,\delta )$-DP 這個放寬的框架，允許有 $\delta$ 的極小機率發生隱私外洩。

雖然能用，但在深度學習梯度下降中，需要對資料庫進行成千上萬次的查詢。每次查詢都加一次高斯雜訊。在 $(ϵ,\delta )$-DP 的框架下，計算這成千上萬次累積下來的總隱私損失在數學上非常複雜，有參數組合爆炸與反向最佳化困難，計算複雜度高

實務上，通常已知總隱私預算 $({ϵ}_{total},{\delta }_{total})$，需要反推單步查詢所需的最佳雜訊標準差 $\sigma$ 以最大化模型準確率。這在數學上會形成一個極度複雜的非凸最佳化問題。

已知總預算，並假設每一次查詢的隱私預算分配相同（實際上可能不均等）， 執行 $k$ 次 滿足 $(ϵ,\delta )$-DP 的查詢，總損失為：

${ϵ}_{total}=\sqrt{2k\ln (1/{\delta }^{\prime })}ϵ+kϵ(e^{ϵ}-1)$ ${\delta }_{total}=k\delta +{\delta }^{\prime }$

• $k$：總迭代次數（在深度學習中通常是 $10^4$ 到 $10^5$ 級別）。

• $ϵ,\delta$：單次查詢的隱私預算。

• ${\delta }^{\prime }$：人為引入的輔助變數，其值必須介於 $0<{\delta }^{\prime }<{\delta }_{total}$ 之間，用來吸收部分失敗機率以換取更緊密的 ${ϵ}_{total}$ 上界。

尋找最小雜訊 $\sigma$單步高斯雜訊公式為：

$\sigma =\frac{\Delta f\sqrt{2\ln (1.25/\delta )}}{ϵ}$

在反推過程中，會面臨以下困難：

• 無法求得解析解：總隱私損失方程式包含了 $ϵ$ 的一次項、指數項 $e^{ϵ}$ 與 $\ln (1/{\delta }^{\prime })$，屬於超越方程式，無法直接移項求得 $ϵ$，必須依賴運算成本高的數值分析方法。
• 輔助變數 ${\delta }^{\prime }$ 的牽制：調大 ${\delta }^{\prime }$ 有助於獲得較大的 $ϵ$（降低 $\sigma$），但會壓縮單步 $\delta$ 的空間（導致 $\sigma$ 增加）。系統必須在連續空間中進行大量搜尋，以尋找最佳的 ${\delta }^{\prime }$。
• 參數組合爆炸：若每次迭代的預算分配不均等（如變動的 Batch Size 或不同神經網路層），這 $k$ 步的 $ϵ$ 會成為獨立變數。要在高達數萬維度的空間中尋找讓總雜訊最小的參數組合，計算量呈指數級爆炸，工程上不可行。

Renyi 差分隱私 (RDP) §

RDP 解決的是高斯機制在連續疊加使用時，隱私損失計算過於鬆散且複雜的問題。

在高斯機制下，RDP 的隱私預算曲線是一條極度簡潔的直線 $ϵ=\alpha /(2{\sigma }^2)$。這意味著，如果做了 $n$ 次高斯機制的查詢，隱私損失可以直接且精準地線性相加。

$D_{\alpha }(P||Q)\triangleq \frac{1}{\alpha -1}\log {\mathbb{E}}_{x\sim Q}\left[{\left(\frac{P(x)}{Q(x)}\right)}^{\alpha }\right]\le ϵ$

${\mathbb{E}}_{x\sim Q}\left[{\left(\frac{P(x)}{Q(x)}\right)}^{\alpha }\right]={\sum }_x\left(Q(x)\cdot {\left(\frac{P(x)}{Q(x)}\right)}^{\alpha }\right)$

• $P(x)$：輸入為 $D^{\prime }$ 時，輸出為 $x$ 的機率
• $Q(x)$：輸入為 $D$ 時，輸出為 $x$ 的機率
• $\alpha$：大於 1 的實數，代表 Renyi 散度的階數
  • 透過將機率比值 $\frac{P(x)}{Q(x)}$ 取 $\alpha$ 次方，能指數級放大、懲罰長尾事件。
• KL 散度的推廣
• 近似 DP 透過 $\delta$ 來忽略尾部事件，而 RDP 藉由期望值，考慮了尾部事件發生的極低機率，對整體加權平均的貢獻極低，因此能合法將其放行，不過仍可透過 $\alpha$ 控制對尾部事件的懲罰程度
• 懲罰的整體平均差異
• 長尾區，${\mathbb{E}}_{x\sim Q}\left[{\left(\frac{P(x)}{Q(x)}\right)}^{\alpha }\right]$ 可能非常大（Q 在 P 有值的地方很小），或非常小（機率 $Q(x)$ 縮小的速度快於比值 $\frac{P(x)}{Q(x)}$ 膨脹的速度或 $Q(x)$ 本身已經非常小）
• Q 需要盡可能覆蓋 P，若 Q 在 P 有值的地方很小，則 $D_{\alpha }(P||Q)$ 會很大

$f$-DP (Gaussian Differential Privacy, GDP) §

目前被認為在數學上更完美的框架。RDP 雖然精準，但在最終需將預算轉換回標準 $(ϵ,\delta )$-DP 以便解釋時，仍會產生微小的鬆弛（Lossy conversion）。$f$-DP 透過假設檢定 (Hypothesis Testing) 的視角重新定義隱私，能達成無損組合 (Lossless composition)，針對高斯機制的疊加界線比 RDP 更為緊緻。

Zero-Concentrated DP (zCDP) §

與 RDP 數學結構高度相關（同樣基於 Rényi Divergence），但在階數與動差的限制條件上不同，在某些複雜機制的代數操作與理論推導上比 RDP 更為直觀且簡便。

DP-SGD §

Moments Accountant §