Sample path based convergence analysis of stochastic approximation algorithm: Theories and applications

The stochastic approximation (SA) algorithm, first proposed by American mathematicans Robbins and Monro, recursively finds the zero of an unknown function based on noisy observations. Due to the universality of the root-searching problem and the online computation in nature, the SA algorithm finds wide applications in systems and control, statistics, signal processing, etc. and much effort has been made on the investigation of the theoretical properties of the SA algorithm. From a sample path based convergence analysis point of view, in this paper we will recall some of the classical methods in this direction, including the probabilistic method, the ordinary differential equation method, and the trajectory-subsequence method. We will also investigate the applications of the SA algorithm to some active research problems in systems and control, including the recursive principal component analysis algorithm and the convergence of distributed randomized PageRank algorithm.