論文の概要: Accelerated Extragradient-Type Methods -- Part 2: Generalization and Sublinear Convergence Rates under Co-Hypomonotonicity

• arxiv url: http://arxiv.org/abs/2501.04585v1
• Date: Wed, 08 Jan 2025 16:06:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-09 14:55:36.478657
• Title: Accelerated Extragradient-Type Methods -- Part 2: Generalization and Sublinear Convergence Rates under Co-Hypomonotonicity
• Title（参考訳）: 加速過次型法 -その2:コヒーポモノトニック性下における一般化と下線収束速度-
• Authors: Quoc Tran-Dinh, Nghia Nguyen-Trung,
• Abstract要約: 本稿では,アンカード・エクストラグラディエントとネステロフのアクセルド・エクストラグラディエントという,2種類のエクストラグラディエント・ベースの手法について検討する。 我々は、より広い範囲のスキームにモノトン包摂を包含するアンカー付き指数関数のクラスを統一し、一般化する。 我々は、包含性を解決するために、Nesterovの高速化された指数関数の新たなクラスを提案する。
• 参考スコア（独自算出の注目度）: 6.78476672849813
• License:
• Abstract: Following the first part of our project, this paper comprehensively studies two types of extragradient-based methods: anchored extragradient and Nesterov's accelerated extragradient for solving [non]linear inclusions (and, in particular, equations), primarily under the Lipschitz continuity and the co-hypomonotonicity assumptions. We unify and generalize a class of anchored extragradient methods for monotone inclusions to a wider range of schemes encompassing existing algorithms as special cases. We establish $\mathcal{O}(1/k)$ last-iterate convergence rates on the residual norm of the underlying mapping for this general framework and then specialize it to obtain convergence guarantees for specific instances, where $k$ denotes the iteration counter. We extend our approach to a class of anchored Tseng's forward-backward-forward splitting methods to obtain a broader class of algorithms for solving co-hypomonotone inclusions. Again, we analyze $\mathcal{O}(1/k)$ last-iterate convergence rates for this general scheme and specialize it to obtain convergence results for existing and new variants. We generalize and unify Nesterov's accelerated extra-gradient method to a new class of algorithms that covers existing schemes as special instances while generating new variants. For these schemes, we can prove $\mathcal{O}(1/k)$ last-iterate convergence rates for the residual norm under co-hypomonotonicity, covering a class of nonmonotone problems. We propose another novel class of Nesterov's accelerated extragradient methods to solve inclusions. Interestingly, these algorithms achieve both $\mathcal{O}(1/k)$ and $o(1/k)$ last-iterate convergence rates, and also the convergence of iterate sequences under co-hypomonotonicity and Lipschitz continuity. Finally, we provide a set of numerical experiments encompassing different scenarios to validate our algorithms and theoretical guarantees.
• Abstract（参考訳）: 本研究は, 線形包摂(および特に方程式)の解法として, 主にリプシッツ連続性およびコ・ハイモノモノニティ仮定の下で, アンカード・エクストラグラディエントとネステロフのアクセルド・エクストラグラディエント(英語版)の2つの手法を包括的に研究する。 我々は,既存のアルゴリズムを特別なケースとして包含する幅広いスキームに対して,モノトーン包含のためのアンカー付き指数関数法を統一し,一般化する。 我々は、この一般的なフレームワークの基盤となる写像の残留ノルムに$\mathcal{O}(1/k)$ の収束率を確立し、それを特殊化して特定のインスタンスに対する収束保証を得る($k$は反復カウンタを表す)。 我々は,コヒポモノトン包摂を解くアルゴリズムのより広範なクラスを得るために,Tseng のフォワード・バック・フォワード・スプリッティング手法のクラスにアプローチを拡張した。 また、この一般的なスキームに対して$\mathcal{O}(1/k)$ last-iterate convergence rate を分析し、既存の変種および新しい変種に対する収束結果を得るために特殊化する。 我々は、Nesterovの高速化された指数関数を、既存のスキームを特殊例としてカバーし、新しい変種を生成するアルゴリズムのクラスに一般化し、統一する。 これらのスキームに対して、非単調な問題のクラスをカバーした残ノルムに対して、$\mathcal{O}(1/k)$ last-iterate convergence rateを証明できる。 我々は、包含性を解決するために、Nesterovの高速化された指数関数の新たなクラスを提案する。 興味深いことに、これらのアルゴリズムは$\mathcal{O}(1/k)$および$o(1/k)$ last-iterate convergence rate、およびコハイモノモニック性およびリプシッツ連続性の下での反復列の収束を達成する。 最後に、アルゴリズムと理論的保証を検証するための様々なシナリオを含む数値実験のセットを提供する。

関連論文リスト

• A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees [31.772894924814395]
  2階局所呼び出しに関して、$epsilon-frac32) + tilde O$と、Hessian-vectorvectorsに対して$tilde O(epsilon-frac74)$という大域的な複雑さを見出す。 予備的な数値計算の結果は、我々のアルゴリズムを示している。
  論文  参考訳（メタデータ） (2025-02-07T10:10:10Z)
• Revisiting Extragradient-Type Methods -- Part 1: Generalizations and Sublinear Convergence Rates [6.78476672849813]
  本稿では、方程式と包摂性の両方を解くためのよく知られた指数関数法(EG法)を包括的に分析する。 アルゴリズムのクラス全体のサブ線形ベストイテレートとラストイテレートの収束率を分析する。 我々は、新しいアルゴリズムのクラスとそれに対応する収束結果を導入し、上述のEGフレームワークをモノトーンの包含に拡張する。
  論文  参考訳（メタデータ） (2024-09-25T12:14:05Z)
• Strictly Low Rank Constraint Optimization -- An Asymptotically $\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
  最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。 我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
  論文  参考訳（メタデータ） (2023-07-04T16:55:41Z)
• Extragradient-Type Methods with $\mathcal{O} (1/k)$ Last-Iterate Convergence Rates for Co-Hypomonotone Inclusions [8.0153031008486]
  我々は、コヒポモノトン包摂の解を近似するために、よく知られた過次法(英語版)の2つの「ネステロフ加速」変種を開発した。 我々の結果は、ルートフィリング問題に対する最近のハルパーン型手法の代替と見なすことができる。
  論文  参考訳（メタデータ） (2023-02-08T14:47:34Z)
• 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)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• 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)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• A New Randomized Primal-Dual Algorithm for Convex Optimization with Optimal Last Iterate Rates [16.54912614895861]
  我々は,非滑らかな制約付き凸最適化問題のクラスを解くために,新しいランダム化ブロック座標原始双対アルゴリズムを開発した。 我々は,一般凸性と強い凸性という2つのケースにおいて,アルゴリズムが最適収束率を達成することを証明した。 その結果,提案手法は異なる実験における性能向上に寄与していることがわかった。
  論文  参考訳（メタデータ） (2020-03-03T03:59:26Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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