# Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds

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

## Key facts

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

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

- [Stochastic Halpern iteration in normed spaces and applications to reinforcement learning](https://mlsanity.com/paper/2403.12338/) (2024)
- [Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise](https://mlsanity.com/paper/2409.19546/) (2024)
- [A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Properties](https://mlsanity.com/paper/2305.05828/) (2023)
- [Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2409.12135/) (2024)
- [Asymptotic regularity of a generalised stochastic Halpern scheme](https://mlsanity.com/paper/2411.04845/) (2024)
- [O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation](https://mlsanity.com/paper/2504.19375/) (2025)
- [Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2505.21391/) (2025)
- [Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity](https://mlsanity.com/paper/2402.05071/) (2024)
- [Learning to Control Unknown Strongly Monotone Games](https://mlsanity.com/paper/2407.00575/) (2024)
- [Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization](https://mlsanity.com/paper/2608.12043/) (2026)
- [Stable Nonconvex-Nonconcave Training via Linear Interpolation](https://mlsanity.com/paper/2310.13459/) (2023)
- [Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis](https://mlsanity.com/paper/2501.10806/) (2025)
- [Policy Gradient Algorithms in Average-Reward Multichain MDPs](https://mlsanity.com/paper/2602.18003/) (2026)
- [Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process](https://mlsanity.com/paper/2606.16729/) (2026)
- [Solving Stochastic Fixed-Point Equations with High Probability](https://mlsanity.com/paper/2607.09097/) (2026)
- [Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis](https://mlsanity.com/paper/2603.19648/) (2026)
- [Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learning](https://mlsanity.com/paper/2605.11289/) (2026)
- [Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework](https://mlsanity.com/paper/2605.31309/) (2026)
- [A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps](https://mlsanity.com/paper/2608.15966/) (2026)
- [A regret minimization approach to fixed-point iterations](https://mlsanity.com/paper/2509.21653/) (2025)
- [Bridging the Gap Between Average and Discounted TD Learning](https://mlsanity.com/paper/2605.02103/) (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)
- [Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approach](https://mlsanity.com/paper/2607.17595/) (2026)
- [Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity](https://mlsanity.com/paper/2609.28543/) (2026)

## Abstract (arXiv)

We study a stochastically perturbed version of the well-known Krasnoselski--Mann iteration for computing fixed points of nonexpansive maps in finite dimensional normed spaces. We discuss sufficient conditions on the stochastic noise and stepsizes that guarantee almost sure convergence of the iterates towards a fixed point, and derive non-asymptotic error bounds and convergence rates for the fixed-point residuals. Our main results concern the case of a martingale difference noise with variances that can possibly grow unbounded. This supports an application to reinforcement learning for average reward Markov decision processes, for which we establish convergence and asymptotic rates. We also analyze in depth the case where the noise has uniformly bounded variance, obtaining error bounds with explicit computable constants.