# Near-Optimal Resilient Aggregation Rules for Distributed Learning Using 1-Center and 1-Mean Clustering with Outliers

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 36 references that are in the map.
- First posted on arXiv 20 Dec 2023.

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

- [Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification](https://mlsanity.com/paper/1909.06335/) (2019)
- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [The Hidden Vulnerability of Distributed Learning in Byzantium](https://mlsanity.com/paper/1802.07927/) (2018)
- [A Little Is Enough: Circumventing Defenses For Distributed Learning](https://mlsanity.com/paper/1902.06156/) (2019)
- [RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasets](https://mlsanity.com/paper/1811.03761/) (2018)
- [Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation](https://mlsanity.com/paper/1903.03936/) (2019)
- [Learning from History for Byzantine Robust Optimization](https://mlsanity.com/paper/2012.10333/) (2020)
- [Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing](https://mlsanity.com/paper/2006.09365/) (2020)
- [Back to the Drawing Board: A Critical Evaluation of Poisoning Attacks on Production Federated Learning](https://mlsanity.com/paper/2108.10241/) (2021)
- [Robust Federated Learning in a Heterogeneous Environment](https://mlsanity.com/paper/1906.06629/) (2019)
- [Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity](https://mlsanity.com/paper/2302.01772/) (2023)
- [Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums](https://mlsanity.com/paper/2205.12173/) (2022)
- [Byzantine-Resilient Non-Convex Stochastic Gradient Descent](https://mlsanity.com/paper/2012.14368/) (2020)
- [Byzantine-Robust Federated Learning with Optimal Statistical Rates and Privacy Guarantees](https://mlsanity.com/paper/2205.11765/) (2022)
- [Approximate Byzantine Fault-Tolerance in Distributed Optimization](https://mlsanity.com/paper/2101.09337/) (2021)
- [Byzantine-Resilient High-Dimensional Federated Learning](https://mlsanity.com/paper/2006.13041/) (2020)
- [On the Privacy-Robustness-Utility Trilemma in Distributed Learning](https://mlsanity.com/paper/2302.04787/) (2023)
- [Approximation Schemes for Clustering with Outliers](https://mlsanity.com/paper/1707.04295/) (2017)
- [PRIOR: Personalized Prior for Reactivating the Information Overlooked in Federated Learning](https://mlsanity.com/paper/2310.09183/) (2023)

## Built on by (most cited first, 4 of 4)

- [A survey on secure decentralized optimization and learning](https://mlsanity.com/paper/2408.08628/) (2024)
- [Byzantine-Robust and Communication-Efficient Distributed Learning via Compressed Momentum Filtering](https://mlsanity.com/paper/2409.08640/) (2024)
- [LiD-FL: Towards List-Decodable Federated Learning](https://mlsanity.com/paper/2408.04963/) (2024)
- [Enhanced Byzantine-Robust Federated Learning Via Truncated-Quadratic Loss for Heterogeneous Data](https://mlsanity.com/paper/2607.10970/) (2026)

## Abstract (arXiv)

Byzantine machine learning has garnered considerable attention in light of the unpredictable faults that can occur in large-scale distributed learning systems. The key to secure resilience against Byzantine machines in distributed learning is resilient aggregation mechanisms. Although abundant resilient aggregation rules have been proposed, they are designed in ad-hoc manners, imposing extra barriers on comparing, analyzing, and improving the rules across performance criteria. This paper studies near-optimal aggregation rules using clustering in the presence of outliers. Our outlier-robust clustering approach utilizes geometric properties of the update vectors provided by workers. Our analysis show that constant approximations to the 1-center and 1-mean clustering problems with outliers provide near-optimal resilient aggregators for metric-based criteria, which have been proven to be crucial in the homogeneous and heterogeneous cases respectively. In addition, we discuss two contradicting types of attacks under which no single aggregation rule is guaranteed to improve upon the naive average. Based on the discussion, we propose a two-phase resilient aggregation framework. We run experiments for image classification using a non-convex loss function. The proposed algorithms outperform previously known aggregation rules by a large margin with both homogeneous and heterogeneous data distributions among non-faulty workers. Code and appendix are available at https://github.com/jerry907/AAAI24-RASHB.