論文の概要: Optimal High-Order Methods for Solving Monotone Variational Inequalities
- arxiv url: http://arxiv.org/abs/2609.23557v1
- Date: Sun, 20 Sep 2026 11:14:34 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-22 20:29:00.851419
- Title: Optimal High-Order Methods for Solving Monotone Variational Inequalities
- Title（参考訳）: 単調変分不等式の最適高次解法
- Abstract要約: 滑らかな単調変分不等式(MVI)の2次および高次解法について検討する。
凸凹型ミニマックス最適化では、Chen、Liu、Luo、Zhang(COLT 2025)といったMVI問題のサブクラスが最近$tildemathcalO(T-1.75)$に改善された。
本稿では,$mathcalO(T-2.5)$の最適レートを実現する新しい2階法を提案する。
我々のアルゴリズムは高階法にも拡張する:任意の整数 $ p ge に対して
- 参考スコア（独自算出の注目度）: 32.69101143776345
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study second- and higher-order methods for solving smooth monotone variational inequalities (MVI). Monteiro and Svaiter (SIAM J. Optim., 2012) showed that a second-order method, NPE, converges at a rate of $\mathcal{O}(T^{-1.5})$. For convex-concave minimax optimization, a subclass of MVI problems, Chen, Liu, Luo, and Zhang (COLT 2025) recently improved this rate to $\tilde{\mathcal{O}}( T^{-1.75})$. However, the result has a substantial gap compared to the lower bound of $Ω(T^{-2.5})$ established by Chen et al. (2026). In this paper, we propose a novel second-order method that achieves the optimal rate of $\mathcal{O}(T^{-2.5})$. Our algorithm also extends to higher-order methods: for any integer $ p \ge 1$, we obtain a $p$th-order method with a convergence rate of $\mathcal{O}(T^{-(3p-1)/2})$, matching the known lower bounds and therefore establishing optimal rates across all orders.
- Abstract（参考訳）: 本研究では,滑らかな単調変分不等式(MVI)の解法について検討した。
Monteiro and Svaiter (SIAM J. Optim., 2012) は、2階法 NPE が$\mathcal{O}(T^{-1.5})$ で収束することを示した。
凸凹極小最適化では、MVI問題のサブクラスであるChen, Liu, Luo, Zhang (COLT 2025) が最近この値を$\tilde{\mathcal{O}}(T^{-1.75})$に改善した。
しかし、Chen et al (2026) によって確立された$Ω(T^{-2.5})$の低い境界と比較すると、大きな差がある。
本稿では,$\mathcal{O}(T^{-2.5})$の最適値を達成する新しい2階法を提案する。
任意の整数 $p \ge 1$ に対して、$\mathcal{O}(T^{-(3p-1)/2})$ の収束率を持つ$p$th-order 法を得る。
関連論文リスト
- Halpern Iteration Achieves $\tilde{\mathcal{O}}(ε^{-1/p})$ $p$th-Order Oracle Complexity for Monotone Variational Inequalities [32.010107520858995]
滑らかな単調変分不等式(MVI)の2次および高次解法について検討する。
MVIを解くために,より高速な$tildemathcalO(T-2)$を実現するHalpern-NPE法を提案する。
論文 参考訳（メタデータ） (2026-08-09T04:13:20Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。
提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Perseus: A Simple and Optimal High-Order Method for Variational
Inequalities [81.32967242727152]
VI は、$langle F(x), x - xstarrangle geq 0$ for all $x in MathcalX$ であるように、mathcalX$ で $xstar を見つける。
そこで本稿では,テキストitが行探索を必要とせず,$O(epsilon-2/(p+1))$で弱解に確実に収束する$pth$-order法を提案する。
論文 参考訳（メタデータ） (2022-05-06T13:29:14Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - Higher-order methods for convex-concave min-max optimization and
monotone variational inequalities [7.645449711892907]
制約付き凸凹 min-max 問題に対する収束率の改善と高次滑らかな単調変分不等式を提供する。
p>2$の場合、ネミロフスキーの1階ミラープロキシ法の反復複雑性を改善する。
さらに、制約のない$p=2$ケースでアルゴリズム全体をインスタンス化する。
論文 参考訳（メタデータ） (2020-07-09T03:12:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。