Asymptotic behavior of stochastic approximation and large deviations
Asymptotic behavior of stochastic approximation and large deviations
复制标题
随机近似和大偏差的渐近行为
DOI：
10.1109/tac.1984.1103434
复制
发表时间：
1983
期刊：
影响因子：
--
通讯作者：
H. Kushner
中科院分区：
文献类型：
--
作者：
H. Kushner
应用大偏差理论研究了随机逼近算法（1.1）和（1.2）的渐近性质。该方法提供了一个有用的替代目前使用的技术，获得收敛速度的结果，通过研究序列{（Xn-<$）/<$an}（对于（1.1）），其中<$是一个'稳定'点的算法。设G是<$的一个有界邻域，对于“极限常微分方程”，G在<$的吸引域中。过程xn（<$）被定义为{Xj，j <$n}的“自然插值”，其中xn（0）= Xn，并且插值间隔{aj，j <$n}。定义<$G n = min{t：xn（t）<$G}。然后证明了Px{<$G n <$T} ~ exp-nqV，其中q依赖于{an，cn}，V依赖于B（<$）cov <$n，G.这样的估计意味着渐近行为比建议的“局部线性化方法”，他们产生了许多新的见解的渐近行为。该技术适用于递归算法的渐近分析中的相关问题，并且比“线性化方法”需要更弱的动力学条件。提供了必要的基本背景，并导出了与获得上述V相关的最优控制问题。
The theory of large deviations is applied to the study of the asymptotic properties of the stochastic approximation algorithms (1.1) and (1.2). The method provides a useful alternative to the currently used technique of obtaining rate of convergence results by studying the sequence {(Xn-¿)/¿an} (for (1.1)), where ¿ is a 'stable' point of the algorithm. Let G be a bounded neighborhood of ¿, which is in the domain of attraction of ¿ for the 'limit ODE'. The process xn(¿) is defined as a 'natural interpolation' of {Xj,j¿n} with xn(0) = Xn, and interpolation intervals {aj,j¿n}. Define ¿G n = min{t:xn(t)¿G}. Then it is shown (among other things) that Px{¿G n ¿ T} ~ exp-nqV, where q depends on {an,cn}, and V depends on the b(¿) cov ¿n, and G. Such estimates imply that the asymptotic behavior is much better than suggested by the 'local linearization methods', and they yield much new insight into the asymptotic behavior. The technique is applicable to related problems in the asymptotic analysis of recursive algorithms, and requires weaker conditions on the dynamics than do the 'linearization methods'. The necessary basic background is provided and the optimal control problems associated with getting the V above are derived.