Sufficient and necessary condition for the convergence of stochastic approximation algorithms

DOI10.1016/J.SPL.2005.07.020MaRDI QIDQ2489838zbMATH OpenOpenAlexWikidataFDO

Authors Neiping Chen, Wenbin Liu, Jianfeng Feng

Publication date 28 April 2006

Published in Statistics \& Probability Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.spl.2005.07.020

global minima local minima nonlinear dynamics simulated annealing stochastic algorithms stochastic differential equations stochastic optimization

Mathematics Subject Classification ID

Ordinary differential equations and systems with randomness (34F05) Generation, random and stochastic difference and differential equations (37H10) Stochastic ordinary differential equations (aspects of stochastic analysis) (60H10) Applications of stochastic analysis (to PDEs, etc.) (60H30) Stochastic approximation (62L20)

Review text

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.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Sufficient and necessary condition for the convergence of stochastic approximation algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2489838)