Convergence of Stochastic Approximation via Martingale and Converse Lyapunov Methods

In this paper, we study the global convergence properties of the stochastic approximation (SA) algorithm, first proposed by Robbins and Monro (1951). At present, most available proofs of convergence make use of the so-called ODE method, whereby it is shown that the (random) sample paths of the SA algorithm begin to track the (deterministic) solution trajectories of an associated ODE. If the ODE has only one globally attractive equilibrium, then under additional assumptions, the SA algorithm converges to the desired solution. Our objective in the present paper is to provide an alternate proof based on martingale methods. We show that the stochastic approximation algorithm converges almost surely to the desired solution, when an associated ODE is globally asymptotically stable. We first present a general theorem based on the existence of a Lyapunov function having suitable properties. Unlike existing results, we do not require the global exponential stability of the equilibrium. Then we study specific situations where the existence of a suitable Lyapunov function can be established—so-called “converse Lyapunov theory.” We state and prove a new converse Lyapunov theorem for global exponential stability, which should be of independent interest to researchers in stability theory, apart from those working on stochastic approximation. We show through examples that our theory covers situations that are not covered by known results. Next, we study an alternate version of SA, first introduced by Kiefer and Wolfowitz (1952). The objective of that paper was to find a stationary point of a scalar-valued function, using first-order differences to approximate its gradient. This problem was further analyzed by Blum (1954), but with a very opaque proof. We simplify Blum’s proof using the proposed framework, for the common case where the function to be minimized is convex. In addition, we also present some extensions of the results in the paper by Gladyshev (1965), who pioneered the martingale approach. A few applications of the theory are also included.