Robust Distributed Estimation: Extending Gossip Algorithms to Ranking and Trimmed Means
Anna van Elst, Igor Colin, Stéphan Clémençon
Abstract
This paper addresses the problem of robust estimation in gossip algorithms over arbitrary communication graphs. Gossip algorithms are fully decentralized, relying only on local neighbor-to-neighbor communication, making them well-suited for situations where communication is constrained. A fundamental challenge in existing mean-based gossip algorithms is their vulnerability to malicious or corrupted nodes. In this paper, we show that an outlier-robust mean can be computed by globally estimating a robust statistic. More specifically, we propose a novel gossip algorithm for rank estimation, referred to as GoRank, and leverage it to design a gossip procedure dedicated to trimmed mean estimation, coined GoTrim. In addition to a detailed description of the proposed methods, a key contribution of our work is a precise convergence analysis: we establish an rate for rank estimation and an rate for trimmed mean estimation, where by is meant the number of iterations. Moreover, we provide a breakdown point analysis of GoTrim. We empirically validate our theoretical results through experiments on diverse network topologies, data distributions and contamination schemes.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Related papers
- Distributed Multi-Agent Bandits Over Erdős-Rényi Random NetworksJingyuan Liu, Hao Qiu, Lin F. Yang, Mengfan XuNeurIPS 2025 · 1 citation
- Correlated Quantization for Distributed Mean Estimation and OptimizationAnanda Theertha Suresh, Ziteng Sun, Jae Ro, Felix X. YuICML 2022 · 18 citations
- RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guaranteesEilon Vaknin Laufer, Boaz NadlerNeurIPS 2025 · 1 citation
- Distributed Ranking with Communications: Approximation Analysis and ApplicationsHong Chen, Yingjie Wang, Yulong Wang, Feng ZhengAAAI 2021
- Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and AveragingEdwige Cyffers, Mathieu Even, Aurélien Bellet, Laurent MassouliéNeurIPS 2022 · 39 citations
