随机逼近算法的样本轨道分析:理论及应用

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

随机逼近算法递推地求解未知函数的零点,自20世纪50年代美国数学家Robbins和Monro给出这类算法以始,由于其处理对象的普适性和在线计算的特点,在系统控制、统计和信号处理等领域得到了广泛应用,关于这类算法的理论探讨引发了许多各具特色的后继研究.本文将从样本轨道这个角度出发,回顾随机逼近算法收敛性分析的几类方法和思想脉络,包括概率方法、常微分方程方法和轨线-子序列(trajectory-subsequence,TS)方法等,并给出随机逼近算法在递推主成分分析和分布式随机化Page Rank算法中的具体应用.

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 Page Rank algorithm.