論文の概要: Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems

• arxiv url: http://arxiv.org/abs/2112.09579v1
• Date: Fri, 17 Dec 2021 15:51:04 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-20 18:55:04.559489
• Title: Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems
• Title（参考訳）: 非凸Min-Max問題の解法における2時間スケールグラディエントDescent-Ascent Dynamicsの収束速度
• Authors: Thinh T. Doan
• Abstract要約: 連立勾配降下指数アルゴリズムの連続時間変動の有限時間特性を特徴付ける。 連続時間アルゴリズムの挙動に関する結果は、離散時間アルゴリズムの収束特性を高めるために用いられる。
• 参考スコア（独自算出の注目度）: 2.0305676256390934
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: There are much recent interests in solving noncovnex min-max optimization problems due to its broad applications in many areas including machine learning, networked resource allocations, and distributed optimization. Perhaps, the most popular first-order method in solving min-max optimization is the so-called simultaneous (or single-loop) gradient descent-ascent algorithm due to its simplicity in implementation. However, theoretical guarantees on the convergence of this algorithm is very sparse since it can diverge even in a simple bilinear problem. In this paper, our focus is to characterize the finite-time performance (or convergence rates) of the continuous-time variant of simultaneous gradient descent-ascent algorithm. In particular, we derive the rates of convergence of this method under a number of different conditions on the underlying objective function, namely, two-sided Polyak-L ojasiewicz (PL), one-sided PL, nonconvex-strongly concave, and strongly convex-nonconcave conditions. Our convergence results improve the ones in prior works under the same conditions of objective functions. The key idea in our analysis is to use the classic singular perturbation theory and coupling Lyapunov functions to address the time-scale difference and interactions between the gradient descent and ascent dynamics. Our results on the behavior of continuous-time algorithm may be used to enhance the convergence properties of its discrete-time counterpart.
• Abstract（参考訳）: 機械学習、ネットワークリソース割り当て、分散最適化など、多くの分野で広く応用されているため、非コブネックスのmin-max最適化問題を解決することには、近年の関心がある。 おそらく、min-max最適化の最も一般的な一階法は、実装の単純さから、いわゆる同時(または単ループ)勾配勾配アルゴリズムである。 しかし、このアルゴリズムの収束に関する理論的保証は、単純な双線型問題においても発散できるため、非常に少ない。 本稿では,同時勾配降下・上昇アルゴリズムの連続時間変動の有限時間性能(あるいは収束率)を特徴付けることを目的とする。 特に,本手法の収束速度は,両面のポリアック-L ojasiewicz (PL), 片面のPL, 非凸-強凹, 強凸-非凹面条件など,様々な条件下で導出する。 我々の収束結果は, 目的関数と同じ条件下で, 先行作業の収束結果を改善する。 我々の分析における重要なアイデアは、古典的な特異摂動理論と結合リアプノフ関数を用いて、勾配降下と上昇ダイナミクスの間の時間スケールの違いと相互作用に対処することである。 連続時間アルゴリズムの挙動に関する結果は,その離散時間アルゴリズムの収束特性を高めるために用いられる。

関連論文リスト

• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Generalized Gradient Flows with Provable Fixed-Time Convergence and Fast Evasion of Non-Degenerate Saddle Points [8.452349885923507]
  グラディエントベースの1次凸最適化アルゴリズムは、機械学習タスクを含むさまざまな領域で広く適用可能である。 最適時間の固定時間理論の最近の進歩に触発されて,高速化最適化アルゴリズムを設計するための枠組みを導入する。 非ド・サドル点を許容する関数に対しては、これらのサドル点を避けるのに必要な時間は初期条件すべてに一様有界であることを示す。
  論文  参考訳（メタデータ） (2022-12-07T16:36:23Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
  論文  参考訳（メタデータ） (2022-03-30T11:39:00Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• Limiting Behaviors of Nonconvex-Nonconcave Minimax Optimization via Continuous-Time Systems [10.112779201155005]
  3つの古典的ミニマックスアルゴリズム(AGDA, AscentGDA, Exgradient Method, EGM)の制限挙動について検討する。 本稿では,GAN(Generative Adrial Networks)において,全ての制限行動が発生しうることを数値的に観察し,様々なGAN問題に対して容易に実演できることを示す。
  論文  参考訳（メタデータ） (2020-10-20T21:14:51Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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