Convergence of stochastic approximation via martingale and converse Lyapunov methods
From MaRDI portal
Publication:6097904
DOI10.1007/S00498-023-00342-9zbMATH Open1518.93148arXiv2205.01303MaRDI QIDQ6097904FDOQ6097904
Authors: M. Vidyasagar 
Publication date: 7 June 2023
Published in: MCSS. Mathematics of Control, Signals, and Systems (Search for Journal in Brave)
Abstract: In this paper, we study the almost sure boundedness and the convergence of the stochastic approximation (SA) algorithm. At present, most available convergence proofs are based on the ODE method, and the almost sure boundedness of the iterations is an assumption and not a conclusion. In Borkar-Meyn (2000), it is shown that if the ODE has only one globally attractive equilibrium, then under additional assumptions, the iterations are bounded almost surely, and the SA algorithm converges to the desired solution. Our objective in the present paper is to provide an alternate proof of the above, based on martingale methods, which are simpler and less technical than those based on the ODE method. As a prelude, we prove a new sufficient condition for the global asymptotic stability of an ODE. Next we prove a "converse" Lyapunov theorem on the existence of a suitable Lyapunov function with a globally bounded Hessian, for a globally exponentially stable system. Both theorems are of independent interest to researchers in stability theory. Then, using these results, we provide sufficient conditions for the almost sure boundedness and the convergence of the SA algorithm. We show through examples that our theory covers some situations that are not covered by currently known results, specifically Borkar-Meyn (2000).
Full work available at URL: https://arxiv.org/abs/2205.01303
Recommendations
- scientific article; zbMATH DE number 1918629
- scientific article; zbMATH DE number 695867
- On the convergence of linear stochastic approximation procedures
- Stability and instability of limit points for stochastic approximation algorithms
- The O.D.E. Method for Convergence of Stochastic Approximation and Reinforcement Learning
Generalizations of martingales (60G48) Asymptotic stability in control theory (93D20) Stochastic stability in control theory (93E15)
Cites Work
- Stochastic approximation methods for constrained and unconstrained systems
- Title not available (Why is that?)
- A Stochastic Approximation Method
- Title not available (Why is that?)
- Nonlinear systems.
- Applications of a Kushner and Clark lemma to general classes of stochastic algorithms
- New converse Lyapunov theorems and related results on exponential stability
- Title not available (Why is that?)
- Two models for analyzing the dynamics of adaptation algorithms
- Analysis of recursive stochastic algorithms
- Title not available (Why is that?)
- Nonlinear Systems Analysis
- An analysis of temporal-difference learning with function approximation
- The O.D.E. Method for Convergence of Stochastic Approximation and Reinforcement Learning
- Title not available (Why is that?)
- Stochastic approximation
- Bounds for Solutions of Ordinary Differential Equations
- Strong convergence of a stochastic approximation algorithm
- A stability criterion for two timescale stochastic approximation schemes
Cited In (7)
- Stability and instability of limit points for stochastic approximation algorithms
- On the convergence, lock-in probability, and sample complexity of stochastic approximation
- Title not available (Why is that?)
- Convergence of stochastic approximation via martingale and converse Lyapunov methods
- Convergence of Markovian stochastic approximation with discontinuous dynamics
- Convergence rates for stochastic approximation: biased noise with unbounded variance, and applications
- A concentration bound for stochastic approximation via Alekseev's formula
This page was built for publication: Convergence of stochastic approximation via martingale and converse Lyapunov methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6097904)
