为方便阅读，故将《The Algorithmic Foundations of Differential Privacy》翻译项目内容搬运至此；

教材原文地址：https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf

中文翻译版 Github 项目地址1：https://github.com/guoJohnny/algorithmic-foundation-of-dp-zh-cn

中文翻译版 Github 项目地址2：https://github.com/doubleheiker/algorithmic-foundation-of-dp-zh-cn

感谢前辈的翻译工作！

三、基本技术与合成定理

本章在回顾了一些概率工具之后，介绍了拉普拉斯机制，该机制为实际（向量）值的查询提供了差分隐私。这种应用自然引出指数机制，这是一种用于从一组离散的候选输出中进行差分隐私选择的方法。然后，我们分析了由多种差分隐私机制构成造成的累积隐私损失。最后，我们提供了一种方法——稀疏矢量技术——主要用于报告可能非常大量的计算结果，但前提是只有少数几个是“有意义的”。

在本节中，我们描述了差异隐私中的一些最基本的技术，我们将再次使用它们。此处描述的技术构成了我们将要开发的所有其他算法的基本合成部分。

3.1 概率工具

以下集中不等式经常会有用。 我们以易于使用的形式而不是最强的形式陈述它们。
（注：集中不等式：集中不等式是数学中的一类不等式，描述了一个随机变量是否集中在某个取值附近。例如大数定律说明了一系列独立同分布随机变量的平均值在概率上趋近于它们的数学期望，这表示随着变量数目增大，平均值会集中在数学期望附近。）

定理3.1（加法形式的切尔诺夫界限、又称切尔诺夫不等式）定义 $X_1,X_2,...,X_m$ 为独立随机变量，对任意,$i$ 有 $0\le X_i\le 1$ 。定义 $S=\frac{1}{m}{\sum }_{i=1}^m{X}_i$ 为随机变量的均值，定义 $\mu =\mathbb{E}[S]$ 为他们的期望均值。则可以得到如下不等式：
$$\begin{array}{rl}\text{Pr}[S>\mu +\epsilon ]& \le e^{-2m{\epsilon }^2}\\ \text{Pr}[S<\mu -\epsilon ]& \le e^{-2m{\epsilon }^2}\end{array}$$

定理3.2（乘法形式的切尔诺夫不等式）定义 $X_1,X_2,...,X_m$ 为独立随机变量，对任意,$i$ 有 $0\le X_i\le 1$ 。定义 $S=\frac{1}{m}{\sum }_{i=1}^m{X}_i$ 为随机变量的均值，定义 $\mu =\mathbb{E}[S]$ 为他们的期望均值。则可以得到如下不等式：
$$\begin{array}{rl}\text{Pr}[S>(1+\epsilon )\mu ]& \le e^{-m\mu {\epsilon }^2/3}\\ \text{Pr}[S<(1-\epsilon )\mu ]& \le e^{-m\mu {\epsilon }^2/2}\end{array}$$

当我们没有独立的随机变量时。我们仍然可以应用 $Azuma$ 不等式：

定理3.3 Azuma不等式 令 $f$ 为 $m$ 个随机变量 $X_1,...,X_m$ 的方法，每一个 $X_i$ 的值取自集合 $A_i$ ，使得 $\mathbb{E}(f)$ 有界。用 $c_i$ 表示 $X_i$ 对 $f$ 的最大影响，即对于所有的 $a_i,a_i^{\prime }\in A_i$， 有：
$$|\mathbb{E}[f|X_1,...,X_{i-1},X_i=a_i]|-|\mathbb{E}[f|X_1,...,X_{i-1},X_i=a_i^{\prime }]|\le c_i$$
则：
$$\text{Pr}[f(X_i,...,X_m)\ge \mathbb{E}[f]+t]\le exp(-\frac{2t^2}{{\sum }_{i=1}^m{c}_i^2})$$
（注：Azuma不等式涉及随机过程中“鞅”（Martingale）的概念）

定理3.4 斯特林近似 $n!$ 可以近似于 $\sqrt{2n\pi }(n/e{)}^n$:
$$\sqrt{2n\pi }(n/e{)}^n{e}^{1/(12n+1)}<n!<\sqrt{2n\pi }(n/e{)}^n{e}^{1/(12n)}$$

3.2 随机响应

让我们回想一下第2节中描述的用于评估非法行为发生频率的简单随机响应机制。 让XYZ成为这样的活动。 面对查询“您在过去一周内从事XYZ吗？”，指示受访者执行以下步骤：

• 1.掷硬币。
• 2.如果是反面，请如实回应。
• 3.如果是正面，那么再掷第二枚硬币，如果正面回答“是”，如果是反面则回答“否”。

随机响应背后的动机是，它提供了“合理的否认”。例如，可能提供了“是”响应，因为第一次和第二次硬币翻转都是正面，概率为1/4。换句话说，隐私是通过过程获得的，没有“好”或“坏”的响应。获得响应的过程会影响如何合理地解释它们。如下声明所示，这种随机响应是差分隐私的。

命题 3.5 上述随机响应方法是 $(ln3,0)$- 差分隐私的。

【证明】： 假设固定随机响应者为同一人。上述分析表明 $\text{Pr}[Response=Yes|Truth=Yes]=3/4$ 。具体来说，当事实是“是”时，如果第一个硬币出现反面（概率1/2）或第一个和第二个出现正面（概率1/4），则结果将是“是”，而 $\text{Pr}[Response=Yes|Truth=No]=1/4$ （第一个出现在正面，第二个出现反面；概率为1/4）。同理，将类似的推理应用于事实为“否”的情况，我们获得：

$$\begin{array}{rl}\frac{\text{Pr}[Response=Yes|Truth=Yes]}{\text{Pr}[Response=Yes|Truth=No]}& \\ =\frac{\text{Pr}[Response=No|Truth=No]}{\text{Pr}[Response=No|Truth=Yes]}& =\frac{3/4}{1/4}=3=exp(ln3)\end{array}$$

于是 $\epsilon =ln3$ 上述随机响应方法是 $(ln3,0)$- 差分隐私的。

【命题 3.5证毕】

3.3 Laplace 机制

数值查询是数据库最基础的数据查询类型，将其定义为：$f:{\mathbb{N}}^{|\mathcal{X}|}\to {\mathbb{R}}^k$。这个查询将数据库映射成为k个真实值。将查询的${\ell }_1$敏感度作为衡量我们对查询回答的准确程度的参数之一。

定义3.1 （${\ell }_1$敏感度） 方法 $f:{\mathbb{N}}^{|\mathcal{X}|}\to {\mathbb{R}}^k$ 的 ${\ell }_1$敏感度为：
$$\Delta f=\underset{x,y\in {\mathbb{N}}^{|\mathcal{X}|},\Vert x-y{\Vert }_1=1}{\max }\Vert f(x)-f(y){\Vert }_1$$

【注：该处在哈佛大学的课程中表示为：$\Delta f={\max }_{x,y\in {\mathbb{N}}^{|\mathcal{X}|},\Vert x-y{\Vert }_1=1}|f(x)-f(y)|$，而《差分隐私算法基础》将 ${\ell }_1$敏感度表示为 定义 3.1 中形式。个人认为，对于以数值形式作为函数的输出，其敏感度计算应遵循哈弗大学课程中的计算公式。对于以分量形式作为函数的输出，应使用本书计算公式。下图使用哈佛大学课程中的举例，用平均值作为函数 $f$：

】

函数 $f$ 的 ${\ell }_1$ 敏感度反映了单体的数据在最坏情况下可以改变函数 $f$ 的程度，因此，直观地讲，为了隐藏单个人的参与，我们必须引入响应的不确定性。确实，我们将这种动机形式化：函数的敏感性为我们对输出施加多少扰动以保护隐私提供了一个上界。自然而然地，一种噪声分布可带来差分隐私。

定义3.2（拉普拉斯分布） 以0为中心，以 $b$ 为尺度的拉普拉斯分布，其概率密度函数的分布为：

$$Lap(x|b)=\frac{1}{2b}\exp (-\frac{|x|}{b})$$

这个分布的方差是 ${\sigma }^2=2b^2$ 。我们有时会写 $Lap(b)$ 来表示带尺度为 $b$ 的Laplace分布，有时会滥用符号，写 $Lap(b)$ 来表示随机变量 $X\backsim Lap(b)$。

拉普拉斯分布是指数分布的对称版本。

我们现在定义拉普拉斯机制。顾名思义，拉普拉斯机制将简单地计算 $f$，并用拉普拉斯分布的噪声扰动每个映射 $f$ 的输出结果(注：此处为个人理解补充进翻译中，原文省略了指代与解释。)。噪声的尺度将校准为 $f$ 的敏感度（除以 $\epsilon$）${}^{[1]}$

（原书注[1]: 或者，使用方差校准为 $\Delta fln(1/\delta )/\epsilon$ 的高斯噪声，可以实现 $(\epsilon ,\delta )$- 差分隐私（请参阅附录A）。拉普拉斯机制的使用更为简洁，两种机制在合成下的行为类似（定理3.20））

定义3.3 （拉普拉斯机制） 给定任意方法 $f:{\mathbb{N}}^{|\mathcal{X}|}\to {\mathbb{R}}^k$， 拉普拉斯机制定义为如下形式：
$${\mathcal{M}}_L(x,f(\cdot ),\epsilon )=f(x)+(Y_1,\dots ,Y_k)$$
此处的 $Y_i$ 是从 $Lap(\Delta f/\epsilon )$ 中提取的独立同分布随机变量。

定理 3.6 拉普拉斯机制是 $(\epsilon ,0)$-差分隐私。

【证明】：设 $x\in {\mathbb{N}}^{|\mathcal{X}|},y\in {\mathbb{N}}^{|\mathcal{X}|}$，同时满足 $\Vert x-y{\Vert }_1\le 1$ （即两者为相邻数据集）。并设 $f(\cdot )$ 是函数 $f:{\mathbb{N}}^{|\mathcal{X}|}\to {\mathbb{R}}^k$。用 $p_x$ 表示概率密度函数 ${\mathcal{M}}_L(x,f,\epsilon )$, $p_y$ 表示概率密度函数 ${\mathcal{M}}_L(y,f,\epsilon )$。我们用任意点 $z$ 比较这两者的概率密度：

$$\begin{array}{rl}\frac{p_x(z)}{p_y(z)}& =\prod _{i=1}^k\left(\frac{\exp (-\frac{\epsilon |f(x{)}_i-z_i|}{\Delta f})}{\exp (-\frac{\epsilon |f(y{)}_i-z_i|}{\Delta f})}\right)\\ & =\prod _{i=1}^k\exp \left(\frac{\epsilon (|f(y{)}_i-z_i|-|f(x{)}_i-z_i|)}{\Delta f}\right)\\ & \le \prod _{i=1}^k\exp \left(\frac{\epsilon |f(x{)}_i-f(y{)}_i|}{\Delta f}\right)\\ & =\exp \left(\frac{\epsilon \Vert f(x)-f(y){\Vert }_1}{\Delta f}\right)\\ & \le \exp (\epsilon )\end{array}$$

第一个不等式由三角不等式推导得来，最后一个不等式是由敏感度定义得到，即：$\Vert x-y{\Vert }_1\le 1$。且由对称性可得 $\frac{p_x(z)}{p_y(z)}\ge \exp (-\epsilon )$。

【定理 3.6 证毕】

【补充1: 由 Laplace机制的定义:

$${\mathcal{M}}_L(x,f(\cdot ),\epsilon )=f(x)+(Y_1,\dots ,Y_k)$$

为直观表示，使用随机变量的分量形式。即：$\overrightarrow{Y}=(Y_1,\dots ,Y_k)$，$f:{\mathbb{N}}^{|\mathcal{X}|}\to {\mathbb{R}}^k=\overrightarrow{f(x)}=(f(x{)}_1,...,f(x{)}_k)$。 所以，根据定理 3.6中的条件：

$$\begin{array}{rl}{p}_x(\overrightarrow{z})& =\text{Pr}[{\mathcal{M}}_L(x,f(\cdot ),\epsilon )=\overrightarrow{z}]\\ & =\text{Pr}[\overrightarrow{f(x)}+\overrightarrow{Y}=\overrightarrow{z}]\\ & =\text{Pr}[\overrightarrow{Y}=\overrightarrow{z}-\overrightarrow{f(x)}]\\ & =\frac{\epsilon }{2\Delta f}\exp (-\frac{\epsilon |\overrightarrow{f(x)}-\overrightarrow{z}|}{\Delta f})\\ & =\frac{\epsilon }{2\Delta f}\prod _{i=1}^k\exp (-\frac{\epsilon |f(x{)}_i-z_i|}{\Delta f})\end{array}$$

$\frac{p_x(z)}{p_y(z)}={\prod }_{i=1}^k\left(\frac{\exp (-\frac{\epsilon |f(x{)}_i-z_i|}{\Delta f})}{\exp (-\frac{\epsilon |f(y{)}_i-z_i|}{\Delta f})}\right)$ 表示形式就是上式拉普拉斯分布的分量形式，即：$p_x(z)=\frac{\epsilon }{2\Delta f}{\prod }_{i=1}^k\exp (-\frac{\epsilon |f(x{)}_i-z_i|}{\Delta f})$

【补充2：由于 定义 2.3 (数据库之间距离) 定义了数据库 $x$ 和 $y$ 之间的 ${\ell }_1$ 距离为 $\Vert x-y{\Vert }_1$

$$\Vert x-y{\Vert }_1=\sum _{i=1}^{|\mathcal{X}|}|x_i-y_i|$$

故：上述证明中的 ${\prod }_{i=1}^k\exp \left(\frac{\epsilon |f(x{)}_i-f(y{)}_i|}{\Delta f}\right)=\exp \left(\frac{\epsilon \Vert f(x)-f(y){\Vert }_1}{\Delta f}\right)$ 可由如下步骤得到：

$$\begin{array}{rl}\prod _{i=1}^k\exp \left(\frac{\epsilon |f(x{)}_i-f(y{)}_i|}{\Delta f}\right)& =\exp \left(\frac{\epsilon {\sum }_{i=1}^k|f(x{)}_i-f(y{)}_i|}{\Delta f}\right)\\ & =\exp \left(\frac{\epsilon \Vert f(x)-f(y){\Vert }_1}{\Delta f}\right)\end{array}$$
】

例3.1 计数查询：计数查询是“数据库中有多少个元素满足属性 P？”形式的查询。我们将一次又一次地回到这些查询，有时是纯形式，有时使用小数形式返回这些查询（“数据库中某元素的占比是多少…？”），有时带有权重（线性查询），有时带有稍微复杂的形式。（例如，对数据库中的每个元素应用 $h:{\mathbb{N}}^{|\mathcal{X}|}\to [0,1]$ 并求和）。计数是一个非常强大的原语。它占据了统计查询学习模型中所有可学习的内容，以及许多标准的数据挖掘任务和基本统计​​信息。由于计数查询的敏感度为1（单个人的添加或删除最多可以影响 1 个计数），因此 定理3.6 的直接结果是，可以实现 $(\epsilon ,0)$-差分隐私 计数通过添加尺度参数为 $1/\epsilon$ 的噪声进行查询，即通过添加从 $Lap(1/\epsilon )$ 分布提取的噪声进行查询。预期的失真或错误为 $1/\epsilon$，与数据库的大小无关。

固定但任意数量的 $m$ 个计数查询列表可以视为向量值查询。缺少有关查询集的任何进一步信息时，此矢量值查询的敏感性的最坏情况范围是 $m$，因为单个个体可能会更改每个计数（敏感度为 $m$）。在这种情况下，可以通过将尺度参数为 $m/\epsilon$ 的噪声添加到每个查询的真实答案中来实现 $(\epsilon ,0)$-差分隐私。

有时我们将响应大量（可能是任意的）查询的问题称为查询发布问题。

例3.2 直方图查询：在查询在结构上不相交的特殊（但很常见）情况下，我们可以做得更好——我们不必让噪声随查询的数量而变化。直方图查询就是一个例子。在这种类型的查询中，数据整体（ ${\mathbb{N}}^{|\mathcal{X}|}$ ）被划分为多个单元格，查询每个单元格中有多少数据库元素。由于单元格是不相交的，单个数据库元素的添加或删除会影响一个单元格中的计数，并且与该单元格的差异是 1，因此直方图查询的敏感度为1，可以对每个单元格中的真实计数增加源自 $Lap(1/\epsilon )$ 分布的噪声来回答查询。

为了了解一般查询的 Laplace 机制的准确性，我们使用以下有用的事实：

事实 3.7： 如果 $Y\backsim Lap(b)$，则：

$$\text{Pr}[|Y|\ge t\cdot b]=\exp (-t)$$

这个事实与布尔不等式（译者注：Union Bound，又称 Boole’s Inequality${}^{<1>}$）一起为我们提供了一个
关于拉普拉斯机制准确性的简单不等式：

定理 3.8 ：设 $f:{\mathbb{N}}^{|\mathcal{X}|}\to {\mathbb{R}}^k,y={\mathcal{M}}_L(x,f(\cdot ),\epsilon )$。则 $\forall \delta \in (0,1]$：
$$\text{Pr}[\Vert f(x)-y{\Vert }_{\infty }\ge \ln (\frac{k}{\delta })\cdot (\frac{\Delta f}{\epsilon })]\le \delta$$

【证明】 我们有：

$$\begin{array}{rl}\text{Pr}[\Vert f(x)-y{\Vert }_{\infty }\ge \ln (\frac{k}{\delta })\cdot (\frac{\Delta f}{\epsilon })]& =\text{Pr}[\underset{i\in [k]}{\max }|Y_i|\ge \ln (\frac{k}{\delta })\cdot (\frac{\Delta f}{\epsilon })]\\ & \le k\cdot \text{Pr}[|Y_i|\ge \ln (\frac{k}{\delta })\cdot (\frac{\Delta f}{\epsilon })]\\ & =k\cdot (\frac{\delta }{k})\\ & =\delta \end{array}$$

在证明中，第二个和最后的不等式是从拉普拉斯分布和事实3.7中推导得到的。

（译者注<1> 布尔不等式：指对于全部事件的概率不大于单个事件的概率总和，对于事件 $A_1,A_2,A_3...:P({\bigcup }_i{A}_i)\le {\sum }_{i}P(A_i)$）

【补充3： 上一证明过程缺少 ${\ell }_{\infty }$ 范数距离，又称切比雪夫距离，如下定义：$\Vert x\Vert$ 为 $x$ 向量各个元素绝对值最大那个元素的绝对值，形式化为：

$$\Vert x{\Vert }_{\infty }=\underset{k\to \infty }{\lim }(\sum _{i=1}^n|p_i-q_i{|}^k{)}^{1/k}=\underset{i\in [k]}{\max }|p_i-q_i|$$

】

【补充4: （定理3.8补充证明） 由 Laplace 机制可知 $Y_i\backsim Lap(\Delta f/\epsilon )$ 和 $y={\mathcal{M}}_L(x,f(\cdot \epsilon )=f(x)+(Y_1,\dots ,Y_k)$，则: $|f(x)-y|=|(Y_1,...Y_k)|$。

又因切比雪夫距离定义：

$$\Vert f(x)-y{\Vert }_{\infty }=ma{x}_{i\in k}|f(x)-y|=ma{x}_{i\in k}|Y_i|$$

故证明的第一步可以由此推导出：

$$\text{Pr}[\Vert f(x)-y{\Vert }_{\infty }\ge \ln (\frac{k}{\delta })\cdot (\frac{\Delta f}{\epsilon })]=\text{Pr}[\underset{i\in [k]}{\max }|Y_i|\ge \ln (\frac{k}{\delta })\cdot (\frac{\Delta f}{\epsilon })]$$

证明第二步是因为 ${\max }_{i\in [k]}|Y_i|\ge \ln (\frac{k}{\delta })\cdot (\frac{\Delta f}{\epsilon })$ 的概率必然小于等于 ⋃ i { ∣ Y i ∣ ≥ ln ⁡ ( k δ ) ⋅ ( Δ f ε ) } \bigcup_{i} \{|Y_i| \geq \ln(\frac{k}{\delta})\cdot(\frac{\Delta f}{\varepsilon})\} ⋃i​{∣Yi​∣≥ln(δk​)⋅(εΔf​)} 全体的概率，且由布尔不等式推导而来，即最大值 $Y_i$ 概率不大于单个事件的概率总和。又因为 事实3.7，推导如下：

Pr [ max ⁡ i ∈ [ k ] ∣ Y i ∣ ≥ ln ⁡ ( k δ ) ⋅ ( Δ f ε ) ] ≤ Pr [ ⋃ i { ∣ Y i ∣ ≥ ln ⁡ ( k δ ) ⋅ ( Δ f ε ) } ] ≤ ∑ i k ⋅ Pr [ ∣ Y i ∣ ≥ ln ⁡ ( k δ ) ⋅ ( Δ f ε ) ] = ∑ i k ⋅ exp ⁡ ( − l n ( k δ ) ) = k ⋅ ( δ k ) = δ \begin{aligned} \text{Pr}\Big[\max_{i \in [k]}|Y_i|\geq \ln(\frac{k}{\delta})\cdot(\frac{\Delta f}{\varepsilon})\Big] & \leq \text{Pr}\Big[ \bigcup_{i} \{|Y_i| \geq \ln(\frac{k}{\delta})\cdot(\frac{\Delta f}{\varepsilon}) \}\Big]\\ &\leq \sum_i^k \cdot \text{Pr}\Big[|Y_i| \geq \ln(\frac{k}{\delta})\cdot(\frac{\Delta f}{\varepsilon})\Big]\\ &= \sum_i^k \cdot \exp\big(-ln(\frac{k}{\delta})\big)\\ &= k\cdot(\frac{\delta}{k})\\ &= \delta \end{aligned} Pr[i∈[k]max​∣Yi​∣≥ln(δk​)⋅(εΔf​)]​≤Pr[i⋃​{∣Yi​∣≥ln(δk​)⋅(εΔf​)}]≤i∑k​⋅Pr[∣Yi​∣≥ln(δk​)⋅(εΔf​)]=i∑k​⋅exp(−ln(δk​))=k⋅(kδ​)=δ​

】

例3.3 名字频度： 假设我们要使用 2010 年人口普查参与者数据，并从数据中统计出给定的 10,000 个名字里各个名字的频度。 这个问题可以用查询 $f:{\mathbb{N}}^{|\mathcal{X}|}\to {\mathbb{R}}^{10000}$ 表示。 这是一个直方图查询，因此灵敏度$\Delta f=1$ ，因为每个人最多只能有一个名字。当频度查询是 $(1,0)$- 差分隐私的，并且概率要为 95％ ，我们使用上面的定理可以计算所有10,000名字的频度，其估计的相加误差不会超过 $\ln (10000/0.05)\approx 12.2$。 对于一个人口超过 300,000,000 的国家来说，这是非常低的错误！

【补充5: 由例3.3可知：$k=10000,\Delta f=1,\epsilon =1,\delta =1-0.95=0.05$，并由定理3.8可以推得上述结论：

$$\begin{array}{rl}\text{Pr}[\underset{i\in [10000]}{\max }|Y_i|\ge \ln (\frac{10000}{0.05})\cdot (\frac{1}{1})]& \le 0.05\\ then\text{Pr}[\underset{i\in [10000]}{\max }|Y_i|\le \ln (\frac{10000}{0.05})\cdot (\frac{1}{1})]& \ge 1-0.05\\ \text{Pr}[\underset{i\in [10000]}{\max }|Y_i|\le \ln (\frac{10000}{0.05})]& \ge 0.95\end{array}$$

】

差分隐私选择 例3.3中的任务是一个差分隐私选择：输出空间是离散的，任务是产生一个“最佳”答案。在例3.3中是选择输出是常用名频度最多的直方图单元。

例3.4 最常见的医学疾病 假设我们希望知道哪一个疾病是在一组被调查者的医疗史中最常见的，因此，需要对这些调查者进行一系列调查，调查其个人是否曾经接受过这些疾病的诊断。由于个人可能得过许多疾病，所以这些调查的敏感性可能很高。尽管如此，正如我们接下来描述的，这个任务可以通过在每个计数中添加 $Lap(1/\epsilon )$ 噪声来解决（注意噪声的小范围，它独立于疾病的总数）。关键是 $m$ 个噪音计数本身不会被发布（尽管“获胜”计数可以释放，没有额外的隐私损失）。（个人理解：m 个噪音计数即存在 m 种常见疾病，需要对 m 个常见疾病的统计计数增加噪声，并返回增加完噪声之后的最大值，即最常见的疾病。原文中的“获胜”应该指的是增加噪声最后的最大值。因为增加噪声之前与之后的最大值可能不一致。）

Report Noisy Max 请考虑以下简单算法，目的是为了确定在 m 个计数查询中哪个具有最高数值：将独立生成的拉普拉斯噪声 $Lap(1/\epsilon )$ 添加到每个计数中，并返回增加完噪声后最大计数索引（我们忽略之间可能的关联）。将此算法称为 Report Noisy Max。

注意到 “Report Noisy Max” 算法中的“信息最小化”原理：仅公开与最大值相对应的索引，而不是发布所有噪声计数并让分析人员找到最大值及其索引。 由于一个人的数据会影响所有计数，因此计数向量具有较高的 ${\ell }_1$ 灵敏度，即 $\Delta f=m$，如果我们想使用拉普拉斯机制发布所有计数，则需要更多的噪声。

命题 3.9 Report Noisy Max 算法是 $(\epsilon ,0)$-差分隐私。

【证明】 令 D = D ′ ∪ { a } D=D' \cup \{a\} D=D′∪{a} 。 令 $c,c^{\prime }$ 分别表示数据库为 $D,D^{\prime }$的计数向量。我们使用两个属性：

• 1.计数的单调性。对于所有 $j\in [m],c_j\ge c_j^{\prime }$
• 2.利普希茨（Lipschitz）属性。对于所有 $j\in [m],c_j^{\prime }+1\ge c_j$（注：Lipschitz连续，要求函数图像的曲线上任意两点连线的斜率一致有界，就是任意的斜率都小于同一个常数，这个常数就是 Lipschitz 常数，此处Lipschitz常数为1。）

定义任意 $i\in [m]$，我们将限制 i 分别从 $D$ 或 $D^{\prime }$ 提取比率的上下界。

定义 $r_{-i}$，从 $Lap(1/\epsilon {)}^{m-1}$ 用于除第 i 个计数外的所有噪声计数。我们会单独讨论每个 $r_{-i}$。我们使用符号 $\text{Pr}[i|\xi ]$ 表示 Report Noisy Max 算法在以 $\xi$ 的条件下，输出为 i 的概率。

我们首先讨论 $\text{Pr}[i|D,r_{-i}]\le e^{\epsilon }\text{Pr}[i|D^{\prime },r_{-i}]$ 的情况。 定义：

$$r^{\ast }=\underset{r_i}{\min }:c_i+r_i>c_j+r_j\forall j\ne i$$

注意，上面已经定义了 $r_{-i}$ 的情况。当且仅当 $r_i\ge r^{\ast }$ 时， i 为数据库 $D$ 的最大统计噪声输出。

对于所有 $1\le j\ne i\le m$：

$$\begin{array}{rl}{c}_i+r^{\ast }& >c_j+r_j\\ ⟹(1+c_i^{\prime })+r^{\ast }\ge c_i+r^{\ast }& >c_j+r_j\ge c_j^{\prime }+r_j\\ ⟹c_i^{\prime }+(r^{\ast }+1)& >c_j^{\prime }+r_j\end{array}$$

因此，如果 $r_i\ge r^{\ast }+1$ ，则当数据库为 D’ 时，第 i 个统计计数是最大的，且噪声向量为 $(r_i,r_{-i})$。下面的概率取决于 $r_i\backsim Lap(1/\epsilon )$ 的选择。

$$\begin{array}{rl}\text{Pr}[r_i\ge 1+r^{\ast }]& \ge e^{-\epsilon }\text{Pr}[r_i\ge r^{\ast }]=e^{-\epsilon }\text{Pr}[i|D,r_{-i}]\\ ⟹\text{Pr}[i|D^{\prime },r_{-i}]\ge \text{Pr}[r_i\ge 1+r^{\ast }]& \ge e^{-\epsilon }\text{Pr}[r_i\ge r^{\ast }]=e^{-\epsilon }\text{Pr}[i|D,r_{-i}]\end{array}$$

上面等式两边乘上 $e^{\epsilon }$ 第一种情况证明完毕。

证明第二种情况，即 $\text{Pr}[i|D^{\prime },r_{-i}]\le e^{\epsilon }\text{Pr}[i|D,r_{-i}]$ 定义：

$$r^{\ast }=\underset{r_i}{\min }:c_i^{\prime }+r_i>c_j^{\prime }+r_j\forall j\ne i$$

注意，上面已经定义了 $r_{-i}$ 的情况。当且仅当 $r_i\ge r^{\ast }$ 时， i 为数据库 $D$ 的最大统计噪声输出。

对于所有 $1\le j\ne i\le m$：

$$\begin{array}{rl}{c}_i^{\prime }+r^{\ast }& >c_j+r_j\\ ⟹1+c_i^{\prime }+r^{\ast }& >1+c_j^{\prime }+r_j\\ ⟹c_i^{\prime }+(r^{\ast }+1)& >(1+c_j^{\prime })+r_j\\ ⟹c_i+(r^{\ast }+1)\ge c_i^{\prime }+(r^{\ast }+1)& >(1+c_j^{\prime })+r_j\ge c_j+r_j\end{array}$$

因此，如果 $r_i\ge r^{\ast }+1$ ，则当数据库为 D 时，第 i 个统计计数是最大的，且噪声向量为 $(r_i,r_{-i})$。下面的概率取决于 $r_i\backsim Lap(1/\epsilon )$ 的选择。

$$\begin{array}{r}\text{Pr}[i|D,r_{-i}]\ge \text{Pr}[r_i\ge r^{\ast }+1]\ge e^{-\epsilon }\text{Pr}[r_i\ge r^{\ast }]=e^{-\epsilon }\text{Pr}[i|D^{\prime },r_{-i}]\end{array}$$

上面等式两边乘上 $e^{\epsilon }$ 第二种情况证明完毕。

【命题 3.9 证毕】

---

目录导航

第1章：https://blog.csdn.net/AdamCY888/article/details/146454841
第2章:https://blog.csdn.net/AdamCY888/article/details/146455093
第3章(1/3):https://blog.csdn.net/AdamCY888/article/details/146455756
第3章(2/3):https://blog.csdn.net/AdamCY888/article/details/146455796
第3章(3/3):https://blog.csdn.net/AdamCY888/article/details/146455328
第4章:https://blog.csdn.net/AdamCY888/article/details/146455882
第5章:https://blog.csdn.net/AdamCY888/article/details/146456100
第6章(1/2):https://blog.csdn.net/AdamCY888/article/details/146456712
第6章(2/2):https://blog.csdn.net/AdamCY888/article/details/146456972
第7章:https://blog.csdn.net/AdamCY888/article/details/146457037
第8章:https://blog.csdn.net/AdamCY888/article/details/146457172
第9章:https://blog.csdn.net/AdamCY888/article/details/146457257
第10章:https://blog.csdn.net/AdamCY888/article/details/146457331
第11章:https://blog.csdn.net/AdamCY888/article/details/146457418
第12章:https://blog.csdn.net/AdamCY888/article/details/146457489
第13章(含附录):https://blog.csdn.net/AdamCY888/article/details/146457601