Unified Breakdown Analysis for Byzantine Robust Gossip
Renaud Gaucher, Aymeric Dieuleveut, Hadrien Hendrikx
Abstract
In decentralized machine learning, different devices communicate in a peer-to-peer manner to collaboratively learn from each other's data. Such approaches are vulnerable to misbehaving (or Byzantine) devices. We introduce F-RG, a general framework for building robust decentralized algorithms with guarantees arising from robust-sum-like aggregation rules F. We then investigate the notion of *breakdown point*, and show an upper bound on the number of adversaries that decentralized algorithms can tolerate. We introduce a practical robust aggregation rule, coined CS+, such that CS+-RG has a near-optimal breakdown. Other choices of aggregation rules lead to existing algorithms such as ClippedGossip or NNA. We give experimental evidence to validate the effectiveness of CS+-RG and highlight the gap with NNA, in particular against a novel attack tailored to decentralized communications.
BibTeX
@inproceedings{
gaucher2025unified,
title={Unified Breakdown Analysis for Byzantine Robust Gossip},
author={Renaud Gaucher and Aymeric Dieuleveut and Hadrien Hendrikx},
booktitle={Forty-second International Conference on Machine Learning},
year={2025},
url={https://openreview.net/forum?id=OOYPeymDz2}
}