論文の概要: 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)と呼ばれ、広く知られている勾配降下上昇アルゴリズムと強く関連している。
本稿では,他の解の概念との関係や最適条件など,局所的なミニマックス点の包括的解析を行うことを目的とする。
局所サドル点は、緩やかな連続性仮定の下で一様局所極小点と呼ばれる局所極小点の特別なタイプと見なすことができる。
非凸)二次ゲームでは、局所的ミニマックス点が(ある意味で)大域的ミニマックス点と同値であることを示す。
最後に,局所極小点近傍の勾配アルゴリズムの安定性について検討する。
勾配アルゴリズムは非退化の場合、局所的/言語的極小点に収束するが、一般的には失敗する。
これは、非凸滑らかなゲームにおいて、サドル点やミニマックス点を超えた新しいアルゴリズムや概念が必要であることを意味する。
関連論文リスト
- How to escape sharp minima with random perturbations [54.05440117388505]
平らなミニマの概念とそれらを見つける複雑さについて研究する。
一般的なコスト関数に対して、近似平坦な局所最小値を求める勾配に基づくアルゴリズムについて論じる。
コスト関数がトレーニングデータよりも経験的リスクであるような環境では、シャープネス認識最小化と呼ばれる最近提案された実用的なアルゴリズムにインスパイアされたより高速なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-05-25T02:12:33Z) - 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) - A Unified Single-loop Alternating Gradient Projection Algorithm for
Nonconvex-Concave and Convex-Nonconcave Minimax Problems [8.797831153231664]
提案手法は,理論上の一般凸目標保証を用いた最小値問題の解法である。
提案アルゴリズムは,ノンカベエプシロン・コンケーブ(強)と(強)コンベックス・ノン・コンケーブ(強)のミニマックス問題を解くために利用できることを示す。
論文 参考訳(メタデータ) (2020-06-03T04:00:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。