差分隐私组合定理（2）🤦‍♂️🤦‍♂️

一、前言

由于网上关于差分隐私（differential privacy, DP）的中文资料比较少，大部分文章仅着重于阐释差分隐私的基本概念，因此想写一些文章来总结差分隐私的研究成果。本文主要探讨如何深入理解几种著名的composition theorem的内在思想，包括最基础的Simple Composition，Dwork et al.在2010年提出的Advanced Composition[1]和Abadi et al.在2016年提出的Moments Accountant[2]。在此之上也有一些更新的理论成果，将会在之后的文章中介绍。本文不会着重介绍差分隐私的概念，因此在阅读本文之前，需要对差分隐私基本概念有一定的了解。

二、背景介绍

1、差分隐私的定义
假设存在一个随机函数，使得在任意两个相邻的数据集（即）上得到任意相同输出集合的概率满足

则称该随机函数满足-differential privacy（差分隐私），简写为-DP。
2、 Composition theorem探讨的问题
当个随机函数作用在同一个数据集上时，将这些随机函数称作一个composition，记作。Composition theorem探讨的问题是：假设每一个随机函数都满足-DP ，那么整个composition满足什么样的DP呢？

三、理解差分隐私：隐私损失（Privacy Loss）

差分隐私（DP）的定义实际上是保证去掉/改变一个样本不会对的输出造成显著的影响。换言之，DP保证了和有着相似的概率分布。按照DP的定义，如果和的概率分布相差越大，那么隐私损失就越大；如果和的概率分布相差越小，那么隐私损失就越小。于是，我们可以按照概率分布的差距严格地定义隐私损失[3]如下。
定义1:（隐私损失，Privacy Loss）对于两个相邻的数据集（即），输出和随机函数，该随机函数造成的隐私损失定义为

隐私损失与-DP 的定义紧密相关，这种关联在定理1中有很好的体现。
定理1[2]：随机函数是-DP 的充分条件是其隐私损失满足
（1）
证明：
定义

如果，那么有
因此，满足-DP

四、简单的思路：Simple Composition

在了解隐私损失的定义后，composition theorem所研究的问题可以转为：已知一个随机函数的隐私损失，那么个随机函数总的隐私损失是多少呢？很惊讶地发现，在每一个随机函数所加的噪声（noise）相互独立时，隐私损失是可以累加的！

（注：严格来说这里的概率都是条件概率，为了简洁，推导中省去了条件）
换言之，如果每一个随机函数的隐私损失都小于，那么个随机函数组成的composition的隐私损失小于。根据这个思路，立刻可以得到一个最简单的composition theorem：Simple Composition。
定理2（Simple Composition）如果是-DP 的随机函数，那么一个composition满足-DP 。

定理3（Simple Composition）如果是-DP 的随机函数，那么一个composition满足-DP 。

五、进阶的思考：Advanced Composition

在Simple Composition中，直接累加隐私损失的上界可以得到一个简单的composition的上界，但是这样的上界足够紧吗？在[1]中给出了否定的答案。
注意到隐私损失是一个随机变量，要获得多个随机变量累加的上界，绝对不是简单的把每一个随机变量的上界累加就可以得到的。注意到随机变量除了本身的值有一个范围，他的期望也有一个范围。如果同时考虑这两个范围，那么就很可能得到一个更紧的上界。
引理1：（期望的上界）如果个随机函数均满足-DP ，那么


引理2：（吾妻不等式，Azuma’s Inequality）假设存在个随机变量，满足对于任意都有，且，那么有


隐私损失值的上界由DP的定义给出，期望的上界由引理1给出，得到这两个上界后，就可以根据吾妻不等式直接得到composition的概率的上界。这个上界由Advanced Composition[1]给出。
定理4（Advanced Composition）对于，如果是-DP 的随机函数，那么满足-DP，其中
可以看到，总的不再像Simple Composition一样随着随机函数的数量线性增长，而是随着线性增长，因此Advanced Composition在较大时显著好于Simple Composition。

六、全面的考虑：Moments Accountant

Simple Composition只考虑了隐私损失值的范围，Advanced Composition多考虑了隐私损失期望的范围，那如果考虑隐私损失这个随机变量更多的性质，是否能进一步减小这个上界呢？Moments Accountant[2]给出了肯定的答案。
众所周知，随机变量的期望又称作随机变量的“一阶原点矩”。期望体现了随机变量分布的某种性质，但是却不能唯一的确定随机变量的分布。随机变量的分布由矩生成函数[6]（moment generating function）唯一的确定。如果能找到所有阶矩（-th moments）的上界，而不仅仅是一阶矩（期望），那么就能找到矩生成函数的上界，并进一步找到一个更紧的隐私损失的上界。这就是Abadi et al.所提出的Moments Accountant的基本思路。
为了证明这个上界，首先需要证明每一个随机函数的矩生成函数的上界。Abadi et al.针对高斯分布的特例，使用了二项展开的方法，证明了前三项远大于其他的项和前三项的上界。之后他们又证明了矩生成函数的上界可以像隐私损失一样累加（在噪声独立的情况下）。最终，他们导出了一个更紧的composition隐私损失的上界。由于他们的研究着重于深度学习，因此给出的定理是以SGD为基础的。
定理5（Moments Accountant）假设SGD的随机选择概率为，训练轮数为，那么存在常数使得，若Gaussian Mechanism的标准差满足

则这一系列个 Gaussian Mechanism所构成的composition满足-DP 。

七、总结

本文着重介绍基于定理1所提出的Composition theorem的具体思想。可以看到，在定理1的框架下，Simple Composition、Advanced Composition和Moments Accountant分别通过分析隐私损失分布的性质得到了总的隐私损失的上界。这些composition theorem主要的区别可以总结为描述概率分布的手段不同，具体总结见下表。

再接下来的工作中，仍然针对这个隐私函数的上界有进一步的降低。不过这些工作的思路已经跳出了定理1的框架，因此不在本文中讨论，将会在接下来的文章中继续介绍这部分工作。
2021.3.18. 更新：由于之前与Prof. Reza Shokri的讨论中他指出定理1是一个“必要充分条件”，但是我没有找到相关的证明，因此暂时删去部分相关的表述。如果有读者了解相关的材料欢迎与我交流讨论。