Lune

NeurIPS2025Top-tier venue

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 O(1/t)\mathcal{O}(1/t) rate for rank estimation and an O(1/t)\mathcal{O}(1 / {t}) rate for trimmed mean estimation, where by tt 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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Distributed Multi-Agent Bandits Over Erdős-Rényi Random NetworksJingyuan Liu, Hao Qiu, Lin F. Yang, Mengfan XuNeurIPS 2025 · 1 citation
  2. Correlated Quantization for Distributed Mean Estimation and OptimizationAnanda Theertha Suresh, Ziteng Sun, Jae Ro, Felix X. YuICML 2022 · 18 citations
  3. RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guaranteesEilon Vaknin Laufer, Boaz NadlerNeurIPS 2025 · 1 citation
  4. Distributed Ranking with Communications: Approximation Analysis and ApplicationsHong Chen, Yingjie Wang, Yulong Wang, Feng ZhengAAAI 2021
  5. Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and AveragingEdwige Cyffers, Mathieu Even, Aurélien Bellet, Laurent MassouliéNeurIPS 2022 · 39 citations
Dusk over the sea between two cliffs drawn in fine vertical lines