Convergence of Byzantine-Resilient Gradient Tracking via Probabilistic Edge Dropout

📄 arXiv: 2604.00449 📥 PDF

作者: Amirhossein Dezhboro, Fateme Maleki, Arman Adibi, Erfan Amini, Jose E. Ramirez-Marquez

分类: cs.LG, cs.MA, eess.SY

发布日期: 2026-04-07

💡 一句话要点

提出基于概率边丢弃的拜占庭容错梯度追踪方法，解决分布式优化中的恶意攻击问题。

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 分布式优化 拜占庭容错 梯度追踪 概率边丢弃 联邦学习

📋 核心要点

  1. 现有分布式优化方法在拜占庭攻击下鲁棒性不足，易受恶意节点发送的任意消息干扰。
  2. 提出GT-PD方法，通过自中心投影和概率边丢弃，限制对抗扰动并保持双重随机混合结构。
  3. 实验表明，GT-PD-L在多种攻击下优于传统方法，例如在隐蔽攻击下比坐标式修剪均值提升高达4.3%。

📝 摘要（中文）

本文研究了存在拜占庭代理的网络上的分布式优化问题，这些代理可能会发送任意对抗性消息。我们提出了一种具有概率边丢弃的梯度追踪方法(GT-PD)，这是一种随机梯度追踪方法，可在对抗性通信下保持梯度追踪的收敛性。GT-PD结合了两个互补的防御层：一种通用的自中心投影，将每个传入消息裁剪到接收代理周围半径为$ au$的球内；以及一种完全分散的概率丢弃规则，该规则由决策和跟踪通道中的双度量信任分数驱动。这种设计限制了对抗性扰动，同时保留了双重随机混合结构，这种结构在分散设置中的鲁棒聚合下经常丢失。在完全拜占庭隔离($p_b=0$)下，GT-PD线性收敛到仅由随机梯度方差决定的邻域。对于部分隔离($p_b>0$)，我们引入了具有概率边丢弃和泄漏积分的梯度追踪(GT-PD-L)，它使用泄漏积分器来控制由持续扰动引起的跟踪误差的累积，并实现线性收敛到由随机方差和裁剪泄漏比率决定的有界邻域。我们进一步表明，在$p_h=1$的双层丢弃下，隔离拜占庭代理不会给诚实验者的共识动态带来额外的方差。在Sign Flip、ALIE和Inner Product Manipulation攻击下，MNIST上的实验表明，在隐蔽攻击下，GT-PD-L的性能优于坐标式修剪均值，最高可达4.3个百分点。

🔬 方法详解

问题定义：论文旨在解决分布式优化过程中，由于网络中存在拜占庭节点（恶意节点）发送任意对抗性消息，导致算法收敛性下降甚至失效的问题。现有方法在鲁棒聚合时，往往会破坏双重随机混合结构，影响收敛速度和精度。

核心思路：论文的核心思路是结合自中心投影和概率边丢弃，构建一个双层防御机制。自中心投影限制了传入消息的幅度，防止恶意节点发送过大的扰动。概率边丢弃则根据信任度动态调整节点间的通信，降低恶意节点的影响。

技术框架：GT-PD方法包含以下主要模块：1) 梯度计算：每个节点计算本地梯度。2) 自中心投影：对接收到的梯度信息进行裁剪，限制其幅度。3) 概率边丢弃：根据信任度分数，以一定概率丢弃部分梯度信息。4) 梯度追踪：利用历史梯度信息，加速收敛。对于部分拜占庭隔离的情况，引入GT-PD-L方法，使用泄漏积分器来控制跟踪误差的累积。

关键创新：最重要的创新在于结合了自中心投影和概率边丢弃，在限制对抗扰动的同时，保留了双重随机混合结构。此外，GT-PD-L方法通过泄漏积分器，有效控制了由持续扰动引起的跟踪误差，提高了算法的鲁棒性。

关键设计：1) 自中心投影的半径$ au$需要根据梯度信息的幅度进行调整。2) 概率边丢弃的概率由双度量信任分数驱动，该分数综合考虑了决策通道和跟踪通道的信息。3) 泄漏积分器的泄漏率需要根据拜占庭节点的比例进行调整，以平衡跟踪误差的抑制和收敛速度。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，GT-PD-L方法在MNIST数据集上，针对Sign Flip、ALIE和Inner Product Manipulation等多种攻击，均优于传统的坐标式修剪均值方法。在隐蔽攻击下，GT-PD-L的性能提升高达4.3个百分点，证明了其在对抗恶意攻击方面的有效性。

🎯 应用场景

该研究成果可应用于联邦学习、分布式机器学习等领域，尤其是在安全性要求较高的场景下，例如金融、医疗等。通过提高分布式优化算法的拜占庭容错能力，可以有效防止恶意攻击，保障模型的安全性和可靠性，促进相关技术的广泛应用。

📄 摘要（原文）

We study distributed optimization over networks with Byzantine agents that may send arbitrary adversarial messages. We propose \emph{Gradient Tracking with Probabilistic Edge Dropout} (GT-PD), a stochastic gradient tracking method that preserves the convergence properties of gradient tracking under adversarial communication. GT-PD combines two complementary defense layers: a universal self-centered projection that clips each incoming message to a ball of radius $\tau$ around the receiving agent, and a fully decentralized probabilistic dropout rule driven by a dual-metric trust score in the decision and tracking channels. This design bounds adversarial perturbations while preserving the doubly stochastic mixing structure, a property often lost under robust aggregation in decentralized settings. Under complete Byzantine isolation ($p_b=0$), GT-PD converges linearly to a neighborhood determined solely by stochastic gradient variance. For partial isolation ($p_b>0$), we introduce \emph{Gradient Tracking with Probabilistic Edge Dropout and Leaky Integration} (GT-PD-L), which uses a leaky integrator to control the accumulation of tracking errors caused by persistent perturbations and achieves linear convergence to a bounded neighborhood determined by the stochastic variance and the clipping-to-leak ratio. We further show that under two-tier dropout with $p_h=1$, isolating Byzantine agents introduces no additional variance into the honest consensus dynamics. Experiments on MNIST under Sign Flip, ALIE, and Inner Product Manipulation attacks show that GT-PD-L outperforms coordinate-wise trimmed mean by up to 4.3 percentage points under stealth attacks.