Byzantine-Robust and Differentially Private Federated Optimization under Weaker Assumptions

Rustem Islamov; Grigory Malinovsky; Alexander Gaponov; Aurelien Lucchi; Peter Richtárik; Eduard Gorbunov

cs.LGMar 24, 2026

Byzantine-Robust and Differentially Private Federated Optimization under Weaker Assumptions

Authors: Rustem Islamov, Grigory Malinovsky, Alexander Gaponov, Aurelien Lucchi, Peter Richtárik, Eduard Gorbunov

Organizations: University of Basel, Switzerland · KAUST, Saudi Arabia · MBZUAI, UAE

Abstract

Federated Learning (FL) enables heterogeneous clients to collaboratively train a shared model without centralizing their raw data, offering an inherent level of privacy. However, gradients and model updates can still leak sensitive information, while malicious servers may mount adversarial attacks such as Byzantine manipulation. These vulnerabilities highlight the need to address differential privacy (DP) and Byzantine robustness within a unified framework. Existing approaches, however, often rely on unrealistic assumptions such as bounded gradients, require auxiliary server-side datasets, or fail to provide convergence guarantees. We address these limitations by proposing Byz-Clip21-SGD2M, a new algorithm that integrates robust aggregation with double momentum and carefully designed clipping. We prove high-probability convergence guarantees under standard $L$ -smoothness and $σ$ -sub-Gaussian gradient noise assumptions, thereby relaxing conditions that dominate prior work. Our analysis recovers state-of-the-art convergence rates in the absence of adversaries and improves utility guarantees under Byzantine and DP settings. Empirical evaluations on CNN and MLP models trained on MNIST further validate the effectiveness of our approach.

Figures & tables

Method	Utility	DP	BR	Assumptions	Additional Comments	Type
SoteriaFL ( Liu et al., 2022 )	$\widetilde{\mathcal{O}}\left(\frac{\sqrt{d}}{\sqrt{G}\varepsilon}\right)$	✓	✗	$M$ -bounded gradients	nCVX, local DP	E
$\alpha$ -Norm ( Shulgin et al., 2025a )	$\widetilde{\mathcal{O}}\left(\frac{\sqrt{d}}{\sqrt{G}\varepsilon}+R\right)^{(a)}$	✓	✗	$L$ -smoothness Full-batch gradients	nCVX, local DP	E
Clip21-SGD2M ( Islamov et al., 2025b )	$\widetilde{\mathcal{O}}\left(\frac{\sqrt{d}}{\sqrt{G}\varepsilon}\right)^{(b)}$	✓	✗	$L$ -smoothness $\sigma$ -sub-Gaussian noise	nCVX, local DP	P
Byz-SGDM ( Karimireddy et al., 2020 )	$\widetilde{\mathcal{O}}\left(\delta_{\rm byz}\zeta^{2}\right)^{(c)}$	✗	✓	$L$ -smoothness Bounded variance	nCVX	E
Robust D-SHB ( Allouah et al., 2023a )	$\widetilde{\mathcal{O}}\left(\delta_{\rm byz}M^{2}\right)$	✗	✓	$L$ -smoothness Full-batch gradients	nCVX CVX	E
Byz-VR-MARINA ( Gorbunov et al., 2022b )	$\widetilde{\mathcal{O}}\left(\delta_{\rm byz}\zeta^{2}\right)$	✗	✓	$L$ -smoothness Local functions are finite-sums	nCVX	E

Table 1: Convergence guarantees of algorithms in the presence of Byzantine and/or DP adversaries.

\widetilde{\mathcal{O}}

hides logarithmic and decaying-with-

T

terms. Notation: (s)CVX=(strongly) convex functions, nCVX=non-convex functions, DP=supports differential privacy, BR=supports Byzantine robustness, E=In-Expectation analysis, P=High-probability analysis.

Figure 1: Performance of Byz-Clip21-SGD2M , Byz-Clip-SGD ( Algorithm 3 ), and Safe-DSHB ( Algorithm 4 ) when training CNN (top line) and MLP (bottom line) models on the MNIST dataset for different numbers of Byzantine clients and privacy budgets, when Byzantine clients use IPM attack.

Figure 2: Performance of Byz-Clip21-SGD2M , Byz-Clip-SGD ( Algorithm 3 ), and Safe-DSHB ( Algorithm 4 ) when training CNN (top line) and MLP (bottom line) models on the MNIST dataset for different numbers of Byzantine clients and privacy budgets, when Byzantine clients use label flipping attack.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Definition	Meaning	Reference
$n$	–	Number of all clients	Section 3
$x$	–	Model parameters	Section 3
$d$	–	Number of model parameters	Section 3
$\mathcal{G}$	–	Set of regular clients	Section 3
$G$	–	Number of regular clients	Section 3
$\mathcal{B}$	–	Set of Byzantine clients	Section 3

Appendix

Table A.1 : Summary of notation used in the paper, including convergence proofs.

Figure 5

Figure F.1 : Performance of Byz-Clip21-SGD2M+ , Byz-Clip-SGD , and Safe-DSHB when training CNN (top line) and MLP (bottom line) models on the MNIST dataset for different numbers of Byzantine clients and privacy budgets, when Byzantine clients use a label flipping attack, when amplification by sub-sampling is done.

Byzantine-Robust Federated Learning

Byzantine-robust federated learning protects collaboratively trained models from clients that send corrupted, poisoned, or strategically manipulated updates.

See all 84 papers

A Byzantine-Robust Federated Learning with Nesterov Momentum
Nov 4, 2025Lihan Xu, Xiaoyi Fan, Gang Wang +3Federated Learning Aggregation Byzantine-Robust Federated Learning
School of Cyber Science and Engineering, Xi’an Jiaotong University, Xi’an 710049, China. · the Artificial Intelligence Research Institute and Guangdong-Hong Kong-Macao Joint Laboratory for Emotional Intelligence and Pervasive Computing, Shenzhen MSU-BIT University, Shenzhen 518172, China. · the State Key Laboratory of Autonomous Intelligent Unmanned Systems, Beijing Institute of Technology, Beijing 100081, China.
Byzantine-Robust Aggregation for Securing Decentralized Federated Learning
Sep 26, 2024Diego Cajaraville-Aboy, Ana Fernández-Vilas, Rebeca P. Díaz-Redondo +1Federated Learning Aggregation Byzantine-Robust Federated Learning
atlanTTic Research Center – ICLAB – Universidade de Vigo, Vigo, 36310, Spain
An Adaptive Differentially Private Federated Learning Framework
Feb 6, 2026Jin Wang, Hui Ma, Yajun Zhang +4Non-IID Federated Learning Differentially Private Federated Learning
Xinjiang Key Laboratory of Intelligent Computing and Smart Applications, School of Software, Xinjiang University, Urumqi 830017, China · College of Geography and Remote Sensing Sciences, Xinjiang University, Urumqi, China · Jilin University, Changchun 130012, China

Nov 4, 2025J/K move · Enter open · S save

A Byzantine-Robust Federated Learning with Nesterov Momentum

Lihan Xu, Xiaoyi Fan, Gang Wang, Runhao Zeng+2

School of Cyber Science and Engineering, Xi’an Jiaotong University, Xi’an 710049, China. · the Artificial Intelligence Research Institute and Guangdong-Hong Kong-Macao Joint Laboratory for Emotional Intelligence and Pervasive Computing, Shenzhen MSU-BIT University, Shenzhen 518172, China. · the State Key Laboratory of Autonomous Intelligent Unmanned Systems, Beijing Institute of Technology, Beijing 100081, China.

Federated Learning Aggregation Byzantine-Robust Federated Learning Communication-Efficient Distributed Training Gradient Descent Federated Learning

Open paper AskPDF arXiv

We investigate robust federated learning, where a group of workers collaboratively train a shared model under the orchestration of a central server in the presence of Byzantine adversaries capable of arbitrary and potentially malicious behaviors. To improve communication efficiency while retaining resilience against such adversaries, we propose a Byzantine-resilient Nesterov-augmented federated learning (Byrd-NAFL) algorithm. Byrd-NAFL applies Nesterov's momentum at the server to the output of any soft

γ

-Byzantine resilient aggregation rule, while each worker only computes and uploads a stochastic gradient, which keeps the workers stateless, as desired for intermittently participating Internet of Things devices. For smooth non-convex losses, we establish a finite-time convergence guarantee for all momentum factors

β\in[0,1)

without requiring the aggregated gradient to be unbiased or bounded; the bound reduces to that of Byzantine-resilient stochastic gradient descent at

β=0

and is tighter than that of server-side heavy-ball momentum. Experiments on MNIST, CIFAR-10, and Sentiment140 show that Byrd-NAFL converges faster and attains higher accuracy than existing benchmarks in most i.i.d. and non-i.i.d. setups under diverse attacks, while its resilience is bounded by that of the underlying aggregation rule.

Abstract

Byzantine-Robust Federated Learning

Explore similar work

A Byzantine-Robust Federated Learning with Nesterov Momentum

Byzantine-Robust Aggregation for Securing Decentralized Federated Learning

An Adaptive Differentially Private Federated Learning Framework