论文标题
通过Martingale和Converse Lyapunov方法的随机近似的收敛性
Convergence of Stochastic Approximation via Martingale and Converse Lyapunov Methods
论文作者
论文摘要
在本文中，我们研究了随机近似（SA）算法的几乎确定的界限和收敛性。目前，大多数可用的收敛证明是基于ODE方法，而迭代的几乎确定的界限是一个假设，而不是结论。在Borkar-Meyn（2000）中，表明，如果ODE只有一个具有全球吸引人的平衡，则在其他假设下，迭代几乎肯定会界定，并且SA算法会收敛到所需的解决方案。本文中我们的目标是基于Martingale方法提供上述替代证明，而Martingale方法比基于ODE方法的方法更简单且技术较少。作为前奏，我们证明了颂歌的全球渐近稳定性是一种新的足够条件。接下来，我们证明了一个“匡威” lyapunov定理，该定理具有适当的lyapunov函数，该函数具有全球有限的黑森，用于全球稳定的系统。两种定理对稳定理论的研究人员都具有独立的兴趣。然后，使用这些结果，我们为几乎确定的有限性和SA算法的收敛提供了足够的条件。我们通过示例表明，我们的理论涵盖了当前已知结果，特别是Borkar-Meyn（2000）的某些情况。
In this paper, we study the almost sure boundedness and the convergence of the stochastic approximation (SA) algorithm. At present, most available convergence proofs are based on the ODE method, and the almost sure boundedness of the iterations is an assumption and not a conclusion. In Borkar-Meyn (2000), it is shown that if the ODE has only one globally attractive equilibrium, then under additional assumptions, the iterations are bounded almost surely, and the SA algorithm converges to the desired solution. Our objective in the present paper is to provide an alternate proof of the above, based on martingale methods, which are simpler and less technical than those based on the ODE method. As a prelude, we prove a new sufficient condition for the global asymptotic stability of an ODE. Next we prove a "converse" Lyapunov theorem on the existence of a suitable Lyapunov function with a globally bounded Hessian, for a globally exponentially stable system. Both theorems are of independent interest to researchers in stability theory. Then, using these results, we provide sufficient conditions for the almost sure boundedness and the convergence of the SA algorithm. We show through examples that our theory covers some situations that are not covered by currently known results, specifically Borkar-Meyn (2000).
