arXiv:2505.17836stat.MLcs.LG2025-05NeurIPS被引 4

提出抗干扰的分布式估计算法,提升网络中节点通信的鲁棒性。

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

  • 通过局部通信实现全局稳健统计量估计,避免异常值影响。
  • 收敛速率达1/t,且在不同网络结构下表现稳定。
  • 适合存在恶意节点或数据污染的分布式系统应用。

本文研究任意通信图上基于共识的分布式估计中的鲁棒性问题。传统基于均值的扩散算法易受恶意或损坏节点影响。本文提出一种新型扩散算法 extsc{GoRank} 用于秩估计,并基于此设计了针对截尾均值估计的 extsc{GoTrim} 算法。核心贡献包括:精确的收敛性分析——秩估计和截尾均值估计均达到 $/mathcal{O}(1/t)$ 的收敛速率($t$ 为迭代次数);对 extsc{GoTrim} 的破点分析。实验在多种网络拓扑、数据分布和污染策略下验证了理论结果的有效性。

原文摘要 · Abstract (English)

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 \textsc{GoRank}, and leverage it to design a gossip procedure dedicated to trimmed mean estimation, coined \textsc{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 $\mathcal{O}(1/t)$ rate for rank estimation and an $\mathcal{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 \textsc{GoTrim}. We empirically validate our theoretical results through experiments on diverse network topologies, data distributions and contamination schemes.

分布式估计鲁棒性扩散算法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。