論文の概要: Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity

• arxiv url: http://arxiv.org/abs/2609.28543v1
• Date: Tue, 22 Sep 2026 23:57:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-25 21:10:09.392144
• Title: Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity
• Title（参考訳）: 確率的慣性Krasnosel'skii-Mannイテレーションは、ほぼ最適サンプル複雑性を実現する
• Abstract要約: 実空間における非拡大作用素の固定点を求めるための単純慣性クラスノセル・スキーマン法(iKM)を解析する。 KM(Bravo and Cominetti, 2024)に慣性外挿を2つ加えるだけで, 1回に1回, バイアスのあるオラクルに1回呼び出すことができる。 また、KM[Bravo Cominetti, 2024]に対する、よく知られた$O(-4)$ランダムイテレート保証を改善している。
• 参考スコア（独自算出の注目度）: 66.59610645394376
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyze a simple stochastic inertial Krasnosel'skii--Mann (iKM) method for finding a fixed point of a nonexpansive operator in a real Hilbert space. Our method is obtained simply by adding two inertial extrapolations to stochastic KM [Bravo and Cominetti, 2024], and it retains one call to a possibly biased stochastic oracle per update and achieves sharp rates in both the stochastic and deterministic regimes. Specifically, with our proposed parameter schedule, we prove the following last-iterate fixed-point residual bound: \[ {O}\!\left(\frac{1}{K} +\frac{σ\log K}{\sqrt K} +\frac{B_K\log K}{K}\right), \] where $K$ is the horizon, $σ$ is the noise level and $B_K$ is the accumulated root-mean-square bias. When $B_K=O(\sqrt K)$, this yields $\widetilde O(ε^{-2})$ sample complexity that matches, up to a logarithmic factor, the stochastic-oracle lower bound given under the unbiased subclass of our model [Foster et al., 2019, Theorem 2]. It also improves the best-known $O(ε^{-4})$ random-iterate guarantee for stochastic KM [Bravo and Cominetti, 2024, Corollary 5.4]. To our knowledge, this is the first single-loop method for general nonexpansive fixed-point problems to attain this near-optimal sample complexity without variance reduction or batching. When the oracle is exact, the same method attains the worst-case-optimal $O(K^{-1})$ last-iterate residual rate [Park and Ryu, 2022, Theorem 4.6], improving the $O(K^{-1/2})$ rate of classical KM [Cominetti et al., 2014; Bravo and Cominetti, 2018].
• Abstract（参考訳）: 実ヒルベルト空間における非拡張作用素の固定点を求めるための単純な確率慣性クラスノセル-マン法(iKM)を解析する。 本手法は, 確率的KM (Bravo and Cominetti, 2024) に慣性外挿法を2つ加えただけで得られ, 1回の更新で偏りのある確率的オラクルへの呼び出しを1回保持し, 確率的および決定論的両体制の急激なレートを達成できる。 具体的には、提案したパラメータスケジュールを用いて、次の最後の定点残差境界を証明します。 \left(\frac{1}{K} +\frac{σ\log K}{\sqrt K} +\frac{B_K\log K}{K}\right), \] ここで、$K$は地平線、$σ$は雑音レベル、$B_K$は蓄積されたルート平均二乗バイアスである。 B_K=O(\sqrt K)$ とすると、これは対数係数まで一致するサンプル複雑性が$\widetilde O(ε^{-2})$ となる。 また、確率的KM[Bravo and Cominetti, 2024, Corollary 5.4]に対して、最もよく知られた$O(ε^{-4})$ランダムイテレート保証を改善している。 我々の知る限り、これは分散化やバッチ化を伴わずに、この準最適サンプル複雑性を達成するための一般的な非拡張的不動点問題に対する最初の単一ループ法である。 オラクルが正確であれば、同じ方法が最悪のケース-最適$O(K^{-1})$ラストイテレート残留率[Park and Ryu, 2022, Theorem 4.6]を達成し、古典的なKM(Cominetti et al , 2014; Bravo and Cominetti, 2018)の$O(K^{-1/2})$レートを改善する。

関連論文リスト

• Asymptotic-Preserving A Posteriori Analysis of Diffusion and Flow-Matching Samplers [0.6768558752130311]
  拡散及びフローマッチングサンプリングは、学習した確率フローODEを、大きなノイズスケールから小さな終端フロア($_min$)まで統合し、スコアが硬く、フローが境界層を発達させる。 特異摂動パラメータとして$_min$を扱い、どの固定ステップサンプリングが解けるかを決定する。
  論文  参考訳（メタデータ） (2026-07-05T04:48:33Z)
• Discrete Double-Bracket Flows for Isotropic-Noise Invariant Eigendecomposition [7.186083931122418]
  本研究では,行列ベクトル積 (MVP) のオラクルによる行列フリー固有分解について検討した。 標準的な近似法では、安定性を$|C_k|$に結合する固定ステップを使用するか、あるいは更新の消滅によって遅くなる適応ステップを使用する。 対角化目標と入力-状態安定性解析のための厳密なサドルと、トレースフリーな摂動の下での複雑さのスケーリングを$O(|C_e|2 / (2))$とすることで、グローバル収束を確立する。
  論文  参考訳（メタデータ） (2026-02-14T13:09:29Z)
• Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime [26.711510824243803]
  本研究では, 最適騒音が0または0に近い政権において, 円滑な凸目標に対する勾配降下(SGD)の集団収束保証について検討した。 十分に調整されたステップサイズでは、最後の繰り返しに対してほぼ最適な$widetildeO (1/T + sigma_star/sqrtT)$レートを得る。
  論文  参考訳（メタデータ） (2025-07-15T12:52:47Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Oblivious Stochastic Composite Optimization [47.48197617884748]
  我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。 3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。 我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)
• Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball [17.33867778750777]
  一般近似問題に対する勾配降下法(SGD)と重球法(SHB)について検討した。 SGD の場合、凸と滑らかな設定において、イテレートの重み付き平均に対して、最初の最も確実な収束式を提供する。
  論文  参考訳（メタデータ） (2020-06-14T11:12:05Z)

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

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