在量子退火器上通过基于QUBO的客户端选择的拜占庭鲁棒联邦学习

# 基于量子退火器上 QUBO 客户端选择的拜占庭弹性联邦学习 来源：https://arxiv.org/html/2605.16438 ###### 摘要 联邦学习 (FL) 是一种成熟的分布式训练全局模型的方法，能够在保护本地数据隐私的同时，消除对大型集中式基础设施的需求。大规模部署的 FL 存在恶意更新的风险，可能影响全局模型。为了减轻此类风险，人们引入了多种拜占庭弹性聚合方法，其中最流行的方法之一是 MultiKrum。虽然该方法通过比较各个梯度与其最近邻的距离来评分，但它很容易遗漏那些保留了诚实更新统计特性的恶意更新。为了解决这些问题，我们提出了一种量子退火方法，将客户端选择重新表述为二次无约束二元优化 (QUBO) 问题，将成对距离编码为由量子退火器 (QA) 求解的成本函数中。与 MultiKrum 贪心的逐客户端评分不同，QUBO 公式在所有可能的客户端子集上进行联合优化，以找到相互最接近的 m 个客户端组。我们在 15 个客户端的小规模实验中对最具挑战性的拜占庭攻击取得了有希望的结果。例如，针对 Advanced LIE 攻击，在 MNIST 训练模型上，QUBO 的检测准确率为 95.11%，而经典 MultiKrum 为 81.33%；在 CIFAR-10 上分别为 97.78% 和 75.56%。尽管我们的 QUBO 方法在应对复杂攻击时表现良好，但在处理简单攻击时效果不佳，而经典 MultiKrum 对此类攻击处理得很好。我们的实验表明这两种方法能够很好地互补。此外，随着客户端数量的增加，QUBO 方法的质量会下降。为了解决这些缺点，我们引入了一种 MultiSignal 集成方法，该方法使用基于欧几里得和余弦 Krum 分数差距的双特征路由门，将攻击分为四种模式，并将规避攻击路由到带有同意投票的怀疑惩罚 QUBO。MultiSignal 集成方法在我们所有的实验中表现均优于经典 MultiKrum，平均检测准确率为 95.3%，而经典方法为 91.8%。最大的提升体现在 Sparse Lie 上，检测准确率从 72.0% 提高到 95.2%，提升了 23.2 个百分点；以及 Advanced Lie，从 80.4% 提高到 85.2%，提升了 4.8 个百分点。这些结果表明，结合 MultiSignal 集成的基于 QUBO 的量子退火是一种针对联邦学习中最具挑战性的拜占庭策略的原理性且可扩展的防御方法。 ## I. 引言 联邦学习 (FL) [14, 8, 22] 通过让客户端（节点）训练模型的本地副本并将梯度更新转发到中央服务器来实现全局模型的训练，中央服务器随后聚合这些更新并将全局模型分发给客户端进行下一轮训练。这种方法促进了本地数据的隐私保护，并消除了对大型中央基础设施的需求。然而，当客户端不可信时，拜占庭更新的风险可能会危及全局模型的收敛 [3]。现有的最先进技术 Krum 算法 [3] 依赖于计算梯度之间的成对欧几里得距离，并选择与大多数梯度最接近的单个梯度。MultiKrum [3] 将此方法扩展为选择多个客户端。这两种方法都无法检测更复杂的攻击，例如"A Little Is Enough" (Lie) 攻击家族 [2]，这些攻击在保持更新统计特性的同时恶意篡改梯度。为了解决这些问题，我们建议将拜占庭客户端检测表述为一个组合优化问题，并通过量子退火来求解。为此，我们将客户端选择目标编码为一个二次无约束二元优化 (QUBO) [9] 问题。这种公式能够对所有 \(\binom{n}{m}\) 个可能的子集进行*全局*优化，这种搜索对于经典穷举方法来说是难以处理的，但自然适合量子退火器 (QA) [1]。我们做出了三项贡献。首先，我们将 MultiKrum 客户端选择问题表述为一个 QUBO 表达式，并带有一个拉格朗日惩罚项以确保恰好选择 m 个客户端。我们在小规模实验中，针对 MNIST [11]、FashionMNIST [20] 和 CIFAR-10 [10] 数据上的 13 种不同的拜占庭攻击类型，使用了 15 个客户端，结果表明基于 QUBO 的选择在检测规避类攻击方面优于经典的 MultiKrum 拜占庭更新检测。其次，我们针对 100 个客户端的大规模实例引入了一种基于阈值的级联双 QUBO 方法，因为此时标准 QUBO 的性能开始下降。该方法在检测 Advanced Lie (ALIE) 攻击方面的准确率仍然未能超过经典的 MultiKrum。第三，我们引入了一种 MultiSignal 集成方法，该方法计算欧几里得和余弦分数，构建四种模式，并将处理路由到经典 MultiKrum 或带有同意投票的怀疑惩罚 QUBO。在 MNIST 上使用 100 个客户端时，MultiSignal 集成方法达到了 95.3% 的平均检测准确率，而经典 MultiKrum 为 91.8%，其最大提升体现在 Sparse Lie 上，提升了 23.2 个百分点，以及 ALIE 上提升了 4.8 个百分点，同时在对所有产生异常值的攻击（包括 Clustered）上保持了完美的检测。我们还提供了经典 MultiKrum、标准 QUBO、级联方法和 MultiSignal 方法的复杂度分析。这项工作补充了我们之前关于基于量子嵌入的拜占庭检测的研究 [7]，该研究使用参数化量子电路进行梯度特征提取。虽然量子嵌入方法利用希尔伯特空间表示，但当前工作是在量子退火的优化范式内进行的，为鲁棒聚合提供了一种根本不同且互补的机制。 ## II. 相关工作 Krum [3] 选择其欧几里得距离最接近其他梯度的梯度。MultiKrum [5] 将选择扩展到 m 个客户端。论文 [23] 使用了按坐标的中位数和修剪均值估计器。DRACO [4] 使用冗余梯度计算来实现弹性。FLAME [15] 使用基于余弦的聚类进行后门防御，Sentinel [6] 结合了余弦相似度过滤与自助法损失验证和归一化，CosDefense [21] 通过方向相似性检测异常值。Dim-Krum [25] 将 Krum 按维度应用于 NLP 任务。所有这些经典解决方案都执行局部或逐维度优化，而不是全局子集选择。Wei 等人 [17] 使用 Bender 分解框架来优化分布式网络中的 FL 调度。同一作者还在 [18] 中将量子退火应用于 FL 资源调度。Liu 等人 [12] 提出了一种用于基于区块链的联邦学习的量子拜占庭协议。Zhang 等人 [24] 使用量子密钥分发来保护梯度更新。论文 [19] 处理了拜占庭参与者发送随机或恶意构造的酉矩阵的场景。Subramanian 和 Chinnadurai [16] 研究了混合量子经典模型在面对对抗性更新时的鲁棒性优势。在我们之前的工作 [7] 中，我们提出使用参数化量子电路（泡利特征映射）将投影梯度嵌入到量子希尔伯特空间中，其中内积产生用于拜占庭检测的量子核矩阵。我们展示了通过特征映射进行降维然后投影到希尔伯特空间，可以改进拜占庭更新的检测。 ## III. 背景 ### III-A. 联邦学习 在 FL [14] 中，n 个客户端在中央服务器的协调下协作训练一个由 W 参数化的全局模型。在每一轮 t 中，服务器将当前模型 \(W_t\) 广播给所有客户端。每个客户端 i 在其私有数据上本地训练，并返回梯度更新 \(G_i = W_i' - W_t\)。服务器聚合这些更新并生成 \(W_{t+1}\)。假设中央服务器接收到的 n 个客户端中有 f 个是拜占庭客户端，目标是生成一个接近 100% 诚实聚合的全局模型。 ### III-B. Krum 和 MultiKrum 令 \(G_1, G_2, ..., G_n \in \mathbb{R}^d\) 为梯度向量。两个梯度之间的距离为： \[ D(G_i, G_j) = \|G_i - G_j\|_2. \tag{1} \] 对于每个更新，Krum 定义为与其最近的 \(n-f-2\) 个邻居的距离之和，即： \[ \text{KRUM}(G_i) = \sum_{j \in \mathcal{N}_i} \|G_i - G_j\|_2^2, \tag{2} \] 其中 \(\mathcal{N}_i\) 是距离 \(G_i\) 最近的 \(n-f-2\) 个梯度的索引集合。Krum 选择： \[ G_{\text{krum}} = \arg\min_i \text{KRUM}(G_i). \] MultiKrum 方法通过选择 Krum 分数最低的 m 个梯度并对其求平均来推广 Krum，如下所示： \[ G_{\text{multi}} = \frac{1}{m} \sum_{i \in \mathcal{M}} G_i, \quad \mathcal{M} = \text{Top-}m\{\text{KRUM}(G_i)\}. \tag{3} \] 值得注意的是，MultiKrum 并不在子集上进行联合优化。任何靠近其邻居的单个拜占庭梯度都将逃避检测。 ### III-C. 量子退火和 QUBO 量子退火器 (QA) [1] 非常适合表示为 QUBO [9] 的优化问题： \[ \min_{x \in \{0,1\}^n} \sum_i Q_{ii} x_i + \sum_{i < j} Q_{ij} x_i x_j, \tag{4} \] 其中 \(Q\) 是一个 \(n \times n\) 上三角实数矩阵。对于量子退火，\(Q\) 中的项被映射到伊辛模型哈密顿量。解向量 \(x\) 对应该问题的二进制赋值。 ## IV. 方法 ### IV-A. QUBO 客户端选择公式 我们将 MultiKrum 的联合选择重新表述为一个 QUBO 问题。主要思想是最大化所选客户端之间的总成对距离，同时通过硬约束确保恰好选择 m 个客户端。在数学上，我们求解： \[ \max_{x \in \{0,1\}^n} \sum_{i < j} D_{ij} x_i x_j \quad \text{subject to} \quad \sum_{i=1}^n x_i = m, \tag{5} \] 其中 \(D_{ij}\) 是客户端 i 和 j 的投影梯度之间的余弦距离，\(x_i = 1\) 表示客户端被选中。引入拉格朗日惩罚项 \(\lambda\) 将约束吸收到目标函数中： \[ \min_{x \in \{0,1\}^n} \left[ -\sum_{i<j} D_{ij} x_i x_j + \lambda \left( \sum_{i=1}^n x_i - m \right)^2 \right]. \tag{6} \] 展开并对 QUBO 形式重新索引后，线性系数为： \[ Q_{ii} = \lambda (1 - 2m), \tag{7} \] 二次系数为： \[ Q_{ij} = -D_{ij} + 2\lambda. \tag{8} \] 在初步实验中，我们仅在较小的客户端数量（\(\le 15\)）上测试了标准 QUBO，因为 D-Wave 退火器上的完全枚举对于 n=15 需要 32,768 个变量，是可行的。对于 n=100，完全 QUBO 需要 \(2^{100}\) 个变量，这在当前退火器上是不可行的。因此，对于 n=100，我们采用了不同的输入。关于输入：QUBO 求解的是编码在一个 \(n \times n\) 矩阵中的问题。虽然索引的数量是 \(2^n\)，但矩阵大小按 \(O(n^2)\) 增长。当我们提到完全枚举时，指的是表示空间，即所有可能的解。 ### IV-B. 投影 V. 拜占庭攻击模型 我们评估了表 I 中列出的 13 种不同的拜占庭攻击策略。令 \(\mu\) 和 \(\sigma\) 表示诚实客户端梯度的坐标均值和标准差。令 \(G_i\) 表示诚实梯度，\(\widetilde{G}\) 表示根据 \((\mu, \sigma)\) 构造的拜占庭更新。 **表 I：评估中使用的拜占庭攻击模型。** 这些攻击范围从易于检测的产生异常值的策略（如高斯噪声和缩放）到旨在规避基于距离的防御的复杂方法（如 Lie 家族和数据中毒标签翻转），提供了对鲁棒性的全面评估。