論文の概要: Don't Fix What ain't Broke: Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization

• arxiv url: http://arxiv.org/abs/2102.09468v1
• Date: Thu, 18 Feb 2021 16:39:35 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-19 14:25:30.497379
• Title: Don't Fix What ain't Broke: Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization
• Title（参考訳）: 故障しないものを修正するな: 極小最適化のための交互勾配Descent-Ascentの局所収束
• Authors: Guodong Zhang, Yuanhao Wang, Laurent Lessard, Roger Grosse
• Abstract要約: 交互降下度(Alt-GDA)は多くの設定において同時降下度(Sim-GDA)よりも優れている。 強凹問題に対してalt-gdaが最適に近い局所収束率を達成することを示す。 特に,Alt-GDAが強凹問題に対してほぼ最適局所収束率を達成することを証明した。
• 参考スコア（独自算出の注目度）: 24.236441934607154
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Minimax optimization has recently gained a lot of attention as adversarial architectures and algorithms proliferate. Often, smooth minimax games proceed by simultaneous or alternating gradient updates. Although algorithms with alternating updates are commonly used in practice for many applications (e.g., GAN training), the majority of existing theoretical analyses focus on simultaneous algorithms. In this paper, we study alternating gradient descent-ascent (Alt-GDA) in minimax games and show that Alt-GDA is superior to its simultaneous counterpart (Sim-GDA) in many settings. In particular, we prove that Alt-GDA achieves a near-optimal local convergence rate for strongly-convex strongly-concave problems while Sim-GDA converges with a much slower rate. Moreover, we show that the acceleration effect of alternating updates remains when the minimax problem has only strong concavity in the dual variables. Numerical experiments on quadratic minimax games validate our claims. Additionally, we demonstrate that alternating updates speed up GAN training significantly and the use of optimism only helps for simultaneous algorithms.
• Abstract（参考訳）: 敵アーキテクチャやアルゴリズムの普及に伴い,Minimaxの最適化が注目されている。 しばしば、スムーズなミニマックスゲームは、同時にまたは交互に勾配を更新する。 更新を交互に行うアルゴリズムは、多くのアプリケーション(例えば GAN トレーニング)で一般的に使われているが、既存の理論分析のほとんどは同時アルゴリズムに重点を置いている。 本稿では,ミニマックスゲームにおける勾配降下上昇(Alt-GDA)を交互に検討し,多くの場面でAlt-GDAが同等(Sim-GDA)よりも優れていることを示す。 特に、Alt-GDAが強凸強凸問題に対してほぼ最適局所収束率を達成するのに対し、Sim-GDAははるかに遅い速度で収束することを示す。 さらに, 交互更新の加速効果は, ミニマックス問題が双対変数の強い凹凸のみを持つ場合にも継続することを示した。 二次ミニマックスゲームにおける数値実験は我々の主張を検証する。 さらに、更新の交互化によってGANトレーニングが大幅にスピードアップし、最適化の使用は同時アルゴリズムにしか役立ちません。

関連論文リスト

• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。 我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
  論文  参考訳（メタデータ） (2024-08-21T20:14:54Z)
• Fundamental Benefit of Alternating Updates in Minimax Optimization [15.170534286366744]
  Gradient Descent-Ascent gradients (GDA) アルゴリズムは、最小限の最適化問題を解決するために設計されている。 Alt-GDAはイテレーションを早く収束させるのが一般的であるが、両者のパフォーマンスギャップはまだよく理解されていない。 本稿では,強いコンケーブとリプシッツの勾配目的に対する両アルゴリズムの微細収束解析について述べる。
  論文  参考訳（メタデータ） (2024-02-16T06:41:35Z)
• ELRA: Exponential learning rate adaption gradient descent optimization method [83.88591755871734]
  我々は, 高速(指数率), ab initio(超自由)勾配に基づく適応法を提案する。 本手法の主な考え方は,状況認識による$alphaの適応である。 これは任意の次元 n の問題に適用でき、線型にしかスケールできない。
  論文  参考訳（メタデータ） (2023-09-12T14:36:13Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• Min-Max Optimization under Delays [26.830212508878162]
  大規模な機械学習問題では遅延と非同期は避けられない。 min-max最適化に類似した理論は存在しない。 たとえ小さな遅延であっても、エクストラグラディエントのような顕著なアルゴリズムが分岐する可能性があることを示す。
  論文  参考訳（メタデータ） (2023-07-13T16:39:01Z)
• Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
  分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。 本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-24T02:19:39Z)
• Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
  本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。 運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
  論文  参考訳（メタデータ） (2022-11-14T12:32:18Z)
• Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization [108.35402316802765]
  本稿では,新しい一階最適化アルゴリズムであるAcceleratedGradient-OptimisticGradient (AG-OG) Ascentを提案する。 我々はAG-OGが様々な設定に対して最適収束率(定数まで)を達成することを示す。 アルゴリズムを拡張して設定を拡張し、bi-SC-SCとbi-C-SCの両方で最適な収束率を達成する。
  論文  参考訳（メタデータ） (2022-10-31T17:59:29Z)
• HessianFR: An Efficient Hessian-based Follow-the-Ridge Algorithm for Minimax Optimization [18.61046317693516]
  HessianFR は理論的な保証を持つ効率的な Hessian-based Follow-the-Ridge アルゴリズムである。 合成および実世界の大規模画像データセットを用いてGAN(Generative Adversarial Network)のトレーニング実験を行った。
  論文  参考訳（メタデータ） (2022-05-23T04:28:52Z)
• Federated Minimax Optimization: Improved Convergence Analyses and Algorithms [32.062312674333775]
  我々は、最小限の最適化を考慮し、GANのようなモダンな機械学習アプリケーションの多くを普及させています。 我々は,既存の文献における収束通信の保証を改善する,新しい,より厳密な解析アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-03-09T16:21:31Z)
• Solve Minimax Optimization by Anderson Acceleration [5.900781483345349]
  勾配降下上昇(GDA)は、その単純さから最もよく使われるアルゴリズムである。 本稿では,GDA力学を固定点反復とみなす新しいミニマックス最適化フレームワークGDA-AMを提案する。 理論上,このアルゴリズムは温和条件下での双線形問題に対する大域収束を実現することができることを示す。
  論文  参考訳（メタデータ） (2021-10-06T02:08:54Z)

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

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