# Collaborative Learning in the Jungle (Decentralized, Byzantine, Heterogeneous, Asynchronous and Nonconvex Learning)

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

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Aug 2020.

## Built on by (most cited first, 30 of 54)

- [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-Robust Decentralized Federated Learning](https://mlsanity.com/paper/2406.10416/) (2024)
- [Byzantine-Robust Decentralized Learning via ClippedGossip](https://mlsanity.com/paper/2202.01545/) (2022)
- [On the Impossible Safety of Large AI Models](https://mlsanity.com/paper/2209.15259/) (2022)
- [Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity](https://mlsanity.com/paper/2309.13591/) (2023)
- [An Equivalence Between Data Poisoning and Byzantine Gradient Attacks](https://mlsanity.com/paper/2202.08578/) (2022)
- [Achieving Byzantine-Resilient Federated Learning via Layer-Adaptive Sparsified Model Aggregation](https://mlsanity.com/paper/2409.01435/) (2024)
- [Byzantine-Robust Learning on Heterogeneous Data via Gradient Splitting](https://mlsanity.com/paper/2302.06079/) (2023)
- [Detecting Backdoor Attacks in Federated Learning via Direction Alignment Inspection](https://mlsanity.com/paper/2503.07978/) (2025)
- [MedBN: Robust Test-Time Adaptation against Malicious Test Samples](https://mlsanity.com/paper/2403.19326/) (2024)
- [Unified Breakdown Analysis for Byzantine Robust Gossip](https://mlsanity.com/paper/2410.10418/) (2024)
- [Can Decentralized Learning be more robust than Federated Learning?](https://mlsanity.com/paper/2303.03829/) (2023)
- [Byzantine Spectral Ranking](https://mlsanity.com/paper/2211.07902/) (2022)
- [Adversarial Sampling for Fairness Testing in Deep Neural Network](https://mlsanity.com/paper/2303.02874/) (2023)
- [On the Byzantine-Resilience of Distillation-Based Federated Learning](https://mlsanity.com/paper/2402.12265/) (2024)
- [Network-Level Adversaries in Federated Learning](https://mlsanity.com/paper/2208.12911/) (2022)
- [Toward Malicious Clients Detection in Federated Learning](https://mlsanity.com/paper/2505.09110/) (2025)
- [The poison of dimensionality](https://mlsanity.com/paper/2409.17328/) (2024)
- [Bant: Byzantine Antidote via Trial Function and Trust Scores](https://mlsanity.com/paper/2505.07614/) (2025)
- [Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participation](https://mlsanity.com/paper/2509.02970/) (2025)
- [Variance Reduction is an Antidote to Byzantines: Better Rates, Weaker Assumptions and Communication Compression as a Cherry on the Top](https://mlsanity.com/paper/2206.00529/) (2022)
- [Decentralized Federated Policy Gradient with Byzantine Fault-Tolerance and Provably Fast Convergence](https://mlsanity.com/paper/2401.03489/) (2024)
- [On the Relevance of Byzantine Robust Optimization Against Data Poisoning](https://mlsanity.com/paper/2405.00491/) (2024)
- [On the Byzantine Fault Tolerance of signSGD with Majority Vote](https://mlsanity.com/paper/2502.19170/) (2025)
- [DeCAF: Decentralized Consensus-And-Factorization for Low-Rank Adaptation of Foundation Models](https://mlsanity.com/paper/2505.21382/) (2025)
- [Strategyproof Learning: Building Trustworthy User-Generated Datasets](https://mlsanity.com/paper/2106.02398/) (2021)
- [Balancing Privacy, Robustness, and Efficiency in Machine Learning](https://mlsanity.com/paper/2312.14712/) (2023)
- [Byzantine-Robust Gossip: Insights from a Dual Approach](https://mlsanity.com/paper/2405.03449/) (2024)
- [ROSS: RObust decentralized Stochastic learning based on Shapley values](https://mlsanity.com/paper/2411.00365/) (2024)

## Abstract (arXiv)

We study Byzantine collaborative learning, where n nodes seek to collectively learn from each others' local data. The data distribution may vary from one node to another. No node is trusted, and f < n nodes can behave arbitrarily. We prove that collaborative learning is equivalent to a new form of agreement, which we call averaging agreement. In this problem, nodes start each with an initial vector and seek to approximately agree on a common vector, which is close to the average of honest nodes' initial vectors. We present two asynchronous solutions to averaging agreement, each we prove optimal according to some dimension. The first, based on the minimum-diameter averaging, requires  n ≥ 6f+1, but achieves asymptotically the best-possible averaging constant up to a multiplicative constant. The second, based on reliable broadcast and coordinate-wise trimmed mean, achieves optimal Byzantine resilience, i.e., n ≥ 3f+1. Each of these algorithms induces an optimal Byzantine collaborative learning protocol. In particular, our equivalence yields new impossibility theorems on what any collaborative learning algorithm can achieve in adversarial and heterogeneous environments.