Convergence of sa algorithms in multi-root or multi-extreme cases
han-fu chen · Stochastics and stochastics reports · 1998
This paper gives necessary and sufficient conditions on the observation noise for convergence of Robbins—Monro (RM) type algorithms in the case where the regression function may have multi-roots, and for convergence of the Kiefer—Wolfowitz (KW) type algorithms in the case where the function may have multi-extrema. In both cases the algorithms are truncated at randomly varying bounds, and for the KW algorithms the randomized differences are used. As results, the conditions imposed on the regression function are possibly the weakest among the existing results