Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-22T19:47:52.041Z Has data issue: false hasContentIssue false
  • English
  • Français

Convergence of stochastic algorithms: from the Kushner–Clark theorem to the Lyapounov functional method

Part of: Sequential methods Limit theorems

Published online by Cambridge University Press:  01 July 2016

Jean-Claude Fort  and
Gilles Pagès
Jean-Claude Fort*
Affiliation:
Université de Nancy 1 and Université de Paris 1
Gilles Pagès*
Affiliation:
Université Pierre et Marie Curie and Université de Paris 12
*
∗ Postal address: Université de Nancy I, Fac. Sciences, Dpt de Math., B.P. 239, F-54506 Vandoeuvre-Lès-Nancy Cedex, France and SAMOS, Université de Paris 1, UFR 27, 90, rue de Tolbiac F-75634 Paris Cedex 13, France.
∗∗ Postal address: Laboratoire de Probabilités, URA 224, Université P. et M. Curie, Pl. Jussieu, F-75252 Paris Cedex 05, France and Université de Paris XII, UFR, Sciences, 61 av. du Gal de Gaulle, 94010 Créteil Cedex, France.
Get access Rights & Permissions [Opens in a new window]

Abstract

In the first part of this paper a global Kushner–Clark theorem about the convergence of stochastic algorithms is proved: we show that, under some natural assumptions, one can ‘read' from the trajectories of its ODE whether or not an algorithm converges. The classical stochastic optimization results are included in this theorem. In the second part, the above smoothness assumption on the mean vector field of the algorithm is relaxed using a new approach based on a path-dependent Lyapounov functional. Several applications, for non-smooth mean vector fields and/or bounded Lyapounov function settings, are derived. Examples and simulations are provided that illustrate and enlighten the field of application of the theoretical results.

Keywords

STOCHASTIC ALGORITHMORDINARY DIFFERENTIAL EQUATIONLYAPOUNOV FUNCTIONAL

MSC classification

Primary: 62L20: Stochastic approximation
Secondary: 60F05: Central limit and other weak theorems
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 28 , Issue 4 , December 1996 , pp. 1072 - 1094
Copyright
Copyright © Applied Probability Trust 1996 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Amann, H. (1990) Ordinary Differential Equations, de Gruyter, Berlin.CrossRefGoogle Scholar
[2] Benaim, M. (1996) A dynamical system approach to stochastic approximations. SIAM J. Control Optim. 34, 437–472.Google Scholar
[3] Benveniste, A., Metivier, M. and Priouret, P. (1987) Algorithmes Adaptatifs et Approximations Stochastiques. Masson, Paris.Google Scholar
[4] Brandiere, O. and Duflo, M. (1995) Les algorithmes stochastiques contournent-ils les pièges. Les Annales de l'I.H.P. 32, 395–427.Google Scholar
[5] Conley, C. (1978) Isolated invariant set and the Morse index. AMS Regional Conference Series in Mathematics. Google Scholar
[6] Delyon, B. (1994) General results on the convergence of stochastic algorithms. IRISA Technical Report No. 890. Rennes, France.Google Scholar
[7] Fort, J. C. (1991) Stabilité de l'algorithme de séparation de source de Jutten et Hérault. Traitement du Signal 8, 35–42.Google Scholar
[8] Fort, J. C. and Pages, G. (1993) Sur la convergence p.s. de l'algorithme de Kohonen généralisé. CRAS 317, 389–394.Google Scholar
[9] Fort, J. C. and Pages, G. (1995) On the a.s. convergence of the Kohonen algorithm with a generalized neighborhood function. Ann. Appl. Prob. 5, 1117–1216.Google Scholar
[10] Hahn, W. (1967) Stability of Motion. Springer, Berlin.CrossRefGoogle Scholar
[11] Herault, J. and Jutten, C. (1988) Une solution neuro-mimétique au problème de séparation de sources. Traitement du Signal 5, 389–403.Google Scholar
[12] Hirsch, M. W. and Smale, S. (1974) Differential Equations, Dynamical Systems and Linear Algebra. Academic Press, New York.Google Scholar
[13] Kushner, H. J. and Clark, D. S. (1978) Stochastic Approximation for Constrained and Unconstrained Systems. Springer, Berlin.Google Scholar
[14] Lapeyre, B., Pages, G. and Sab, K. (1990) Sequences with low discrepancy: generalization and application to Robbins-Monro algorithm. Statistics 21, 251–272.Google Scholar
[15] Lazarev, V. A. (1992) Convergence of stochastic-approximation procedures in the case of a regression equation with several roots. Translated from: Problemy Pederachi Inf. 28.Google Scholar
[16] Nevel'Son, M. B. and Has'Minakii, R. Z. (1972) Stochastic Approximation and Recursive Estimations. Nauka, Moscow.Google Scholar
[17] Oja, E. (1982) A simplified neuron model as a principal components analyzer. J. Math. Biol. 15, 267–273.Google Scholar
[18] Pages, G. (1993) Voronoï tessellation, space quantization algorithms and numerical integration. In Proc. ESANN 93. De Facto Editions, Bruxelles, pp. 221–228.Google Scholar
[19] Robbins, H. and Monro, S. (1951) A stochastic approximation method. Ann. Math. Statist. 22, 400–407.Google Scholar