論文の概要: Extragradient Method for $(L_0, L_1)$-Lipschitz Root-finding Problems

• arxiv url: http://arxiv.org/abs/2510.22421v1
• Date: Sat, 25 Oct 2025 19:43:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 17:41:21.963873
• Title: Extragradient Method for $(L_0, L_1)$-Lipschitz Root-finding Problems
• Title（参考訳）: $(L_0, L_1)$-Lipschitz根絞り問題に対する過次解法
• Authors: Sayantan Choudhury, Nicolas Loizou,
• Abstract要約: 勾配法(EG)は、min-max最適化、ルートフィンディング問題、変分不等式(VIs)を解くための基礎技術となっている。 本稿では, 単調作用素に対する線形収束率と強単調作用素に対する線形収束率を確立するために, EG の新たなステップサイズ戦略を提案する。
• 参考スコア（独自算出の注目度）: 15.649189456012811
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Introduced by Korpelevich in 1976, the extragradient method (EG) has become a cornerstone technique for solving min-max optimization, root-finding problems, and variational inequalities (VIs). Despite its longstanding presence and significant attention within the optimization community, most works focusing on understanding its convergence guarantees assume the strong L-Lipschitz condition. In this work, building on the proposed assumptions by Zhang et al. [2024b] for minimization and Vankov et al.[2024] for VIs, we focus on the more relaxed $\alpha$-symmetric $(L_0, L_1)$-Lipschitz condition. This condition generalizes the standard Lipschitz assumption by allowing the Lipschitz constant to scale with the operator norm, providing a more refined characterization of problem structures in modern machine learning. Under the $\alpha$-symmetric $(L_0, L_1)$-Lipschitz condition, we propose a novel step size strategy for EG to solve root-finding problems and establish sublinear convergence rates for monotone operators and linear convergence rates for strongly monotone operators. Additionally, we prove local convergence guarantees for weak Minty operators. We supplement our analysis with experiments validating our theory and demonstrating the effectiveness and robustness of the proposed step sizes for EG.
• Abstract（参考訳）: 1976年にコルペレヴィチによって導入され、極次法(EG)はmin-max最適化、ルートフィンディング問題、変分不等式(VIs)を解くための基礎技術となっている。 最適化コミュニティにおける長年の存在と顕著な関心にもかかわらず、収束の保証を理解することに焦点を当てた研究の多くは、強いL-リプシッツ条件を仮定している。 本研究では、最小化のために Zhang et al [2024b] と VIs に対して Vankov et al [2024] によって提案された仮定に基づいて、より緩和された $\alpha$-symmetric $(L_0, L_1)$-Lipschitz 条件に焦点を当てる。 この条件は、リプシッツ定数を作用素ノルムにスケールさせることで標準的なリプシッツ仮定を一般化し、現代の機械学習における問題構造のより洗練された特徴付けを提供する。 $\alpha$-symmetric $(L_0, L_1)$-Lipschitz条件の下では、EGの新たなステップサイズ戦略を提案する。 さらに、弱ミンティ作用素に対する局所収束保証を証明する。 本研究は,本理論を検証し,提案したEGのステップサイズの有効性とロバスト性を示す実験により,解析を補完する。

関連論文リスト

• Convergence Rate Analysis of LION [54.28350823319057]
  LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。 従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
  論文  参考訳（メタデータ） (2024-11-12T11:30:53Z)
• Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity [18.427215139020632]
  1L 1$は、マルチレベルなCarloイテレーションであっても、最先端の問題を改善するために使用できることを示す。 解に関する唯一のホールドが新しい1L 1$理論である場合、不正確なハルパーネス推定器を1L 1$で解析する。
  論文  参考訳（メタデータ） (2024-02-07T18:22:41Z)
• A Unified Analysis on the Subgradient Upper Bounds for the Subgradient Methods Minimizing Composite Nonconvex, Nonsmooth and Non-Lipschitz Functions [7.972544890243396]
  本稿では, 近位降下法(Prox-SubGrad) 型アプローチの統一解析について述べる。 我々は, 誤差有界条件, 対象の下位次数の成長条件, および主次次次次次次数反復の挙動を, 極めて広い目的関数のクラスに関連付けることができる。
  論文  参考訳（メタデータ） (2023-08-30T23:34:11Z)
• A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
  Yang et al. (2023) は最近、一般的な変分不等式を解決するために一階勾配法を使う方法を示した。 この方法の収束性を証明し、演算子が$L$-Lipschitz と monotone である場合、この手法の最後の繰り返しのギャップ関数が$O(frac1sqrtK)$で減少することを示す。
  論文  参考訳（メタデータ） (2022-10-27T17:59:09Z)
• Solving Constrained Variational Inequalities via an Interior Point Method [88.39091990656107]
  制約付き変分不等式(cVI)問題を解くためのインテリアポイントアプローチを開発する。 本稿では,2種類の問題においてACVIの収束保証を提供する。 この設定における以前の作業とは異なり、ACVIは制約が自明でない場合にcVIを解く手段を提供する。
  論文  参考訳（メタデータ） (2022-06-21T17:55:13Z)
• KL-Entropy-Regularized RL with a Generative Model is Minimax Optimal [70.15267479220691]
  モデル強化学習のサンプル複雑性を,生成的分散自由モデルを用いて検討・解析する。 我々の分析は、$varepsilon$が十分小さい場合、$varepsilon$-optimal Policyを見つけるのが、ほぼ最小の最適化であることを示している。
  論文  参考訳（メタデータ） (2022-05-27T19:39:24Z)
• Extragradient Method: $O(1/K)$ Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity [21.22292220954549]
  Extragradient Method (EG) Korpelevichは、サドル点と変分不等式問題を解く最も一般的な方法の1つである。 最適化コミュニティにおける長い歴史と重要な関心にもかかわらず、EGの収束に関する重要なオープンな疑問が残っている。
  論文  参考訳（メタデータ） (2021-10-08T17:16:12Z)

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

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