Convergence of stochastic approximation via martingale and converse Lyapunov methods

Vidyasagar, Mathukumalli (2023) Convergence of stochastic approximation via martingale and converse Lyapunov methods. Mathematics of Control, Signals, and Systems, 35 (2). pp. 351-374. ISSN 0932-4194

Full text not available from this repository. (Request a copy)

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 and Meyn (SIAM J Control Optim 38:447–469, 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 and Meyn (2000).

[error in script]

IITH Creators:

IITH Creators	ORCiD
Vidyasagar, Mathukumalli	https://orcid.org/0000-0003-1057-1942

Item Type:

Article

Uncontrolled Keywords:

converse Lyapunov theory; global asymptotic stability; martingale methods; Stochastic approximation; Approximation algorithms; Approximation theory; Asymptotic stability; Lyapunov functions; Ordinary differential equations; Stochastic systems; Almost sure boundedness; Condition; Converse Lyapunov theorem; Converse Lyapunov theory; Global asymptotic stability; Lyapunov's methods; Martingale method; Simple++; Stochastic approximation algorithms; Stochastic approximations; Lyapunov methods

Subjects:

Electrical Engineering

Divisions:

Department of Electrical Engineering

Depositing User:

Mr Nigam Prasad Bisoyi

Date Deposited:

26 Nov 2023 06:21

Last Modified:

26 Nov 2023 06:21

URI:

http://raiithold.iith.ac.in/id/eprint/11756