# Stochastic Krasnoselskii-Mann Iterations: Convergence without Uniformly Bounded Variance

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Apr 2026.

## Built on by (most cited first, 5 of 5)

- [Quadratic Objective Perturbation: Curvature-Based Differential Privacy](https://mlsanity.com/paper/2605.05905/) (2026)
- [Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Acceleration](https://mlsanity.com/paper/2607.13414/) (2026)
- [Stochastic Nonconvex Bilevel Optimization: Improved Rates Without Rare-Visit Assumption](https://mlsanity.com/paper/2609.06580/) (2026)
- [Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps](https://mlsanity.com/paper/2609.09524/) (2026)
- [Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity](https://mlsanity.com/paper/2609.28543/) (2026)

## Abstract (arXiv)

We investigate the Stochastic Krasnoselskii-Mann iterations for expected nonexpansive fixed-point problems in a real separable Hilbert space. We establish convergence guarantees under significantly weaker assumptions on the variance than those typically used in the literature. In particular, instead of a uniform bound on the variance of the stochastic oracle, we only assume finite variance at a single fixed point. Under this assumption, we prove almost sure weak convergence of the iterates, derive convergence rates for the expected residual and the last-iterate residual, and obtain almost sure convergence rates for the running minimum residual. Notably, we recover the best-known stochastic oracle complexity without imposing uniformly bounded variance. We illustrate the applicability of our results to Stochastic Gradient Descent, where we recover known guarantees, to Stochastic Three-Operator Splitting and Stochastic Backward-Forward Splitting, for which we obtain the first results that avoid uniform variance bounds, and to a novel Stochastic Lifted Three-Operator Splitting.