Convergence of Stochastic Approximation via Martingale and Converse
  Lyapunov Methods
  This paper is dedicated to Prof. Eduardo Sontag on the occasion of his
seventieth birthday. In this paper, we build upon the ideas first proposed in
Gladyshev (1965) to develop a very general framework for proving the almost
sure boundedness and the convergence of stochastic approximation algorithms.
These ideas are based on martingale methods and are in some ways simpler than
convergence proofs based on the ODE method, e.g., Borkar-Meyn (2000). First we
study the original version of the SA algorithm introduced in Robbins-Monro
(1951), where the objective is to determine a zero of a function, when only
noisy measurements of the function are available. The proof makes use of the
general framework developed here, together with a new theorem on converse
Lyapunov stability, which might be of independent interest. Next we study an
alternate version of SA, first introduced in Kiefer-Wolfowitz (1952). The
objective here is to find a stationary point of a scalar-valued function, using
first-order differences to approximate its gradient. This problem is analyzed
in Blum (1954), but with a very opaque proof. We reproduce Blum's conclusions
using the proposed framework.
