論文の概要: Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems

• arxiv url: http://arxiv.org/abs/2609.30212v1
• Date: Thu, 24 Sep 2026 17:43:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-25 21:10:10.177854
• Title: Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems
• Title（参考訳）: Anchored Extra-proximal Methods:Optimal Higher-Order Methods for Monotone Inclusion Problems
• Abstract要約: 本稿では,合成単調包摂問題に対する近似解を求める決定論的複雑性について検討する。 我々はアンコールド・エクストラ・プロクシマル・フレームワークを導入し、アンカード・ステップとアンカード・プロクシマル・アップデートを組み合わせた。 このフレームワークは1次設定で合成Fast Extragradient法を復元する。
• 参考スコア（独自算出の注目度）: 10.76988998630904
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the deterministic oracle complexity of finding approximate solutions to composite monotone inclusion problems, formed by the sum of a smooth single-valued monotone operator and a maximally monotone set-valued operator, under the tangent-residual criterion. We introduce the Anchored Extra-Proximal (AEP) framework, which combines an anchored extrapolation step with an inexact anchored proximal update satisfying a relative-error condition. The framework recovers the composite Fast Extragradient method in the first-order setting and yields natural second- and higher-order extensions by replacing the operator in the implicit update with its Taylor approximation at the extrapolated point. For every $p\geq 2$, assuming that the $(p-1)$th derivative of the single-valued operator is Lipschitz continuous, we combine this construction with a bisection line search to obtain a $p$th-order method that finds a point with tangent residual at most $\varepsilon$ in $\widetilde{O}(\varepsilon^{-2/(3p-1)})$ oracle calls. This improves all prior upper bounds for $p$th-order methods: in particular, it improves the previous best-known $\widetilde{O}(\varepsilon^{-1/p})$ tangent-residual complexity as well as the classical $O(\varepsilon^{-2/(p+1)})$ bound of higher-order hybrid proximal extragradient methods under the weaker duality-gap criterion. We complement this result with a worst-case lower bound of $Ω(\varepsilon^{-2/(3p-1)})$ for every deterministic algorithm in the $p$th-order oracle model, without restricting the algorithm to tensor steps or any other prescribed update structure. Thus, the proposed method attains the optimal dependence on $\varepsilon$, up to logarithmic factors, for all $p\geq2$.
• Abstract（参考訳）: 単調な単調な単調演算子と最大単調な単調整合演算子の和によって構成される合成単調包摂問題に対する近似解を求める決定論的オラクルの複雑性について,タンジェント-残留基準の下で検討した。 本稿では,アンコールド・エクストラプロキシ(AEP)フレームワークを導入し,アンコールド外挿工程と,相対エラー条件を満たすアンコールド近位更新を併用する。 このフレームワークは1次設定で合成Fast Extragradient法を復元し、暗黙の更新における演算子を外挿点におけるTaylor近似に置き換えることで自然の2次および高次拡張を生成する。 すべての$p\geq 2$に対して、単値作用素の$(p-1)$th微分がリプシッツ連続であると仮定すると、この構成を二分線探索と組み合わせて、少なくとも$\varepsilon$ in $\widetilde{O}(\varepsilon^{-2/(3p-1)})$ oracle コールで接残差を持つ点を求める$p$th-order法を得る。 特に、以前の最もよく知られた$\widetilde{O}(\varepsilon^{-1/p})$ tangent-residual complexity と古典的な $O(\varepsilon^{-2/(p+1)})$ より弱い双対性-ギャップの基準の下での高次ハイブリッド近位法の境界を改良する。 我々は、この結果を、アルゴリズムをテンソルステップや他の所定の更新構造に制限することなく、$p$第1次オラクルモデルにおけるすべての決定論的アルゴリズムに対して$Ω(\varepsilon^{-2/(3p-1)})の最悪の低い値で補う。 したがって、提案手法は、すべての$p\geq2$に対して、対数係数まで$\varepsilon$に最適な依存が得られる。

関連論文リスト

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• 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)
• Primal-dual extrapolation methods for monotone inclusions under local Lipschitz continuity [1.0742675209112622]
  単調な包摂問題の解法として, 単調な外挿法を提案する。 提案手法は$cal O(log epsilon-1)$の演算複雑性を享受する。 また、凸円錐最適化の $varepsilon$-KKT や $varepsilon$-residual の解を求めるためにも得られる。
  論文  参考訳（メタデータ） (2022-06-02T10:31:45Z)
• 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)
• Generalized Optimistic Methods for Convex-Concave Saddle Point Problems [24.5327016306566]
  この楽観的な手法は凸凹点問題の解法として人気が高まっている。 我々は,係数を知らずにステップサイズを選択するバックトラックライン探索手法を開発した。
  論文  参考訳（メタデータ） (2022-02-19T20:31:05Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)

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

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