論文の概要: A first-order method for nonconvex-nonconcave minimax problems under a local Kurdyka-Łojasiewicz condition

• arxiv url: http://arxiv.org/abs/2507.01932v1
• Date: Wed, 02 Jul 2025 17:45:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-03 14:23:00.407118
• Title: A first-order method for nonconvex-nonconcave minimax problems under a local Kurdyka-Łojasiewicz condition
• Title（参考訳）: 局所クルディカ・ジョジャシエヴィチ条件下での非凸非凸ミニマックス問題の一階法
• Authors: Zhaosong Lu, Xiangyuan Wang,
• Abstract要約: 局所的なクルディカ・ロジャシエヴィチ(KL)条件の内的問題と外的最小化変数が相違する非コンケーブ最小化問題のクラスについて検討する。 特に、アルゴリズムが問題の定常点に向かって進むと、KL条件が成立する領域は縮小し、より不規則な風景が生じる。
• 参考スコア（独自算出の注目度）: 1.534667887016089
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a class of nonconvex-nonconcave minimax problems in which the inner maximization problem satisfies a local Kurdyka-{\L}ojasiewicz (KL) condition that may vary with the outer minimization variable. In contrast to the global KL or Polyak-{\L}ojasiewicz (PL) conditions commonly assumed in the literature -- which are significantly stronger and often too restrictive in practice -- this local KL condition accommodates a broader range of practical scenarios. However, it also introduces new analytical challenges. In particular, as an optimization algorithm progresses toward a stationary point of the problem, the region over which the KL condition holds may shrink, resulting in a more intricate and potentially ill-conditioned landscape. To address this challenge, we show that the associated maximal function is locally H\"older smooth. Leveraging this key property, we develop an inexact proximal gradient method for solving the minimax problem, where the inexact gradient of the maximal function is computed by applying a proximal gradient method to a KL-structured subproblem. Under mild assumptions, we establish complexity guarantees for computing an approximate stationary point of the minimax problem.
• Abstract（参考訳）: 内最大化問題は、外最小化変数に変化する可能性のある局所的なクルディカ-{\L}ojasiewicz (KL) 条件を満たす。 グローバルな KL や Polyak-{\L}ojasiewicz (PL) の条件とは対照的に、この局所的な KL 条件はより広範な実践シナリオに対応している。 しかし、新たな分析課題も導入されている。 特に、最適化アルゴリズムが問題の定常点に向かって進むと、KL条件が成立する領域は縮小し、より複雑で、潜在的に条件が不適切になる可能性がある。 この問題に対処するために、関連する最大関数が局所的に H\"古いスムーズであることを示す。 このキー特性を生かして,KL構造サブプロブレムに近似勾配法を適用することにより,最大関数の不正確な勾配を求めるミニマックス問題を解く不正確な近勾配法を開発する。 軽微な仮定の下では,ミニマックス問題の定常点を近似的に計算する複雑性を保証する。

関連論文リスト

• On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization [37.41427897807821]
  暗号非既知の正規最適化の複雑さを示す。 リプシッツ関数に作用する局所アルゴリズムは、最悪の場合、亜指数最小値の値に関して有意義な局所を与えることができない。
  論文  参考訳（メタデータ） (2024-09-16T14:35:00Z)
• Energy Landscapes for the Quantum Approximate Optimisation Algorithm [0.0]
  QAOA anszeのエネルギー景観を様々なグラフでナビゲートするために、流域ホットなグローバルな手法を用いています。 対応するランドスケープは一般的に単一のファンネル組織を持つため、Max-Cut ソリューションの確率がよい低いミニマを見つけることは比較的容易である。
  論文  参考訳（メタデータ） (2024-01-09T19:17:01Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
  論文  参考訳（メタデータ） (2023-11-04T11:12:24Z)
• Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems [46.71914490521821]
  本稿では,非コンケーブなミニマックス問題のクラスに対して,新たな漸進型アルゴリズムを提案する。 提案アルゴリズムは制約付き正規化問題に適用可能である。
  論文  参考訳（メタデータ） (2023-02-20T08:37:08Z)
• 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)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
  我々はGasnikov et al., 2017のアプローチを一般化し、不正確な勾配のないオラクルで(確率的な)凸最適化問題を解けるようにした。 我々のアプローチは、$fracnlog n$ の要求するオラクル呼び出しの回数を削減します。 論文の後半では、そのような仮定ができない場合を分析し、この問題を解決する方法の近代化方法に関する一般的なアプローチを提案する。
  論文  参考訳（メタデータ） (2020-05-12T16:44:27Z)

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

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