Convergence of Byzantine-Resilient Gradient Tracking via Probabilistic Edge Dropout
Authors: Amirhossein Dezhboro, Fateme Maleki, Arman Adibi, Erfan Amini, Jose E. Ramirez-Marquez
Organizations: Department of Systems Engineering, Stevens Institute of Technology, Hoboken, NJ 07030. · Department of Industrial and Systems Engineering, Rutgers University, Piscataway, NJ 08854. · School of Computer and Cyber Sciences, Augusta University, Augusta, GA 30912. · Center for Climate Systems Research, Columbia University, Palisades, NY 10964.
We study distributed optimization over networks with Byzantine agents that may send arbitrary adversarial messages. We propose 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 τ 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 (pb=0), GT-PD converges linearly to a neighborhood determined solely by stochastic gradient variance. For partial isolation (pb>0), we introduce 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 ph=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.
Figures & tables
Figure 1: GT-PD system model. A decentralized network of N agents communicates over a graph G , where M agents are Byzantine adversaries. Honest agents (blue) exchange decision variables via reliable links (solid arrows). All edges are subject to probabilistic dropout based on a local trust score. For edges to suspected adversaries (dashed), the retention probability drops to pij→0 .
Figure 2: Test accuracy of GT-PD, GT-PD-L, CWTM, and unprotected gradient tracking under three Byzantine attacks on MNIST ( n=20 , b=4 , non-IID). GT-PD-L achieves the highest accuracy in all three settings, outperforming CWTM by 4.3 percentage points under the stealth ALIE attack.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 3: Extended diagnostics across three attacks (rows). Column (a): test accuracy. Column (b): consensus disagreement Ck on log scale. Column (c): mean retention probabilities for honest-honest ( phh , solid) and honest-Byzantine ( phb , dashed) edges. Under ALIE, the dropout layer fails to isolate Byzantine agents ( phb>phh ), yet GT-PD-L converges via the projection and leaky integrator layers.
In this paper, we study the problem of distributed training (DT) under Byzantine attacks with communication constraints. While prior work has developed various robust aggregation rules at the server to enhance robustness to Byzantine attacks, the existing methods suffer from a critical limitation in that the solution error does not diminish when the local gradients sent by different devices vary considerably, as a result of data heterogeneity among the subsets held by different devices. To overcome this limitation, we propose a novel DT method, cyclic gradient coding-based DT (LAD). In LAD, the server allocates the entire training dataset to the devices before training begins. In each iteration, it assigns computational tasks redundantly to the devices using cyclic gradient coding. Each honest device then computes local gradients on a fixed number of data subsets and encodes the local gradients before transmitting to the server. The server aggregates the coded vectors from the honest devices and the potentially incorrect messages from Byzantine devices using a robust aggregation rule. Leveraging the redundancy of computation across devices, the convergence performance of LAD is analytically characterized, demonstrating improved robustness against Byzantine attacks and significantly lower solution error. Furthermore, we extend LAD to a communication-efficient variant, compressive and cyclic gradient coding-based DT (Com-LAD), which further reduces communication overhead under constrained settings. Numerical results validate the effectiveness of the proposed methods in enhancing both Byzantine resilience and communication efficiency.
Chengxi Li, Youssef Allouah, Rachid Guerraoui +2
Division of Information Science and Engineering, School of Electrical Engineering and Computer Science, KTH Royal Institute of Technology, 10044 Stockholm, Sweden · Stanford University, CA 94305, United States · School of Computer and Communication Sciences, the Swiss Federal Institute of Technology in Lausanne (EPFL), 1015 Lausanne, Switzerland
We consider distributed optimization under Byzantine attacks in the presence of (L0,L1)-smoothness, a generalization of standard L-smoothness that captures functions with state-dependent gradient Lipschitz constants. We propose Byz-NSGDM, a normalized stochastic gradient descent method with momentum that achieves robustness against Byzantine workers while maintaining convergence guarantees. Our algorithm combines momentum normalization with Byzantine-robust aggregation enhanced by Nearest Neighbor Mixing (NNM) to handle both the challenges posed by (L0,L1)-smoothness and Byzantine adversaries. We prove that Byz-NSGDM achieves a convergence rate of O(K−1/4) up to a Byzantine bias floor proportional to the robustness coefficient and gradient heterogeneity. Experimental validation on heterogeneous MNIST classification, synthetic (L0,L1)-smooth optimization, and character-level language modeling with a small GPT model demonstrates the effectiveness of our approach against various Byzantine attack strategies. An ablation study further shows that Byz-NSGDM is robust across a wide range of momentum and learning rate choices.
Arman Bolatov, Samuel Horváth, Martin Takáč +1
Mohamed bin Zayed University of Artificial Intelligence, UAE
Byzantine-robust distributed optimization relies on robust aggregation rules to mitigate the influence of malicious Byzantine workers. Despite the proliferation of such rules, a unified convergence analysis framework that accommodates general data heterogeneity is lacking. In this work, we provide a thorough convergence theory of Byzantine-robust distributed stochastic gradient descent (SGD), analyzing variants both with and without local momentum. We establish the convergence rates for nonconvex smooth objectives and those satisfying the Polyak-Lojasiewicz condition under a general data heterogeneity assumption. Our analysis reveals that while stochasticity and data heterogeneity introduce unavoidable error floors, local momentum provably reduces the error component induced by stochasticity. Furthermore, we derive matching lower bounds to demonstrate that the upper bounds obtained in our analysis are tight and characterize the fundamental limits of Byzantine resilience under stochasticity and data heterogeneity. Empirical results support our theoretical findings.
Boyuan Ruan, Xiaoyu Wang, Ya-Feng Liu
School of Advanced Interdisciplinary Sciences, University of Chinese Academy of Sciences, Beijing 100049, China · School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China · Ministry of Education Key Laboratory of Mathematics and Information Networks, School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing 102206, China