Weak convergence rates for stochastic approximation with application to multiple targets and simulated annealing. (English) Zbl 0965.62065

Summary: We study convergence rates of \(\mathbb{R}^d\)-valued algorithms, especially in the case of multiple targets and simulated annealing. We precise, for example, the convergence rate of simulated annealing algorithms, whose weak convergence to a distribution concentrated on the potential’s minima had been established by S.B. Gelfand and S.K. Mitter [see SIAM J. Control Optimization 29, No. 5, 999-1018 (1991; Zbl 0753.65051)] or by C.R. Hwang and S.J. Sheu [On the behavior of a stochastic algorithm with annealing. Tech. Rep., Acad. Sinica. Taiwan (1990)].


62L20 Stochastic approximation
60F05 Central limit and other weak theorems
60H10 Stochastic ordinary differential equations (aspects of stochastic analysis)


Zbl 0753.65051
Full Text: DOI


[1] Benaim, M. (1996). A dy namical sy stem approach to stochastic approximation. SIAM J. Control Optim. 34 437-472. · Zbl 0841.62072
[2] Benveniste, A., Metivier, M. and Priouret, P. (1990). Adaptive Algorithms and Stochastic Approximation. Springer, New York. · Zbl 0752.93073
[3] Bouton, C. (1988). Approximation gaussienne d’algorithmes stochastiques a dy namique markovienne. Ann. Inst. H. Poincaré 24 131-155. · Zbl 0643.60038
[4] Chen, H. F., Guo, L. and Gao, A. J. (1988). Convergence and robustness of the Robbins- Monro algorithm truncated at randomly varying bounds. Stochastic Process. Appl. 27 217-231. · Zbl 0632.62082
[5] Chiang, T. S., Hwang, C. R. and Sheu, S. J. (1987). Diffusion for global optimization in Rn. SIAM J. Control Optim. 25 737-753. · Zbl 0622.60093
[6] Duflo, M. (1996). Algorithmes Stochastiques. Collection Mathématiques et Applications. Springer, New York. · Zbl 0849.62043
[7] Dupuis, P. and Kushner, H. J. (1989). Stochastic approximation and large deviations: upper bounds and w.p. 1 convergence. SIAM J. Control Optim. 27 1108-1135. · Zbl 0679.60041
[8] Feigin, P. D. (1985). Stable convergence of semimartingales. Stochastic Process. Appl. 19 125-134. · Zbl 0558.60022
[9] Feller, W. (1968). An Introduction to Probability Theory and Its Applications 2, 3rd. ed. Wiley, New York. · Zbl 0155.23101
[10] Fort, J. C. and Pages, G. (1996). Convergence of stochastic algorithms: from the Kushner- Clark theorem to the Ly apunov functional method. Adv. in Appl. Probab. 28 1072-1094. JSTOR: · Zbl 0881.62085
[11] Gelfand, S. B. and Mitter, S. K. (1991). Recursive stochastic algorithms for global optimization in Rd. SIAM J. Control Optim. 29 999-1018. · Zbl 0753.65051
[12] Gelfand, S. B. and Mitter, S. K. (1993). Metropolis-ty pe annealing algorithms for global optimization in Rd. SIAM J. Control Optim. 31 111-131. · Zbl 0814.65059
[13] Geman, S. and Hwang, C. R. (1986). Diffusions for global optimization. SIAM J. Control Optim. 1031-1043. · Zbl 0602.60071
[14] Hall, P. and Hey de, C. (1980). Martingale Limit Theory and Its Applications. Academic Press, New York. · Zbl 0462.60045
[15] Hwang, C. R. (1980). Laplace’s method revisited. Ann. Probab. 8 1177-1182. · Zbl 0452.60007
[16] Hwang, C. R and Sheu, S. J. (1990). Large time behavior of perturbed diffusion Markov process with applications to the second eigenvalue problem for Fokker-Planck operator and simulated annealing. Acta Appl. Math. 19 253-295. · Zbl 0708.60056
[17] Hwang, C. R and Sheu, S. J. (1990). On the behavior of a stochastic algorithm with annealing. Technical report, Academia Sinica, Taiwan. · Zbl 0708.60056
[18] Jacquot, S. (1992). Comportement asy mptotique de la seconde valeur propre des processus de Kolmogorov. J. Multivariate Anal. 40 335-347. · Zbl 0749.60026
[19] Kaniovski, Yu. (1988). Limit theorems for processes of stochastic approximation when the regression function has several roots. Kibernetika 2 136-138. (In Russian, 120-122; English trans.)
[20] Kaniovski, Yu. and Pflug, G. (1994). Non-standard limit theorems for urn models and stochastic approximation procedures. · Zbl 0823.62068
[21] Kersting, G. D. (1978). A weak convergence theorem with application to the Robbins-Monro process. Ann. Probab. 6 1015-1025. · Zbl 0405.60019
[22] Kiefer, J. and Wolfowitz, J. (1952). Stochastic estimation of the maximum of a regression function. Ann. Math. Statist. 23 462-466. · Zbl 0049.36601
[23] Kushner, H. J. (1987). Asy mptotic global behavior for stochastic approximations and diffusions with slowly decreasing noise effects: global minimization via Monte Carlo. SIAM J. Appl. Math. 47 169-185. JSTOR: · Zbl 0615.60024
[24] Kushner, H. J. and Clark, D. S. (1978). Stochastic approximation for constrained and unconstrained sy stems. Appl. Math. Sci. 26. Springer, New York. · Zbl 0381.60004
[25] Kushner, H. J. and Huang, H. (1979). Rates of convergence for stochastic approximation ty pe algorithms. SIAM J. Control Optim. 17 607-617. · Zbl 0418.93093
[26] Kushner, H. J. and Huang, H. (1981). Asy mptotic properties of stochastic approximations with constant coefficients. SIAM J. Control Optim. 19 87-105. · Zbl 0475.93082
[27] Lai, T. Z. and Wei, C. Z. (1983). A note on martingale difference sequences satisfying the local Marcinkiewicz-Zigmund condition. Bull. Institute Math. Acad. Sinica 11 1-13. · Zbl 0517.60054
[28] Ljung, L., Pflug, G. and Walk, H. (1992). Stochastic Approximation and Optimization of Random Sy stems. Birkhäuser, Boston. · Zbl 0747.62090
[29] Marquez, D. (1997). Convergence rates for annealing diffusion processes. Ann. Appl. Probab. 7 1118-1139. · Zbl 0949.62072
[30] Mey n, S. P. and Tweedie, R. L. (1993). Stability of Markovian processes. III: Foster- Ly apunov criteria for continuous time processes with examples. Adv. in Appl. Probab. 25 518-548. JSTOR: · Zbl 0781.60053
[31] Nevel’son, M. B. and Ha’sminskii, R. Z. (1972). Stochastic approximation and recursive estimation. Transl. Math. Monogr. 47. (In Russian, Nauka.)
[32] Roy er, G. (1989). A remark on simulated annealing of diffusion processes. SIAM J. Control Optim. 27 1403-1408. · Zbl 0689.60059
[33] Seneta, E. (1976). Regularly Varying functions. Lecture Notes in Math. 508. Springer, Berlin. · Zbl 0324.26002
[34] Touati, A. (1993). Two theorems on convergence in distribution for stochastic integrals and statistical applications. Theory Probab. Appl. 38 95-117. · Zbl 0802.60050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.