mlsanityData to 14 Oct 2026

Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity

arXiv 2609.28543 ↗First posted 22 Sep 2026stat.ML cs.LG math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

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(frac1K +fracσlog K√ K +fracBKlog KKright), ] where K is the horizon, σ is the noise level and BK is the accumulated root-mean-square bias. When BK=O(√ 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].

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 19 of its 29 references that are in the map. First posted on arXiv 22 Sep 2026.

Builds on

19 of 29 references.

References · 19

  1. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 57
  2. 2019The Complexity of Making the Gradient Small in Stochastic Convex Optimizationcited by 34
  3. 2022Exact Optimal Accelerated Complexity for Fixed-Point Iterationscited by 25
  4. 2022Stochastic fixed-point iterations for nonexpansive maps: Convergence and error boundscited by 24
  5. 2022Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimizationcited by 20
  6. 2022Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusionscited by 19
  7. 2014Convergence rate analysis of several splitting schemescited by 13
  8. 2021Optimal error bounds for nonexpansive fixed-point iterations in normed spacescited by 12
  9. 2024Stochastic Halpern iteration in normed spaces and applications to reinforcement learningcited by 12
  10. 2022Inertial Krasnoselskii-Mann Iterationscited by 5
  11. 2024Asymptotic regularity of a generalised stochastic Halpern schemecited by 5
  12. 2026Stochastic Krasnoselskii-Mann Iterations: Convergence without Uniformly Bounded Variancecited by 5
7 more
  1. 2026Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularizationcited by 4
  2. 2026Solving Stochastic Fixed-Point Equations with High Probabilitycited by 3
  3. 2016Sharp convergence rates for averaged nonexpansive mapscited by 2
  4. 2024Krasnoselskii-Mann Iterations: Inertia, Perturbations and Approximationcited by 2
  5. 2024Fast Krasnoselskii-Mann Method with Overrelaxation and Preconditionerscited by 1
  6. 2025A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applicationscited by 1
  7. 2026Mini-Batch Stochastic Krasnosel'skiui-Mann Algorithm for Nonexpansive Fixed Point Problemscited by 1

Built on by

Not cited yet.