Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity
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 (1/K +(σlog K)/√K +(BKlog K)/K), where K is the horizon, σ is the noise level and BK is the accumulated root-mean-square bias. When BK=O(√K), this yields Õ(ε−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].
Related
- Continuized Nesterov Momentum Achieves the O(ε−7/4) Complexity in Smooth Nonconvex Optimization
- Optimal Oracle Complexity of Dual Halpern Iteration in Normed Spaces
- Continuous Policy and Value Iteration for Stochastic Control Problems with Inhomogeneous Synchronous Coupling
- SDDP has polynomial iteration complexity in the horizon
- Amortized Score-Hamiltonian Policy Iteration: A Grid-Free Scheme for Relaxed Stochastic Control Problems
BibTeX
@misc{yang2026stochastic,
title = {{Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity}},
author = {Tong Yang and Tao Jiang and Yuejie Chi and Ashok Cutkosky and Lin Xiao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.28543},
eprint = {2609.28543},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28543},
}
RIS
TY - UNPB
TI - Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity
AU - Tong Yang
AU - Tao Jiang
AU - Yuejie Chi
AU - Ashok Cutkosky
AU - Lin Xiao
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.28543
UR - https://arxiv.org/abs/2609.28543
AB - 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 (1/K +(σlog K)/√K +(B_Klog K)/K), where K is the horizon, σ is the noise level and B_K is the accumulated root-mean-square bias. When B_K=O(√K), this yields Õ(ε^−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].
ER -