論文の概要: Optimality and Stability in Non-Convex Smooth Games

• arxiv url: http://arxiv.org/abs/2002.11875v3
• Date: Thu, 3 Feb 2022 16:29:21 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-28 08:05:48.131516
• Title: Optimality and Stability in Non-Convex Smooth Games
• Title（参考訳）: 非凸滑らかゲームにおける最適性と安定性
• Authors: Guojun Zhang, Pascal Poupart and Yaoliang Yu
• Abstract要約: 興味深い概念は局所ミニマックス点(英語版)として知られているが、これは降下と強く相関している。 勾配アルゴリズムは非退化の場合、局所的/言語的極小点に収束するが、一般的には失敗する。 これは、未知の滑らかなゲームにおいて、新しいアルゴリズムまたはサドル点を超える概念が必要であることを意味する。
• 参考スコア（独自算出の注目度）: 39.365235811852365
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Convergence to a saddle point for convex-concave functions has been studied for decades, while recent years has seen a surge of interest in non-convex (zero-sum) smooth games, motivated by their recent wide applications. It remains an intriguing research challenge how local optimal points are defined and which algorithm can converge to such points. An interesting concept is known as the local minimax point, which strongly correlates with the widely-known gradient descent ascent algorithm. This paper aims to provide a comprehensive analysis of local minimax points, such as their relation with other solution concepts and their optimality conditions. We find that local saddle points can be regarded as a special type of local minimax points, called uniformly local minimax points, under mild continuity assumptions. In (non-convex) quadratic games, we show that local minimax points are (in some sense) equivalent to global minimax points. Finally, we study the stability of gradient algorithms near local minimax points. Although gradient algorithms can converge to local/global minimax points in the non-degenerate case, they would often fail in general cases. This implies the necessity of either novel algorithms or concepts beyond saddle points and minimax points in non-convex smooth games.
• Abstract（参考訳）: 凸凹関数のサドル点への収束は何十年にもわたって研究されてきたが、近年は非凸(ゼロサム)滑らかなゲームへの関心が高まっている。 局所最適点をどのように定義し、どのアルゴリズムがそのような点に収束できるか、興味深い研究課題である。 興味深い概念は局所ミニマックス点(local minimax point)と呼ばれ、広く知られている勾配降下上昇アルゴリズムと強く関連している。 本稿では,他の解の概念との関係や最適条件など,局所的なミニマックス点の包括的解析を行うことを目的とする。 局所サドル点は、緩やかな連続性仮定の下で一様局所極小点と呼ばれる局所極小点の特別なタイプと見なすことができる。 非凸)二次ゲームでは、局所的ミニマックス点が(ある意味で)大域的ミニマックス点と同値であることを示す。 最後に,局所極小点近傍の勾配アルゴリズムの安定性について検討する。 勾配アルゴリズムは非退化の場合、局所的/言語的極小点に収束するが、一般的には失敗する。 これは、非凸滑らかなゲームにおいて、サドル点やミニマックス点を超えた新しいアルゴリズムや概念が必要であることを意味する。

関連論文リスト

• On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization [37.41427897807821]
  暗号非既知の正規最適化の複雑さを示す。 リプシッツ関数に作用する局所アルゴリズムは、最悪の場合、亜指数最小値の値に関して有意義な局所を与えることができない。
  論文  参考訳（メタデータ） (2024-09-16T14:35:00Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
  論文  参考訳（メタデータ） (2023-11-04T11:12:24Z)
• Two-timescale Extragradient for Finding Local Minimax Points [8.056359341994941]
  ミニマックス問題の解法として, 2時間スケールのエクストラグレード法が有効であることを示す。 この研究は、局所ミニマックス点の発見に関する過去のすべての結果に対して、確実に改善する。
  論文  参考訳（メタデータ） (2023-05-25T16:52:26Z)
• Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
  ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。 本稿では,2種類のミニマックスアルゴリズムを提案する。 そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
  論文  参考訳（メタデータ） (2023-02-08T01:42:45Z)
• Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
  バイレベル最適化は、機械学習における問題の1つだ。 双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
  論文  参考訳（メタデータ） (2022-02-08T07:10:06Z)
• Faster Perturbed Stochastic Gradient Methods for Finding Local Minima [92.99933928528797]
  局所最小値を求めるための高速な摂動勾配フレームワークであるtttPullbackを提案する。 SARAH/SP や STORM のような勾配推定器を用いたプルバックは $(epsilon, epsilon_H)$approximate local minima を $tilde O(epsilon-3 + H-6)$ 内で見つけることができる。 我々のフレームワークの中核となる考え方は、勾配評価の平均運動を制御するステップサイズのプルバック方式である。
  論文  参考訳（メタデータ） (2021-10-25T07:20:05Z)
• Escaping Saddle Points in Distributed Newton's Method with Communication efficiency and Byzantine Resilience [49.379254729853756]
  我々は、ビザンチン機械の存在下で分散フレームワークにおける非正規化損失関数(サドルポイント付き)を最適化する問題を検討する。 キューブ正規化されたニュートンアルゴリズムを堅牢化し、サドルポイントと偽のローカルミニマを効率的に回避します。 提案手法は, (サブサンプリング) と hessian を含むいくつかの近似設定で理論的に保証される。
  論文  参考訳（メタデータ） (2021-03-17T03:53:58Z)
• 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)
• The Complexity of Constrained Min-Max Optimization [29.57458485068705]
  十分大きな局所点 min-max が存在することが保証されていることを示す。 さらに重要なこととして、近似的な固定勾配 Descent/Ascent 近似が完成することを示す。 この結果は、2つの基本的な最適化問題の指数関数近似を初めて示したものである。
  論文  参考訳（メタデータ） (2020-09-21T05:54:12Z)

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

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