Unified Breakdown Analysis for Byzantine Robust Gossip

Renaud Gaucher (1, 2) , Aymeric Dieuleveut (1) , Hadrien Hendrikx (2)

1 CMAP - Centre de Mathématiques Appliquées de l'Ecole polytechnique
2 Thoth - Apprentissage de modèles à partir de données massives

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 CSours, such that CSours-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 CSours-RG and highlight the gap with NNA, in particular against a novel attack tailored to decentralized communications.

Domaines: Optimisation et contrôle [math.OC]; Calcul parallèle, distribué et partagé [cs.DC]

Renaud Gaucher, Aymeric Dieuleveut, Hadrien Hendrikx. Unified Breakdown Analysis for Byzantine Robust Gossip. 2024. ⟨hal-04830823v2⟩