# Robust Collaborative Learning with Linear Gradient Overhead

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 35 references that are in the map.
- First posted on arXiv 22 Sep 2022.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [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)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [A Little Is Enough: Circumventing Defenses For Distributed Learning](https://mlsanity.com/paper/1902.06156/) (2019)
- [Asynchronous Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1710.06952/) (2017)
- [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)
- [Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent](https://mlsanity.com/paper/1705.05491/) (2017)
- [Byzantine-Resilient Non-Convex Stochastic Gradient Descent](https://mlsanity.com/paper/2012.14368/) (2020)
- [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-resilient Decentralized Stochastic Gradient Descent](https://mlsanity.com/paper/2002.08569/) (2020)
- [Approximate Byzantine Fault-Tolerance in Distributed Optimization](https://mlsanity.com/paper/2101.09337/) (2021)
- [Byzantine-Resilient SGD in High Dimensions on Heterogeneous Data](https://mlsanity.com/paper/2005.07866/) (2020)
- [Asynchronous Byzantine Machine Learning (the case of SGD)](https://mlsanity.com/paper/1802.07928/) (2018)
- [A Survey on Fault-tolerance in Distributed Optimization and Machine Learning](https://mlsanity.com/paper/2106.08545/) (2021)
- [Byzantine Fault Tolerance in Distributed Machine Learning : a Survey](https://mlsanity.com/paper/2205.02572/) (2022)

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

- [On the Impossible Safety of Large AI Models](https://mlsanity.com/paper/2209.15259/) (2022)
- [Decentralized SGD and Average-direction SAM are Asymptotically Equivalent](https://mlsanity.com/paper/2306.02913/) (2023)
- [Adaptive Gradient Clipping for Robust Federated Learning](https://mlsanity.com/paper/2405.14432/) (2024)
- [Unified Breakdown Analysis for Byzantine Robust Gossip](https://mlsanity.com/paper/2410.10418/) (2024)
- [Overcoming the Challenges of Batch Normalization in Federated Learning](https://mlsanity.com/paper/2405.14670/) (2024)
- [ByzFL: Research Framework for Robust Federated Learning](https://mlsanity.com/paper/2505.24802/) (2025)
- [On the Relevance of Byzantine Robust Optimization Against Data Poisoning](https://mlsanity.com/paper/2405.00491/) (2024)
- [Byzantine-Robust Gossip: Insights from a Dual Approach](https://mlsanity.com/paper/2405.03449/) (2024)
- [SABLE: Secure And Byzantine robust LEarning](https://mlsanity.com/paper/2309.05395/) (2023)
- [Robust and Efficient Collaborative Learning](https://mlsanity.com/paper/2510.08311/) (2025)
- [Topology-Independent Robustness of the Weighted Mean under Label Poisoning Attacks in Heterogeneous Decentralized Learning](https://mlsanity.com/paper/2601.02682/) (2026)
- [From Inexact Gradients to Byzantine Robustness: Acceleration and Optimization under Similarity](https://mlsanity.com/paper/2602.03329/) (2026)

## Abstract (arXiv)

Collaborative learning algorithms, such as distributed SGD (or D-SGD), are prone to faulty machines that may deviate from their prescribed algorithm because of software or hardware bugs, poisoned data or malicious behaviors. While many solutions have been proposed to enhance the robustness of D-SGD to such machines, previous works either resort to strong assumptions (trusted server, homogeneous data, specific noise model) or impose a gradient computational cost that is several orders of magnitude higher than that of D-SGD. We present MoNNA, a new algorithm that (a) is provably robust under standard assumptions and (b) has a gradient computation overhead that is linear in the fraction of faulty machines, which is conjectured to be tight. Essentially, MoNNA uses Polyak's momentum of local gradients for local updates and nearest-neighbor averaging (NNA) for global mixing, respectively. While MoNNA is rather simple to implement, its analysis has been more challenging and relies on two key elements that may be of independent interest. Specifically, we introduce the mixing criterion of (α, λ)-reduction to analyze the non-linear mixing of non-faulty machines, and present a way to control the tension between the momentum and the model drifts. We validate our theory by experiments on image classification and make our code available at https://github.com/LPD-EPFL/robust-collaborative-learning.