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)
Stochastic Bandits Robust to Adversarial Attacks [33.278131584647745]
本稿では,敵攻撃に対して頑健なマルチアームバンディットアルゴリズムについて検討する。我々は、攻撃予算の知識の有無に関わらず、このモデルの2つのケースを調査する。我々は、加法的あるいは乗法的な$C$依存項を持つ後悔境界を持つ2種類のアルゴリズムを考案する。
論文参考訳（メタデータ） (2024-08-16T17:41:35Z)
Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
論文参考訳（メタデータ） (2024-05-09T17:40:09Z)
Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文参考訳（メタデータ） (2023-12-24T08:27:30Z)
Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
我々は、M$のクライアントが中央サーバと通信し、線形文脈の帯域幅問題を解決するための連合線形帯域幅モデルについて検討する。逆有限作用集合のユニークな問題に対処するため、FedSupLinUCBアルゴリズムを提案する。我々は、FedSupLinUCBが$tildeO(sqrtd T)$の完全後悔を達成したことを証明している。
論文参考訳（メタデータ） (2023-11-02T03:41:58Z)
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)
Optimal Algorithms for Latent Bandits with Cluster Structure [50.44722775727619]
本稿では,複数のユーザが存在するクラスタ構造を持つ潜伏包帯問題と関連するマルチアーム包帯問題とを考察する。本稿では,潜伏クラスタ構造を利用して$widetildeO(sqrt(mathsfM+mathsfN)mathsfTの最小限の後悔を提供するLATTICEを提案する。
論文参考訳（メタデータ） (2023-01-17T17:49:04Z)
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)
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)
Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文参考訳（メタデータ） (2021-10-25T02:53:24Z)
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)
Provable Robustness of Adversarial Training for Learning Halfspaces with Noise [95.84614821570283]
ラベル雑音の存在下での敵対的ロバストなハーフスペースの特性を分析する。我々の知る限りでは、これは敵の訓練がノイズの分類子を与えることを示す最初の研究である。
論文参考訳（メタデータ） (2021-04-19T16:35:38Z)
Communication Efficient Parallel Reinforcement Learning [34.77250498401055]
我々は、$m$エージェントが$s$状態と$a$アクションを持つ$m$同一および独立環境と相互作用する問題を考える。我々はエージェントが不適切なコミュニケーションラウンドで後悔を最小限に抑えるアルゴリズムを見つけることを目的としている。
論文参考訳（メタデータ） (2021-02-22T02:46:36Z)
Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。機械は独立して勾配を計算し協力することができます私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。それは非常に実用的です:それはないときすべての前の方法の性能を改善します。セッティングマシンがあります。
論文参考訳（メタデータ） (2020-12-28T17:19:32Z)
Impact of Community Structure on Consensus Machine Learning [0.17188280334580192]
ブロックモデルから引き出されたネットワーク上でのコンセンサス機械学習について検討する。私たちは、$tau_epsilon$が低い境界に達するような、コミュニティ構造の重要なレベルが存在することに気付きました。
論文参考訳（メタデータ） (2020-11-02T21:41:35Z)
Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文参考訳（メタデータ） (2020-03-04T07:36:38Z)

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