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