A weak convergence approach to large deviations for stochastic approximations

Stochastic approximation (SA) algorithms, first introduced by Robbins and Monro in the 1950's [24], has become one of the most important classes of stochastic numerical methods. Originally aimed at finding the the root of a continuous function given noisy observations, SA is now a fundamental tool in a range of areas such as statistics, optimization, electrical engineering, and machine learning, to mention but a few. Within the latter, the importance of SA algorithms is illustrated by the fact that a specific subclass of methods--stochastic gradient descent (SGD) methods--is central to the training of deep learning methods, and in reinforcement learning the standard methods (Q-learning and temporal-difference-learning) are variants of SA. The general class that is SA algorithms with state-dependent noise (see below for the definition) therefore constitute a rich and important family of stochastic recursive algorithms. In addition to the examples already mentioned (SGD, reinforcement learning), this class also includes persistent contrastive divergence, adaptive Markov chain Monte-Carlo (MCMC) and extended ensemble algorithms such as the Wang-Landau algorithm. The theory of SA stems from the pioneering work of Robbins and Monro [24] and Kiefer and Wolfowitz [20], and remains an active research area within probability theory. This is in part due to the many and diverse applications of SA algorithms where, due to the complex nature of the systems under considerations, different variants of the original Robbins-Monro algorithm are needed. In turn, developing the theoretical foundation for SA algorithms, such as, e.g., convergence results, central limit theorems, concentration results and results on deviations, is of fundamental importance; monographs covering many of the standard results of