論文の概要: Limiting Behaviors of Nonconvex-Nonconcave Minimax Optimization via Continuous-Time Systems

• arxiv url: http://arxiv.org/abs/2010.10628v2
• Date: Thu, 4 Mar 2021 18:09:47 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-05 07:57:38.252630
• Title: Limiting Behaviors of Nonconvex-Nonconcave Minimax Optimization via Continuous-Time Systems
• Title（参考訳）: 非凸非凸ミニマックス最適化の連続時間系による限界挙動
• Authors: Benjamin Grimmer, Haihao Lu, Pratik Worah, Vahab Mirrokni
• Abstract要約: 3つの古典的ミニマックスアルゴリズム(AGDA, AscentGDA, Exgradient Method, EGM)の制限挙動について検討する。 本稿では,GAN(Generative Adrial Networks)において,全ての制限行動が発生しうることを数値的に観察し,様々なGAN問題に対して容易に実演できることを示す。
• 参考スコア（独自算出の注目度）: 10.112779201155005
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Unlike nonconvex optimization, where gradient descent is guaranteed to converge to a local optimizer, algorithms for nonconvex-nonconcave minimax optimization can have topologically different solution paths: sometimes converging to a solution, sometimes never converging and instead following a limit cycle, and sometimes diverging. In this paper, we study the limiting behaviors of three classic minimax algorithms: gradient descent ascent (GDA), alternating gradient descent ascent (AGDA), and the extragradient method (EGM). Numerically, we observe that all of these limiting behaviors can arise in Generative Adversarial Networks (GAN) training and are easily demonstrated for a range of GAN problems. To explain these different behaviors, we study the high-order resolution continuous-time dynamics that correspond to each algorithm, which results in the sufficient (and almost necessary) conditions for the local convergence by each method. Moreover, this ODE perspective allows us to characterize the phase transition between these different limiting behaviors caused by introducing regularization as Hopf Bifurcations.
• Abstract（参考訳）: 非凸最適化とは異なり、勾配降下は局所最適化に収束することが保証されるが、非凸非凹極小最適化のアルゴリズムは位相的に異なる解経路を持つことがある。 本稿では,勾配降下上昇法(gda),交流勾配降下上昇法(agda),超勾配法(egm)の3つの古典的なminimaxアルゴリズムの限界挙動について検討する。 本稿では,これらの制限行動がGAN(Generative Adversarial Networks)トレーニングで発生し,多様なGAN問題に対して容易に実証できることを観察する。 これらの異なる挙動を説明するために、各アルゴリズムに対応する高次分解能連続時間ダイナミクスについて検討し、各手法による局所収束に十分な(そしてほぼ必要)条件を導出する。 さらに、この ode の視点により、ホップ分岐として正規化を導入することによって引き起こされるこれらの異なる制限挙動間の位相遷移を特徴付けることができる。

関連論文リスト

• Convergence of mean-field Langevin dynamics: Time and space discretization, stochastic gradient, and variance reduction [49.66486092259376]
  平均場ランゲヴィンダイナミクス(英: mean-field Langevin dynamics、MFLD)は、分布依存のドリフトを含むランゲヴィン力学の非線形一般化である。 近年の研究では、MFLDは測度空間で機能するエントロピー規則化された凸関数を地球規模で最小化することが示されている。 有限粒子近似,時間分散,勾配近似による誤差を考慮し,MFLDのカオスの均一時間伝播を示す枠組みを提供する。
  論文  参考訳（メタデータ） (2023-06-12T16:28:11Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems [2.0305676256390934]
  連立勾配降下指数アルゴリズムの連続時間変動の有限時間特性を特徴付ける。 連続時間アルゴリズムの挙動に関する結果は、離散時間アルゴリズムの収束特性を高めるために用いられる。
  論文  参考訳（メタデータ） (2021-12-17T15:51:04Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。 我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
  論文  参考訳（メタデータ） (2021-08-18T09:26:17Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• Conditional Gradient Methods for Convex Optimization with General Affine and Nonlinear Constraints [8.643249539674612]
  本稿では,一般アフィンおよび非線形制約を用いた凸最適化問題に対する条件勾配法を提案する。 まず、スムーズかつ構造化された非滑らかな関数制約凸最適化に対して、$cal O (1/epsilon2)$の反復複雑性を達成できる新しい制約外挿条件勾配(CoexCG)法を提案する。 さらに,制約外挿法と二重正規化条件勾配法(CoexDurCG)の新たな変種を開発した。
  論文  参考訳（メタデータ） (2020-06-30T23:49:38Z)
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems [39.13924898972611]
  非minimaxewicz問題は、生成的対向ネットワークと対向学習の応用において頻繁に現れる。 一定の大きさのGDAアルゴリズムは凸設定でも潜在的に分岐する可能性がある。 AGDAアルゴリズムは、サブレートに達する速度でグローバルに収束する。
  論文  参考訳（メタデータ） (2020-02-22T04:20:37Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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