Sufficient and necessary condition for the convergence of stochastic approximation algorithms (Q2489838): Difference between revisions

Consider the problem of finding the extreme values of non-random real-valued \(H \in C^1(R^N)\) or roots of vector-valued functions \(R \in C^1(R^N,R^N)\). Assume that \(H\) has finitely many isolated local minima and \(R\) finitely many isolated attractors. There is a well-known stochastic approximation theory with very widespread applications proposed originally by \textit{H. Robbins} and \textit{S. Monro} (1951) and discussed by many authors later (e.g., \textit{Nevelson} and \textit{Has'minskii} (1976), \textit{H.-J. Kushner} and \textit{D. S. Clark} (1978), \textit{Yin} and \textit{Yin} (1994), Benveniste et al (1990), among others) in order to find the minima of \(H\) or roots of \(R\). The main aim of this paper is to present sufficient and necessary conditions for the convergence of stochastic approximation algorithms relying on the study of the asymptotic behavior of stochastic differential equations (SDE) \[ dX(t) = \eta (t) [ - \nabla H(X(t)) dt + \beta (t) dW(t) ],\text{ and } dX(t) = \eta (t) [ R(X(t)) dt + \beta (t) dW(t) ], \] driven by an \(N\)-dimensional Wiener process as time \(t \to +\infty\). (Note that \(R \in C^1(R^N,R^N)\) does not have to be the gradient of a function, but the roots of \(R(x)=0\) are to be found as one of the main applications). Especially, the authors answer the question on a proper definition of an ``optimal solution'' to ensure that \(X(t)\) converges in probability to the ``optimal solution''. Necessary and sufficient conditions on the convergence are expressed in terms of integrals involving the coefficients \(\eta\) and \(\beta\), and limits \(\lim_{t \to +\infty} \beta (t) \sqrt{\eta(t)} = 0\) for the nonautonomous potentials \(\eta (t) H\) or given functions \(\eta (t) R\). The main results are remarkable since most of the so far known contributions deal with various sufficient conditions only. The here obtained conditions are sufficiently simple and have some physical meaning.