論文の概要: Halpern Iteration Achieves $\tilde{\mathcal{O}}(ε^{-1/p})$ $p$th-Order Oracle Complexity for Monotone Variational Inequalities

• arxiv url: http://arxiv.org/abs/2608.08463v1
• Date: Sun, 09 Aug 2026 04:13:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-11 19:16:36.835339
• Title: Halpern Iteration Achieves $\tilde{\mathcal{O}}(ε^{-1/p})$ $p$th-Order Oracle Complexity for Monotone Variational Inequalities
• Title（参考訳）: Halpern Iteration Achieves $\tilde{\mathcal{O}}(ε^{-1/p})$$p$th-次 Oracle Complexity for Monotone Variational Inequalities
• Abstract要約: 滑らかな単調変分不等式(MVI)の2次および高次解法について検討する。 MVIを解くために,より高速な$tildemathcalO(T-2)$を実現するHalpern-NPE法を提案する。
• 参考スコア（独自算出の注目度）: 32.010107520858995
• 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 the rate of $\mathcal{O}(T^{-1.5})$. For convex-concave minimax optimization, a subset of MVI problems, Chen, Liu, Luo, and Zhang (COLT 2025) recently improved the complexity to $\tilde{\mathcal{O}}( T^{-1.75})$ . However, it is open whether the conjectured complexity for MVI can be improved. In this paper, by using a large-step inexact Halpern iteration, we propose a novel Halpern-NPE method that achieves an even faster rate of $\tilde{\mathcal{O}}(T^{-2})$ for solving MVIs. We also provide the $p$th-order generalization of our method. We first introduce an Anchored Tensor Method (ATM) that achieves the rate of $\mathcal{O}(T^{-(p-1)})$, and then combine it with the Halpern iteration to achieve a faster convergence rate of $\tilde{\mathcal{O}}(T^{-p})$. This improves all prior results for $p \ge 2$ and matches the classical extragradient method for $p=1$.
• Abstract（参考訳）: 本研究では,滑らかな単調変分不等式(MVI)の解法について検討した。 Monteiro and Svaiter (SIAM J. Optim., 2012) は、二階法 NPE が $\mathcal{O}(T^{-1.5})$ の速度で収束することを示した。 凸凹型ミニマックス最適化では、Chen, Liu, Luo, Zhang (COLT 2025) というMVI問題のサブセットが最近複雑さを$\tilde{\mathcal{O}}(T^{-1.75})$ に改善した。 しかし、MVIの予想複雑性が改善できるかは明らかである。 本稿では,Halpern-NPE法を用いて,MVIの解法として,より高速な$\tilde{\mathcal{O}}(T^{-2})$のHalpern-NPE法を提案する。 また、この手法の$p$th-orderの一般化も提供する。 まず、まず、$\mathcal{O}(T^{-(p-1)})$を達成し、Halpern反復と組み合わせて$\tilde{\mathcal{O}}(T^{-p})$を高速に収束するAnchored Tensor Method(ATM)を導入する。 これにより、$p \ge 2$の前の結果をすべて改善し、古典的な外部階調メソッドを$p=1$にマッチさせる。

関連論文リスト

• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Solving Convex-Concave Problems with $\ ilde{\mathcal{O}}(ε^{-4/7})$ Second-Order Oracle Complexity [27.760400553380823]
  凸最適化のための最適二階法を一般化することにより,$tildemathcalO(epsilon-4/7)$の改善された上限を示す。 さらに,遅延ヘシアンアルゴリズムに類似した手法を適用し,提案アルゴリズムが二階触媒の枠組みであることを示す。
  論文  参考訳（メタデータ） (2025-06-10T02:20:48Z)
• Second-Order Min-Max Optimization with Lazy Hessians [17.17389531402505]
  本稿では,凸凹型最小値最適化のための2次法について検討する。 計算コストは反復的にヘッセンによって削減できることを示す。
  論文  参考訳（メタデータ） (2024-10-12T15:30:17Z)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。 我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。 また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
  論文  参考訳（メタデータ） (2024-06-07T08:26:31Z)
• Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems [8.0153031008486]
  有限和共役方程式 $Gx = 0$ を解くために, 分散還元を伴う高速クラスクラスKrasnoselkii-Mann 法を提案する。 我々のアルゴリズムは単一ループであり、より広範なルートフィンディングアルゴリズムのために特別に設計された、偏りのない分散還元推定器の新たなファミリーを利用する。 数値実験は我々のアルゴリズムを検証し、最先端の手法と比較して有望な性能を示す。
  論文  参考訳（メタデータ） (2024-06-04T15:23:29Z)
• Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
  本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。 また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
  論文  参考訳（メタデータ） (2023-06-30T20:36:44Z)
• A Formal Perspective on Byte-Pair Encoding [100.75374173565548]
  Byte-Pairimation (BPE) は、当初圧縮法として考案されたものの、NLPでデータをトークン化するために使われる一般的なアルゴリズムである。 我々は、ランタイムの複雑さを$mathcalOleft(N log Mright)$から$mathcalOleft(N log Mright)$に改善するBPEのより高速な実装を提供しています。
  論文  参考訳（メタデータ） (2023-06-29T10:29:23Z)
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
  本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。 この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。 我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
  論文  参考訳（メタデータ） (2022-05-19T16:04:40Z)
• 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)
• 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)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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