論文の概要: Unified Breakdown Analysis for Byzantine Robust Gossip

• arxiv url: http://arxiv.org/abs/2410.10418v2
• Date: Mon, 03 Feb 2025 12:16:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-04 16:04:37.042826
• Title: Unified Breakdown Analysis for Byzantine Robust Gossip
• Title（参考訳）: ビザンチンロバストゴシップの統一的破壊解析
• Authors: Renaud Gaucher, Aymeric Dieuleveut, Hadrien Hendrikx,
• Abstract要約: 分散機械学習では、異なるデバイスがピアツーピアで通信し、互いのデータから協調的に学習する。 我々は、堅牢な分散アルゴリズムを構築するための一般的なフレームワークである$mathrmFtext-rm RG$を紹介した。 分散化されたアルゴリズムが許容できる敵の数に上限があることを示す。
• 参考スコア（独自算出の注目度）: 15.69624587054777
• License:
• Abstract: In decentralized machine learning, different devices communicate in a peer-to-peer manner to collaboratively learn from each other's data. Such approaches are vulnerable to misbehaving (or Byzantine) devices. We introduce $\mathrm{F}\text{-}\rm RG$, a general framework for building robust decentralized algorithms with guarantees arising from robust-sum-like aggregation rules $\mathrm{F}$. We then investigate the notion of *breakdown point*, and show an upper bound on the number of adversaries that decentralized algorithms can tolerate. We introduce a practical robust aggregation rule, coined $\rm CS_{ours}$, such that $\rm CS_{ours}\text{-}RG$ has a near-optimal breakdown. Other choices of aggregation rules lead to existing algorithms such as $\rm ClippedGossip$ or $\rm NNA$. We give experimental evidence to validate the effectiveness of $\rm CS_{ours}\text{-}RG$ and highlight the gap with $\mathrm{NNA}$, in particular against a novel attack tailored to decentralized communications.
• Abstract（参考訳）: 分散機械学習では、異なるデバイスがピアツーピアで通信し、互いのデータから協調的に学習する。 このようなアプローチは、誤った行動(あるいはビザンティン)デバイスに対して脆弱である。 これは、ロバストなsumライクなアグリゲーションルールから生じる保証を持つ、ロバストな分散アルゴリズムを構築するための一般的なフレームワークである。 次に、*ブレークダウンポイント*の概念を調査し、分散アルゴリズムが許容できる敵の数に上限を示す。 我々は、$\rm CS_{ours}\text{-}RG$がほぼ最適分解であるような、実用的なロバストなアグリゲーションルール($\rm CS_{ours}$)を導入する。 他のアグリゲーションルールの選択は、$\rm ClippedGossip$や$\rm NNA$といった既存のアルゴリズムにつながる。 我々は、$\rm CS_{ours}\text{-}RG$の有効性を検証する実験的な証拠を与え、特に分散通信に適した新しい攻撃に対して、$\mathrm{NNA}$とのギャップを強調する。

関連論文リスト

• Stochastic Bandits Robust to Adversarial Attacks [33.278131584647745]
  本稿では,敵攻撃に対して頑健なマルチアームバンディットアルゴリズムについて検討する。 我々は、攻撃予算の知識の有無に関わらず、このモデルの2つのケースを調査する。 我々は、加法的あるいは乗法的な$C$依存項を持つ後悔境界を持つ2種類のアルゴリズムを考案する。
  論文  参考訳（メタデータ） (2024-08-16T17:41:35Z)
• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
  両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。 我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
  論文  参考訳（メタデータ） (2023-12-24T08:27:30Z)
• Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards [40.99322897009357]
  トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。 我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。 我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
  論文  参考訳（メタデータ） (2023-10-28T13:01:10Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum Optimization [25.21457349137344]
  私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
  論文  参考訳（メタデータ） (2022-10-25T11:37:11Z)
• Minimax Rates for Robust Community Detection [19.229475414802213]
  逆ノードの破損を伴うブロックモデルにおけるコミュニティ検出の問題点について検討する。 我々の主な結果は、$epsilon$-fraction of corruption and unbounded error $O(epsilon) + e-fracC2 (1 pm o(1))$ where $C = (sqrta - sqrtb)2$ is the signal-to-noise ratio。 アルゴリズムがさらに機能するという意味では、我々のアルゴリズムは2倍に損なわれていることを示す。
  論文  参考訳（メタデータ） (2022-07-25T04:45:16Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
  論文  参考訳（メタデータ） (2021-10-25T02:53:24Z)
• Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
  与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。 次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。 頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
  論文  参考訳（メタデータ） (2021-07-22T14:25:16Z)
• Provable Robustness of Adversarial Training for Learning Halfspaces with Noise [95.84614821570283]
  ラベル雑音の存在下での敵対的ロバストなハーフスペースの特性を分析する。 我々の知る限りでは、これは敵の訓練がノイズの分類子を与えることを示す最初の研究である。
  論文  参考訳（メタデータ） (2021-04-19T16:35:38Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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