Research map / Learning theory and algorithms / Sample complexity
Robust Distributed Estimation: Extending Gossip Algorithms to Ranking and Trimmed Means
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GoRank, a pairwise-comparison gossip algorithm for rank estimation with O(1/t) convergence on arbitrary graphs, and GoTrim, which uses GoRank ranks to gossip alpha-trimmed means robustly, with convergence and breakdown-point analysis.
Problem
Robust mean estimation in fully decentralized gossip networks where a fraction of nodes hold outlying (contaminated) observations, requiring global robust statistics such as trimmed means over arbitrary communication graphs.
Approach
Estimate ranks via gossip of pairwise indicator averages (extending GoSta to ranks), then gossip the weighted sum of observations with rank-dependent trimming weights, so the trimmed mean is computed globally without a central server.
Key results
- GoRank achieves an O(1/t) rate for expected rank estimates on arbitrary connected non-bipartite graphs, with constant c = lambda_2/|E|.
- GoTrim converges in expectation to the alpha-trimmed mean at rate O(1/(c^2 t)) and quickly improves over the corrupted mean in experiments (scaling s=10, 10% contamination).
- Breakdown point of partial trimmed mean estimate is bounded above by floor(alpha n)/n, with a lower bound that tends to it as t grows.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GoRank instead of Baseline for gossip ranking | Distributed rank estimation · Large, poorly connected graphs, including the 2D grid | normalized absolute rank error | Helped |
| Use Baseline++ instead of GoRank for gossip ranking | Distributed rank estimation · 2D grid | normalized absolute rank error | Mixed |
| Use GoTrim with GoRank rather than the naive corrupted mean | Trimmed-mean estimation · Contaminated simulated data and Basel Luftklima | absolute trimmed-mean error | Helped |
| Use GoTrim rather than ClippedGossip for robust estimation | Trimmed-mean estimation · Contaminated data | absolute trimmed-mean error | Helped |
Surprising findings
- ClippedGossip with fixed clipping radius converges to the corrupted mean rather than the robust estimate in pairwise setups.
Limitations
- Robustness analysis covers only Huber-style data contamination, not Byzantine adversaries.
- The c^2 dependence in the GoTrim rate may be pessimistic; bounds are in expectation and sparse/poorly connected graphs slow convergence.
- Baseline++ convergence on arbitrary graphs is not analyzed.
Experimental setup
Datasets: Basel Luftklima temperature dataset (n=105 sensors) synthetic observations on S={1,...,n}, n=500
Benchmarks: Basel Luftklima dataset simulated datasets on Watts-Strogatz and 2D grid graphs
Metrics: normalized absolute rank error absolute error of trimmed mean estimate convergence over iterations breakdown point
Baselines: Chiuso et al. (Baseline) Baseline++ ClippedGossip naive corrupted mean
Builds on: GoSta Chiuso et al. distributed ranking gossip ClippedGossip gossip averaging
Closest papers by meaning
- Decentralized Ranking Aggregation via Gossip: Convergence and Robustness (NeurIPS 2026 · similarity 0.87)
- Unified Breakdown Analysis for Byzantine Robust Gossip (ICML 2025 · similarity 0.87)
- Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages (ICML 2024 · similarity 0.85)
- Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point (NeurIPS 2025 · similarity 0.85)
- Robust Estimation Under Heterogeneous Corruption Rates (NeurIPS 2025 · similarity 0.84)
- Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.