論文の概要: Polyak-Type Extragradient Methods for Monotone Root-Finding Problems

• arxiv url: http://arxiv.org/abs/2609.26581v1
• Date: Tue, 22 Sep 2026 15:27:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-24 01:05:39.728132
• Title: Polyak-Type Extragradient Methods for Monotone Root-Finding Problems
• Title（参考訳）: モノトンルートフィンディング問題に対するポリアク型分解法
• Abstract要約: 我々はPolyak-type Extragradient Method(PolyakEG)の統一的決定論的解析を提供する。 まず、すべての成分作用素が共通解を共有するとき、直接変分PolyakSEGの収束を証明します。 また、この条件がなければ、不要なステップサイズを持つPolyakSEGは平均作用素の零点に収束しないかもしれないことも示している。
• 参考スコア（独自算出の注目度）: 15.294997701022217
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study Polyak-type step-size selection for extragradient methods for solving deterministic and stochastic monotone root-finding problems. We show that the known projection-type correction for deterministic extragradient arises from minimizing an upper bound on the distance to a solution, paralleling the classical Polyak step-size construction. Using this viewpoint, we provide a unified deterministic analysis of the Polyak-type Extragradient Method (PolyakEG), based on a local critical condition controlling the variation of operator $F$ along the extrapolation direction. This analysis does not require global Lipschitz continuity, and covers sublinear convergence under broader conditions such as Hölder continuity or $(L_0, L_1)$-Lipschitzness and linear convergence under additional strong monotonicity, all through a single framework. We then study the stochastic extensions of this approach. We first prove convergence of a direct stochastic variant, PolyakSEG, when all stochastic component operators share a common solution. We also show that, without this condition, PolyakSEG with nonvanishing step-sizes may fail to converge to a zero of the mean operator. To address this limitation, we propose DecPolyakSEG, which combines decreasing step-sizes with Polyak-type updates, and establish a sublinear residual convergence result without requiring a common solution across the component operators. These results parallel recent developments in stochastic Polyak step-sizes from the convex minimization literature and establish an analogous research avenue in the broader root-finding regime.
• Abstract（参考訳）: 本研究では, 決定論的および確率的単調根絶問題の解法として, ポリアク型ステップサイズ選択法について検討した。 決定論的外勾配に対する既知のプロジェクション型補正は、古典的ポリアックのステップサイズ構成と平行して、解への距離上の上限を最小化することから生じる。 この観点から、演算子$F$の変動を外挿方向に沿って制御する局所臨界条件に基づいて、Polyak-type Extragradient Method(PolyakEG)の統一的決定論的解析を行う。 この分析では、大域的なリプシッツ連続性は必要とせず、ヘルダー連続性や$(L_0, L_1)$-Lipschitzness のようなより広い条件下での線型収束と、さらに強い単調性の下での線形収束を全て単一の枠組みでカバーしている。 次に、このアプローチの確率的拡張について研究する。 まず、すべての確率成分作用素が共通解を共有するとき、直確率多様体 PolyakSEG の収束を証明する。 また、この条件がなければ、不要なステップサイズを持つPolyakSEGは平均作用素の零点に収束しないかもしれないことも示している。 この制限に対処するために,ステップサイズを小さくするDecPolyakSEGとPolyak型更新を組み合わせ,コンポーネント演算子間の共通解を必要としない線形残差収束結果を確立する。 これらの結果は、凸最小化文献からの確率的ポリアックのステップサイズにおける最近の発展と並行して、より広いルートフィディング体制における類似した研究方法を確立している。

関連論文リスト

• A proximal subgradient method for nonconvex stochastic optimization under the Kurdyka-Łojasiewicz condition [39.146761527401424]
  本研究は,期待されるコストの和を最小化するための近位次法を導入する。 クルディカ・ロジャシエヴィチ(KL)特性を用いて、全軌道の1つの定常点への収束を保証する。
  論文  参考訳（メタデータ） (2026-08-05T23:07:27Z)
• New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results [12.40603596036849]
  Polyakのステップサイズは凸最適化の基本的なステップサイズであることが証明されている。 ポリアックの階段の普遍性は、理論的な保証と強い経験的性能を含む多くの変種にも影響を与えた。 多くの理論的結果にもかかわらず、Polyakの立体化の収束特性と欠点に対する我々の理解は、異なる解析で不完全かつ破断である。
  論文  参考訳（メタデータ） (2025-05-26T17:00:27Z)
• Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias [55.72269695392027]
  本稿では,線形系を解くためにエントロピックミラー降下を適用することに焦点を当てる。 収束解析の主な課題は、領域の非有界性に起因する。 制限的な仮定を課さずにこれを克服するために、Polyak型階段の変種を導入する。
  論文  参考訳（メタデータ） (2025-05-05T12:33:18Z)
• Inexact subgradient methods for semialgebraic functions [18.293072574300798]
  機械学習における近似勾配の広範囲な適用を動機として, 永続的な誤差を受ける部分エクサクティヴな加算法について検討する。 我々の分析は、消滅と定常的なステップサイズ体制の両方に対処する。
  論文  参考訳（メタデータ） (2024-04-30T12:47:42Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• 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)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。 一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
  論文  参考訳（メタデータ） (2020-04-09T17:54:18Z)

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

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