論文の概要: Robust Distributed Estimation: Extending Gossip Algorithms to Ranking and Trimmed Means
- arxiv url: http://arxiv.org/abs/2505.17836v5
- Date: Wed, 11 Jun 2025 09:42:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-13 02:07:43.212049
- Title: Robust Distributed Estimation: Extending Gossip Algorithms to Ranking and Trimmed Means
- Title（参考訳）: ロバストな分散推定:Gossipアルゴリズムをランク付けとトリミングに拡張
- Authors: Anna Van Elst, Igor Colin, Stephan Clémençon,
- Abstract要約: 本研究では,大域的にロバストな数値を推定することにより,外乱平均を計算することができることを示す。
我々は,textscGoRankと呼ばれるランク推定のための新しいゴシップアルゴリズムを提案し,それを応用して,トリミング平均推定専用のゴシップ手順を設計する。
- 参考スコア（独自算出の注目度）: 3.481985817302898
- License: http://creativecommons.org/licenses/by/4.0/
- 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 \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}((\log t)/\sqrt{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.
- Abstract（参考訳）: 本稿では,任意の通信グラフ上のゴシップアルゴリズムにおけるロバストな推定の問題に対処する。
Gossipアルゴリズムは完全に分散化されており、近隣の通信にのみ依存しているため、通信が制約された状況に適している。
既存の平均ベースのゴシップアルゴリズムにおける根本的な課題は、悪意のあるノードや破損したノードに対する脆弱性である。
本稿では,ロバストな外乱平均は,世界規模で頑健な統計を推定することで計算可能であることを示す。
具体的には、ランク推定のための新しいゴシップアルゴリズムを提案し、それを応用して、トリミング平均推定専用のゴシップを設計する。
提案手法の詳細な説明に加えて、我々の研究の重要な貢献は正確な収束解析である: ランク推定に$\mathcal{O}(1/t)$レート、トリミング平均推定に$\mathcal{O}((\log t)/\sqrt{t})$レートを確立する。
さらに, \textsc{GoTrim} の分解点解析を行う。
我々は,ネットワークトポロジ,データ分布,汚染スキームの実験を通じて,理論的結果を実証的に検証した。
関連論文リスト
- Unified Breakdown Analysis for Byzantine Robust Gossip [15.69624587054777]
分散機械学習では、異なるデバイスがピアツーピアで通信し、互いのデータから協調的に学習する。
我々は、堅牢な分散アルゴリズムを構築するための一般的なフレームワークである$mathrmFtext-rm RG$を紹介した。
分散化されたアルゴリズムが許容できる敵の数に上限があることを示す。
論文 参考訳（メタデータ） (2024-10-14T12:10:52Z) - Robust Barycenter Estimation using Semi-Unbalanced Neural Optimal Transport [84.51977664336056]
本研究では、ロバストな連続バリセンタを推定するための新しいスケーラブルなアプローチを提案する。
提案手法は min-max 最適化問題であり,一般的なコスト関数に適用可能である。
論文 参考訳（メタデータ） (2024-10-04T23:27:33Z) - Decentralized Multi-Task Online Convex Optimization Under Random Link
Failures [5.513958040574729]
我々は不均一な確率を持つランダムリンク障害に対する頑健な分散型サドルポイントアルゴリズムを開発した。
我々はアルゴリズムと分析を2点の帯域フィードバックシナリオに拡張する。
論文 参考訳（メタデータ） (2024-01-04T00:57:33Z) - Distributed Contextual Linear Bandits with Minimax Optimal Communication
Cost [48.288452411283444]
そこでは,$N$エージェントが協調して,$d$次元の特徴を持つ線形帯域最適化問題を解く。
本稿では,LinUCBアルゴリズムの分散バッチ除去版であるDisBE-LUCBを提案する。
我々は、DisBE-LUCBの通信コストがわずか$tildemathcalO(dN)$であり、その後悔は少なくとも$tildemathcalO(dN)$であることを示す。
論文 参考訳（メタデータ） (2022-05-26T05:56:23Z) - Decentralized Sparse Linear Regression via Gradient-Tracking: Linear Convergence and Statistical Guarantees [23.256961881716595]
エージェントネットワーク上の疎線形回帰を非指向グラフとしてモデル化し,サーバノードを持たない。
分布予測勾配追跡に基づくアルゴリズムの収束率と統計的保証を解析する。
論文 参考訳（メタデータ） (2022-01-21T01:26:08Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳（メタデータ） (2021-10-24T04:03:00Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-01T14:10:38Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。