mlsanityData to 14 Oct 2026

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

arXiv 2208.04193 ↗First posted 8 Aug 2022math.OCcited by 24

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 6; 2025: 4; 2026: 12.

24 papers.

Sort:

By area:

  1. 2024Stochastic Halpern iteration in normed spaces and applications to reinforcement learningcited by 12
  2. 2024Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noisecited by 10
  3. 2023A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Propertiescited by 5
  4. 2024Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
  5. 2024Asymptotic regularity of a generalised stochastic Halpern schemecited by 5
  6. 2025O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximationcited by 5
  7. 2025Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
  8. 2024Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexitycited by 4
  9. 2024Learning to Control Unknown Strongly Monotone Gamescited by 4
  10. 2026Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularizationcited by 4
  11. 2023Stable Nonconvex-Nonconcave Training via Linear Interpolationcited by 3
  12. 2025Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysiscited by 3
12 more
  1. 2026Policy Gradient Algorithms in Average-Reward Multichain MDPscited by 3
  2. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 3
  3. 2026Solving Stochastic Fixed-Point Equations with High Probabilitycited by 3
  4. 2026Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysiscited by 1
  5. 2026Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learningcited by 1
  6. 2026Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Frameworkcited by 1
  7. 2026A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Mapscited by 1
  8. 2025A regret minimization approach to fixed-point iterationscited by 0
  9. 2026Bridging the Gap Between Average and Discounted TD Learningcited by 0
  10. 2026Non-Expansive Two-Time-Scale Stochastic Approximation: A Fixed-Schedule One-Quarter Barrier and Bias-Corrected Accelerationcited by 0
  11. 2026Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approachcited by 0
  12. 2026Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexitycited by 0