Dynamics of stochastic approximation algorithms

Michel Benaïm

Séminaire de probabilités de Strasbourg (1999)

  • Volume: 33, page 1-68

How to cite


Benaïm, Michel. "Dynamics of stochastic approximation algorithms." Séminaire de probabilités de Strasbourg 33 (1999): 1-68. <http://eudml.org/doc/114007>.

author = {Benaïm, Michel},
journal = {Séminaire de probabilités de Strasbourg},
keywords = {dynamical systems; Lyapunov functions; asymptotic pseudotrajectories; limit sets; attractor; shadowing; empirical occupation measure},
language = {eng},
pages = {1-68},
publisher = {Springer - Lecture Notes in Mathematics},
title = {Dynamics of stochastic approximation algorithms},
url = {http://eudml.org/doc/114007},
volume = {33},
year = {1999},

AU - Benaïm, Michel
TI - Dynamics of stochastic approximation algorithms
JO - Séminaire de probabilités de Strasbourg
PY - 1999
PB - Springer - Lecture Notes in Mathematics
VL - 33
SP - 1
EP - 68
LA - eng
KW - dynamical systems; Lyapunov functions; asymptotic pseudotrajectories; limit sets; attractor; shadowing; empirical occupation measure
UR - http://eudml.org/doc/114007
ER -


  1. Akin, E. (1993). The General Topology of Dynamical Systems. American Mathematical Society, Providence. Zbl0781.54025MR1219737
  2. Arthur, B., Ermol'ev, Y., and Kaniovskii, Y. (1983). A generalized urn problem and its applications. Cybernetics, 19:61-71. Zbl0534.90049
  3. Arthur, B.M. (1988). Self-reinforcing mechanisms in economics. In W, A. P., Arrow, K. J., and Pines, D., editors,The Economy as an Evolving Complex System, SFI Studies in the Sciences of Complexity. Addison-Wesley. MR1120101
  4. Benaïm, M. (1996). A dynamical systems approach to stochastic approximations. SIAM Journal on Control and Optimization, 34:141-176. Zbl0841.62072MR1377706
  5. Benaïm, M. (1997). Vertex reinforced random walks and a conjecture of Pemantle. The Annals of Probability, 25:361-392. Zbl0873.60044MR1428513
  6. Benaïm, M. and Hirsch, M.W. (1994). Learning processes, mixed equilibria and dynamical systems arising from repeated games. Submitted. 
  7. Benaïm, M. and Hirsch, M.W. (1995a). Chain recurrence in surface flows. Discrete and Continuous Dynamical Systems, 1(1):1-16. Zbl0871.58062MR1355862
  8. Benaïm, M. and Hirsch, M.W. (1995b). Dynamics of morse-smale urn processes. Ergodic Theory and Dynamical Systems, 15:1005-1030. Zbl0846.60054MR1366305
  9. Benaïm, M. and Hirsch, M.W. (1996). Asymptotic pseudotrajectories and chain recurrent flows, with applications. J. Dynam. Differential Equations, 8:141-176. Zbl0878.58053MR1388167
  10. Benaïm, M. and Schreiber, S.J. (1997). Weak asymptotic pseudotrajectories for semiflows: Ergodic properties. Preprint. Zbl0998.37013
  11. Benveniste, A., Métivier, M., and Priouret, P. (1990). Stochastic Approximation and Adaptive Algorithms. Springer-Verlag, Berlin and New York. Zbl0752.93073MR1082341
  12. Bowen, R. (1975). Omega limit sets of Axiom A diffeomorphisms. J. Diff. Eq, 18:333-339. Zbl0315.58019MR413181
  13. Brandière, O. (1996). Autour des pièges des algorithmes stochastiques. Thèse de Doctorat, Université de Marne-la-Vallée. 
  14. Brandière., O. (1997). Some pathological traps for stochastic approximation. SIAM Journal on Control and Optimization. To Appear. Zbl0980.62068MR1618037
  15. Brandière, O. and Duflo., M. (1996). Les algorithmes stochastique contournent ils les pièges. Annales de l'IHP, 32:395-427. Zbl0849.62043MR1387397
  16. Conley, C.C. (1978). Isolated invariant sets and the Morse index. CBMS Regional conference series in mathematics. American Mathematical Society, Providence. Zbl0397.34056MR511133
  17. Delyon, B. (1996), General convergence results on stochastic approximation. IEEE trans. on automatic control, 41:1245-1255. Zbl0867.93075MR1409470
  18. Duflo, M. (1990). Méthodes Récursives Aléatoires. Masson. English Translation: Random Iterative Models, Springer Verlag1997. Zbl0703.62084
  19. Duflo, M. (1996). Algorithmes Stochastiques. Mathématiques et Applications. Springer-Verlag. Zbl0882.60001MR1612815
  20. Duflo, M. (1997). Cibles atteignables avec une probabilité positive d'après M. BENAIM. Unpublished manuscript. 
  21. Ethier, S.N.and Kurtz, T.G. (1986). Markov Processes, Characterization and Convergence. John Wiley and Sons, Inc. Zbl0592.60049MR838085
  22. Fort, J.C.and Pages, G. (1994). Résaux de neurones: des méthodes connexionnistes d'apprentissage. Matapli, 37:31-48. 
  23. Fort, J.C. and Pages, G. (1996). Convergence of stochastic algorithms: From Kushner-Clark theorem to the lyapounov functional method. Adv. Appl. Prob, 28:1072-1094. Zbl0881.62085MR1418247
  24. Fort, J.C. and Pages, G. (1997). Stochastic algorithm with non constant step: a.s. weak convergence of empirical measures. Preprint. 
  25. Fudenberg, D. and Kreps, K. (1993). Learning mixed equilibria. Games and Econom. Behav., 5:320-367. Zbl0790.90092MR1227915
  26. Fudenberg, F. and Levine, D. (1998). Theory of Learning in Games. MIT Press, Cambridge, MA. In Press. Zbl0939.91004MR1629477
  27. Hartman, P. (1964). Ordinary Differential Equationq. Wiley, New York. Zbl0125.32102MR171038
  28. Hill, B.M., Lane, D., and Sudderth, W. (1980). A strong law for some generalized urn processes. Annals of Probability, 8:214-226. Zbl0429.60021MR566589
  29. Hirsch, M.W. (1976). Differential Topology. Springer-Verlag, Berlin, New York, Heidelberg. Zbl0356.57001MR448362
  30. Hirsch, M.W. (1994). Asymptotic phase, shadowing and reaction-diffusion systems. In Differential equations, dynamical systems and control science, volume 152 of Lectures notes in pure and applied mathematics, pages 87-99. Marcel Dekker, New-York. Zbl0795.93055MR1243195
  31. Hirsch, M.W. and Pugh, C.C. (1988). Cohomology of chain recurrent sets. Ergodic Theory and Dynamical Systems, 8:73-80. Zbl0643.54039MR939061
  32. Kaniovski, Y. and Young, H. (1995). Learning dynamics in games with stochastic perturbations. Games and Econom. Behav., 11:330-363. Zbl0841.90124MR1360043
  33. Kiefer, J. and Wolfowitz, J. (1952). Stochastic estimation of the maximum of a regression function. Ann. Math. Statis, 23:462-466. Zbl0049.36601MR50243
  34. Kushner, H.J. and Clarck, C.C. (1978). Stochastic Approximation for Constrained and Unconstrained Systems. Springer-Verlag, Berlin and New York. Zbl0381.60004MR499560
  35. Kushner, H.J. and Yin, G.G. (1997). Stochastic Approximation Algorithms and Applications. Springer-Verlag, New York. Zbl0914.60006MR1453116
  36. Ljung, L. (1977). Analysis of recursive stochastic algorithms. IEEE Trans. Automat. Control., AC-22:551-575. Zbl0362.93031MR465458
  37. Ljung, L. (1986). System Identification Theory for the User. Prentice Hall, Englewood Cliffs, NJ. Zbl0615.93004
  38. Ljung, L. and Söderström, T. (1983). Theory and Practice of Recursive Identification. MIT Press, Cambridge, MA. Zbl0548.93075MR719192
  39. Mañé, R. (1987). Ergodic Theory and Differentiable Dynamics. Springer-Verlag, New York. Zbl0616.28007MR889254
  40. Métivier, M. and Priouret, P. (1987). Théorèmes de convergence presque sure pour une classe d'algorithmes stochastiques à pas décroissant. Probability Theory and Related Fields, 74:403-428. Zbl0588.62153MR873887
  41. Munkres, J.R. (1975). Topology a first course. Prentice Hall. Zbl0306.54001MR464128
  42. Nevelson, M.B.and Khasminskii, R.Z. (1976). Stochastic Approximation and Recursive Estimation. Translation of Math. Monographs. American Mathematical Society, Providence. 
  43. Pemantle, R. (1990). Nonconvergence to unstable points in urn models and stochastic approximations. Annals of Probability, 18:698-712. Zbl0709.60054MR1055428
  44. Pemantle, R. (1992). Vertex reinforced random walk. Probability Theory and Related Fields, 92:117-136. Zbl0741.60029MR1156453
  45. Robbins, H. and Monro, S. (1951). A stochastic approximation method. Ann. Math. Statis, 22:400-407. Zbl0054.05901MR42668
  46. Robinson, C.. (1977). Stability theorems and hyperbolicity in dynamical systems. Rocky Journal of Mathematics, 7:425-434. Zbl0375.58016MR494300
  47. Robinson, C. (1995). Introduction to the Theory of Dynamical Systems. Studies in Advances Mathematics. CRC Press, Boca Raton. MR1396532
  48. Schreiber, S.J. (1997). Expansion rates and Lyapunov exponents. Discrete and Conts. Dynam. Sys., 3:433-438. Zbl0948.37019MR1444204
  49. Shub, M. (1987). Global Stability of Dynamical Systems. Springer-Verlag, Berlin, New York, Heidelberg. Zbl0606.58003MR869255
  50. Stroock, D.W. (1993). Probability Theory. An analytic view. Cambridge University Press. Zbl0925.60004MR1267569
  51. White, H. (1992). Artificial Neural Networks: Approximation and Learning Theory. Blackwell, Cambridge, Massachussets. MR1203316

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.