为什么在正式的差别隐私定义中使用集合成员资格符号(∈)？

Question

在差分隐私的The算法基础 (Dwork，C；Roth，A)中，微分隐私的形式定义如下：

“

带有域\mathbb{N}^{|\mathcal{X}|}的随机算法D1对于所有的\mathcal{S} \subseteq Range(\mathcal{M})和x, y \in \mathbb{N}^{|\mathcal{X}|}都是不同的私有的，例如\|x - y\|_1 \leq 1：Pr[\mathcal{M}(x) \in \mathcal{S}] \leq \exp(\epsilon) Pr[\mathcal{M}(y) \in \mathcal{S}] + \delta，\mathcal{X}是来自宇宙的记录的集合，x, y是数据库

“

我不明白为什么这个定义使用'\in‘运算符。我的意思是，如果他们使用'=‘符号而不是'\in’运算符，这不是一样的，因为每个\mathcal{S} \subseteq Range(\mathcal{M})的定义都应该成立。你能帮我理解为什么他们在正式的差别隐私定义中使用“\in”符号吗？

Answer 1

子集语句更强。的确，\mathrm{Pr}[\mathcal M(x)\in\mathcal S]=\sum_{\xi\in \mathcal S}\mathrm{Pr}[\mathcal M(x)=\xi].

但是，如果我们对每个\mathrm{Pr}[\mathcal M(x)=\xi]\le\exp(\epsilon)\mathrm{Pr}[\mathcal M(y)=\xi]+\delta都有一个语句\xi\in \mathcal S，然后尝试为\mathrm{Pr}[\mathcal M(x)\in\mathcal S]开发一个绑定，那么我们所能管理的最好的就是\mathrm{Pr}[\mathcal M(x)\in\mathcal S]=\sum_{\xi\in \mathcal S}\mathrm{Pr}[\mathcal M(x)=\xi]\le\exp(\epsilon)\sum_{\xi\in\mathcal S}\mathrm{Pr}[\mathcal M(y)=\xi]+\sum_{\xi\in\mathcal S}\delta，其中RHS是\exp(\epsilon)\mathrm{Pr}[\mathcal M(y)\in\mathcal S]+|\mathcal S|\delta.。

由于适用于\delta的子集大小的额外因素，这比给出的定义要弱。简单地说，子集绑定意味着单个输出绑定，因为子集可以有一个元素。

Answer 2

编辑：你的问题不清楚(至少对我来说是这样)，直到我的答案底部的评论。在这种情况下，正如在另一个答案中指出的，set子集语句更强:我们有一个一致保持而不是以点态方式保持的界。

集合成员资格\in不同于\epsilon，后者是这些定义中用作参数的一个小的正常量。因此，您可以将\epsilon>0,设置为任意大小，并为您设计的\delta差异私有机制找出相应的D3是什么。

因此，如果x,y彼此接近，那么算法的输出是接近的，并且算法输出的接近程度由(\epsilon,\delta)决定，在Pr[\mathcal{M}(x) \in \mathcal{S}] \leq \exp(\epsilon) Pr[\mathcal{M}(y) \in \mathcal{S}] + \delta中，\exp(\epsilon)是标量因子，\delta是一个加性因子，控制算法的x输出降到\cal S的概率与算法在算法范围内所有子集的y输出下降为\cal S的概率相比较。