Centroid Approximation for Byzantine-Tolerant Federated Learning

2025/06/18 by Mélanie Cambus, Cambus, Mélanie, Darya Melnyk +5
Computer Science · Engineering · #Advanced Memory and Neural Computing #Distributed #FOS: Computer and information sciences #Machine Learning (cs.LG) #Parallel #Stochastic Gradient Optimization Techniques #Wireless Communication Security Techniques #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.2506.15264

openalex publication_date 2025/06/18 · openalex created_date 2025/10/19 · openalex updated_date 2026/07/28

Abstract

Federated learning allows each client to keep its data locally when training machine learning models in a distributed setting. Significant recent research established the requirements that the input must satisfy in order to guarantee convergence of the training loop. This line of work uses averaging as the aggregation rule for the training models. In particular, we are interested in whether federated learning is robust to Byzantine behavior, and observe and investigate a tradeoff between the average/centroid and the validity conditions from distributed computing. We show that the various validity conditions alone do not guarantee a good approximation of the average. Furthermore, we show that reaching good approximation does not give good results in experimental settings due to possible Byzantine outliers. Our main contribution is the first lower bound of min\(n-t)/(t),√(d)\ on the centroid approximation under box validity that is often considered in the literature, where n is the number of clients, t the upper bound on the number of Byzantine faults, and d is the dimension of the machine learning model. We complement this lower bound by an upper bound of 2min\n,√(d)\, by providing a new analysis for the case n

Citations

• Centroid Approximation with Multidimensional Approximate Agreement Protocols
• FedExP: Speeding Up Federated Averaging via Extrapolation
• FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learning
• Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums
• Challenges and Approaches for Mitigating Byzantine Attacks in Federated Learning
• Byzantine-robust Federated Learning through Collaborative Malicious Gradient Filtering
• Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients
• Byzantine-Resilient Secure Federated Learning
• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization
• Byzantine-Resilient High-Dimensional Federated Learning
• Resilient Distributed Vector Consensus Using Centerpoints
• Adaptive Federated Optimization
• Advances and Open Problems in Federated Learning
• BRIDGE: Byzantine-resilient Decentralized Gradient Descent
• Robust Federated Learning in a Heterogeneous Environment
• Federated Optimization in Heterogeneous Networks
• A Resilient Convex Combination for consensus-based distributed algorithms
• Byzantine Stochastic Gradient Descent
• The Hidden Vulnerability of Distributed Learning in Byzantium
• Revisiting Distributed Synchronous SGD
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Poisoning Attacks against Support Vector Machines
• Reaching Agreement in the Presence of Faults

Related

• Trade-off in Estimating the Number of Byzantine Clients in Federated Learning
• Towards Federated Learning With Byzantine-Robust Client Weighting
• Federated Learning Robust to Byzantine Attacks: Achieving Zero Optimality Gap
• Genuinely Distributed Byzantine Machine Learning
• Byzantine-Robust Federated Learning: Impact of Client Subsampling and Local Updates