Fugu-MT 論文翻訳(概要): Achieving Optimal Breakdown for Byzantine Robust Gossip

論文の概要: Achieving Optimal Breakdown for Byzantine Robust Gossip

arxiv url: http://arxiv.org/abs/2410.10418v1
Date: Mon, 14 Oct 2024 12:10:52 GMT
ステータス: 処理完了
システム内更新日: 2024-10-29 21:44:49.430278
Title: Achieving Optimal Breakdown for Byzantine Robust Gossip
Title（参考訳）: ビザンチン・ロバスト・ゴシップの最適ブレークダウン達成
Authors: Renaud Gaucher, Aymeric Dieuleveut, Hadrien Hendrikx,
Abstract要約: 本稿では,デバイス同士が直接通信する分散環境でのビザンチン耐性アルゴリズムについて検討する。我々は,$mathrmClippedGossip$と$mathrmNNA$の交差点におけるアルゴリズムである$mathrmCG+$を紹介した。
参考スコア（独自算出の注目度）: 15.69624587054777
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Distributed approaches have many computational benefits, but they are vulnerable to attacks from a subset of devices transmitting incorrect information. This paper investigates Byzantine-resilient algorithms in a decentralized setting, where devices communicate directly with one another. We investigate the notion of breakdown point, and show an upper bound on the number of adversaries that decentralized algorithms can tolerate. We introduce $\mathrm{CG}^+$, an algorithm at the intersection of $\mathrm{ClippedGossip}$ and $\mathrm{NNA}$, two popular approaches for robust decentralized learning. $\mathrm{CG}^+$ meets our upper bound, and thus obtains optimal robustness guarantees, whereas neither of the existing two does. We provide experimental evidence for this gap by presenting an attack tailored to sparse graphs which breaks $\mathrm{NNA}$ but against which $\mathrm{CG}^+$ is robust.
Abstract（参考訳）: 分散アプローチには多くの計算上の利点があるが、誤った情報を伝達するデバイスのサブセットからの攻撃に対して脆弱である。本稿では,デバイス同士が直接通信する分散環境でのビザンチン耐性アルゴリズムについて検討する。本稿では, 分解点の概念を考察し, 分散アルゴリズムが許容できる敵数に対する上限を示す。我々は,$\mathrm{CG}^+$,$\mathrm{ClippedGossip}$と$\mathrm{NNA}$の交点にあるアルゴリズムを紹介した。 $\mathrm{CG}^+$ は私たちの上限を満たすので、どちらの2つもそうでないのに対して、最適なロバスト性を保証する。このギャップに対する実験的な証拠として、スパースグラフに適合する攻撃が$\mathrm{NNA}$を破るが、$\mathrm{CG}^+$が堅牢であることを示す。

関連論文リスト

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)

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