論文の概要: Escaping Saddle Points in Nonconvex Minimax Optimization via Cubic-Regularized Gradient Descent-Ascent

• arxiv url: http://arxiv.org/abs/2110.07098v2
• Date: Fri, 15 Oct 2021 00:55:49 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-18 10:52:50.131932
• Title: Escaping Saddle Points in Nonconvex Minimax Optimization via Cubic-Regularized Gradient Descent-Ascent
• Title（参考訳）: 立方体正規化勾配降下法による非凸ミニマックス最適化におけるサドル点の脱出
• Authors: Ziyi Chen, Qunwei Li, Yi Zhou
• Abstract要約: 勾配降下度アルゴリズム(GDA)は、非ミニマックス最適化問題の解法として広く応用されている。 我々は,非コンケーブ極小最適化における点のエスケープのための第一型GDAアルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 13.565010494569243
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The gradient descent-ascent (GDA) algorithm has been widely applied to solve nonconvex minimax optimization problems. However, the existing GDA-type algorithms can only find first-order stationary points of the envelope function of nonconvex minimax optimization problems, which does not rule out the possibility to get stuck at suboptimal saddle points. In this paper, we develop Cubic-GDA -- the first GDA-type algorithm for escaping strict saddle points in nonconvex-strongly-concave minimax optimization. Specifically, the algorithm uses gradient ascent to estimate the second-order information of the minimax objective function, and it leverages the cubic regularization technique to efficiently escape the strict saddle points. Under standard smoothness assumptions on the objective function, we show that Cubic-GDA admits an intrinsic potential function whose value monotonically decreases in the minimax optimization process. Such a property leads to a desired global convergence of Cubic-GDA to a second-order stationary point at a sublinear rate. Moreover, we analyze the convergence rate of Cubic-GDA in the full spectrum of a gradient dominant-type nonconvex geometry. Our result shows that Cubic-GDA achieves an orderwise faster convergence rate than the standard GDA for a wide spectrum of gradient dominant geometry. Our study bridges minimax optimization with second-order optimization and may inspire new developments along this direction.
• Abstract（参考訳）: 勾配降下度(GDA)アルゴリズムは非凸極小最適化問題に広く応用されている。 しかし、既存のGDA型アルゴリズムでは、非凸極小最適化問題のエンベロープ関数の1次定常点しか見つからないため、準最適サドル点で立ち往生する可能性を排除できない。 本稿では,非凸強凸ミニマックス最適化において,厳密な鞍点から逃れる最初のgda型アルゴリズムであるcubic-gdaを開発した。 特に、このアルゴリズムは勾配上昇を用いてミニマックス目的関数の2次情報を推定し、立方体正規化技術を利用して厳密な鞍点を効率的に回避する。 目的関数の標準滑らか性仮定の下では、立方体-GDA はミニマックス最適化過程において単調に値が減少する固有ポテンシャル関数を許容することを示す。 そのような性質は、cubic-gdaの所望のグローバル収束をサブリニアレートの2次定常点へと導く。 さらに,勾配支配型非凸幾何学の全スペクトルにおける立方体gdaの収束速度を解析した。 以上の結果から,立方体-GDAは勾配支配幾何学の幅広いスペクトルに対して標準GDAよりも次々に高速な収束速度が得られることが示された。 本研究は,2次最適化によるミニマックス最適化を橋渡しし,この方向に新たな展開をもたらす可能性がある。

関連論文リスト

• 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)
• An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimization [111.24899593052851]
  条件勾配アルゴリズム(Frank-Wolfeアルゴリズムとも呼ばれる)は、最近、機械学習コミュニティで人気を取り戻している。 ARCSは、ゼロ階最適化において凸問題を解く最初のゼロ階条件勾配スライディング型アルゴリズムである。 1次最適化では、ARCSの収束結果は、勾配クエリのオラクルの数で、従来のアルゴリズムよりも大幅に優れていた。
  論文  参考訳（メタデータ） (2021-09-18T07:08:11Z)
• Proximal Gradient Descent-Ascent: Variable Convergence under K{\L} Geometry [49.65455534654459]
  有限降下指数パラメータ (GDA) はミニマックス最適化問題の解法として広く応用されている。 本稿では、KL-L型幾何学の収束を研究することにより、そのようなギャップを埋める。
  論文  参考訳（メタデータ） (2021-02-09T05:35:53Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• 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)
• Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling [29.600975900977343]
  我々はZOROと呼ばれる新しい$textbfZ$eroth-$textbfO$rder $textbfR$egularized $textbfO$ptimization法を提案する。 基礎となる勾配がイテレートでほぼスパースである場合、ZOROは目的関数を減少させる新しいイテレートを得るために、非常に少数の客観的関数評価を必要とする。
  論文  参考訳（メタデータ） (2020-03-29T11:01:17Z)

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

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