論文の概要: 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階必要条件を満たす点に収束することを示した。
この研究は、最大化変数に関するヘッセンが非退化であるという決定的な仮定を排除し、局所極小点を求める以前のすべての結果に対して証明的に改善する。
関連論文リスト
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Randomized Gradient Descents on Riemannian Manifolds: Almost Sure Convergence to Global Minima in and beyond Quantum Optimization [0.0]
本研究では,スムーズなコスト関数の最小化を目的とした勾配流の接空間方向のランダム化について検討する。
我々は,サドル点が存在するにもかかわらず,局所最適点への収束がほぼ確実に得られることを証明した。
簡単な2次元設定でサドル点を通過させるのに必要な時間について論じる。
論文 参考訳（メタデータ） (2024-05-20T14:06:45Z) - Near-Optimal Algorithms for Making the Gradient Small in Stochastic
Minimax Optimization [14.719077076351377]
本研究では,スムーズなミニマックス最適化のための準定常点を求める問題について検討する。
Recursive IteratioNRAINと呼ばれる新しいアルゴリズムは凸凹と強凹の両方のケースを実現する。
論文 参考訳（メタデータ） (2022-08-11T16:55:26Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。