論文の概要: Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding

• arxiv url: http://arxiv.org/abs/2609.36033v1
• Date: Mon, 28 Sep 2026 18:04:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-30 21:28:46.924999
• Title: Dual-Anchor Acceleration Is Near-Optimal for Stochastic Monotone Root-Finding
• Title（参考訳）: 二重アンカー加速は確率的モノトンルートフィンディングに最適である
• Abstract要約: O (LD / ) ell + (2 / 2) ell2)$, $ell = log (1 + LD / )$ と $D$ は解の最初の距離である。 この結果は、これらのサンプリングワイズ仮定の下で、ノイズに支配された状態における最もよく知られたオラクルの複雑さを改善する。
• 参考スコア（独自算出の注目度）: 15.2286904549704
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Among distinct optimal acceleration mechanisms for deterministic monotone root-finding problems and fixed-point problems, dual-anchoring has recently been shown to admit a more robust direct stochastic extension than standard anchor acceleration. However, without additional strong monotonicity, the existing stochastic dual-anchoring guarantee has two limitations: first, it requires cocoercivity in expectation, and second, it attains only $O(ε^{-3})$ oracle complexity, leaving a gap to the near-optimal $\tilde{O}(ε^{-2})$ complexity achieved by other methods. In this work, we address both of these limitations by combining dual-anchoring with stochastic resolvent approximation and optimized variance control. For unbiased stochastic oracles with variance bounded by $σ^2$, where sample operators are monotone and uniformly $L$-Lipschitz, our algorithm finds a point with $ε$-residual with a near-optimal oracle complexity of $O ( (LD / ε) \ell + (σ^2 / ε^2) \ell^2)$, where $\ell = \log (1 + LD / ε)$ and $D$ is the initial distance to a solution. This result improves the best known oracle complexity in the noise-dominated regime under these samplewise assumptions, reducing the poly-logarithmic factor from cubic to quadratic.
• Abstract（参考訳）: 決定論的単調なルートフィニング問題と固定点問題に対する最適な加速機構のうち、双対アンチョリングは、最近標準アンカー加速度よりも頑健な直接確率的拡張が認められた。 しかし、より強い単調性なしでは、既存の確率的双対アンカリング保証には2つの制限がある: 1つ目は、期待において共保力を必要とすること、2つめは、O(ε^{-3})$オラクルの複雑さにのみ到達し、その差は、他の方法によって達成される、ほぼ最適の$\tilde{O}(ε^{-2})$複雑性に留まる。 本研究では,2重アンカリングと確率論的リゾルト近似を組み合わせ,分散制御を最適化することにより,これらの制約に対処する。 サンプル作用素が単調で均一に$L$-Lipschitz であるような σ^2$ で有界な確率的オラクルに対して、我々のアルゴリズムは、$O ( ( (LD / ε) \ell + (σ^2 / ε^2) \ell^2)$, $\ell = \log (1 + LD / ε)$ と $D$ が解の最初の距離である点を求める。 この結果は、これらの標本的な仮定の下で、ノイズに支配された状態において最もよく知られたオラクルの複雑さを改善し、多対数因子を立方体から二次体へと減少させる。

関連論文リスト

• Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity [66.59610645394376]
  実空間における非拡大作用素の固定点を求めるための単純慣性クラスノセル・スキーマン法(iKM)を解析する。 KM(Bravo and Cominetti, 2024)に慣性外挿を2つ加えるだけで, 1回に1回, バイアスのあるオラクルに1回呼び出すことができる。 また、KM[Bravo Cominetti, 2024]に対する、よく知られた$O(-4)$ランダムイテレート保証を改善している。
  論文  参考訳（メタデータ） (2026-09-22T23:57:59Z)
• SGHA: A Single-Loop Fully First-Order Algorithm for Nonconvex-Strongly-Convex Bilevel Optimization [9.118433290504035]
  我々は、Stoc-SGHAが$Oleft(bar_y-4)$のオラクル複雑性を、任意の$in(1)$に対して少なくとも$$$と、追加の仮定の下で$Oleft(bar_y-4)$の複雑さを達成することを示す。 決定論的設定では、Stoc-SGHAは$Oleft(bar_y)$のオラクル複雑性を少なくとも$in(1)$に対して$$$$$で達成し、$Oleft(bar_y)$以下の複雑さを達成している。
  論文  参考訳（メタデータ） (2026-08-24T13:00:40Z)
• Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization [15.2286904549704]
  二重アンカー機構,すなわち二重アンカー機構が,そのようなエラーの蓄積を伴わずに反復設定にまで拡張されていることを示す。 強い単調作用素の場合、同じアルゴリズムはよりシャープな複雑さを達成し、$$-dependenceという観点で下界とほぼ一致する。
  論文  参考訳（メタデータ） (2026-08-12T13:25:55Z)
• MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimization [6.024178662558234]
  本稿では,DC正則化を用いた非制約問題のクラスを示す。 証明可能な複雑性保証を伴う問題に対してMomentum Mo Mo Penalty法を提案する。
  論文  参考訳（メタデータ） (2026-05-28T09:06:26Z)
• Discrete Double-Bracket Flows for Isotropic-Noise Invariant Eigendecomposition [7.186083931122418]
  本研究では,行列ベクトル積 (MVP) のオラクルによる行列フリー固有分解について検討した。 標準的な近似法では、安定性を$|C_k|$に結合する固定ステップを使用するか、あるいは更新の消滅によって遅くなる適応ステップを使用する。 対角化目標と入力-状態安定性解析のための厳密なサドルと、トレースフリーな摂動の下での複雑さのスケーリングを$O(|C_e|2 / (2))$とすることで、グローバル収束を確立する。
  論文  参考訳（メタデータ） (2026-02-14T13:09:29Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods [57.050204432302195]
  本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。 我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
  論文  参考訳（メタデータ） (2022-11-03T14:12:51Z)
• A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization [12.096252285460814]
  合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。 提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
  論文  参考訳（メタデータ） (2022-02-09T06:05:38Z)
• 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)

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

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