Fugu-MT 論文翻訳(概要): Optimality and Stability in Federated Learning: A Game-theoretic Approach

論文の概要: Optimality and Stability in Federated Learning: A Game-theoretic Approach

arxiv url: http://arxiv.org/abs/2106.09580v1
Date: Thu, 17 Jun 2021 15:03:51 GMT
ステータス: 処理完了
システム内更新日: 2021-06-18 15:35:27.115690
Title: Optimality and Stability in Federated Learning: A Game-theoretic Approach
Title（参考訳）: フェデレーション学習における最適性と安定性:ゲーム理論的アプローチ
Authors: Kate Donahue and Jon Kleinberg
Abstract要約: 我々は,フェデレーションエージェント(プレーヤ)の平均誤差率によって与えられる最適性の概念を動機付け,定義する。まず、パラメータ空間のいくつかの領域に対して、すべての安定な配置が最適である(アナーキーの値が 1 に等しい)ことを示す。しかし、これはすべての設定に当てはまるものではなく、最適よりも高いコストで安定な配置の例が存在する(AnaarchyのPrice of Anarchy larger than 1)。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Federated learning is a distributed learning paradigm where multiple agents, each only with access to local data, jointly learn a global model. There has recently been an explosion of research aiming not only to improve the accuracy rates of federated learning, but also provide certain guarantees around social good properties such as total error. One branch of this research has taken a game-theoretic approach, and in particular, prior work has viewed federated learning as a hedonic game, where error-minimizing players arrange themselves into federating coalitions. This past work proves the existence of stable coalition partitions, but leaves open a wide range of questions, including how far from optimal these stable solutions are. In this work, we motivate and define a notion of optimality given by the average error rates among federating agents (players). First, we provide and prove the correctness of an efficient algorithm to calculate an optimal (error minimizing) arrangement of players. Next, we analyze the relationship between the stability and optimality of an arrangement. First, we show that for some regions of parameter space, all stable arrangements are optimal (Price of Anarchy equal to 1). However, we show this is not true for all settings: there exist examples of stable arrangements with higher cost than optimal (Price of Anarchy greater than 1). Finally, we give the first constant-factor bound on the performance gap between stability and optimality, proving that the total error of the worst stable solution can be no higher than 9 times the total error of an optimal solution (Price of Anarchy bound of 9).
Abstract（参考訳）: フェデレートラーニング(Federated Learning)は、複数のエージェントがローカルデータのみにアクセスし、グローバルモデルと共同で学習する分散ラーニングパラダイムである。近年,フェデレーション学習の精度向上だけでなく,総誤差などの社会的良質性に関する確実な保証も目指す研究が急増している。この研究の一分野はゲーム理論的なアプローチを採っており、特に以前の研究では、フェデレーション学習をヘドニックゲームと見なしており、エラー最小化プレイヤーはフェデレーション連立に配置している。この過去の研究は、安定した連立分割の存在を証明しているが、これらの安定解がどの程度最適から遠いかなど、幅広い疑問が残る。本研究では,フェデレーションエージェント(プレイヤー)の平均誤差率によって与えられる最適性の概念を動機付け,定義する。まず、プレイヤーの最適配置(誤差最小化)を計算するための効率的なアルゴリズムの正確性を示し、証明する。次に,アレンジメントの安定性と最適性の関係を分析する。まず、パラメータ空間のある領域において、全ての安定配置が最適であることを示す(アナーキーの価格が 1 に等しい)。しかし、これはすべての設定に当てはまるものではなく、最適よりも高いコストで安定な配置の例が存在する(AnaarchyのPrice of Anarchy larger than 1)。最後に、安定性と最適性の間の性能ギャップに対する最初の定数係数を与え、最悪の安定解の総誤差が最適解の総誤差の9倍に満たないことを証明した(アナキリ限界の9倍)。

関連論文リスト

Stable Matching with Ties: Approximation Ratios and Learning [20.84610303094647]
我々は、市場の一方が他方の会員に対して厳格な嗜好を必ずしも持たないような、市場と結びつきのある市場との整合性の問題について検討する。我々は,各作業員が最良で安定したマッチングにおいて,ユーティリティから最大のシェアを確保できるようにすることを目標としている。
論文参考訳（メタデータ） (2024-11-05T17:14:46Z)
Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
論文参考訳（メタデータ） (2024-06-05T08:02:40Z)
Distributed Fractional Bayesian Learning for Adaptive Optimization [7.16937736207894]
本稿では,各エージェントが共通パラメータを持つローカルコスト関数にのみアクセス可能な分散適応最適化問題について考察する。分散最適化問題におけるパラメータの不確実性に対処し、同時に最適解を見つけるための貴重な洞察を提供することを目的としている。
論文参考訳（メタデータ） (2024-04-17T13:09:33Z)
Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
論文参考訳（メタデータ） (2023-10-21T18:38:13Z)
Offline Learning in Markov Games with General Function Approximation [22.2472618685325]
マルコフゲームにおけるオフラインマルチエージェント強化学習(RL)について検討する。マルコフゲームにおけるサンプル効率のよいオフライン学習のための最初のフレームワークを提供する。
論文参考訳（メタデータ） (2023-02-06T05:22:27Z)
Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文参考訳（メタデータ） (2022-11-29T05:52:17Z)
Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文参考訳（メタデータ） (2022-01-28T05:53:28Z)
Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。次に,政策最適化におけるコミット率の概念を紹介する。第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
論文参考訳（メタデータ） (2021-10-29T06:35:44Z)
Achieving Statistical Optimality of Federated Learning: Beyond Stationary Points [19.891597817559038]
Federated Learning(FL)は、プライバシ保護とクラウドでの計算負荷の低減に大きな可能性を持つ、有望なフレームワークである。最近の研究は、(1)その固定点が元の最適化問題の定常点に対応していないこと、(2)見いだされた共通モデルが局所的にうまく一般化できないこと、の2つの方法に対する懸念を提起している。一般的なカーネル回帰設定では、FedAvgとFedProxの両方が極小最大誤差率に収束することを示す。
論文参考訳（メタデータ） (2021-06-29T09:59:43Z)
A Hybrid 2-stage Neural Optimization for Pareto Front Extraction [3.918940900258555]
最適なトレードオフソリューションに対する大きな障害は、それらが必ずしも互いに収束しないことです。正確かつ費用対効果の高い二段階アプローチを提案する。
論文参考訳（メタデータ） (2021-01-27T20:56:19Z)
An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文参考訳（メタデータ） (2020-10-23T09:12:47Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。