# Robust Distributed Estimation: Extending Gossip Algorithms to Ranking and Trimmed Means

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 44 references that are in the map.
- First posted on arXiv 23 May 2025.

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

- [Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates](https://mlsanity.com/paper/1803.01498/) (2018)
- [Robust Aggregation for Federated Learning](https://mlsanity.com/paper/1912.13445/) (2019)
- [A Little Is Enough: Circumventing Defenses For Distributed Learning](https://mlsanity.com/paper/1902.06156/) (2019)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [Distributed Learning in Wireless Networks: Recent Progress and Future Challenges](https://mlsanity.com/paper/2104.02151/) (2021)
- [Federated Learning: Opportunities and Challenges](https://mlsanity.com/paper/2101.05428/) (2021)
- [Byzantine-Robust Decentralized Learning via ClippedGossip](https://mlsanity.com/paper/2202.01545/) (2022)
- [Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions](https://mlsanity.com/paper/1606.02421/) (2016)
- [Distributed Robust Learning](https://mlsanity.com/paper/1409.5937/) (2014)
- [Extending Gossip Algorithms to Distributed Estimation of U-Statistics](https://mlsanity.com/paper/1511.05464/) (2015)
- [Optimal Gossip Algorithms for Exact and Approximate Quantile Computations](https://mlsanity.com/paper/1711.09258/) (2017)

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

- [High-Dimensional Statistics: Reflections on Progress and Open Problems](https://mlsanity.com/paper/2605.05076/) (2026)
- [Asynchronous Gossip Algorithms for Rank-Based Statistical Methods](https://mlsanity.com/paper/2509.07543/) (2025)
- [Fast and Efficient Asynchronous Gossip Algorithm for Robust and Non-Smooth Convex Decentralized Learning](https://mlsanity.com/paper/2601.20571/) (2026)
- [Decentralized Ranking Aggregation via Gossip: Convergence and Robustness](https://mlsanity.com/paper/2602.22847/) (2026)

## Abstract (arXiv)

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 textscGoRank, and leverage it to design a gossip procedure dedicated to trimmed mean estimation, coined textscGoTrim. 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) rate for rank estimation and an O(1 / t) rate for trimmed mean estimation, where by t is meant the number of iterations. Moreover, we provide a breakdown point analysis of textscGoTrim. We empirically validate our theoretical results through experiments on diverse network topologies, data distributions and contamination schemes.