論文の概要: 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}$とのギャップを強調する。
関連論文リスト
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。
この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文 参考訳（メタデータ） (2024-05-09T17:40:09Z) - Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
我々は、M$のクライアントが中央サーバと通信し、線形文脈の帯域幅問題を解決するための連合線形帯域幅モデルについて検討する。
逆有限作用集合のユニークな問題に対処するため、FedSupLinUCBアルゴリズムを提案する。
我々は、FedSupLinUCBが$tildeO(sqrtd T)$の完全後悔を達成したことを証明している。
論文 参考訳（メタデータ） (2023-11-02T03:41:58Z) - Optimal Algorithms for Latent Bandits with Cluster Structure [50.44722775727619]
本稿では,複数のユーザが存在するクラスタ構造を持つ潜伏包帯問題と関連するマルチアーム包帯問題とを考察する。
本稿では,潜伏クラスタ構造を利用して$widetildeO(sqrt(mathsfM+mathsfN)mathsfTの最小限の後悔を提供するLATTICEを提案する。
論文 参考訳（メタデータ） (2023-01-17T17:49:04Z) - 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) - A Simple and Provably Efficient Algorithm for Asynchronous Federated
Contextual Linear Bandits [77.09836892653176]
我々は,M$エージェントが相互に協力して,中央サーバの助けを借りて,グローバルなコンテキスト線形バンドイット問題を解決するためのフェデレーション付きコンテキスト線形バンドイットについて検討した。
すべてのエージェントが独立して動作し、ひとつのエージェントとサーバ間の通信が他のエージェントの通信をトリガーしない非同期設定を考える。
texttFedLinUCBの後悔は$tildeO(dsqrtsum_m=1M T_m)$で、通信の複雑さは$tildeO(dM)であることを示す。
論文 参考訳（メタデータ） (2022-07-07T06:16:19Z) - Tight FPT Approximation for Constrained k-Center and k-Supplier [0.38073142980733]
我々は、$k$-supplierと$k$-center問題の制約付きバージョンについて検討する。
Ding と Xu [SODA 2015] は、$k$-median と $k$-means の目的という文脈で、制約付きクラスタリングのための統一されたフレームワークを提案した。
論文 参考訳（メタデータ） (2021-10-27T07:52:59Z) - FriendlyCore: Practical Differentially Private Aggregation [67.04951703461657]
我々は、制約のない(擬似)計量空間から点の集合を$cal D$として取り出す、単純で実用的なツールである$mathsfFriendlyCore$を提案する。
$cal D$ が有効直径 $r$ を持つとき、$mathsfFriendlyCore$ はすべての点を含む "stable" サブセット $cal D_Gsubseteq cal D$ を返す。
$mathsfFriendlyCore$は、プライベートに集約する前に入力を前処理するために使用することができる。
論文 参考訳（メタデータ） (2021-10-19T17:43:50Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - Communication Efficient Parallel Reinforcement Learning [34.77250498401055]
我々は、$m$エージェントが$s$状態と$a$アクションを持つ$m$同一および独立環境と相互作用する問題を考える。
我々はエージェントが不適切なコミュニケーションラウンドで後悔を最小限に抑えるアルゴリズムを見つけることを目的としている。
論文 参考訳（メタデータ） (2021-02-22T02:46:36Z) - Impact of Community Structure on Consensus Machine Learning [0.17188280334580192]
ブロックモデルから引き出されたネットワーク上でのコンセンサス機械学習について検討する。
私たちは、$tau_epsilon$が低い境界に達するような、コミュニティ構造の重要なレベルが存在することに気付きました。
論文 参考訳（メタデータ） (2020-11-02T21:41:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。