论文主要内容：提出了一个新的散度计算公式，α- 散度（α-divergence）来分析 差分隐私中的子采样隐私增强现象。这种方法能够恢复并改进现有的隐私增强分析结果，同时提供新的隐私增强实例。

论文贡献：

• 证明了子采样后引入加噪机制可以严格提高隐私保护效果（降低 $\epsilon$）
• 量化 子采样差分隐私机制 （使用 Mechanism $\mathcal{M}$）对隐私保护的放大（Privacy Amplification）的作用， 并证明边界的最优性
• 注：该论文是完全基于数学证明的论文，只作为介绍和扩展使用

前置知识

总变差距离

总变差距离（Total Variation Distance，记作 $\eta$）：用来衡量两个概率分布之间差异程度的指标。它表示 <u> 在最坏的情况下 </u>，两个分布给出的结果有多不一样。

$$\eta =TV(\nu ,{\nu }^{\prime })=\frac{1}{2}\sum _y|\nu (y)-{\nu }^{\prime }(y)|$$

或者

$$\eta =1-\sum _{y}min\{\nu (y),{\nu }^{\prime }(y)\}$$

理解这两个公式：

1. 前一个公式可以认为是对两个分布的所有情况，即所有取值 $y$ 上的差异进行求和后，进行归一化得到 由于两个分布概率总和为 $1+1=2$，所以进行归一化（即除以 2）
2. 后一个公式可以认为是计算两个分布在所有情况下最小概率之和，然后用总概率减去这个概率，就是有差异的最大概率

高级联合凸性定理

提供了一种 计算两个混合分布之间 差异的方法，通过分析其组成部分的差异，简化了计算。对于两个混合分布：

• 相同的基础分布：${\mu }_0$
• 不同的成分：${\mu }_1,{\mu }_1^{\prime }$
  则有

$$\begin{array}{rl}\mu & =(1-\eta ){\mu }_0+\eta {\mu }_1\\ {\mu }^{\prime }& =(1-\eta ){\mu }_0+\eta {\mu }_1^{\prime }\end{array}$$

公式

$$D_{{\alpha }^{\prime }}(\mu ||{\mu }^{\prime })=\eta D_{\alpha }({\mu }_1||(1-\beta ){\mu }_0+\beta {\mu }_1^{\prime })$$

其中 $D_{\alpha }$ 为α- 散度

• $\alpha \ge 1$，且 ${\alpha }^{\prime }=1+\eta (\alpha -1)$
• $\beta =\frac{{\alpha }^{\prime }}{\alpha }$

用处

子抽样会导致机制的输出是一个混合分布，直接分析这种混合分布的差异非常困难。高级联合凸性定理提供了一种方法，将对混合分布的分析转化为对其组成部分的分析。这使得计算更简单、更可控。

graph LR
A[分析混合分布]
B[分析混合分布的组成成分]
A--> B

$\alpha -$ 散度

定义

$\alpha$ - 散度就是对于差分隐私使用的最大散度的扩展定义

$$D_{e^{\epsilon }}(M(x)\parallel M(x^{\prime }))\le \delta$$

其中

$$D_{\alpha }(\mu \parallel {\mu }^{\prime })=\underset{E}{sup}{(\mu (E)-\alpha {\mu }^{\prime }(E))}_{+}={\int }_Z{[\frac{d\mu }{d{\mu }^{\prime }}(z)-\alpha ]}_{+}d{\mu }^{\prime }(z)$$

• 用于衡量两个 概率测度 $\mu$ 和 ${\mu }^{\prime }$ 之间的差异，也就是两个概率分布的差异
• $\underset{E}{sup}$ 表示对所有可测子集$E$ 取上确界（supremum），$(\cdot {)}_{+}$ 表示取正部，即$max\{x,0\}$。

连续与离散情形下$D_{\alpha }(\mu \parallel {\mu }^{\prime })$ 的计算方法：

• 连续情形：$$$$$$$$$$$$$$$$

差分隐私与 $\alpha -$ 散度

差分隐私的定义可以通过这个散度度量来表达的
若对于所有满足 $x{\sim }_X{x}^{\prime }$ 的输入对 $x$ 和 $x^{\prime }$，$D_{e^{\epsilon }}(M(x)\parallel M(x^{\prime }))\le \delta$，则称机制 $M$ 满足 $(\epsilon ,\delta )$ - 差分隐私。这里 $\epsilon$ 和 $\delta$ 表示差分隐私中的隐私损失参数和容许误差。

隐私曲线

隐私曲线 Privacy Profile
$(\epsilon ,\delta )-$ 差分隐私公式，已知 $\epsilon ,\delta$，可以用来描述一个机制 $\mathcal{M}$ 是否满足对应隐私要求.
若已知一个机制 $\mathcal{M}$ – 在不同的 $\epsilon$ 下需要满足 $(\epsilon ,\delta )-$ 差分隐私，所需要的最小 $\delta$ 值，则使用 隐私曲线。

• 隐私曲线提供了机制 $M$ 满足 $(\epsilon ,\delta )$ - 差分隐私的所有参数对 $(\epsilon ,\delta )$。
• 机制 $M$ 是 $(\epsilon ,\delta )$ - 差分隐私的，当且仅当：$$\delta \ge {\delta }_M(\epsilon )$$或者说，对于给定的 $\epsilon$，只要 $\delta$ 不小于 ${\delta }_M(\epsilon )$，机制 $M$ 就满足 $(\epsilon ,\delta )$ - 差分隐私。

定义

隐私曲线 ${\delta }_M(\epsilon )$ 是一个函数 / 曲线，它将每个隐私参数 $\epsilon$ 关联到机制 $M$ 在该 $\epsilon$ 下的最小 $\delta$ 值。公式为：
$$
\delta_M(\varepsilon) = \sup_{x \sim_X x’} D_{e^\varepsilon}(M(x) | M(x’))
$$
其中 $x{\sim }_X{x}^{\prime }$表示 $x$和 $x^{\prime }$是相邻的数据集。

理解

• 直观理解： 隐私曲线描述了机制 $M$ 在不同的 $\epsilon$ 下需要满足 $(\epsilon ,\delta )$ - 差分隐私所对应的最小 $\delta$ 值。
• 隐私参数空间划分： 隐私曲线 ${\delta }_M(\epsilon )$将 $(\epsilon ,\delta )$参数空间划分为两部分：
  • 当 $\delta \ge {\delta }_M(\epsilon )$时，机制 $M$满足 $(\epsilon ,\delta )$- 差分隐私。
  • 当 $\delta <{\delta }_M(\epsilon )$时，机制 $M$不满足 $(\epsilon ,\delta )$- 差分隐私。

• 曲线存在性： 对于任何机制 $M$，隐私曲线 ${\delta }_M(\epsilon )$都存在，即使对于某些 $\epsilon$值机制满足纯差分隐私（即 $\delta =0$）。

群体隐私曲线

• 定义： 对于 $k\ge 1$，群体隐私曲线 ${\delta }_{M,k}(\epsilon )$ 表示在改变 $k$个数据的情况下，机制 $M$的隐私损失。
• 公式： 使用邻接关系 ${\sim }_X$诱导的路径距离 $d(x,x^{\prime })$：$${\delta }_{M,k}(\epsilon )=\underset{d(x,x^{\prime })\le k}{sup}{D}_{e^{\epsilon }}(M(x)\parallel M(x^{\prime }))$$其中 $d(x,x^{\prime })$是从 $x$到 $x^{\prime }$的最短相邻路径的长度。

总结：

• 隐私曲线 为差分隐私机制提供了一个全面的隐私参数描述，明确了在每个 $\epsilon$下机制需要满足的最小 $\delta$值。
• 与原始 $(\epsilon ,\delta )$- 差分隐私的关系 在于，隐私曲线为机制是否满足差分隐私提供了直接的判定标准。
• 公式关系 可以概括为：$$\text{对于所有 }\epsilon \ge 0,M\text{ 是 }(\epsilon ,\delta )\text{- 差分隐私的，当且仅当 }\delta \ge {\delta }_M(\epsilon )$$

通过理解隐私曲线，我们可以更好地分析和比较不同机制的隐私特性，设计满足特定隐私要求的算法。

子采样

子采样 Subsampling

使用子采样的原因

将加噪机制应用到子采样中可以提高机制的隐私性
*“A well-known method for increasing privacy of a mechanism is to apply the mechanism to a random subsample of the input database, rather than on the database itself. Intuitively, the method decreases the chances of leaking information about a particular individual because nothing about that individual can be leaked in the cases where the individual is not included in the subsample.”(Balle 等, 2018, p. 3) (pdf) 🔤一种众所周知的提高机制隐私性的方法是将机制应用于输入数据库的随机子样本，而不是数据库本身。直观地说，这种方法可以降低特定个人的信息泄露几率，因为在子样本中不包含该个人的情况下，该个人的任何信息都不会泄露。🔤

定义

子采样 机制

$$\mathcal{S}:\mathbf{X}\to \mathbb{P}(\mathbf{Y})$$

它接受一个数据库 $x$ 作为输入，输出一个关于数据库的 有限支持的概率分布。这意味着对于给定的 $x$，$S(x)$ 是一组 <u> 可能的子样本及其对应的概率 </u>。

量化

条件

• 给定一个差 分隐私机制 $\mathcal{M}:Y\to \mathbb{P}(Z)$，它对输入 $y$ 输出一个关于结果空间 $Z$ 的概率分布。$M$ 的隐私曲线 ${\delta }_M(\epsilon )$ 描述了机制在不同隐私参数 $\epsilon$ 下的隐私损失。
• 考虑 组合后的机制 ${\mathcal{M}}_S:X\to P(Z)$，定义为 ${\mathcal{M}}_S(x)=\mathcal{M}(S(x))$。
  • 对输入数据库 $x$ 先进行子抽样 $S(x)$，然后对得到的子样本 应用机制 加入噪声 $\mathcal{M}$。

目标

[!info] 找到下面两者之间的关系。

• $\mathcal{M}$ 的隐私曲线 ${\delta }_{\mathcal{M}}$
• ${\mathcal{M}}_S$ 的隐私曲线 ${\delta }_{{\mathcal{M}}_S}$

即希望对于每个 $\epsilon \ge 0$，存在 $0\le {\epsilon }^{\prime }\le \epsilon$，使得：

$${\delta }_{M_S}({\epsilon }^{\prime })\le h({\delta }_M(\epsilon ))$$

其中 $h$ 是一个待确定的函数。这表示如果 $\mathcal{M}$ 是 $(\epsilon ,\delta )$ - 差分隐私的，那么经过子抽样后的机制 ${\mathcal{M}}_S$ 会是 $({\epsilon }^{\prime },h(\delta ))$ - 差分隐私的，且 ${\epsilon }^{\prime }\le \epsilon$。体现了 隐私增强 的效果，因为新的机制在隐私参数上表现得更好。

结论

对于所有子采样后引入机制的结果，可以使用下面的式子同一表示其隐私增强的结果

$${\delta }_{{\mathcal{M}}_S}({\epsilon }^{\prime })⩽h({\delta }_{\mathcal{M}}(\epsilon ))$$

• ${\epsilon }^{\prime }=\log (1+\eta (e^{\epsilon }-1))$，这个值必然小于等于 $\epsilon$
• 表明经过子抽样后，机制的隐私参数得到了增强，对应的 $\delta$ 也有所改善

函数 $h$

函数 $h$ 的形式取决于

• 子采样的策略：不同的子采样方法，会导致不同的函数形式，整理如下