Stochastic Approximation and Large Deviations: Upper Bounds and w.p.1 Convergence

With probability one convergence results are obtained for stochastic recursive approximation algorithms under very general conditions. The gain sequence \ aₙ \ can go to zero very slowly and state-dependent noise, discontinuous dynamical equations, and the projected or constrained algorithm are all treated. The basic technique is the theory of large deviations. Prior results obtained via this theory are extended in many directions. Let x = b(x) denote the “mean” equation for the algorithm, let δ > 0 be given, and let G(θ ) be a neighborhood of a stable point θ of that ordinary differential equation. Then, asymptotic upper bounds to aN log P\ Xₙ ∉ G(θ ),n N | XN - θ | δ \, are obtained. These are often more informative than the usual classical rate of convergence results (that use a “local linearization”) and, furthermore, are obtained for the constrained and nonsmooth cases, for which there are no “rate of convergence” results. The methods are also used to extend currently available upper bounds for algorithms with constant gains, with simpler proofs.