Certified Robustness to Adversarial Exampleswith Differential Privacy
这篇文章将Differential Privacy 和 Certified Robustness相结合，提出了一种defend 和 verification的新思路。以往提出的defend方法大部分都立即被破解了，唯一的例外是Madry提出的adversarial training。然而，尽管Madry的方法在实际使用过程中的确有效，但是却缺少对单个预测鲁棒性的理论分析（比如说，经过adversarial training后得到的model，对某一个具体的样本，我们并不知道在多大范围内它的结果是鲁棒的）。
PixelDP则较好得解决了这个问题。它不仅从理论上对certified robustness的结果进行了分析（能够对单个样本分析其保持预测结果的范围），同时在实证过程中也表现不俗：它能够顺利得扩展到大规模数据集（Imagenet） 和复杂深度网络（InceptionV3, ResNet）的使用。下面介绍文章的基本思路：
Differential Privacy
DP is concerned with whether the output of a computation over a database can reveal information about individual records in the database.
简单来说，就是对数据库进行某种云端，我们能否通过这个运算来推知数据库汇中某条记录的值。希望有一种算法，它对于两个非常相近的数据库d 和d'，得到的结果非常接近。这样，我们就既能够得到想要的结果，又不用担心数据泄漏了。数学表示为:
A randomized algorithm A that takes as input a database d and outputs a value in space O is said to satisfy
with respect to a metric
if, for any databases
and
with
, and for any subset of possible output
, we have
这里我们进行一个对应，如果把一个图看成database, 每一个pixel看成一条record，网络看成一个随机算法，那么满足上述条件的随机算法其实也是我们希望的具有鲁棒性的算法：我们所说的鲁棒性，是指当输入在一定范围内受到扰动时，网络的结果不要改变。对于分类网络来说，就是具有最大概率的类别的概率值要始终比第二大的概率要大。如果这个随机算法是的，两个输入对应输出的概率分布应该是类似的，所以预测的类别应该是一样的。这就是根本的联系。
现在的问题是，如何训练出满足的网络？作者的做法是，在卷积层后加入噪声层，后续不变。通过保证卷积层+噪声层构成的函数是
，从而保证整个网络满足。这部分在文内有详细分析，包括噪声层的方差和
与
的关系，为什么在第一个卷积层加等等。
当我们训练好这个网络后，使用方法是，多次draw噪声，得到多个概率向量，取平均值作为最后的结果。这里我们其实是用 作为
的替代。这里会用到随机算法的知识：即，
和
有多靠近。因为
，即是一个有界的随机变量，我们由Hoeffding's equality，在给定失败概率
的情况下，我们能够给出两者差距的一个bound：
由此，我们可以给出最后的判定条件，当
时，我们可以说，此时网络对于这个样本
以大于
的概率对p-norm
的attack时鲁棒的。
总的来说，这篇文章突破了过去做verfication的框架，巧妙得将差分隐私和certified defense联系起来，应用随机算法分析的方法，给出了certified defense的理论结果以及实操方案。文中指出，在实际使用过程中，训练部分花费的时间和原本训练非defended的网络需要的时间几乎一致，这要明显优于Madry的方法：因为Madry需要取找对应的“错的最厉害的样本”，这一步要花费很多时间；不过，对应的，PixelDP会在做inference的时候花费更多时间。
