Stochastic Fixed-Point Iterations for Nonexpansive Maps: Convergence and Error Bounds

DOI10.1137/22M1515550arXiv2208.04193OpenAlexW4390977426MaRDI QIDQ6180255FDOQ6180255

Roberto Cominetti, Mario Bravo

Publication date: 19 January 2024

Published in: SIAM Journal on Control and Optimization (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/2208.04193

zbMATH Keywords

error bounds\(Q\)-learningconvergence ratesfixed pointsstochastic gradient descentnonexpansive mapsstochastic iterations

Mathematics Subject Classification ID

Stochastic approximation (62L20) Analysis of algorithms and problem complexity (68Q25) Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09) Fixed-point theorems (47H10) Fixed-point iterations (47J26) Numerical methods for mathematical programming, optimization and variational techniques (65Kxx)

Cites Work

• Title not available (Why is that?)
• Acceleration of Stochastic Approximation by Averaging
• Title not available (Why is that?)
• A Stochastic Approximation Method
• Robust Stochastic Approximation Approach to Stochastic Programming
• Stochastic approximation and its applications
• Construction of fixed points of nonlinear mappings in Hilbert space
• Quelques propriétés des opérateurs angle-bornes et n-cycliquement monotones
• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
• Stochastic forward-backward splitting for monotone inclusions
• Title not available (Why is that?)
• Stochastic Quasi-Fejér Block-Coordinate Fixed Point Iterations with Random Sweeping
• Stochastic approximations and perturbations in forward-backward splitting for monotone operators
• Stochastic Estimation of the Maximum of a Regression Function
• Title not available (Why is that?)
• Asynchronous stochastic approximation and Q-learning
• Learning algorithms for Markov decision processes with average cost
• Stochastic Approximation for Nonexpansive Maps: Application to Q-Learning Algorithms
• On the Convergence of Stochastic Iterative Dynamic Programming Algorithms
• Title not available (Why is that?)
• Stochastic approximation, cooperative dynamics and supermodular games
• Rates of convergence for inexact Krasnosel'skii-Mann iterations in Banach spaces
• On variance reduction for stochastic smooth convex optimization with multiplicative noise
• Variance-Based Extragradient Methods with Line Search for Stochastic Variational Inequalities

This page was built for publication: Stochastic Fixed-Point Iterations for Nonexpansive Maps: Convergence and Error Bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6180255)