Fugu-MT 論文翻訳(概要): A Communication-efficient Algorithm with Linear Convergence for Federated Minimax Learning

論文の概要: A Communication-efficient Algorithm with Linear Convergence for Federated Minimax Learning

arxiv url: http://arxiv.org/abs/2206.01132v2
Date: Tue, 6 Jun 2023 16:17:23 GMT
ステータス: 処理完了
システム内更新日: 2023-06-08 00:04:15.219279
Title: A Communication-efficient Algorithm with Linear Convergence for Federated Minimax Learning
Title（参考訳）: フェデレーションミニマックス学習のための線形収束型通信効率アルゴリズム
Authors: Zhenyu Sun, Ermin Wei
Abstract要約: GAN(Geneimation Adversarial Networks)をモデル化した大規模マルチエージェントミニマックス最適化問題について検討する。全体的な目的は、エージェントのプライベートなローカルな目的関数の総和である。我々は,FedGDA-GTが,大域的な$epsilon GDA解に一定のステップサイズで線形収束することを示した。
参考スコア（独自算出の注目度）: 1.713291434132985
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper, we study a large-scale multi-agent minimax optimization problem, which models many interesting applications in statistical learning and game theory, including Generative Adversarial Networks (GANs). The overall objective is a sum of agents' private local objective functions. We first analyze an important special case, empirical minimax problem, where the overall objective approximates a true population minimax risk by statistical samples. We provide generalization bounds for learning with this objective through Rademacher complexity analysis. Then, we focus on the federated setting, where agents can perform local computation and communicate with a central server. Most existing federated minimax algorithms either require communication per iteration or lack performance guarantees with the exception of Local Stochastic Gradient Descent Ascent (SGDA), a multiple-local-update descent ascent algorithm which guarantees convergence under a diminishing stepsize. By analyzing Local SGDA under the ideal condition of no gradient noise, we show that generally it cannot guarantee exact convergence with constant stepsizes and thus suffers from slow rates of convergence. To tackle this issue, we propose FedGDA-GT, an improved Federated (Fed) Gradient Descent Ascent (GDA) method based on Gradient Tracking (GT). When local objectives are Lipschitz smooth and strongly-convex-strongly-concave, we prove that FedGDA-GT converges linearly with a constant stepsize to global $\epsilon$-approximation solution with $\mathcal{O}(\log (1/\epsilon))$ rounds of communication, which matches the time complexity of centralized GDA method. Finally, we numerically show that FedGDA-GT outperforms Local SGDA.
Abstract（参考訳）: 本稿では,GAN(Generative Adversarial Networks)を含む,統計学習やゲーム理論における多くの興味深い応用をモデル化した大規模マルチエージェントミニマックス最適化問題について検討する。全体的な目的は、エージェントのプライベートなローカルな目的関数の総和である。まず, 統計的サンプルを用いて, 全体目標が真の個体群ミニマックスリスクに近似する, 経験的ミニマックス問題 (experience minimax problem) を考察した。我々はラデマッハ複雑性解析を通じて,この目的を学習するための一般化境界を提供する。次に、エージェントがローカル計算を実行し、中央サーバと通信できるフェデレーション設定に焦点を当てる。既存のフェデレートされたミニマックスアルゴリズムは、局所確率勾配上昇(SGDA)を除いて、イテレーション毎の通信を必要とするか、性能保証が欠如している。局所sgdaを勾配雑音のない理想条件で解析することにより, 一般に, 定常ステップによる完全収束を保証できず, 収束速度が遅いことを示す。この問題に対処するため,グラディエントトラッキング(GT)に基づく改良型Federated (Fed) Gradient Descent Ascent (GDA)法であるFedGDA-GTを提案する。局所的な目的がリプシッツの滑らかかつ強凸-強対流であるとき、FedGDA-GTは、集中型GDA法の時間的複雑さに一致する$\mathcal{O}(\log (1/\epsilon))$ラウンドで、大域的な$\epsilon$-approximationソリューションへと線形に収束することが証明される。最後に,FedGDA-GTがローカルSGDAより優れていることを示す。

関連論文リスト

On the Convergence of Multi-objective Optimization under Generalized Smoothness [27.87166415148172]
我々はより一般的で現実的な$ell$-smooth損失関数のクラスを研究し、$ell$は一般の非減少関数ノルムである。我々は、$ell$-smooth Generalized Multi-MOO GradientGradと、その変種である Generalized Smooth Multi-MOO descentの2つの新しいアルゴリズムを開発した。私たちのアルゴリズムは、より厳密な$mathcalO(epsilon-2)$を各イテレーションで、より多くのサンプルを使って保証します。
論文参考訳（メタデータ） (2024-05-29T18:36:59Z)
Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。本稿では,2種類のミニマックスアルゴリズムを提案する。そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文参考訳（メタデータ） (2023-02-08T01:42:45Z)
Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文参考訳（メタデータ） (2022-11-14T12:32:18Z)
SGDA with shuffling: faster convergence for nonconvex-P{\L} minimax optimization [18.668531108219415]
逐次降下勾配(SGDA)を用いた最小最適化問題に対する理論的アプローチを提案する。我々は,ポリアック・ロジャシエヴィチ(PL)幾何を用いて,非凹凸対象に対するSGDA-LLの同時的および交互的目的を解析した。我々のレートはミニバッチGDARRにも拡張され、完全な勾配勾配降下勾配 (GDA) の既知率はほとんど回復しない。最後に, 2 時間スケール GDA の包括的下限について述べる。
論文参考訳（メタデータ） (2022-10-12T08:05:41Z)
Federated Minimax Optimization: Improved Convergence Analyses and Algorithms [32.062312674333775]
我々は、最小限の最適化を考慮し、GANのようなモダンな機械学習アプリケーションの多くを普及させています。我々は,既存の文献における収束通信の保証を改善する,新しい,より厳密な解析アルゴリズムを提案する。
論文参考訳（メタデータ） (2022-03-09T16:21:31Z)
Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文参考訳（メタデータ） (2021-10-20T02:25:25Z)
Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Minimax Problems [80.46370778277186]
大規模凸凹型ミニマックス問題は、ゲーム理論、堅牢なトレーニング、生成的敵ネットワークのトレーニングなど、多くの応用で発生する。通信効率のよい分散外グレードアルゴリズムであるLocalAdaSientを開発した。サーバモデル。等質な環境と異質な環境の両方において,その有効性を実証する。
論文参考訳（メタデータ） (2021-06-18T09:42:05Z)
Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency [15.04034188283642]
Local SGDは分散学習における通信オーバーヘッドを克服するための有望なアプローチである。局所sgdaは均質データと異質データの両方において分散ミニマックス問題を確実に最適化できることを示す。
論文参考訳（メタデータ） (2021-02-25T20:15:18Z)
Proximal Gradient Descent-Ascent: Variable Convergence under K{\L} Geometry [49.65455534654459]
有限降下指数パラメータ (GDA) はミニマックス最適化問題の解法として広く応用されている。本稿では、KL-L型幾何学の収束を研究することにより、そのようなギャップを埋める。
論文参考訳（メタデータ） (2021-02-09T05:35:53Z)
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates [70.9701218475002]
分散通信方式の統一収束解析を導入する。いくつかの応用に対して普遍収束率を導出する。私たちの証明は弱い仮定に依存している。
論文参考訳（メタデータ） (2020-03-23T17:49:15Z)
Replica Exchange for Non-Convex Optimization [4.421561004829125]
勾配降下(GD)は凸目的関数に対して急速に収束することが知られているが、局所的なミニマに閉じ込められることがある。ランゲヴィン力学(LD)は状態空間を探索し、大域的な最小値を見つけることができるが、正確な推定を得るためには、LDは小さな離散化ステップサイズで実行し、弱い力を検証する必要がある。本稿では,これら2つのアルゴリズムとその非スワッピング変種が,単純な交換機構によって協調可能であることを示す。
論文参考訳（メタデータ） (2020-01-23T03:13:19Z)

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

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