Full Text: PDF
DOI: 10.23952/cot.2025.39
Received May 3, 2024; Accepted December 12, 2024; Published online August 17, 2025
Abstract. We begin by briefly surveying some results on the convergence of the Stochastic Gradient Descent (SGD) Method, proved in a recent paper. These results are based on viewing SGD as a version of Stochastic Approximation (SA). Ever since its introduction in the classic paper of Robbins and Monro in 1951, SA has become a standard tool for finding a solution of an equation of the form 
, when only noisy measurements of 
are available. In most situations, every component of the putative solution $\theta_t$ is updated at each step 
. In some applications in Reinforcement Learning (RL), only one component of 
is updated at each . This is known as asynchronous SA. In this paper, we study Block Asynchronous SA (BASA), in which, at each step , some but not necessarily all components of are updated. The theory presented here embraces both conventional (synchronous) SA as well as asynchronous SA, and all in-between possibilities. We provide sufficient conditions for the convergence of BASA, and also prove bounds on the rate of convergence of to the solution. For the case of conventional SGD, these results reduce to those proved in our companion paper. Then we apply these results to the problem of finding a fixed point of a map with only noisy measurements. This problem arises frequently in RL. We prove sufficient conditions for convergence as well as estimates for the rate of convergence.
How to Cite this Article:
R.L. Karandikar, M. Vidyasagar, Recent advances in stochastic approximation with applications to optimization and fixed point problems, Commun. Optim. Theory 2025 (2025) 39.