13.4.1. 基于LDP的安全聚合¶

差分隐私（differential privacy）是一种保护用户数据隐私的机制。差分隐私定义为：

对于两个差别只有一条记录的数据集D,D′，通过随机算法K，输出结果为集合S子集的概率满足上面公式。ϵ为差分隐私预算，δ扰动，ϵ和δ越小，说明K在D和D′上输出的数据分布越接近。

在联邦学习中，假设FL-Client本地训练之后的模型权重矩阵是W，由于模型在训练过程中会“记住”训练集的特征，所以敌手可以借助W还原出用户的训练数据集。

MindSpore Federated Learning提供基于本地差分隐私的安全聚合算法，防止本地模型的权重上云时泄露隐私数据。

FL-Client会生成一个与本地模型权重W相同维度的差分噪声矩阵G，然后将二者相加，得到一个满足差分隐私定义的权重Wp:

FL-Client将加噪后的模型权重Wp上传至云侧FL-Server进行联邦聚合。噪声矩阵G相当于给原模型加上了一层掩码，在降低模型泄露敏感数据风险的同时，也会影响模型训练的收敛性。如何在模型隐私性和可用性之间取得更好的平衡，仍然是一个值得研究的问题。实验表明，当参与方的数量n足够大时（一般指1000以上），大部分噪声能够相互抵消，本地差分机制对聚合模型的精度和收敛性没有明显影响。

13.4.2. 基于MPC的安全聚合¶

尽管差分隐私技术可以适当保护用户数据隐私，但是当参与FL-Client数量比较少或者高斯噪声幅值较大时，模型精度会受较大影响。为了同时满足模型保护和模型收敛这两个要求，MindSpore Federated Learning提供了基于MPC的安全聚合方案。

在这种训练模式下，假设参与的FL-Client集合为U，对于任意FL-Client u和v， 它们会两两协商出一对随机扰动puv、pvu，满足

于是每个FL-Client u 在上传模型权重至FL-Server前，会在原模型权重xu加上它与其它用户协商的扰动：

从而FL-Server聚合结果x―为：

上面的过程只是介绍了聚合算法的主要思想，基于MPC的聚合方案是精度无损的，代价是通讯轮次的增加。

13.4.3. 基于LDP-SignDS算法的安全聚合¶

对于先前的基于维度加噪的LDP算法，在隐私预算一定时，添加到每个维度的噪声规模基本上与模型参数的数量成正比。因此，对于高维模型，可能需要非常多的参与方来减轻噪音对模型收敛的影响。为了解决上述“维度依赖”问题，MindSpore Federated Learning进一步提供了基于维度选择的Sign-based Dimension Selection (SignDS) [Jiang et al., 2022]算法，进一步提升模型可用性。这里，我们考虑客户端仅上传本地模型更新（即本地模型和全局模型权重差值）的场景。SignDS算法的主要思想是，对于每一条真实的本地更新Δ∈Rd，用户端首先选择一小部分更新最明显的维度构建topk集合Sk，并以此选择一个维度集合J返回给服务器。服务器根据维度集合J构建一条对应的稀疏更新Δ′，并聚合所有稀疏更新进用于更新全局模型。由于本地模型更新与本地数据信息相关联，直接选取真实的最大更新维度可能导致隐私泄露。对此，SignDS算法在两方面实现了隐私保证。一方面，算法使用了一种基于指数机制（Exponential Mechanism， EM [McSherry & Talwar, 2007]）的维度选择算法EM-MDS，使得所选维度集满足严格的ϵ-LDP保证；另一方面，在构建稀疏更新时，对所选维度分配一个常量值而不直接使用实际更新值，以保证稀疏更新和本地数据不再直接关联。由于维度选择满足ϵ-LDP，且分配给所选维度的更新值与本地数据无关，根据差分隐私的传递性 [Dwork & Roth, 2014]，所构建的稀疏更新同样满足ϵ-LDP保证。相较于之前基于维度加噪的LDP算法，SignDS算法可以显著提升高维模型的训练精度。同时，由于客户端只需上传一小部分的维度值而不是所有的模型权重，因此联邦学习的上行通信量也被大大降低。

下面，我们分别对topk集合Sk的构建和EM-MDS维度选择算法进行详细介绍。

首先，由于实际更新值有正负，直接给所有选定的维度分配相同的常量值可能会明显改变模型更新方向，影响模型收敛。为了解决这个问题，SignDS提出了一种基于符号的topk集合构建策略。具体来讲，算法引入了一个额外的符号变量s∈−1,1。该变量由客户端以等概率随机采样，用于确定本地更新Δ的topk集合Sk。如果s=1，我们将Δ按真实更新值排序，并将最大的k个更新维度记为Sk。我们进一步从Sk中随机选择一部分维度，并将s=1作为这些维度的更新值用以构建稀疏更新。直觉上，Sk中维度的更新值很可能大于零。因此，将s=1分配给选定的维度不会导致模型更新方向的太大差异，从而减轻了对模型精度的影响。类似的，当s=−1时，我们选取最小的k个更新维度记为Sk，并将s=−1分配给所选维度。

下面，我们进一步介绍用于维度选择的EM-MDS算法。简单来说，EM-MDS算法的目的是从输出维度域J中以一定概率P随机选择一个维度集合J∈J，不同维度集合对应的概率不同。我们假设J总共包含h个维度，其中有ν个维度属于topk集合（即|Sk∩J|=ν，且ν∈[0,h]），另外h−ν个维度属于非topk集合。直观上，ν越大，J中包含的topk维度越多，模型收敛越好。因此，我们希望给ν较大的维度集合分配更高的概率。基于这个想法，我们将评分函数定义为：

u(Sk,J)用来衡量输出维度集合J中包含的topk维度的数量是否超过某一阈值νth（νth∈[1,h]），超过则为1，否则为0。进一步，u(Sk,J)的敏感度可计算为：

注意 sensitivity对于任意一对不同的topk集合Sk和Sk′均成立。

根据以上定义，EM-MDS算法描述如下：

给定真实本地更新:math:`Deltainmathbb{R}^{d}`的topk集合:math:`S_k`和隐私预算:math:`epsilon`，输出维度集合:math:`Jinmathcal{J}`的采样概率为：

其中，:math:`nu`是:math:`J`中包含的topk维度数量，:math:`nu_{th}`是评分函数的阈值，:math:`J^prime`是任意一输出维度集合，:math:`omega_{tau}=binom{k}{tau}binom{d-k}{h-tau}`是所有包含:math:`tau`个topk维度的集合数。

我们进一步提供了EM-MDS算法的隐私证明:

对于每个客户端，给定随机采样的符号值:math:`x`，任意两个本地更新:math:`Delta`，:math:`Delta^prime`的topk集合记为:math:`S_k`和:math:`S_k^prime`，对于任意输出维度集合:math:`Jinmathcal{J}`，令:math:`nu=|S_k cap J|`, :math:`nu^prime=|S_k^prime cap J|`为:math:`J`与两组topk维度集的交集数量。根据 :eq:`emmds`，以下不等式成立：

证明EM-MDS算法满足:math:`epsilon`-LDP保证。

值得注意的是，计算 emmds需要先确定topk维度数的阈值νth。为此，我们首先推导在给定阈值νth时，任意一组输出维度集合J包含的topk维度的概率分布和期望：

这里，Ω为 emmds中P的分母部分。直觉上，E\[ν|νth\]越高，随机采样的J集合中包含的topk维度的概率就越大，从而模型效用就越好。因此，我们将E\[ν|νth\]最高时的阈值确定为目标阈值νth\*，即：

最后，我们在 图13.4.1中描述了SignDS算法的详细流程。给定本地模型更新Δ，我们首先随机采样一个符号值s并构建topk集合Sk。接下来，我们根据 threshold确定阈值νth\*并遵循 emmds定义的概率选择输出集合J。考虑到输出域J包含(dk)个可能的维度集合，以一定概率直接从J中随机采样一个组合需要很大的计算成本和空间成本。因此，我们采用了逆采样算法以提升计算效率。具体来说，我们首先从标准均匀分布中采样一个随机值β∼U(0,1)，并根据 discrete-prob中p(ν=τ|νth)的累计概率分布CDFτ确定输出维度集合中包含的topk维度数ν。最后，我们从topk集合Sk中随机选取ν个维度，从非topk集合中随机采样h−ν个维度，以构建最终的输出维度集合J。