Search papers, labs, and topics across Lattice.
This paper introduces Gradient Tracking with Probabilistic Edge Dropout (GT-PD) and its variant GT-PD-L, novel stochastic gradient tracking methods designed to maintain convergence in distributed optimization settings with Byzantine agents. GT-PD employs a self-centered projection and probabilistic edge dropout based on trust scores to mitigate adversarial message perturbations while preserving the doubly stochastic mixing structure. The authors prove linear convergence to a bounded neighborhood under both complete and partial Byzantine isolation, and demonstrate superior performance against coordinate-wise trimmed mean in MNIST experiments with various attacks.
Even with Byzantine attackers sending arbitrary adversarial messages, this new gradient tracking method provably converges linearly to a small error neighborhood.
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.
