Abstract
These notes were written for a D.E.A. course given at Ecole Normale Supérieure de Cachan during the 1996–97 and 1997–98 academic years and at University Toulouse III during the 1997–98 academic year. Their aim is to introduce the reader to the dynamical system aspects of the theory of stochastic approximations.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Akin, E. (1993). The General Topology of Dynamical Systems. American Mathematical Society, Providence.
Arthur, B., Ermol'ev, Y., and Kaniovskii, Y. (1983). A generalized urn problem and its applications. Cybernetics, 19: 61–71.
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.
Benaïm, M. (1996). A dynamical systems approach to stochastic approximations. SIAM Journal on Control and Optimization, 34: 141–176.
Benaïm, M. (1997). Vertex reinforced random walks and a conjecture of Pemantle. The Annals of Probability, 25: 361–392.
Benaïm, M. and Hirsch, M. W. (1994). Learning processes, mixed equilibria and dynamical systems arising from repeated games. Submitted.
Benaïm, M. and Hirsch, M. W. (1995a). Chain recurrence in surface flows. Discrete and Continuous Dynamical Systems, 1(1): 1–16.
Benaïm, M. and Hirsch, M. W. (1995b). Dynamics of morse-smale urn processes. Ergodic Theory and Dynamical Systems, 15: 1005–1030.
Benaïm, M. and Hirsch, M. W. (1996). Asymptotic pseudotrajectories and chain recurrent flows, with applications. J. Dynam. Differential Equations, 8: 141–176.
Benaïm, M. and Schreiber, S. J. (1997). Weak asymptotic pseudotrajectories for semiflows: Ergodic properties. Preprint.
Benveniste, A., Métivier, M., and Priouret, P. (1990). Stochastic Approximation and Adaptive Algorithms. Springer-Verlag, Berlin and New York.
Bowen, R. (1975). Omega limit sets of Axiom A diffeomorphisms. J. Diff. Eq, 18: 333–339.
Brandière, O. (1996). Autour des pièges des algorithmes stochastiques. Thèse de Doctorat, Université de Marne-la-Vallée.
Brandière, O. (1997). Some pathological traps for stochastic approximation. SIAM Journal on Control and Optimization. To Appear.
Brandière, O. and Duflo, M. (1996). Les algorithmes stochastique contournent ils les pièges. Annales de l'IHP, 32: 395–427.
Conley, C. C. (1978). Isolated invariant sets and the Morse index. CBMS Regional conference series in mathematics. American Mathematical Society, Providence.
Delyon, B. (1996). General convergence results on stochastic approximation. IEEE trans. on automatic control, 41: 1245–1255.
Duflo, M. (1990). Méthodes Récursives Aléatoires. Masson. English Translation: Random Iterative Models, Springer Verlag 1997.
Duflo, M. (1996). Algorithmes Stochastiques. Mathématiques et Applications. Springer-Verlag.
Duflo, M. (1997). Cibles atteignables avec une probabilité positive d'après m. benaim. Unpublished manuscript.
Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes, Characterization and Convergence. John Wiley and Sons, Inc.
Fort, J. C., and Pages, G. (1994). Résaux de neurones: des méthodes connexionnistes d'apprentissage. Matapli, 37: 31–48.
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.
Fort, J. C. and Pages, G. (1997). Stochastic algorithm with non constant step: a.s. weak convergence of empirical measures. Preprint.
Fudenberg, D., and Kreps, K. (1993). Learning mixed equilibria. Games and Econom. Behav., 5: 320–367.
Fudenberg, F., and Levine, D. (1998). Theory of Learning in Games. MIT Press, Cambridge, MA. In Press.
Hartman, P. (1964). Ordinary Differential Equationq. Wiley, New York.
Hill, B. M., Lane, D., and Sudderth, W. (1980). A strong law for some generalized urn processes. Annals of Probability, 8: 214–226.
Hirsch, M. W. (1976). Differential Topology. Springer-Verlag, Berlin, New York, Heidelberg.
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.
Hirsch, M. W., and Pugh, C. C. (1988). Cohomology of chain recurrent sets. Ergodic Theory and Dynamical Systems, 8: 73–80.
Kaniovski, Y., and Young, H. (1995). Learning dynamics in games with stochastic perturbations. Games and Econom. Behav., 11: 330–363.
Kiefer, J., and Wolfowitz, J. (1952). Stochastic estimation of the maximum of a regression function. Ann. Math. Statis, 23: 462–466.
Kushner, H. J., and Clarck, C. C. (1978). Stochastic Approximation for Constrained and Unconstrained Systems. Springer-Verlag, Berlin and New York.
Kushner, H. J., and Yin, G. G. (1997). Stochastic Approximation Algorithms and Applications. Springer-Verlag, New York.
Ljung, L. (1977). Analysis of recursive stochastic algorithms. IEEE Trans. Automat. Control., AC-22: 551–575.
Ljung, L. (1986). System Identification Theory for the User. Prentice Hall, Englewood Cliffs, NJ.
Ljung, L., and Sőderstrőm, T. (1983). Theory and Practice of Recursive Identification. MIT Press, Cambridge, MA.
Mañé, R. (1987). Ergodic Theory and Differentiable Dynamics. Springer-Verlag, New York.
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.
Munkres, J. R. (1975). Topology a first course. Prentice Hall.
Nevelson, M. B., and Khasminskii, R. Z. (1976). Stochastic Approximation and Recursive Estimation. Translation of Math. Monographs. American Mathematical Society, Providence.
Pemantle, R. (1990). Nonconvergence to unstable points in urn models and stochastic approximations. Annals of Probability, 18: 698–712.
Pemantle, R. (1992). Vertex reinforced random walk. Probability Theory and Related Fields, 92: 117–136.
Robbins, H., and Monro, S. (1951). A stochastic approximation method. Ann. Math. Statis, 22: 400–407.
Robinson, C. (1977). Stability theorems and hyperbolicity in dynamical systems. Rocky Journal of Mathematics, 7: 425–434.
Robinson, C. (1995). Introduction to the Theory of Dynamical Systems. Studies in Advances Mathematics. CRC Press, Boca Raton.
Schreiber, S. J. (1997). Expansion rates and Lyapunov exponents. Discrete and Conts. Dynam. Sys., 3: 433–438.
Shub, M. (1987). Global Stability of Dynamical Systems. Springer-Verlag, Berlin, New York, Heidelberg.
Stroock, D. W. (1993). Probability Theory. An analytic view. Cambridge University Press.
White, H. (1992). Artificial Neural Networks: Approximation and Learning Theory. Blackwell, Cambridge, Massachussets. *** DIRECT SUPPORT *** A00I6C60 00002
Editor information
Rights and permissions
Copyright information
© 1999 Springer-Verlag
About this paper
Cite this paper
Benaïm, M. (1999). Dynamics of stochastic approximation algorithms. In: Azéma, J., Émery, M., Ledoux, M., Yor, M. (eds) Séminaire de Probabilités XXXIII. Lecture Notes in Mathematics, vol 1709. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0096509
Download citation
DOI: https://doi.org/10.1007/BFb0096509
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66342-3
Online ISBN: 978-3-540-48407-3
eBook Packages: Springer Book Archive