收录于 · 差分隐私合集

143 人赞同了该文章

差分隐私的 Composition Theorem

在前面三节介绍的内容是 0到1 的一个过程，是为了明白差分隐私的基本概念。而这一节要讲到 Composition Theorem 是 1到n 的过程。

Composition Theorem 直接翻译的话就是 组成原理 ，目的就是将一系列满足差分隐私的查询组合在一起，并且保证整体仍然满足差分隐私。

例如，对一个简单的3层 神经网络 ，如果将每个 神经元 计算 梯度 看成一个查询函数 $\nabla f : D \rightarrow g$ ，输入是数据集 $D$ ，输出是梯度 $g$ 。那么组成原理研究的就是整个神经网络满足怎样的差分隐私。这篇里面主要讲的包括两个部分的内容:

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

基本的内容目录如下：

• 基本组成原理 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 中的定义是：

其中 $M_i$表示一个满足 $\epsilon_i$的差分隐私算法，而 $M_i(X)$表示所有的算法作用于同一个数据集 ,那么这些算法构成的集合满足 $\sum_i \epsilon_i -$差分隐私，证明很简单，可以直接参考[PINQ] 3 中的 2.4节 。简单的示意图如下面图1中左边的 Sequential Composition 。

1.2 Parallel Composition 并行组合

并行组合简单讲就是 不同数据集，不同查询函数 ，在[PINQ] 4 中的定义是：