# Centroid Approximation for Byzantine-Tolerant Federated Learning

arXiv: https://arxiv.org/abs/2506.15264 · HTML: https://mlsanity.com/paper/2506.15264/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 56 references that are in the map.
- First posted on arXiv 18 Jun 2025.

## Builds on (most cited first, 27 of 27)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [Federated Learning with Non-IID Data](https://mlsanity.com/paper/1806.00582/) (2018)
- [Adaptive Federated Optimization](https://mlsanity.com/paper/2003.00295/) (2020)
- [Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization](https://mlsanity.com/paper/2007.07481/) (2020)
- [The Hidden Vulnerability of Distributed Learning in Byzantium](https://mlsanity.com/paper/1802.07927/) (2018)
- [RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasets](https://mlsanity.com/paper/1811.03761/) (2018)
- [Revisiting Distributed Synchronous SGD](https://mlsanity.com/paper/1702.05800/) (2017)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [Byzantine-Resilient Secure Federated Learning](https://mlsanity.com/paper/2007.11115/) (2020)
- [Robust Federated Learning in a Heterogeneous Environment](https://mlsanity.com/paper/1906.06629/) (2019)
- [Byzantine Stochastic Gradient Descent](https://mlsanity.com/paper/1803.08917/) (2018)
- [Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks](https://mlsanity.com/paper/1912.12716/) (2019)
- [FedExP: Speeding Up Federated Averaging via Extrapolation](https://mlsanity.com/paper/2301.09604/) (2023)
- [FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learning](https://mlsanity.com/paper/2207.14130/) (2022)
- [Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums](https://mlsanity.com/paper/2205.12173/) (2022)
- [Collaborative Learning in the Jungle (Decentralized, Byzantine, Heterogeneous, Asynchronous and Nonconvex Learning)](https://mlsanity.com/paper/2008.00742/) (2020)
- [Challenges and Approaches for Mitigating Byzantine Attacks in Federated Learning](https://mlsanity.com/paper/2112.14468/) (2021)
- [BRIDGE: Byzantine-resilient Decentralized Gradient Descent](https://mlsanity.com/paper/1908.08098/) (2019)
- [ByRDiE: Byzantine-resilient distributed coordinate descent for decentralized learning](https://mlsanity.com/paper/1708.08155/) (2017)
- [Byzantine-robust Federated Learning through Collaborative Malicious Gradient Filtering](https://mlsanity.com/paper/2109.05872/) (2021)
- [Byzantine-Resilient High-Dimensional Federated Learning](https://mlsanity.com/paper/2006.13041/) (2020)
- [A Resilient Convex Combination for consensus-based distributed algorithms](https://mlsanity.com/paper/1806.10271/) (2018)
- [Resilient Distributed Vector Consensus Using Centerpoints](https://mlsanity.com/paper/2003.05497/) (2020)
- [Centroid Approximation with Multidimensional Approximate Agreement Protocols](https://mlsanity.com/paper/2306.12741/) (2023)

## Abstract (arXiv)

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 minfracn-tt,√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 2minn,√d, by providing a new analysis for the case n<d. In addition, we present a new algorithm that achieves a √2d-approximation under convex validity, which also proves that the existing lower bound in the literature is tight. We show that all presented bounds can also be achieved in the distributed peer-to-peer setting. We complement our analytical results with empirical evaluations in federated stochastic gradient descent and federated averaging settings.