論文の概要: Byzantine-Robust Federated Linear Bandits
- arxiv url: http://arxiv.org/abs/2204.01155v1
- Date: Sun, 3 Apr 2022 20:22:26 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-05 14:13:07.482449
- Title: Byzantine-Robust Federated Linear Bandits
- Title（参考訳）: ビザンチン・ロバスト連合線形バンド
- Authors: Ali Jadbabaie, Haochuan Li, Jian Qian, Yi Tian
- Abstract要約: 分散エージェントの集合が共通の線形帯域モデルを協調的に学習するフェデレート環境で線形帯域最適化問題を研究する。
標準的な連邦学習アルゴリズムは、少数のエージェントに対するビザンチン攻撃に対して脆弱である。
提案アルゴリズムは, エージェントの半数未満に対するビザンチン攻撃に対して堅牢であり, サブ線形$tildemathcalO(T3/4)$ regret with $mathcalO(sqrtT)$ steps of communicationを実現している。
- 参考スコア（独自算出の注目度）: 27.77095339417368
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study a linear bandit optimization problem in a federated
setting where a large collection of distributed agents collaboratively learn a
common linear bandit model. Standard federated learning algorithms applied to
this setting are vulnerable to Byzantine attacks on even a small fraction of
agents. We propose a novel algorithm with a robust aggregation oracle that
utilizes the geometric median. We prove that our proposed algorithm is robust
to Byzantine attacks on fewer than half of agents and achieves a sublinear
$\tilde{\mathcal{O}}({T^{3/4}})$ regret with $\mathcal{O}(\sqrt{T})$ steps of
communication in $T$ steps. Moreover, we make our algorithm differentially
private via a tree-based mechanism. Finally, if the level of corruption is
known to be small, we show that using the geometric median of mean oracle for
robust aggregation further improves the regret bound.
- Abstract（参考訳）: 本稿では,分散エージェントの大規模な集合が共同で共通の線形バンディットモデルを学習するフェデレート環境での線形バンディット最適化問題について検討する。
この設定に適用される標準的なフェデレーション学習アルゴリズムは、少数のエージェントに対するビザンチン攻撃に対して脆弱である。
幾何中央値を利用するロバストアグリゲーションオラクルを用いた新しいアルゴリズムを提案する。
提案するアルゴリズムは,約半数以下のエージェントに対するビザンチン攻撃に対して頑健であり,$t$ステップの通信ステップに対して$\mathcal{o}(\sqrt{t})$で後悔するサブ線形$\tilde{\mathcal{o}}({t^{3/4}})が得られることを証明した。
さらに,木に基づく機構によりアルゴリズムを微分プライベートにする。
最後に,汚職のレベルが小さいことが分かっている場合,平均オラクルの幾何学的中央値を用いてロバストアグリゲーションを行うことで,後悔の限界がさらに改善されることを示す。
関連論文リスト
- Multi-Agent Best Arm Identification in Stochastic Linear Bandits [0.7673339435080443]
固定予算シナリオ下での線形包帯における協調的ベストアーム識別の問題について検討する。
学習モデルでは、複数のエージェントがスターネットワークまたはジェネリックネットワークを介して接続され、線形バンディットインスタンスと並列に相互作用すると考えられる。
我々は、スターネットワークとジェネリックネットワークのためのアルゴリズムMaLinBAI-StarとMaLinBAI-Genをそれぞれ考案した。
論文 参考訳（メタデータ） (2024-11-20T20:09:44Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - 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) - Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear
Contextual Bandits and Markov Decision Processes [59.61248760134937]
本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。
提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。
本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
論文 参考訳（メタデータ） (2022-12-12T15:04:56Z) - Collaborative Linear Bandits with Adversarial Agents: Near-Optimal
Regret Bounds [31.5504566292927]
我々は, 後悔を最小限に抑えるために, 中央サーバを介して協調できる$M$エージェントを含む線形帯域幅問題を考える。
これらのエージェントのわずか$alpha$は敵対的であり、任意に作用し、次の緊張に繋がる。
我々は、厳密な信頼区間を慎重に構築し、探索と探索のトレードオフをバランスさせる新しいアルゴリズムを設計する。
論文 参考訳（メタデータ） (2022-06-06T18:16:34Z) - Escaping Saddle Points in Distributed Newton's Method with Communication
efficiency and Byzantine Resilience [49.379254729853756]
我々は、ビザンチン機械の存在下で分散フレームワークにおける非正規化損失関数(サドルポイント付き)を最適化する問題を検討する。
キューブ正規化されたニュートンアルゴリズムを堅牢化し、サドルポイントと偽のローカルミニマを効率的に回避します。
提案手法は, (サブサンプリング) と hessian を含むいくつかの近似設定で理論的に保証される。
論文 参考訳（メタデータ） (2021-03-17T03:53:58Z) - Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
バンディットアルゴリズムを結合する簡単な手法を提案する。
私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
論文 参考訳（メタデータ） (2020-12-24T05:36:29Z) - Decentralized Multi-Agent Linear Bandits with Safety Constraints [31.67685495996986]
本研究では,N$エージェントのネットワークが協調して線形帯域最適化問題を解く分散線形帯域幅について検討する。
ネットワーク全体の累積的後悔を最小限に抑える完全分散アルゴリズム DLUCB を提案する。
私たちのアイデアは、より困難な、安全な盗賊の設定にもかかわらず、自然界に広まっています。
論文 参考訳（メタデータ） (2020-12-01T07:33:00Z) - Consistent $k$-Median: Simpler, Better and Robust [20.692372082600972]
簡単な局所探索に基づくオンラインアルゴリズムでは,O(k2 log2 (nD))$ swaps of centrals (recourse) という問題に対して,バイクリテリア定数を近似することができることを示す。
外れ値のない問題に制限される場合、我々のアルゴリズムはより単純で決定論的であり、近似比とレコメンデーションがより良くなる。
論文 参考訳（メタデータ） (2020-08-13T20:24:28Z) - An Empirical Process Approach to the Union Bound: Practical Algorithms
for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。
サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。
また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-21T00:56:33Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。