Byzantine-Robust Distributed SGD: A Unified Analysis and Tight Error Bounds

Boyuan Ruan; Xiaoyu Wang; Ya-Feng Liu

math.OCApr 11, 2026

Byzantine-Robust Distributed SGD: A Unified Analysis and Tight Error Bounds

Authors: Boyuan Ruan, Xiaoyu Wang, Ya-Feng Liu

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

Abstract

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.

Figures & tables

Settings	Algorithm	Heterogeneity	Convergence	Reference
smooth	R-DSGD	$(G,0)$	$\mathcal{O}\left(\frac{\sigma^{2}+\Delta_{0}}{\sqrt{T}}+\kappa\sigma^{2}+\kappa G^{2}\right)$	( Guerraoui et al., 2024b )
	R-DSGD	$(G,B)$	$\mathcal{O}\biggl(\frac{\sigma^{2}+\Delta_{0}}{\sqrt{T}}+\bm{\frac{\kappa\sigma^{2}+\kappa G^{2}}{1-\kappa B^{2}}}\biggr)$	Corollary 3.2
	R-DSGD-M	$(G,0)$	$\mathcal{O}\left(\frac{(1+\kappa)\sigma^{2}+\Delta_{0}}{\sqrt{T}}+\kappa G^{2}\right)$	( Allouah et al., 2023a )
	R-DGD-M	$(G,B)$	$\mathcal{O}\left(\frac{\Delta_{0}}{T}+\frac{\kappa G^{2}}{1-\kappa B^{2}}\right)$	( Gupta et al., 2025 )
	R-DSGD-M	$(G,B)$	$\mathcal{O}\left(\frac{(1+\kappa)\sigma^{2}+\Delta_{0}}{\sqrt{T}}+\bm{\frac{\kappa G^{2}}{1-\kappa B^{2}}}\right)$	Corollary 3.5
smooth and PL	R-DSGD	$(G,0)$	$\mathcal{O}\left(\frac{(1+\kappa)\sigma^{2}+\kappa G^{2}}{T}+\frac{\kappa\sigma^{2}+\kappa G^{2}}{\mu}\right)$	( Guerraoui et al., 2024b )

Table 1: A comparison of prior work with our convergence results of R-DSGD and R-DSGD-M. Here,

\sigma^{2}

refers to the stochastic noise bound,

\mu

is the PL condition parameter, and

\Delta_{0}:=f_{\mathcal{H}}(x^{0})-f_{\mathcal{H}}^{*}

represents the initial gap on the global objective function. The bold terms indicate the Byzantine error, which we prove to be tight for the first time.

Panel of Figure 1 — Figure 1: The performance of the oracle aggregation rules when increasing $B^{2}$ under three choices of the parameter $\kappa$ : $\kappa=0.05$ (left), $\kappa=0.1$ (middle), and $\kappa=0.2$ (right).

Panel of Figure 2 — Figure 2: Performance comparison of R-DSGD (dashed lines) and R-DSGD-M (solid lines) on training MLP in the MNIST dataset using various robust aggregation rules in the absence of Byzantine attacks. Left: Settings with large batch size ( $m=64$ ) and high data heterogeneity ( $\alpha=0.1$ ). Right: Settings with small batch size ( $m=1$ ) and low data heterogeneity ( $\alpha=10$ ).

Panel of Figure 4 — Figure 4: Performance comparison of R-DSGD (dashed lines) and R-DSGD-M (solid lines) on training ResNet-20 in the CIFAR-10 dataset with various robust aggregation rules under four scenarios: no attack (top-left), label flip attack (top-right), sign flip attack (bottom-left), and “a little is enough” attack (bottom-right). All experiments use a batch size of $m=4$ and a Dirichlet distribution parameter of $\alpha=0.5$ , simulating an environment with large stochastic noise and high data heterogeneity.

Distributed Optimization

Distributed optimization coordinates computation across multiple agents or machines while balancing convergence, communication, privacy, and reliability.

See all 92 papers

Byzantine-Robust Optimization under $(L_0, L_1)$ -Smoothness
Mar 12, 2026Arman Bolatov, Samuel Horváth, Martin Takáč +1Distributed Optimization Byzantine-Robust Federated Learning
Mohamed bin Zayed University of Artificial Intelligence, UAE
Accelerating Byzantine-Robust Distributed Learning with Compressed Communication via Double Momentum and Variance Reduction
Mar 16, 2026Yanghao Li, Changxin Liu, Yuhao YiDistributed Optimization Communication-Efficient Distributed Training
Sichuan University · East China University of Science and Technology
Robustifying Asynchronous SGD via Soft Throttling
Sep 30, 2026Kaoru Otsuka, Maxime Meyer, Yuki Takezawa +2Distributed Optimization Fault-Tolerant Distributed Training
Okinawa Institute of Science and Technology · National University of Singapore · Toyota Motor Corporation +1

Mar 12, 2026J/K move · Enter open · S save

Byzantine-Robust Optimization under $(L_0, L_1)$ -Smoothness

Arman Bolatov, Samuel Horváth, Martin Takáč, Eduard Gorbunov

Mohamed bin Zayed University of Artificial Intelligence, UAE

Distributed Optimization Byzantine-Robust Federated Learning Stochastic Gradient Descent

Open paper AskPDF arXiv

We consider distributed optimization under Byzantine attacks in the presence of

(L_0,L_1)

-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

(L_0,L_1)

-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

(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.

Abstract

Distributed Optimization

Explore similar work

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

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

Robustifying Asynchronous SGD via Soft Throttling

Byzantine-Robust Optimization under $(L_0, L_1)$ -Smoothness