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

arXiv: https://arxiv.org/abs/2609.28543 · HTML: https://mlsanity.com/paper/2609.28543/

## 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 (most cited first, 19 of 19)

- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [The Complexity of Making the Gradient Small in Stochastic Convex Optimization](https://mlsanity.com/paper/1902.04686/) (2019)
- [Exact Optimal Accelerated Complexity for Fixed-Point Iterations](https://mlsanity.com/paper/2201.11413/) (2022)
- [Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds](https://mlsanity.com/paper/2208.04193/) (2022)
- [Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization](https://mlsanity.com/paper/2208.05925/) (2022)
- [Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions](https://mlsanity.com/paper/2203.09436/) (2022)
- [Convergence rate analysis of several splitting schemes](https://mlsanity.com/paper/1406.4834/) (2014)
- [Optimal error bounds for nonexpansive fixed-point iterations in normed spaces](https://mlsanity.com/paper/2108.10969/) (2021)
- [Stochastic Halpern iteration in normed spaces and applications to reinforcement learning](https://mlsanity.com/paper/2403.12338/) (2024)
- [Inertial Krasnoselskii-Mann Iterations](https://mlsanity.com/paper/2210.03791/) (2022)
- [Asymptotic regularity of a generalised stochastic Halpern scheme](https://mlsanity.com/paper/2411.04845/) (2024)
- [Stochastic Krasnoselskii-Mann Iterations: Convergence without Uniformly Bounded Variance](https://mlsanity.com/paper/2604.22581/) (2026)
- [Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization](https://mlsanity.com/paper/2608.12043/) (2026)
- [Solving Stochastic Fixed-Point Equations with High Probability](https://mlsanity.com/paper/2607.09097/) (2026)
- [Sharp convergence rates for averaged nonexpansive maps](https://mlsanity.com/paper/1606.05300/) (2016)
- [Krasnoselskii-Mann Iterations: Inertia, Perturbations and Approximation](https://mlsanity.com/paper/2401.16870/) (2024)
- [Fast Krasnoselskii-Mann Method with Overrelaxation and Preconditioners](https://mlsanity.com/paper/2411.18574/) (2024)
- [A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications](https://mlsanity.com/paper/2512.13547/) (2025)
- [Mini-Batch Stochastic Krasnosel'skiui-Mann Algorithm for Nonexpansive Fixed Point Problems](https://mlsanity.com/paper/2604.06909/) (2026)

## 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].