联邦学习“没有免费午餐定理”
联邦学习的安全威胁
在公众越来越注重数据隐私，相关法律和政策不断出台的背景下，为了在数据隐私的基础上进行机器学习，联邦学习技术发展迅猛，应用范围不断增加。根据数据集的性质不同，联邦学习可分为横向联邦学习，纵向联邦学习和联邦迁移学习。横向联邦学习适用于各参与方的数据集特征大体相同，样本基本不重合的情况，纵向联邦学习适用于样本有很大幅度的重合，特征基本不重合的情况，联邦迁移学习则适用于样本和特征都很少重合的情况。不论是哪种联邦学习，系统都存在多个参与方，各自持有一部分明文数据，这些明文数据本身是不泄露给其他参与方的。
联邦学习虽然不泄露明文数据，但并不代表就高枕无忧了。根据具体的联邦学习算法的不同，存在不同的攻击手段，可以起到窥视隐私数据等可能。我们只考虑半诚实模型：联邦学习各参与方在执行计算和通信的时候都遵守协议，不会任意地修改数据以达到给模型投毒的作用。在半诚实模型中，各参与方只有一种作恶方式，那就是通过参与通信的中间数据反推关于其他参与方的数据的额外信息。在这种模型下，文献已经报告过梯度反转攻击，基于输出的模型反转攻击，基于对抗生成网络（GAN）的攻击等具体的攻击手段。为了应对这些攻击，研究者提出了很多种针对性的保护手段：随机化（差分隐私）、同态加密、稀疏化（分裂学习（SL））、秘密分享等。但是，每种保护手段都会相应地降低算法的性能。所谓性能下降，就是说，比起集中式的机器学习，模型的准确度等评价指标有所下降。
鱼与熊掌不可兼得
论文信息
作者：Xiaojin Zhang, Hanlin Gu, Lixin Fan, Kai Chen, Qiang Yang
标题：No Free Lunch Theorem for Security and Utility in Federated Learning
链接：https://arxiv.org/abs/2203.05816
研究的一般框架
专注于横向联邦学习问题。存在一个服务器和多个客户端。客户端负责根据自身数据计算本地模型参数，服务器负责聚合参数并下发给客户端。
具体算法为：
各客户端根据各自的隐私数据计算出本地的模型信息。
各客户端采取某种保护手段，把模型信息加以保护。
各客户端把受保护的模型信息上传到服务器。服务器将其聚合为全局模型。
各客户端下载全局模型，用以更新本地模型。回到1.
（上图中，左边展示联邦学习的上述四个步骤。右边展示隐私泄露的原因：敌手可能通过受保护的模型信息反推出隐私信息 以及，保护算法会带来模型精度和效用的损失。）
在这个框架下，任何隐私泄露的来源都可以归结为，保护后的模型信息（图中的）可反推出原始隐私信息的后验分布。保护越严格，这个后验分布和先验分布越接近，隐私信息泄露风险越低。但是保护会导致模型效用的损失。这个损失即未保护的模型的效用与受保护的模型的效用的差。
定义（贝叶斯推理攻击）：设在受保护变量确定的情况下，隐私变量具有后验密度函数 那么用最大似然法可以得到隐私变量最可能的值 这就是贝叶斯推理攻击。我们要求上述攻击算法必须在多项式时间内完成。
多种具体的攻击手法都是以上定义的特例：梯度反转攻击、模型反转攻击、穷举攻击等。
接下来，我们定义贝叶斯推理攻击威胁大小的量度，即贝叶斯隐私泄露。
定义（贝叶斯隐私泄露）：设在得到受保护信息W_k^D和未得到任何信息的情况下，攻击者相信的客户端k的隐私变量分布函数分别为 则我们把 称为客户端的贝叶斯隐私泄露。把平均值称为整个联邦学习模型的贝叶斯隐私泄露。其中，JS是琴生-香农散度（Jensen-Shannon divergence），它衡量了两个分布的差别大小。选择JS散度而非KL散度的原因是，JS散度具有对称性，而且其平方根满足三角不等式，方便后续的证明。
接下来，我们利用一个合适的效用函数来给出效用损失的定义。
定义（效用损失）：设使用未保护的信息的情况下，得到的模型参数分布为 使用受保护的信息的情况下，得到的模型分布为 模型效用函数为 则单个客户端的效用损失定义为 其平均值就是整个联邦学习系统的效用损失
效用函数取决于具体的联邦学习任务，例如分类问题可以选取分类准确率为效用函数，回归问题可以选取预测准确率为效用函数。效用函数的选取在一定范围内是自由的。效用函数在一个分布上取值，就是对各点取值的期望。
没有免费午餐（NFL）定理
NFL定理：在某种连续性假设（论文假设4.1）下，我们有不等式其中， 是完全不进行保护的情况下的贝叶斯隐私泄露，它只与数据集有关，和信息保护手段无关。而是和数据集、保护手段、效用函数相关的常数。这个定理揭示了隐私性和效用的权衡。在一定范围内，要加强一个就必须牺牲另一个。
证明思路
使用JS散度的平方根的三角不等式证明。先验信念和真实信念的差距，不超过它们各自和后验信念的差距之和。
如图，我们使用JS散度的三角不等式证明定理。三角形顶端是对隐私信息分布的后验信念，也就是在知道模型信息后的信念，左边是先验信念，也就是在知道模型信息前的信念，右边是真实信念，也就是真实的数据分布。贝叶斯信息泄露就是后验信念和先验信念之差，即三角形的左边长。右边长是后验信念和真实信念之差，可以证明它不超过效用损失与常数的乘积。底边长是一个只与数据本身和先验信念有关，和联邦学习过程无关的常数。
具体应用
NFL定理可以对各种具体的保护算法找到相应的参数边界。
对于随机化算法，有以下不等式：
其中是客户端的个数，为随机化算法涉及的高斯噪声参数。
对于稀疏算法，有以下公式：
其中是只与稀疏算法参数有关且易于计算的常数。
对于同态加密算法，有以下公式：
注意到，这种算法只有效用损失，但没有隐私泄露。这是因为，同态加密算法是语义安全的。
贝叶斯隐私（BP）和之前研究的比较
本文提出的隐私模型称为贝叶斯隐私（BP）。
和差分隐私DP及其变种BDP等相比：本文提出的贝叶斯隐私模型，是第一个能够同时处理随机化（差分隐私及其变种）和同态加密两种保护手段的模型，且给出了清晰的NFL定理表明隐私性和效用的权衡。
和信息隐私IP相比：本文提出的模型适用于联邦学习，而IP是否适用于联邦学习还没有研究证实。
后续研究课题
我们已经给出了隐私性和效用的权衡的边界，这可以指导我们对具体保护算法构造最优的参数。但是，效率，即通讯、计算和存储的开销，也是一个很重要的问题，特别是在同态加密方面，目前仍然欠缺高效算法。是否可以把效率问题考虑进去，得到一个升级版的NFL定理，即隐私性-效用-效率三个变量之间的权衡的边界？