FedPAC | 概率近似正确联邦学习

隐私(Privacy)、效用(Utility)和效率(Efficiency)是可信联邦学习的三大核心，但已有研究表明，在设计联邦学习算法时，无法保证隐私泄露无穷小的同时，还能达到效用损失和效率损失同时最小。因此，如何实现三者的权衡（trade-off）取舍是联邦学习算法设计的关键。一种常见的方案是将权衡问题归为约束多目标最优化（Multi-objective optimization）问题，即在保证隐私泄露小于某个预设值的前提下，同时最小化效用损失和效率损失。但多目标的优化通常是一个很复杂的问题，现有的多目标优化策略都非常耗时，而且无法保证能得到最优解。今天为大家带来一篇名为《概率近似正确联邦学习（Probably Approximately Correct Federated Learning）》的论文解读，在本文中，作者提出了基于PAC Learning概率近似正确（Probably Approximately Correct，简称PAC）的统一度量框架，来权衡不同目标并求解Pareto前沿。PAC Learning是一个机器学习的数学分析框架，是由Leslie Valiant于1984年在《Communications of the ACM》上发表的论文“A theory of the learnable”中首次提出，Valiant因其对PAC学习理论、枚举、计算代数复杂性等理论计算机科学问题的重要贡献，在2010年被ACM授予图灵奖[1][2][3]。论文链接：https://arxiv.org/abs/2304.04641

1

研究的开创性

本研究创新性地提出了“概率近似正确联邦学习”（FedPAC），首次将PAC learning学习理论与联邦学习相结合，该框架开创性地针对下面的问题进行分析解答：

• 基于PAC理论，为联邦学习的隐私、效用和效率提供性能限界(bound)。具体来说，我们将使用样本复杂度（Sample complexity）作为中间桥梁，对隐私、效用和效率进行统一的量化，将三者都放在相同的维度空间上进行度量。这样做的好处是使得三者之间具有可比性，并且多个目标的解约束在相同的共享空间中，从而将三者的权衡问题从多目标优化转化为单目标优化求解。
• 创新性地将联邦学习的所有参与者(包括防守者、攻击者、模型构建者)，都构建在PAC学习架构上。因此，对于攻击算法和防守策略，我们都可以用样本复杂度来衡量。具体来说，从防守者的角度，使用样本复杂度来衡量添加保护机制后可能出现的效用和效率损失，防守者通过成本分析调整防守策略；从攻击者的角度，使用样本复杂度来衡量攻击的成本，攻击者可以通过成本分析是否值得进行攻击。

进一步对上面问题的深入分析，我们将得到本文中最重要的一个结论，即隐私泄露、效用损失和训练效率三者权衡的表达式，如下图所示，该结论及其相关推论，可用于指导实际的算法设计。

• 当训练效率固定时，隐私泄露越小，则效用损失的上界就越大。也就是说，对于任意两个保护机制，当它们的训练效率相同时，保护性能较强的保护机制，其产生的隐私泄露就越小，所带来的模型效用损失就越大；反之，保护性能较弱的保护机制，其产生的隐私泄露就越大，所带来的模型效用损失就越小。 
• 当隐私泄露固定时，训练效率越小，则效用损失的上界就越大。也就是说，对于任意两个保护机制，当它们具有相同的保护能力时，训练效率较小的保护机制，其训练样本量也较少，从而导致较大的模型效用损失；反之，训练效率较大的保护机制，其训练样本量也较多，训练数据越多则训练越充分，模型的效用损失将减少。

2

研究的方法与场景

权衡问题可以通过下面的约束多目标优化来形式化表示，如下方公式所示。不失一般性，我们以最小化为例，其中待求解的目标有个，记为 ，其中  ；含有个约束，记为  ，其中  。

但像上面公式所示的多目标优化问题往往很难求解，主要体现在下面三个方面：

• 现有的很多研究表明，多目标的优化算法很难同时得到多个目标的最优解。

• 大多数情况下，多目标优化不能直接使用基于梯度的方法来高效求解，需要借助于像基于进化（Evolution-based）的算法、基于贝叶斯（Bayesian-based）的优化、基于深度学习（Deep learning-based）的优化等，但这些算法的求解复杂度都很高。

• 现有的多目标转化为单目标的方法，如线性标量法（linear scalarization）等，会通过不同的权重将多个目标组合起来变为一个单目标，即 ，但权重参数的设置需要通过手工设置，通常情况下是靠经验和多次尝试，因此效率很低。

考虑到上述多目标问题优化遇到的困难和挑战，我们提出一种利用PAC learning来对多个目标进行统一度量的框架，具体来说，我们将使用样本复杂度作为中间桥梁，对隐私、效用和效率进行统一的量化，使得三者都在相同的维度空间上进行度量，此时，多个目标的解将在相同的共享空间中取得，从而将多目标优化问题转化为单目标优化问题,如下面公式所示。

3

研究场景1：防守者训练流 

本文是在横向联邦场景下进行分析讨论，如下图所示，其中服务端是一个半诚实的（semi-honst）攻击者，而客户端则是防御者。不失一般性，我们假设当前处在第 轮迭代中，系统将按下面的步骤进行训练：

步骤一：服务端向所有客户端发送最新的全局模型 ，客户端接收到 后，对其进行解密操作： 。

步骤二：利用本地数据，客户端单独进行本地模型训练。以第 个客户端为例，得到更新后的本地模型参数为  ：

步骤三：第个客户端上传更新的梯度到服务端中，为了保护梯度信息，上传的梯度将添加扭曲信息  ：

步骤四：服务端接收到所有客户端上传的扭曲梯度后，进行梯度聚合，更新全局模型参数，得到新的全局模型参数为  ：

4

研究场景2：攻击者威胁模型

我们考虑服务端是一个半诚实的攻击者，即：它将遵循联邦学习的协议进行训练，但另一方面，它对中间结果数据感兴趣，试图从这些中间数据中，推导出客户端的隐私信息。在本文中对攻击者，我们将分析两个方面的内容：一是如何衡量攻击者造成的隐私泄露；二是衡量攻击的成本。为此，攻击者将执行下面两个任务：

• 任务一：服务端对第个客户端上传的梯度 ，使用梯度攻击等攻击算法，还原出该客户端的本地数据信息。目标是还原的数据越接近于原始数据越好。 

• 任务二：利用还原的数据，训练一个分类器，目的是推导出需要多少样本量，才能使得攻击算法是PAC可学习的。

5

研究结论

该论文基于PAC学习理论，以样本复杂度作为度量，给出了隐私泄露、效用损失和攻击成本的边界，如上图所示，其中： 

隐私泄露的上界：隐私泄露将以不低于  的概率,满足：

从直观上来说，上式表明样本量（）越多，模型隐私泄露的上界值就越小，即在相同的概率下，模型越难被攻击，攻击造成的隐私泄露越少。

攻击者的攻击成本：攻击者通过从上传的梯度信息中，还原原始数据，从而造成隐私泄露。为了评估其攻击效果，攻击者会利用还原的数据来重新训练一个分类器，如果分类器的效果越好，说明还原的数据质量越高，造成的隐私泄露也就越大。对于DLG攻击，当攻击者所需要的样本量 满足下式时，攻击者算法是PAC可学习的，也就是分类器的泛化误差小于 的概率不低于 （其中满足）。

效用损失的上界：则效用损失将以不低于 的概率，满足：

从直观上来说，定理1表明样本量（）越多，模型效用损失的上界值就越小，即在相同的概率下，模型能达到更好的性能。

6

总结和未来工作

在本文中，我们从PAC learning的角度，为联邦学习构建了一个统一的度量机制用以量化隐私、效用和效率。具体来说，对于保护者，我们提供了一个上界，用以衡量保护算法对模型效用损失的影响；对于攻击者，我们提供一个上界用以衡量攻击者造成的隐私泄露，并详细分析了样本量对攻击成本的影响。在此基础上，我们进一步构建出隐私、效用和效率三者权衡的关系，如：当样本的数量满足一定的条件时，我们可以确保保护机制带来的模型效用损失，将以较大的概率不会超过某一个上限值；同样地，当样本的数量满足一定的条件时，我们可以确保保护机制对隐私信息保护，能使得攻击者付出的成本远大于收益，这为保护算法的设计提供了指导意义。

7

参考资料

[1]周志华.《机器学习》. 清华大学出版社, 2016.2. 

[2]Russell S J. Artificial intelligence a modern approach[M]. Pearson Education, Inc., 2010.

[3]L. Valiant. A theory of the learnable. Communications of the ACM, 27, 1984.

本文参考：FATE开源社区

转载仅供学习参考，若有不当，请联系我们处理

END

​

往期推荐

1.一文了解零知识证明基础知识
2.利用不经意传输完成隐私集合求交3.中国密码学会及各分支机构2023年主要学术活动计划4.笔记分享 | 冯登国院士MPC讲座（2）——基于秘密分享方法的安全多方计算协议