論文の概要: Extragradient Type Methods for Riemannian Variational Inequality Problems

• arxiv url: http://arxiv.org/abs/2309.14155v2
• Date: Sat, 1 Jun 2024 11:40:49 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-04 20:50:48.281584
• Title: Extragradient Type Methods for Riemannian Variational Inequality Problems
• Title（参考訳）: リーマン変分不等式問題に対する漸進型法
• Authors: Zihao Hu, Guanghui Wang, Xi Wang, Andre Wibisono, Jacob Abernethy, Molei Tao,
• Abstract要約: 我々は、REG と RPEG の両者の平均収束度が、2020 年の場合と一致する$Oleft(frac1Tright)$であることを示す。 結果はホロノミー効果の偏見に対処することで可能となり、さらなる観測を減らせることができる。
• 参考スコア（独自算出の注目度）: 25.574847201669144
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Riemannian convex optimization and minimax optimization have recently drawn considerable attention. Their appeal lies in their capacity to adeptly manage the non-convexity of the objective function as well as constraints inherent in the feasible set in the Euclidean sense. In this work, we delve into monotone Riemannian Variational Inequality Problems (RVIPs), which encompass both Riemannian convex optimization and minimax optimization as particular cases. In the context of Euclidean space, it is established that the last-iterates of both the extragradient (EG) and past extragradient (PEG) methods converge to the solution of monotone variational inequality problems at a rate of $O\left(\frac{1}{\sqrt{T}}\right)$ (Cai et al., 2022). However, analogous behavior on Riemannian manifolds remains an open question. To bridge this gap, we introduce the Riemannian extragradient (REG) and Riemannian past extragradient (RPEG) methods. We demonstrate that both exhibit $O\left(\frac{1}{\sqrt{T}}\right)$ last-iterate convergence. Additionally, we show that the average-iterate convergence of both REG and RPEG is $O\left(\frac{1}{{T}}\right)$, aligning with observations in the Euclidean case (Mokhtari et al., 2020). These results are enabled by judiciously addressing the holonomy effect so that additional complications in Riemannian cases can be reduced and the Euclidean proof inspired by the performance estimation problem (PEP) technique or the sum-of-squares (SOS) technique can be applied again.
• Abstract（参考訳）: リーマン凸最適化とミニマックス最適化は近年注目されている。 彼らの魅力は、目的関数の非凸性とユークリッドの意味で実現可能な集合に固有の制約を十分に管理する能力にある。 本研究では, 単調なリーマン変分不等式問題 (RVIP) を探索し, リーマン凸最適化とミニマックス最適化の両方を対象とする。 ユークリッド空間の文脈では、過次(EG)法と過去の過次(PEG)法の両方の最終定式式は、O\left(\frac{1}{\sqrt{T}}\right)$ (Cai et al , 2022) の速度で単調変分不等式問題の解に収束する。 しかし、リーマン多様体上の類似の挙動は未解決の問題である。 このギャップを埋めるために、リーマン・エクストラグラディエント(REG)法とリーマン・パス・エクストラグラディエント(RPEG)法を導入する。 どちらも$O\left(\frac{1}{\sqrt{T}}\right)$ last-iterate convergenceを示す。 さらに、REG と RPEG の双方の平均定位収束は$O\left(\frac{1}{{T}}\right)$であり、ユークリッドの場合の観測と一致している(Mokhtari et al , 2020)。 これらの結果は、リーマン事件における追加の合併症を減らすためにホロノミー効果を司法的に解決し、性能推定問題(PEP)法や2乗法(SOS)法にインスパイアされたユークリッド証明を再び適用することができる。

関連論文リスト

• Riemannian Bilevel Optimization [35.42472057648458]
  特に,2次情報を回避することを目的とした,バッチおよび勾配に基づく手法に着目する。 本稿では,一階勾配情報を活用する手法である$mathrmRF2SA$を提案し,分析する。 様々な設定の下で、$epsilon$-stationary 点に達するための明示的な収束率を提供する。
  論文  参考訳（メタデータ） (2024-05-22T20:49:01Z)
• Convergence and Complexity Guarantee for Inexact First-order Riemannian Optimization Algorithms [18.425648833592312]
  tBMM は $O(epsilon-2)$ 内の $ilon$-定常点に収束することを示す。 軽度反復の下では、全最適性ギャップが有界である場合、各反復においてサブプロブレムが解かれるときの結果は依然として保たれる。
  論文  参考訳（メタデータ） (2024-05-05T22:53:14Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
  論文  参考訳（メタデータ） (2023-11-04T11:12:24Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。 我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces [93.35384756718868]
  min-maxアルゴリズムはユークリッド設定で解析されている。 指数関数法 (RCEG) が線形速度で最終収束を補正したことを証明した。
  論文  参考訳（メタデータ） (2022-06-04T18:53:44Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  断片的な離散化は既存の離散化問題と矛盾しないことを示す。 この理論を2つの画像のマッチング問題に適用する。
  論文  参考訳（メタデータ） (2021-07-13T12:31:06Z)
• Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descent [15.136397170510834]
  我々は,新たな測地的凸性の結果を証明し,イテレートのより強力な制御,自由収束を実現した。 また, この手法により, 平均化の概念, エントロピック規則化バリセンタ, 幾何中央値の2つの解析が可能となった。
  論文  参考訳（メタデータ） (2021-06-16T01:05:19Z)
• Proximal Gradient Descent-Ascent: Variable Convergence under K{\L} Geometry [49.65455534654459]
  有限降下指数パラメータ (GDA) はミニマックス最適化問題の解法として広く応用されている。 本稿では、KL-L型幾何学の収束を研究することにより、そのようなギャップを埋める。
  論文  参考訳（メタデータ） (2021-02-09T05:35:53Z)

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

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