Necessary and sufficient conditions for the Robbins-Monro method

DOI10.1016/0304-4149(84)90011-5MaRDI QIDQ792727zbMATH OpenOpenAlexFDO

Authors Dean S. Clark

Publication date 1984

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-4149(84)90011-5

zbMATH Keywords

Counter-examples for non-convergence in probabilitydifferential inequalitiesembedded differential equationlaw of large numbersLyapunov functionRobbins-Monro methodweak law of large numbers

Mathematics Subject Classification ID

Strong limit theorems (60F15) (L^p)-limit theorems (60F25) Stochastic approximation (62L20)

Review text

Consider the Robbins-Monro method \(X_{n+1}=X_ n-a_ nf(X_ n)+a_ n\xi_ n\), \(a_ n\cong c/n\), \(c>0\), \(n=0,1,...\). This paper shows that the law of large numbers \(\lim_{n\to \infty}a_ n\sum^{n- 1}_{j=1}\xi_ j=0\) is necessary and sufficient for the convergence of \(X_ n\) to \(\theta\) of the unknown f, almost surely or in \(L_ p\), \(p\geq 2\), and the weak law of large numbers \(\lim_{n\to \infty}a_ n\sum^{n-1}_{j=0}\xi_ j=0\) is neither necessary nor sufficient for the convergence of \(X_ n\) to \(\theta\) in probability. The proof is carried out by embedding the R-M method in a continuous- parameter RM differential equation \(X(t)=- a(t)f(X(t))+a(t)\xi(t)+a(t)\zeta(t)\), where a(t)\(\zeta\) (t) is the error due to embedding and tends to zero in some probabilistic sense as \(t\to \infty\). Counter-examples for non-convergence in probability are presented.

Recommendations

• scientific article; zbMATH DE number 774863
• Convergence and robustness of the Robbins-Monro algorithm truncated at randomly varying bounds
• One-sided convergence of the Robbins-Monro process
• An estimate for the rate of convergence of the Robbins-Monro process
• Publication:4892311

Cites work

• A Stochastic Approximation Method
• A stochastic difference equation
• Stability by Liapunov's direct method. With applications

Cited in

(12)

• Convergence and robustness of the Robbins-Monro algorithm truncated at randomly varying bounds
• On robustness of the Robbins-Monro method for parallel processing
• Weighted averaging and stochastic approximation
• Some convergence theorems for RM algorithm
• The averaged Robbins-Monro method for linear problems in a Banach space
• Convergence of a Robbins-Monro Algorithm for Recursive Estimation with Non-Monotone Weights for a Function with a Restricted Domain and Multiple Zeros
• Sequences with low discrepancy generalisation and application to bobbins-monbo algorithm
• scientific article; zbMATH DE number 4157849 (Why is no real title available?)
• scientific article; zbMATH DE number 4055175 (Why is no real title available?)
• Adaptative Monte Carlo Method, A Variance Reduction Technique
• scientific article; zbMATH DE number 774863 (Why is no real title available?)
• Necessary and sufficient conditions for a stochastic approximation method

This page was built for publication: Necessary and sufficient conditions for the Robbins-Monro method

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