論文の概要: Federated Minimax Optimization: Improved Convergence Analyses and
Algorithms
- arxiv url: http://arxiv.org/abs/2203.04850v1
- Date: Wed, 9 Mar 2022 16:21:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-10 20:38:30.295361
- Title: Federated Minimax Optimization: Improved Convergence Analyses and
Algorithms
- Title(参考訳): Federated Minimax Optimization:改良された収束解析とアルゴリズム
- Authors: Pranay Sharma, Rohan Panda, Gauri Joshi and Pramod K. Varshney
- Abstract要約: 我々は、最小限の最適化を考慮し、GANのようなモダンな機械学習アプリケーションの多くを普及させています。
我々は,既存の文献における収束通信の保証を改善する,新しい,より厳密な解析アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 32.062312674333775
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we consider nonconvex minimax optimization, which is gaining
prominence in many modern machine learning applications such as GANs.
Large-scale edge-based collection of training data in these applications calls
for communication-efficient distributed optimization algorithms, such as those
used in federated learning, to process the data. In this paper, we analyze
Local stochastic gradient descent ascent (SGDA), the local-update version of
the SGDA algorithm. SGDA is the core algorithm used in minimax optimization,
but it is not well-understood in a distributed setting. We prove that Local
SGDA has \textit{order-optimal} sample complexity for several classes of
nonconvex-concave and nonconvex-nonconcave minimax problems, and also enjoys
\textit{linear speedup} with respect to the number of clients. We provide a
novel and tighter analysis, which improves the convergence and communication
guarantees in the existing literature. For nonconvex-PL and
nonconvex-one-point-concave functions, we improve the existing complexity
results for centralized minimax problems. Furthermore, we propose a
momentum-based local-update algorithm, which has the same convergence
guarantees, but outperforms Local SGDA as demonstrated in our experiments.
- Abstract(参考訳): 本稿では,GANなどの現代の機械学習アプリケーションにおいて,非凸最小値最適化が注目されている。
これらのアプリケーションにおける大規模エッジベーストレーニングデータの収集は、フェデレーション学習で使用されるような、通信効率のよい分散最適化アルゴリズムを呼び出す。
本稿では,SGDAアルゴリズムの局所更新版である局所確率勾配勾配上昇(SGDA)を解析する。
SGDAはミニマックス最適化で使用されるコアアルゴリズムであるが、分散環境では十分に理解されていない。
局所 sgda が非凸凸および非凸非凸ミニマックス問題のクラスに対して \textit{order-optimal} サンプル複雑性を持つことを証明し、クライアント数に関して \textit{linear speedup} を楽しむ。
既存の文献における収束とコミュニケーションの保証を改善する,新しい,より厳密な分析手法を提案する。
非凸PLおよび非凸1点凹関数に対しては、集中化ミニマックス問題に対する既存の複雑性結果を改善する。
さらに,同じ収束保証を持つモーメントに基づく局所更新アルゴリズムを提案する。
関連論文リスト
- Stability and Generalization for Distributed SGDA [70.97400503482353]
分散SGDAのための安定性に基づく一般化分析フレームワークを提案する。
我々は, 安定性の誤差, 一般化ギャップ, 人口リスクの包括的分析を行う。
理論的結果から,一般化ギャップと最適化誤差のトレードオフが明らかになった。
論文 参考訳(メタデータ) (2024-11-14T11:16:32Z) - Fast Decentralized Gradient Tracking for Federated Minimax Optimization with Local Updates [5.269633789700637]
textttK-GT-Minimaxのデータ不均一性を扱う能力は、フェデレートされた学習研究と応用の進展において、その重要性を浮き彫りにしている。
論文 参考訳(メタデータ) (2024-05-07T17:25:56Z) - Can Decentralized Stochastic Minimax Optimization Algorithms Converge
Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。
本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-04-24T02:19:39Z) - Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax
Problems [39.197569803430646]
最小限の最適化は、敵対的ネットワーク(GAN)や敵対的トレーニングなど、多くの機械学習タスクにおいて重要な役割を果たす。
近年,ミニマックス問題の解法として多種多様な最適化手法が提案されているが,そのほとんどは分散設定を無視している。
論文 参考訳(メタデータ) (2023-04-21T11:38:41Z) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳(メタデータ) (2022-11-14T12:32:18Z) - A Communication-efficient Algorithm with Linear Convergence for
Federated Minimax Learning [1.713291434132985]
GAN(Geneimation Adversarial Networks)をモデル化した大規模マルチエージェントミニマックス最適化問題について検討する。
全体的な目的は、エージェントのプライベートなローカルな目的関数の総和である。
我々は,FedGDA-GTが,大域的な$epsilon GDA解に一定のステップサイズで線形収束することを示した。
論文 参考訳(メタデータ) (2022-06-02T16:31:16Z) - Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD
for Communication Efficient Nonconvex Distributed Learning [58.79085525115987]
ローカル手法は通信時間を短縮する有望なアプローチの1つである。
局所的データセットが局所的損失の滑らかさよりも小さい場合,通信の複雑さは非局所的手法よりも優れていることを示す。
論文 参考訳(メタデータ) (2022-02-12T15:12:17Z) - The Minimax Complexity of Distributed Optimization [0.0]
分散最適化に適用可能な古典的なオラクルフレームワークの拡張である「グラフオラクルモデル」を紹介します。
私は「間欠的コミュニケーション設定」の具体例に焦点をあてる
コンベックス設定におけるSGD(Local Descent)アルゴリズムの理論的特性を解析する。
論文 参考訳(メタデータ) (2021-09-01T15:18:33Z) - Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Minimax
Problems [80.46370778277186]
大規模凸凹型ミニマックス問題は、ゲーム理論、堅牢なトレーニング、生成的敵ネットワークのトレーニングなど、多くの応用で発生する。
通信効率のよい分散外グレードアルゴリズムであるLocalAdaSientを開発した。
サーバモデル。
等質な環境と異質な環境の両方において,その有効性を実証する。
論文 参考訳(メタデータ) (2021-06-18T09:42:05Z) - Second-Order Guarantees in Centralized, Federated and Decentralized
Nonconvex Optimization [64.26238893241322]
単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。
いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。
これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
論文 参考訳(メタデータ) (2020-03-31T16:54:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。