論文の概要: Robust Distributed Estimation: Extending Gossip Algorithms to Ranking and Trimmed Means

• arxiv url: http://arxiv.org/abs/2505.17836v6
• Date: Thu, 10 Jul 2025 12:56:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-11 14:32:08.076116
• 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}(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.
• Abstract（参考訳）: 本稿では,任意の通信グラフ上のゴシップアルゴリズムにおけるロバストな推定の問題に対処する。 Gossipアルゴリズムは完全に分散化されており、近隣の通信にのみ依存しているため、通信が制約された状況に適している。 既存の平均ベースのゴシップアルゴリズムにおける根本的な課題は、悪意のあるノードや破損したノードに対する脆弱性である。 本稿では,ロバストな外乱平均は,世界規模で頑健な統計を推定することで計算可能であることを示す。 具体的には、ランク推定のための新しいゴシップアルゴリズムを提案し、それを応用して、トリミング平均推定専用のゴシップを設計する。 提案手法の詳細な説明に加えて、我々の研究の重要な貢献は正確な収束解析である: ランク推定に$\mathcal{O}(1/t)$レート、トリミング平均推定に$\mathcal{O}(1 / {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)
• Approximate Algorithms For $k$-Sparse Wasserstein Barycenter With Outliers [10.259254824702555]
  我々は、外乱が存在する場合に、$k$-sparse Wasserstein Barycenter問題を研究する。 既存のWBアルゴリズムは、ケースを外れ値で処理するために直接拡張することはできない。 本稿では,外乱問題のある$k$sparse WBに対して定数近似係数を求めるクラスタリングに基づくLP法を提案する。
  論文  参考訳（メタデータ） (2024-04-20T15:01:35Z)
• Decentralized Multi-Task Online Convex Optimization Under Random Link Failures [5.513958040574729]
  我々は不均一な確率を持つランダムリンク障害に対する頑健な分散型サドルポイントアルゴリズムを開発した。 我々はアルゴリズムと分析を2点の帯域フィードバックシナリオに拡張する。
  論文  参考訳（メタデータ） (2024-01-04T00:57:33Z)
• Robust Sparse Mean Estimation via Incremental Learning [15.536082641659423]
  そこで本研究では, 部分的に破損したサンプルの集合から, k$-sparse平均を推定することを目的とする, 頑健な平均推定問題について検討する。 両課題を適度な条件下で克服する簡易平均推定器を提案する。 私たちのメソッドは、スパーシティレベル$k$に関する事前の知識を必要としない。
  論文  参考訳（メタデータ） (2023-05-24T16:02:28Z)
• Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes [59.61248760134937]
  本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。 提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。 本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
  論文  参考訳（メタデータ） (2022-12-12T15:04:56Z)
• Byzantine-Robust Online and Offline Distributed Reinforcement Learning [60.970950468309056]
  本稿では,複数のエージェントが環境を探索し,その経験を中央サーバを通じて伝達する分散強化学習環境について考察する。 エージェントの$alpha$-fractionは敵対的であり、任意の偽情報を報告することができる。 我々は、これらの対立エージェントの存在下で、マルコフ決定プロセスの根底にある準最適政策を特定することを模索する。
  論文  参考訳（メタデータ） (2022-06-01T00:44:53Z)
• Communication-efficient distributed eigenspace estimation with arbitrary node failures [5.279475826661644]
  任意のノード障害のある分散環境を対象とした固有空間推定アルゴリズムを開発した。 この設定は、分散コンピューティングやデータ収集環境で発生するいくつかの重要なシナリオを含んでいる。 我々の推定器は、最近提案された非ロバスト推定器の性能に基づいて、$tildeO(sigma sqrtalpha)$エラーを加算する。
  論文  参考訳（メタデータ） (2022-05-31T22:01:41Z)
• 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)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
  論文  参考訳（メタデータ） (2020-10-12T17:41:44Z)
• $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a Robust Divergence Estimator [95.71091446753414]
  最寄りの$gamma$-divergence推定器をデータ差分尺度として用いることを提案する。 本手法は既存の不一致対策よりも高いロバスト性を実現する。
  論文  参考訳（メタデータ） (2020-06-13T06:09:27Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。