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

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

cs.LGMar 12, 2026

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

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

Organizations: Mohamed bin Zayed University of Artificial Intelligence, UAE

Abstract

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.

Figures & tables

v_{i}^{k}=\begin{cases}(1-\eta_{k-1})v_{i}^{k-1}+\eta_{k-1}\nabla f_{\xi_{i}^{k-1}}(x^{k-1}),&i\in\mathcal{G}\\ \text{arbitrary }\tilde{v}_{i}^{k}\in\mathbb{R}^{d},&i\in\mathcal{B}\end{cases}

Algorithm 1 Byz-NSGDM

		MNIST (Acc. %)			Synthetic ( $\\|\nabla f\\|\times 10^{-6}$ )			LM (Perplexity)
Attack	Agg.	Base	Decay	Ours	Base	Decay	Ours	Base	Decay	Ours
BF	RFA	$78.6{\scriptstyle\pm 4.0}$	$84.1{\scriptstyle\pm 0.2}$	$\mathbf{86.0{\scriptstyle\pm 0.2}}$	$12.8{\scriptstyle\pm 1.2}$	$38.2{\scriptstyle\pm 32.5}$	$\mathbf{7.3{\scriptstyle\pm 0.4}}$	$11.64{\scriptstyle\pm 0.02}$	$12.28{\scriptstyle\pm 0.09}$	$\mathbf{10.22{\scriptstyle\pm 0.13}}$
	Krum	$76.5{\scriptstyle\pm 11.7}$	$81.8{\scriptstyle\pm 0.3}$	$\mathbf{86.0{\scriptstyle\pm 0.1}}$	$14.0{\scriptstyle\pm 2.0}$	$84.5{\scriptstyle\pm 9.8}$	$\mathbf{7.0{\scriptstyle\pm 0.5}}$	$11.68{\scriptstyle\pm 0.04}$	$12.31{\scriptstyle\pm 0.08}$	$\mathbf{10.34{\scriptstyle\pm 0.05}}$
	CM	$78.8{\scriptstyle\pm 4.2}$	$81.8{\scriptstyle\pm 0.3}$	$\mathbf{86.1{\scriptstyle\pm 0.1}}$	$13.0{\scriptstyle\pm 1.0}$	$64.1{\scriptstyle\pm 10.6}$	$\mathbf{7.7{\scriptstyle\pm 0.6}}$	$11.66{\scriptstyle\pm 0.02}$	$12.35{\scriptstyle\pm 0.14}$	$\mathbf{10.34{\scriptstyle\pm 0.06}}$
LF	RFA	$91.9{\scriptstyle\pm 4.6}$	$\mathbf{95.2{\scriptstyle\pm 4.6}}$	$92.2{\scriptstyle\pm 4.5}$	–	–	–	–	–	–
	Krum	$\mathbf{91.9{\scriptstyle\pm 4.6}}$	$88.8{\scriptstyle\pm 0.0}$	$89.1{\scriptstyle\pm 0.0}$	–	–	–	–	–	–

Table 1: Experimental results across all tasks. MNIST: test accuracy (%,

\uparrow

); Synthetic: gradient norm (

\times 10^{-6}

\downarrow

); LM: validation perplexity (

\downarrow

). Mean

\pm

std over 3 seeds. Best in bold .

Figure 1: Ablation study on heterogeneous MNIST under Bit Flipping attack with RFA aggregation. (a) Final test accuracy heatmap across momentum ( $\beta$ ) and learning rate ( $\gamma_{0}$ ). (b) Training curves for each momentum value using its best learning rate. (c) Final accuracy vs momentum for different learning rates.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2: Test accuracy curves on heterogeneous MNIST under Byzantine attacks. Each row corresponds to a different attack (BF, LF, Mimic), and each column to a different aggregator (RFA, Krum, CM). Lines show mean accuracy over 3 seeds with shaded regions indicating $\pm 1$ standard deviation.

Figure 3: Gradient norm evolution (log scale) for synthetic $(L_{0},L_{1})$ -smooth optimization under Byzantine attacks. Each row shows a different attack (BF, Mimic, ALIE), and each column a different aggregator (RFA, Krum, CM). Lines show mean gradient norm over 3 seeds with shaded regions indicating $\pm 1$ standard deviation. Legend includes tuned learning rates.

Figure 4: Validation perplexity (log scale) on Shakespeare character-level language modeling under Byzantine attacks. Each row shows a different attack (BF, Mimic, ALIE), and each column a different aggregator (RFA, Krum, CM).

Distributed Optimization

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

See all 92 papers

Byzantine-Robust Distributed SGD: A Unified Analysis and Tight Error Bounds
Apr 11, 2026Boyuan Ruan, Xiaoyu Wang, Ya-Feng LiuDistributed Optimization Fault-Tolerant Distributed Training
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
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
Byzantine-Robust and Differentially Private Federated Optimization under Weaker Assumptions
Mar 24, 2026Rustem Islamov, Grigory Malinovsky, Alexander Gaponov +3Byzantine-Robust Federated Learning Differentially Private Federated Learning
University of Basel, Switzerland · KAUST, Saudi Arabia · MBZUAI, UAE

Apr 11, 2026J/K move · Enter open · S save

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

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

Distributed Optimization Fault-Tolerant Distributed Training Stochastic Gradient Descent Nonconvex Stochastic Optimization

Open paper AskPDF arXiv

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.

Abstract

Distributed Optimization

Explore similar work

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

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

Byzantine-Robust and Differentially Private Federated Optimization under Weaker Assumptions