cs.DCMar 17, 2026

Byzantine-Robust and Communication-Efficient Distributed Training: Compressive and Cyclic Gradient Coding

Authors: Chengxi Li, Youssef Allouah, Rachid Guerraoui, Mikael Skoglund, Ming Xiao

Organizations: 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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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.

Figures & tables

Figure 1: The implementation of a single iteration of LAD.
Figure 2: The error term as a function of δ\delta .
Figure 3: The error term as a function of dd .
Figure 4: The training loss as a function of number of iterations for different methods.
Figure 5: The training loss as a function of number of iterations for different methods under different values of σH\sigma_{H} . (a) σH=0\sigma_{H}=0 . (b) σH=0.1\sigma_{H}=0.1 .
Figure 6: The training loss as a function of number of iterations for different methods with compressed communication.
More in this topic

Distributed Training

Distributed training coordinates computation across multiple devices or machines to train models that exceed single-device limits.

See all 129 papers

Explore similar work

CardsList
Apr 1, 2026

Convergence of Byzantine-Resilient Gradient Tracking via Probabilistic Edge Dropout

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=0p_b=0), GT-PD converges linearly to a neighborhood determined solely by stochastic gradient variance. For partial isolation (pb>0p_b>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=1p_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.

Amirhossein Dezhboro, Fateme Maleki, Arman Adibi +2

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. +1

Decentralized OptimizationStochastic Gradient Descent
AskPDF
Mar 16, 2026

Accelerating Byzantine-Robust Distributed Learning with Compressed Communication via Double Momentum and Variance Reduction

In collaborative and distributed learning, Byzantine robustness reflects a major facet of optimization algorithms. Such distributed algorithms are often accompanied by transmitting a large number of parameters, so communication compression is essential for an effective solution. In this paper, we propose Byz-DM21, a novel Byzantine-robust and communication-efficient stochastic distributed learning algorithm. Our key innovation is a novel gradient estimator based on a double-momentum mechanism, integrating recent advancements in error feedback techniques. Using this estimator, we design both standard and accelerated algorithms that eliminate the need for large batch sizes while maintaining robustness against Byzantine workers. We prove that the Byz-DM21 algorithm has a smaller neighborhood size and converges to ε\varepsilon-stationary points in O(ε−4)\mathcal{O}(\varepsilon^{-4}) iterations. To further enhance efficiency, we introduce a distributed variant called Byz-VR-DM21, which incorporates local variance reduction at each node to progressively eliminate variance from random approximations. We show that Byz-VR-DM21 provably converges to ε\varepsilon-stationary points in O(ε−3)\mathcal{O}(\varepsilon^{-3 }) iterations. Additionally, we extend our results to the case where the functions satisfy the Polyak-Łojasiewicz condition. Finally, numerical experiments demonstrate the effectiveness of the proposed method.

Yanghao Li, Changxin Liu, Yuhao Yi

Sichuan University · East China University of Science and Technology

Distributed OptimizationCommunication-Efficient Distributed Training
AskPDF
Mar 12, 2026

Byzantine-Robust Optimization under (L0,L1)(L_0, L_1)-Smoothness

We consider distributed optimization under Byzantine attacks in the presence of (L0,L1)(L_0,L_1)-smoothness, a generalization of standard LL-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)(L_0,L_1)-smoothness and Byzantine adversaries. We prove that Byz-NSGDM achieves a convergence rate of O(K−1/4)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)(L_0,L_1)-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

Distributed OptimizationByzantine-Robust Federated LearningStochastic Gradient Descent
AskPDF