論文の概要: Two-timescale Extragradient for Finding Local Minimax Points
- arxiv url: http://arxiv.org/abs/2305.16242v2
- Date: Mon, 22 Apr 2024 12:06:46 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-24 01:22:08.947655
- Title: Two-timescale Extragradient for Finding Local Minimax Points
- Title(参考訳): 局所極小点探索のための2時間外勾配法
- Authors: Jiseok Chae, Kyuwon Kim, Donghwan Kim,
- Abstract要約: ミニマックス問題の解法として, 2時間スケールのエクストラグレード法が有効であることを示す。
この研究は、局所ミニマックス点の発見に関する過去のすべての結果に対して、確実に改善する。
- 参考スコア(独自算出の注目度): 8.056359341994941
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Minimax problems are notoriously challenging to optimize. However, we present that the two-timescale extragradient method can be a viable solution. By utilizing dynamical systems theory, we show that it converges to points that satisfy the second-order necessary condition of local minimax points, under mild conditions that the two-timescale gradient descent ascent fails to work. This work provably improves upon all previous results on finding local minimax points, by eliminating a crucial assumption that the Hessian with respect to the maximization variable is nondegenerate.
- Abstract(参考訳): Minimaxの問題は最適化が難しいことで有名だ。
しかし, 2 時間スケールの指数勾配法は, 実現可能な解である可能性が示唆された。
力学系理論を利用して、局所極小点の2階必要条件を満たす点に収束することを示した。
この研究は、最大化変数に関するヘッセンが非退化であるという決定的な仮定を排除し、局所極小点を求める以前のすべての結果に対して証明的に改善する。
関連論文リスト
- Near-Optimal Algorithms for Making the Gradient Small in Stochastic
Minimax Optimization [14.719077076351377]
本研究では,スムーズなミニマックス最適化のための準定常点を求める問題について検討する。
Recursive IteratioNRAINと呼ばれる新しいアルゴリズムは凸凹と強凹の両方のケースを実現する。
論文 参考訳(メタデータ) (2022-08-11T16:55:26Z) - 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) - Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
バイレベル最適化は、機械学習における問題の1つだ。
双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
論文 参考訳(メタデータ) (2022-02-08T07:10:06Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳(メタデータ) (2021-02-15T07:10:33Z) - Escaping Saddle Points for Nonsmooth Weakly Convex Functions via
Perturbed Proximal Algorithms [0.0]
主な結果は、非滑らか関数に対する$epsilon$-approximate Local minimumの新たな特徴に基づいている。
標準的な仮定では、摂動近位点、摂動近位勾配、摂動近位線形アルゴリズムは非滑らかな凸関数に対して$epsilon$-approximate局所最小値を求める。
論文 参考訳(メタデータ) (2021-02-04T19:17:13Z) - 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) - Optimality and Stability in Non-Convex Smooth Games [39.365235811852365]
興味深い概念は局所ミニマックス点(英語版)として知られているが、これは降下と強く相関している。
勾配アルゴリズムは非退化の場合、局所的/言語的極小点に収束するが、一般的には失敗する。
これは、未知の滑らかなゲームにおいて、新しいアルゴリズムまたはサドル点を超える概念が必要であることを意味する。
論文 参考訳(メタデータ) (2020-02-27T02:16:01Z) - Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max
Optimization [61.66927778694731]
エポッチ勾配降下法(エポッチ勾配降下法、Epoch-GD)は、2011年にHazan and Kaleによって提唱された。
Epoch-GDA が SCSC min-max 問題の双対性ギャップに対して$O (1/T) の最適レートを達成できることを示す最初の実験である。
論文 参考訳(メタデータ) (2020-02-13T02:16:57Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳(メタデータ) (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。