論文の概要: STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games

• arxiv url: http://arxiv.org/abs/2210.09769v1
• Date: Tue, 18 Oct 2022 11:33:30 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-19 16:09:49.452952
• Title: STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games
• Title（参考訳）: Staay-ON-the-Ridge:非凸ノンコンケーブゲームにおける局所ミニマックス平衡への保証収束
• Authors: Constantinos Daskalakis, Noah Golowich, Stratis Skoulakis and Manolis Zampetakis
• Abstract要約: 非競合対象に対してmin-maxサイクルを収束させることが保証される手法を提案する。 我々の方法は問題の潜在的な性質を満たすように設計されている。
• 参考スコア（独自算出の注目度）: 34.04699387005116
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Min-max optimization problems involving nonconvex-nonconcave objectives have found important applications in adversarial training and other multi-agent learning settings. Yet, no known gradient descent-based method is guaranteed to converge to (even local notions of) min-max equilibrium in the nonconvex-nonconcave setting. For all known methods, there exist relatively simple objectives for which they cycle or exhibit other undesirable behavior different from converging to a point, let alone to some game-theoretically meaningful one~\cite{flokas2019poincare,hsieh2021limits}. The only known convergence guarantees hold under the strong assumption that the initialization is very close to a local min-max equilibrium~\cite{wang2019solving}. Moreover, the afore-described challenges are not just theoretical curiosities. All known methods are unstable in practice, even in simple settings. We propose the first method that is guaranteed to converge to a local min-max equilibrium for smooth nonconvex-nonconcave objectives. Our method is second-order and provably escapes limit cycles as long as it is initialized at an easy-to-find initial point. Both the definition of our method and its convergence analysis are motivated by the topological nature of the problem. In particular, our method is not designed to decrease some potential function, such as the distance of its iterate from the set of local min-max equilibria or the projected gradient of the objective, but is designed to satisfy a topological property that guarantees the avoidance of cycles and implies its convergence.
• Abstract（参考訳）: 非凸非凸目的のMin-max最適化問題は、対向訓練やその他のマルチエージェント学習設定において重要な応用を見出した。 しかし、非凸-非凹面条件における(局所的な概念である) min-max 平衡に収束することが保証される勾配降下法は存在しない。 すべての既知の方法に対して、それらが収束から一点まで異なる他の望ましくない振る舞いを循環または示すという比較的単純な目的が存在する。 唯一知られている収束は、初期化が局所 min-max 平衡~\cite{wang2019solving} に非常に近いという強い仮定の下で成り立つ。 さらに、前述の課題は単に理論的な好奇性だけではない。 既知のすべてのメソッドは、単純な設定であっても、実際には不安定である。 滑らかな非凸非凸目的に対して局所min-max平衡に収束することが保証される最初の方法を提案する。 本手法は二階法であり, 探索容易な初期点で初期化される限り, 限界サイクルを回避できる。 本手法の定義と収束解析はどちらも,問題のトポロジカルな性質によって動機付けられている。 特に,本手法は,局所的な min-max 平衡の集合からのイテレート距離や目的の射影勾配などのポテンシャル関数を減少させるように設計されていないが,サイクルの回避を保証し,その収束を示唆する位相特性を満たすように設計されている。

関連論文リスト

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
  分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。 本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-24T02:19:39Z)
• Beyond first-order methods for non-convex non-concave min-max optimization [6.097141897343098]
  モノトーンおよびミンティ条件設定を超える改善が達成できることを示す。 具体的には、離散時間最小化の新しい理解を提供する。 離散時間設定に適合する連続時間解析を提示する。
  論文  参考訳（メタデータ） (2023-04-17T15:55:40Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。 連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
  論文  参考訳（メタデータ） (2023-03-02T05:08:15Z)
• Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization [26.218670461973705]
  非漸近勾配ノルム保証を協調する問題の解法を提案する。 本研究は,ニューラルネットの深部学習における循環還元方式の有効性を実証するものである。
  論文  参考訳（メタデータ） (2022-12-09T19:17:39Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• Direct-Search for a Class of Stochastic Min-Max Problems [0.0]
  オラクルを通してのみ対象物にアクセスする導関数探索法について検討する。 この手法の収束性は軽微な仮定で証明する。 私達の分析は設定のminmax目的のための直接調査方法の収束に取り組む最初のものです。
  論文  参考訳（メタデータ） (2021-02-22T22:23:58Z)
• Stochastic optimization with momentum: convergence, fluctuations, and traps avoidance [0.0]
  本稿では,重球法,ネステロフ加速勾配法(S-NAG),広く使用されているアダム法など,勾配勾配勾配のいくつかの変種を統一する一般最適化手法について検討する。 この回避は、非自明な常微分方程式のノイズ離散化として研究される。
  論文  参考訳（メタデータ） (2020-12-07T19:14:49Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• The Landscape of the Proximal Point Method for Nonconvex-Nonconcave Minimax Optimization [10.112779201155005]
  Minimax PPMは、堅牢で強化された学習、GANなど、マシンラーニングの中心的なツールになっています。 これらの応用はしばしば非可逆であるが、既存の理論ではそれと根本的な困難を識別できない。
  論文  参考訳（メタデータ） (2020-06-15T18:17:00Z)

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

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