差分隐私组合定理（1）🐱‍🚀🐱‍🚀

https://zhuanlan.zhihu.com/p/212819144

差分隐私的 Composition Theorem

在前面三节介绍的内容是0到1的一个过程，是为了明白差分隐私的基本概念。而这一节要讲到Composition Theorem是1到n的过程。
Composition Theorem直接翻译的话就是组成原理，目的就是将一系列满足差分隐私的查询组合在一起，并且保证整体仍然满足差分隐私。
例如，对一个简单的3层神经网络，如果将每个神经元计算梯度看成一个查询函数 ，输入是数据集 ，输出是梯度 。那么组成原理研究的就是整个神经网络满足怎样的差分隐私。这篇里面主要讲的包括两个部分的内容:

• 第一个是基本组成原理，就是不考虑查询函数之间的关联性（查询相互独立）
• 第二个是高级组成原理，就是考虑查询函数之间的关联性

基本的内容目录如下：

• 基本组成原理 Basic Composition Theorem
  • 并行组成 不相交数据集，不同查询
  • 串行组成 同一数据集，不同查询
• 高级组成原理 Advanced Composition Theorem
  • Naive Composition Theorem
  • Strong Composition Theorem
  • Moment Account (15年Deep Learning with Differential Privacy[1]中提出的)

    1. Basic Composition Theorem

    1.1 Sequential Composition 串行组合

    串行组合简单讲就是同一数据集，不同查询函数，在[PINQ][2]中的定义是：
    
    其中 表示一个满足 的差分隐私算法，而 表示所有的算法作用于同一个数据集 ,那么这些算法构成的集合满足 差分隐私，证明很简单，可以直接参考[PINQ][2] 中的2.4节。简单的示意图如下面图1中左边的Sequential Composition。

    1.2 Parallel Composition 并行组合

    并行组合简单讲就是不同数据集，不同查询函数，在[PINQ][2] 中的定义是：
    
    其中 表示一个满足 的差分隐私算法， 表示互不相交的数据集， 表示各个差分隐私算法之间作用的数据集互不相交，那么整体满足 差分隐私。一个推广是，如果 满足 的差分隐私算法，那么整体满足 差分隐私。简单示意图如图1中右边的Parallel Composition。
    
    图1 串行和并行组成原理

    2. Advanced Composition 高级组成

    在上一节我们讲了两个基本的组成原理，并行的和串行的。而这一节，我们向更高级一点的方向研究一下。我们考虑攻击者可以自适应地影响数据库以及对应的查询机制，换句话说查询与查询之间是存在关联的，如下图所示。
    
    其中， 表示一系列满足差分隐私的查询机制，数量为 ； 表示第 个查询机制； 表示攻击者； 表示两个邻接数据库； 表示的是实验的下标； 表示第 个查询机制得到的结果。
    最终的输出结果可以用 进行表示：
    
    其中 代表的是攻击者 随机扔出的一个骰子，值可以是0或者1，代表两个实验；其余的 表示的是 次查询的结果。
    这个输出是一个多维的随机变量，它有对应的分布；我们的目标就是让基于任意两个兄弟数据集（只相差一个样本）得到的两个输出变量之后，他们对应的分布的差异应该尽可能接近，以至于攻击者不知道用了哪个数据集。而两个分布的差异就称为Privacy Loss，如果是严格约束这个Privacy Loss，那么就是 差分隐私；如果允许一定程度违背，那么就是 差分隐私。

    2.1 Navie Composition Throrem

    
    这是最简单的组合机制，可以看到组合之后的 。证明内容可以参考[lecture][3]，一个简单的例子如下[DLDP][4]。
    

    2.2 Strong Composition Throrem

    强组合原理的基本思想就是用很小的一点 换取很多的 。这里的证明可以参考[Privacy Book][5]中的[Theorem 3.20]。
    
    这里咋一看组合之后的 比Naive Composition的还多，但实际上当 的时候，后面一项 近似等于0，这样整体的 ，相当于 ，相对于原来的 节省了更多的隐私预算。一个简单的例子如下[DLDP][4]：
    

    2.3 Moments Accountant

    这是在Deep Learning with differential privacy中提出来的方法，细节的证明可以参考[1]，这里我讲述一下基本思路。
    它提出的方法就是在计算的梯度 中加入噪声，而重要的就是噪声的大小，整篇文章的重点就是研究如何在满足差分隐私的前提下加入噪声。
    
    
    
    而这个 决定了加入噪声 的大小，其中 。一个简单的例子为[4]：
    
    可以看到在三种方法种，Moment Account方法在同样的花费的隐私预算最小。