Asymptotic behavior of constrained stochastic approximations via the theory of large deviations (Q1080265): Difference between revisions

Let G be a bounded convex set, and \(\Pi_ G\) the projection onto G, and \(\{\xi_ j\}^ a \)bounded random process. Projected algorithms of the types \[ X^{\epsilon}_{n+1}=\Pi_ G(X_ n^{\epsilon}+\epsilon b(X_ n^{\epsilon},\xi_ n))\quad (or\quad X_{n+1}=\Pi_ G(X_ n+a_ nb(X_ n,\xi_ n)), \] where \(0<a_ n\to 0\), \(\sum a_ n=\infty)\) occur frequently in applications (among other places) in control and communications theory. The asymptotic convergence properties of \(\{X_ n^{\epsilon}\}\) as \(\epsilon\) \(\to 0\), \(\epsilon\) \(n\to \infty\), have been well analyzed in the literature. Here, we use large deviations methods to get a more thorough understanding of the global behavior. Let \(\theta\) be a stable point of the algorithm in the sense that \(X_ n^{\epsilon}\to \theta\) in distribution as \(\epsilon\) \(\to 0\), \(n\epsilon\) \(\to \infty\). For the unconstrained case, rate of convergence results involve showing asymptotic normality of \(\{(X_ n^{\epsilon}- \theta)/\sqrt{\epsilon}\}\), and use linearizations about \(\theta\). In the constrained case \(\theta\) is often on \(\partial G\), and such methods are inapplicable. But the large deviations method yields an alternative which is often more useful in the applications. The action functionals are derived and their properties (lower semicontinuity, etc.) are obtained. The statistics (mean value, etc.) of the escape times from a neighborhood of \(\theta\) are obtained, and the global behavior on the infinite interval is described.