論文の概要: 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}^+$が堅牢であることを示す。
関連論文リスト
- Learning Theory of Decentralized Robust Kernel-Based Learning Algorithm [1.3597551064547502]
我々は、カーネルヒルベルト空間(RKHS)を再現する枠組みの中で、新しい堅牢なカーネルベース学習アルゴリズムを提案する。
分散化アルゴリズムから生成された各局所ロバスト推定器を用いて回帰関数を近似することができることを示す。
局所的なサンプルサイズに対する厳密な選択ルールを提供し、適切に選択されたステップサイズとスケーリングパラメータ$sigma$では、分散化されたロバストアルゴリズムが最適な学習率を達成することができることを示す。
論文 参考訳(メタデータ) (2025-06-05T16:30:05Z) - 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) - Multi-Agent Best Arm Identification in Stochastic Linear Bandits [0.7673339435080443]
固定予算シナリオ下での線形包帯における協調的ベストアーム識別の問題について検討する。
本稿では,任意の構造を持つスターネットワークとネットワークに対して,MaLinBAI-StarとMaLinBAI-Genの2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-11-20T20:09:44Z) - Boosting the Performance of Decentralized Federated Learning via Catalyst Acceleration [66.43954501171292]
本稿では,Catalytics Accelerationを導入し,DFedCataと呼ばれる促進型分散フェデレート学習アルゴリズムを提案する。
DFedCataは、パラメータの不整合に対処するMoreauエンベロープ関数と、アグリゲーションフェーズを加速するNesterovの外挿ステップの2つの主要コンポーネントで構成されている。
実験により, CIFAR10/100における収束速度と一般化性能の両面において, 提案アルゴリズムの利点を実証した。
論文 参考訳(メタデータ) (2024-10-09T06:17:16Z) - Byzantine-Robust Aggregation for Securing Decentralized Federated
Learning [0.32985979395737774]
Federated Learning(FL)は、デバイス上でAIモデルをローカルにトレーニングすることで、プライバシの問題に対処する分散機械学習アプローチとして登場した。
分散フェデレートラーニング(DFL)は、中央サーバを排除し、単一障害点の回避を通じてスケーラビリティと堅牢性を向上させることで、FLパラダイムを拡張します。
We present a novel byzantine-robust aggregate algorithm to enhance the security of DFL environment, coin, WFAgg。
論文 参考訳(メタデータ) (2024-09-26T11:36:08Z) - Stochastic Bandits Robust to Adversarial Attacks [33.278131584647745]
本稿では,敵攻撃に対して頑健なマルチアームバンディットアルゴリズムについて検討する。
我々は、攻撃予算の知識の有無に関わらず、このモデルの2つのケースを調査する。
我々は、加法的あるいは乗法的な$C$依存項を持つ後悔境界を持つ2種類のアルゴリズムを考案する。
論文 参考訳(メタデータ) (2024-08-16T17:41:35Z) - Robust Zero Trust Architecture: Joint Blockchain based Federated learning and Anomaly Detection based Framework [17.919501880326383]
本稿では,IoTネットワーク内の効率的なリモートワークとコラボレーションを支援する分散システムに適した,堅牢なゼロトラストアーキテクチャ(ZTA)を紹介する。
ブロックチェーンベースのフェデレーション学習原則を使用することで、当社のフレームワークは、漏洩したクライアントからの悪意のある更新を防止すべく、堅牢な集約メカニズムを備えている。
このフレームワークは異常検出と信頼計算を統合し、セキュアで信頼性の高いデバイスコラボレーションを分散的に保証する。
論文 参考訳(メタデータ) (2024-06-24T23:15:19Z) - 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) - Speeding up Heterogeneous Federated Learning with Sequentially Trained
Superclients [19.496278017418113]
フェデレートラーニング(FL)は、ローカルなデータ共有を必要とせず、エッジデバイスの協調を可能にすることにより、プライバシに制約のあるシナリオで機械学習モデルをトレーニングすることを可能にする。
このアプローチは、ローカルデータセットとクライアントの計算的不均一性の異なる統計分布のために、いくつかの課題を提起する。
我々は、多種多様なクライアント、すなわちスーパークオリエントの部分グループのシーケンシャルトレーニングを活用して、集中型パラダイムをプライバシに準拠した方法でエミュレートする新しいフレームワークであるFedSeqを提案する。
論文 参考訳(メタデータ) (2022-01-26T12:33:23Z) - 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) - Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge
Computing [113.52575069030192]
セキュリティ要件の高いアプリケーションを含むビッグデータは、モバイルデバイスやドローン、車両など、複数の異種デバイスに収集され、格納されることが多い。
通信コストとセキュリティ要件の制限のため、核融合センターにデータを集約するのではなく、分散的に情報を抽出することが最重要となる。
分散エッジノードを介してデータを局所的に処理するマルチエージェントシステムにおいて,モデルパラメータを学習する問題を考える。
分散学習モデルを開発するために,乗算器アルゴリズムの最小バッチ交互方向法(ADMM)のクラスについて検討した。
論文 参考訳(メタデータ) (2020-10-02T10:41:59Z) - A black-box adversarial attack for poisoning clustering [78.19784577498031]
本稿では,クラスタリングアルゴリズムのロバスト性をテストするために,ブラックボックス対逆攻撃法を提案する。
我々の攻撃は、SVM、ランダムフォレスト、ニューラルネットワークなどの教師付きアルゴリズムに対しても転送可能であることを示す。
論文 参考訳(メタデータ) (2020-09-09T18:19:31Z) - F2A2: Flexible Fully-decentralized Approximate Actor-critic for
Cooperative Multi-agent Reinforcement Learning [110.35516334788687]
分散マルチエージェント強化学習アルゴリズムは複雑なアプリケーションでは実践的でないことがある。
本稿では,大規模で汎用的なマルチエージェント設定を扱える,柔軟な完全分散型アクター批判型MARLフレームワークを提案する。
当社のフレームワークは,大規模環境におけるスケーラビリティと安定性を実現し,情報伝達を低減できる。
論文 参考訳(メタデータ) (2020-04-17T14:56:29Z) - Monotonic Value Function Factorisation for Deep Multi-Agent
Reinforcement Learning [55.20040781688844]
QMIXは、中央集権的なエンドツーエンドで分散ポリシーをトレーニングできる新しい価値ベースの手法である。
深層多エージェント強化学習のための新しいベンチマークとして,StarCraft Multi-Agent Challenge (SMAC)を提案する。
論文 参考訳(メタデータ) (2020-03-19T16:51:51Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳(メタデータ) (2020-03-04T07:36:38Z) - Byzantine-resilient Decentralized Stochastic Gradient Descent [85.15773446094576]
分散学習システムのビザンチンレジリエンスに関する詳細な研究について述べる。
ビザンチンフォールトトレランスを用いた分散学習を支援する新しいアルゴリズムUBARを提案する。
論文 参考訳(メタデータ) (2020-02-20T05:11:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。