論文の概要: Escaping limit cycles: Global convergence for constrained
nonconvex-nonconcave minimax problems
- arxiv url: http://arxiv.org/abs/2302.09831v1
- Date: Mon, 20 Feb 2023 08:37:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-21 16:08:35.733800
- Title: Escaping limit cycles: Global convergence for constrained
nonconvex-nonconcave minimax problems
- Title（参考訳）: エスケープ極限サイクル:制約付き非凸非凸ミニマックス問題に対する大域収束
- Authors: Thomas Pethick, Puya Latafat, Panagiotis Patrinos, Olivier Fercoq,
Volkan Cevher
- Abstract要約: 本稿では,非コンケーブなミニマックス問題のクラスに対して,新たな漸進型アルゴリズムを提案する。
提案アルゴリズムは制約付き正規化問題に適用可能である。
- 参考スコア（独自算出の注目度）: 46.71914490521821
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper introduces a new extragradient-type algorithm for a class of
nonconvex-nonconcave minimax problems. It is well-known that finding a local
solution for general minimax problems is computationally intractable. This
observation has recently motivated the study of structures sufficient for
convergence of first order methods in the more general setting of variational
inequalities when the so-called weak Minty variational inequality (MVI) holds.
This problem class captures non-trivial structures as we demonstrate with
examples, for which a large family of existing algorithms provably converge to
limit cycles. Our results require a less restrictive parameter range in the
weak MVI compared to what is previously known, thus extending the applicability
of our scheme. The proposed algorithm is applicable to constrained and
regularized problems, and involves an adaptive stepsize allowing for
potentially larger stepsizes. Our scheme also converges globally even in
settings where the underlying operator exhibits limit cycles.
- Abstract（参考訳）: 本稿では,非凸非凸ミニマックス問題に対する新しい超勾配型アルゴリズムを提案する。
一般ミニマックス問題に対する局所解を見つけることは計算上難解であることはよく知られている。
この観測は、いわゆる弱ミンティ変分不等式(MVI)が成立するより一般的な変分不等式の設定において、一階法の収束に十分な構造の研究を動機付けている。
この問題クラスは、実例で示すような非自明な構造を捉え、既存のアルゴリズムの大規模なファミリーは、確実に極限サイクルに収束する。
その結果,従来知られていたよりも弱いmviの制約パラメータ範囲が小さくなり,提案手法の適用性が向上した。
提案アルゴリズムは制約付きおよび正規化問題に適用可能であり、適応的なステップサイズを伴い、潜在的により大きなステップサイズを実現する。
我々のスキームは、基礎となる演算子がリミットサイクルを示す設定でもグローバルに収束する。
関連論文リスト
- Stochastic Optimization with Constraints: A Non-asymptotic Instance-Dependent Analysis [2.1756081703276]
凸制約下での凸最適化のための自然分散低減近位勾配(VRPG)アルゴリズムの挙動を解析する。
我々の主な成果は、VRPGアルゴリズムの漸近的でない保証である。
我々の保証は、損失関数の複雑さ、雑音の可変性、制約集合の幾何を捉えていることを示す。
論文 参考訳（メタデータ） (2024-03-24T14:45:11Z) - Decentralized gradient descent maximization method for composite
nonconvex strongly-concave minimax problems [7.5573375809946395]
定常的非平滑項の両方にフォーカスできるNCSCミニマックス問題を解くための最初の試みを行う。
提案アルゴリズムは,ミニマックス問題の新たな再構成に基づいて設計されている。
論文 参考訳（メタデータ） (2023-04-05T13:54:43Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳（メタデータ） (2023-02-08T01:42:45Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。
連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。
提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
論文 参考訳（メタデータ） (2021-11-01T21:06:35Z) - Stability and Generalization of Stochastic Gradient Methods for Minimax
Problems [71.60601421935844]
多くの機械学習問題は、GAN(Generative Adversarial Networks)のようなミニマックス問題として定式化できる。
ミニマックス問題に対するトレーニング勾配法から例を包括的に一般化解析する。
論文 参考訳（メタデータ） (2021-05-08T22:38:00Z) - Cyclic Coordinate Dual Averaging with Extrapolation [22.234715500748074]
単調作用素を用いた変分不等式(VI)問題の一般クラスに適用可能な新しいブロック座標法を提案する。
得られた収束境界は、全勾配法の最適収束境界と一致する。
座標ブロックが$m$の場合、我々の境界における勾配リプシッツ定数は、従来のユークリッドのリプシッツ定数と比較して$sqrtm$よりも大きくなることはない。
論文 参考訳（メタデータ） (2021-02-26T00:28:58Z) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。
このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文 参考訳（メタデータ） (2020-10-31T21:35:42Z) - Global Convergence and Variance-Reduced Optimization for a Class of
Nonconvex-Nonconcave Minimax Problems [39.13924898972611]
非minimaxewicz問題は、生成的対向ネットワークと対向学習の応用において頻繁に現れる。
一定の大きさのGDAアルゴリズムは凸設定でも潜在的に分岐する可能性がある。
AGDAアルゴリズムは、サブレートに達する速度でグローバルに収束する。
論文 参考訳（メタデータ） (2020-02-22T04:20:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。