越“安全”，越“强大”：京东探索研究院何凤翔等证明模型的泛化和安全具有协同性

越“安全”，越“强大”：京东探索研究院何凤翔等证明模型的泛化和安全具有协同性

作者 | 王博涵

编辑 | 维克多

人工智能系统需要依赖大量数据，然而数据的流转过程以及人工智能模型本身都有可能泄漏敏感隐私数据。

学界针对隐私泄露问题提出了多种针对性的保护方法，例如差分隐私和联邦学习。

差分隐私的核心思想是：具有优秀隐私保护能力的人工智能算法应当对输入数据中的微小扰动不敏感。基于该思想，可以通过对数据进行下采样、顺序置换、添加噪声等方式，来防御攻击者进行隐私窃取。

虽然差分隐私具有良好的应用前景，但对此算法的可解释性和稳定性以及隐私保护能力的理论研究仍需努力。

近日，不确定性人工智能领域顶会UAI（Conference on Uncertainty in Artificial Intelligence）刊登了一篇题为“Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms”的论文， 该论文从理论方面证明了隐私保护和可解释性之间的关系：通过利用差分隐私来解释泛化能力，发现模型的泛化能力和隐私保护能力具有协同性。

论文作者有人工智能和信息科学领域国际知名学者、京东探索研究院院长陶大程，京东探索研究院算法科学家何凤翔，以及UIUC一年级博士生王博涵(进行该工作时在悉尼大学访问)。

具体而言，该论文从理论和实验上证明了：

(1). 差分隐私与泛化能力的正相关性；

(2). 差分隐私与时间的负相关性；

(3). 泛化能力和训练时间的负相关性。

1 背景介绍：隐私保护蕴含泛化能力

在用户数据隐私安全正遭受日渐严峻的威胁的当下，具有隐私保护能力(Privacy-preserving)的机器学习算法成为人工智能领域的研究热点之一。一般来说，一个算法对于数据的隐私保护能力越好，它就越不容易受到个别个体的影响。以目前最常用的隐私度量(Privacy Metric)方式差分隐私(Differential Privacy)举例，我们说一个随机算法A具有(%u3B5,%u3B4)的差分隐私，这意味着，如果A满足对于任意两个相邻的数据集(即只相差一个数据点)S和S&apos，A的输出A(S)和A(S&apos)的分布满足对于任意输出空间的集合B：

%u3B5和%u3B4越小，A(S)和A(S&apos)的分布就越接近，改变一个数据点对算法输出的影响也就越小。因此，隐私保护能力好的算法将更倾向于学到整个数据集服从的分布(underlying distribution)，而不是每个个体单独的信息。这在直觉上与模型的泛化能力(Generalization Property)不谋而合。

模型的泛化能力指模型在训练集(training set)和测试集(test set)上的表现的差距。具体而言，对于监督学习(Supervised Learning)，记训练集为S={z_1= (x_1,y_1 ),⋯,z_N=(x_N,y_N )}独立同分布地抽样于分布D，其中x_i是第i个数据的特征(feature)，y_i是第i个数据的标签(label)；类似地，记测试集T={(x_(N+1),y_(N+1) ),⋯,(x_(N+M),y_(N+M) )}同样独立同分布地抽样于分布D。那么，对于随机算法A与损失函数l，算法输出A(S)在训练集上的风险函数可以定义为：

而测试集上的风险函数则可以定义为：

更进一步地，由于T与算法输出A(S)无关，并且应当体现出数据分布的特征，一般会考虑：

由于神经网络在机器学习中的广泛应用，模型在训练集上的表现基本都能达到100%分类正确。因此，越好的泛化能力等价于越好的测试集表现 。更进一步地，由于训练集和测试集往往只共享服从的分布，一个算法学到越多分布的信息，它在测试集上的表现就越好，从而泛化能力越强。总而言之，一个算法的泛化能力和它的隐私保护能力成正相关。

另一方面，机器学习/深度学习的算法往往是迭代式的，在这个前提下，尽管每一步的隐私保护能力很容易得到，但算法整体的隐私保护能力却很难获得。更具体来说，对于一个迭代算法A，数据集S以及初始化后的参数w_0，第t+1步迭代后的参数由以下式子给出：

由于M_(t+1)具有显示形式，所以得到第t+1步的隐私保护能力是容易的。而研究者发现，算法整体的差分隐私可以由每一步的差分隐私来估计(称为Composition Theorem)。由于对于每一步的隐私保护能力的估计往往是精确的，因此使Composition Theorem变紧是让算法整体隐私保护能力估计变紧的重要方式。

2 本篇工作的贡献

本篇工作证明了在给定差分隐私参数(%u3B5,%u3B4)下的具有迭代结构的机器学习算法(例如随机梯度法)的更紧的泛化误差界。更具体来说，对于该泛化误差界的提升可以分为两部分：第一，对于任意的服从(%u3B5,%u3B4) 差分隐私的机器学习算法证明了更紧的泛化误差界；第二，对于第i次迭代服从(%u3B5_i,%u3B4_i) 差分隐私的迭代算法证明了更紧的算法整体的差分隐私参数。最终，通过合并以上两点，可以得出对于具有迭代结构的机器学习算法的更紧的泛化界。在实验上，本论文验证了

(1). 差分隐私与泛化能力的正相关性(泛化定理)；

(2). 差分隐私与时间的负相关性(Composition Theorem)；

(3).泛化能力和训练时间的负相关性((1)+(2))。

3 理论细节

1.更紧的由差分隐私给出的泛化误差界

定理的正式描述由下图给出：

本论文的定理相较之前的State-of-the-art [1]有如下提升：

(1).在%u3B5≤1/10的情形下，把a从13%u3B5缩小到了4%u3B5；

(2) 在%u3B5≤1/10的情形下，把b缩小了e^(-1.7%u3B5)倍；

(3).论文中的定理给出了%u3B5&gt1/10情形下的泛化误差界。

关于证明，该论文采用了[1]中构造的多数据集框架。简单来说，多数据库框架是指对于任意运行在一个数据集(大小为N)上的算法A，都能构造一个运行在k个数据集(大小也为N)上的算法B。更进一步的，B满足和A相近大小的差分隐私，同时 B的泛化误差可以导出A的泛化误差。因此，只需要给出B的泛化误差界即可，而这可以通过先计算期望再利用马尔可夫不等式得到。提升来源于对于B的泛化的期望更紧地估计：具体来说，由于差分隐私的对称性，因而基于差分隐私构造的泛化误差界满足上界与下界互为相反数。因此，该论文转而去估计该泛化误差的下界，并发现该估计在相反数意义下比估计上界更紧。

2.更紧的Composition Theorem

定理的正式描述由下图给出：

相较于当前的State-of-art [2]，该论文的定理给出了对于%u3B4&apos的%u3B4 (e^%u3B5-1)/(e^%u3B5+1)(T-⌈%u3B5&apos/%u3B5⌉) 大小的提升。由于实际应用中算法的迭代步数往往很多，所以这一提升是显著的。

关于证明，[2]中给出了最坏情况下Composition Theorem对应的算法/机制。该论文同样利用了这一机制，有所不同的是其先将(%u3B5_t,%u3B4_t)的每一步迭代M_t近似成一个(%u3B5_t,0)的迭代 M %u303_t(并满足与M_t之间的距离小于%u3B4/(1+e^%u3B5 ))。该论文先对 M %u303_t使用Composition Theorem，再通过整体算法之前的距离得到原本的差分隐私参数。这一过程减少了差分隐私参数估计的损失。

3.应用结果到SGLD上

作为举例，该论文将以上两个例子应用到DP-SGD上。DP-SGD可以视作SGD加上高斯噪声的版本，是SGLD(Stochastic Langevin Dynamics)的特殊情形，其具体定义如下：

该论文计算了泛化对于N的渐进误差界

这一泛化界对于N是紧的。

4 实验

为了验证理论的正确性，该论文在MNIST、CIFAR-10以及CIFAR-100上进行了实验，分别验证了：

(1). 差分隐私与泛化能力的正相关性；

(2). 差分隐私与时间的负相关性；

(3).泛化能力和训练时间的负相关性。实验结果如下，可以看到与该论文的推断是一致的。

References:

[1] Fengxiang He, Bohan Wang, Dacheng Tao. “Tighter Generalization Bounds for Iterative Privacy-Preserving Algorithms.” Conference on Uncertainty of Artificial Intelligence. 2021.

[2] Kobbi Nissim, and Uri Stemmer. &quotOn the generalization properties of differential privacy." arXiv preprint arXiv:1504.05800. 2015.

[3] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. &quotThe composition theorem for differential privacy." International conference on machine learning. 2015.

由于微信公众号试行乱序推送，您可能不再能准时收到的推送。为了第一时间收到的报道， 请将“”设为 星标账号在看”。

如懿传3 http://www.cityruyi.com/lm-4/lm-1/3627.html