Skip to main navigation menu Skip to main content Skip to site footer

Vol. 46 No. 4 (2020)
Serdica Mathematical Journal

Articles

Multivariate compact law of the iterated logarithm for averaged stochastic approximation algorithms

Published 01-10-2021

  • Abdelkader Mokkadem
    • ,
  • Mariane Pelletier

Abdelkader Mokkadem
Université Paris-Saclay

Mariane Pelletier
Université Paris-Saclay

Abstract

The aim of this paper is to establish a multivariate compact law of the iterated logarithm for the averaged version of stochastic approximation algorithms. This is achieved by studying the strong convergence rate of a two-time-scale stochastic approximation algorithm, the use of which generalizes the averaging principle of stochastic approximation algorithms. The general result obtained is then applied to the well-known averaged versions of Robbins-Monro's and Kiefer-Wolfowitz's algorithms.

2020 Mathematics Subject Classification:

62L20, 60F05, 62G07

Keywords

stochastic approximation algorithm, averaging principle, strong convergence rate

Full text

Author Details

Abdelkader Mokkadem

Université Paris-Saclay, UVSQ, CNRS
Laboratoire de Mathématiques de Versailles
78000, Versailles, France.
e-mail: abdelkader.mokkadem@uvsq.fr

Mariane Pelletier

Université Paris-Saclay, UVSQ, CNRS
Laboratoire de Mathématiques de Versailles
78000, Versailles, France.
e-mail: mariane.pelletier@uvsq.fr

References

  1. A. Benvéniste, M. Métivier, P. Priouret. Adaptive algorithms and stochastic approximation. Applications of Mathematics (New York), vol. 22. Berlin, Springer-Verlag, 1990.
  2. J. S. Baras, V. S. Borkar. A learning algorithm for Markov decision processes with adaptive state aggregation. Proc. 39th IEEE Conference on Decision and Control, vol. 4, 2000, 3351–3356 doi: 10.1109/CDC.2000.912220.
  3. S. Bhatnagar, M. C. Fu, S. I. Marcus, S. Bathnagar., Two timescale algorithms for simulation optimization of hidden Markov models. IIE Transactions 33, 3 (2001), 245–258, https://doi.org/10.1080/07408170108936826.
  4. S. Bhatnagar, M. C. Fu, S. I. Marcus, P. J. Fard. Optimal structured feedback policies for ABR flow control using two timescale SPSA. IEEE/ACM Transactions on Networkings 9, 4 (2001), 479–491, https://doi.org/10.1109/90.944345.
  5. V. S. Borkar. Stochastic approximation with two time scales. Systems Control Lett. 29, 5 (1997), 291–294
  6. J. R. Blum. Multidimensional stochastic approximation methods. Ann. Math. Statist. 25 (1954), 737–744
  7. R. Bojanic, E. Seneta. A unified theory of regularly varying sequences. Math. Z. 134 (1973), 91–106
  8. B. Delyon, A. B. Juditsky. Stochastic optimization with averaging of trajectories. Stochastics Stochastic Rep. 39, 2–3 (1992), 107–118.
  9. J. Dippon, J. Renz. Weighted means in stochastic approximation of minima, SIAM J. Control Optim. 35, 5 (1997), 1811–1827
  10. M. Duflo. Stochastic algorithms. (Algorithmes stochastiques) Mathématiques & applications (Berlin), vol. 23. Berlin, Springer-Verlag, 1996 (in French).
  11. M. Duflo. Random iterative models. (Transl. from the French by Stephen S. Wilson) Applications of Mathematics, vol. 34, Springer, Berlin, 1997.
  12. J. Galambos, E. Seneta. Regularly varying sequences. Proc. Amer. Math. Soc. 41 (1973), 110-116
  13. V. F. Gaposhkin, T. P. Krasulina. On the law of the iterated logarithm in stochastic approximation processes. Teor. Verojatnost. i Primenen. 19 (1974), 879–886 (in Russian); English translation in: Theory of Probab. and its Appl. 19 (1974), 844–850 (1975).
  14. P. Hall, C.C. Heyde. Martingale limit theory and its application. Probability and Mathematical Statistics. New York-London, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], 1980.
  15. J. Kiefer, J. Wolfowitz. Stochastic estimation of the maximum of a regression function. Ann. Math. Statistics. 23 (1952), 462–466
  16. V. R. Konda, V. S. Borkar. Actor-critic like learning algorithms for Markov decision processes. SIAM J. Control Optim. 38, 1 (1999), 94–123
  17. V. R. Konda, J. N. Tsitsiklis. On actor-critic algorithms. SIAM J. Control Optim. 42, 4 (2003), 1143–1166
  18. V. R. Konda, J. N. Tsitsiklis. Convergence rate of linear two-time-scale stochastic approximation. Ann. of Appl. Probab. 14, 2 (2004), 796–819
  19. V. Koval. On the rate of convergence of stochastic approximation procedures in a Banach space. Kibernet. Sistem. Anal. 3 (1998), 8189, 189–190 (in Russian); English translation in: Cybernet. Systems Anal. 34, 3 (1998), 386–394 (1999).
  20. V. Koval, R. Schwabe. Exact bounds for the rate of convergence of stochastic approximation procedures. Stochastic Anal. Appl. 16, 3 (1998), 501–515
  21. V. Koval, R. Schwabe. A law of the iterated logarithm for stochastic approximation procedures in d-dimensional Euclidean space, Stochastic Process. Appl. 105, 2 (2003), 299–313.
  22. H. J. Kushner, D. S. Clark. Stochastic approximation methods for constrained and unconstrained systems. Applied Mathematical Sciences, vol. 26. New York-Berlin, Springer-Verlag, 1978.
  23. H. J. Kushnerand, J. Yang. Stochastic approximation with averaging: of the iterates: Optimal asymptotic rate of convergence for general processes. SIAM J. Control Optim. 31, 4 (1993), 1045–1062.
  24. H. J. Kushner, G. G. Yin. Stochastic approximation and recursive algorithms and applications, Second edition. Applications of Mathematics (New York), vol. 35. Stochastic Modelling and Applied Probability. New York, Springer-Verlag, 2003.
  25. T. Z. Lai, H. Robbins. Limit theorems for weighted sums and stochastic approximation processes. Proc. Natl. Acad. Sci. USA 75, 3 (1978), 1068-1070
  26. L. Ljung. Analysis of recursive stochastic algorithms. IEEE Trans. Automatic Control, AC-22, 4 (1977), 551-575
  27. L. Ljung. Strong convergence of a stochastic approximation algorithm. Ann. Statist., 6, 3 (1978), 680–696
  28. L. Ljung, G. Pflug, H. Walk. Stochastic approximation and optimization of random systems. DMV Seminar, vol. 17. Basel, Birkh¨auser Verlag, 1992.
  29. A. Mokkadem, M. Pelletier. The law of the iterated logarithm for the multivariable kernel mode estimator ESAIM Probab. Stat. 7 (2003), 1–21.
  30. A. Mokkadem, M. Pelletier. The compact law of the iterated logarithm for multivariate stochastic approximation algorithms. Stoch. Anal. Appl. 23, 1 (2005), 181–203.
  31. A. Mokkadem, M. Pelletier. Convergence rate and averaging of non-linear two-time-scale stochastic approximation algorithms. Ann. of Appl. Probab. 16, 3 (2006), 1671–1702
  32. A. Mokkadem, M. Pelletier. A companion for the Kiefer-Wolfowitz-Blum stochastic approximation algorithm. Annals of Statistics 35, 4 (2007), 1749–1772.
  33. A. Mokkadem, M. Pelletier, Y. Slaoui. The stochastic approximation method for the estimation of a multivariate probability density. J. Statist. Plann. Inference 139, 7 (2009), 2459–2478.
  34. A. Mokkadem, M. Pelletier. A generalization of the averaging procedure: the use of two-time-scale algorithms. SIAM J. Control Optim. 49, 4 (2011), 1523–1543.
  35. G. Morrow, W. Philipp. An almost sure invariance principle for Hilbert space valued martingales. Trans. Amer. Math. Soc. 273, 1 (1982), 231–251.
  36. M. B. Nevels’on, R. Z. Has’minskiĭ. Stochastic Approximation and Recursive Estimation. Monographs in Probability Theory and Mathematical Statistics. Moscow, Nauka, 1972 (in Russian); English translations in: Mathematical Monographs, vol. 47. Providence, R. I., AMS, 1976.
  37. A. Pechtl. Arithmetic means and invariance principles in stochastic approximation. J. Theor. Probab. 6, 1 (1993), 153–173.
  38. M. Pelletier. On the almost sure asymptotic behaviour of stochastic algorithms. Stochastic Process. Appl. 78, 2, (1998) 217–244
  39. M. Pelletier. Asymptotic almost sure efficiency of averaged stochastic algorithms. SIAM J. Control Optim. 39, 1 (2000), 49–72.
  40. V. V. Petrov. Limit theorems of probability theory. Sequences of independent random variables. Oxford Studies in Probability, vol. 4. Oxford Science Publications. New York, The Clarendon Press, Oxford University Press, 1995.
  41. B. T. Polyak. A new method of stochastic approximation type. Avtomat. i Telemekh. 1990, 7 (1990), 98–107 (in Russian); English translation in: Automat. Remote Control 51, 7, part 2 (1990), 937–946 (1991).
  42. B. T. Polyak, A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. 30, 4 (1992), 838–855.
  43. H. Robbins, S. Monro. A stochastic approximation method. Ann. Math. Statistics 22 (1951), 400–407.
  44. D. Ruppert. Almost sure approximations to the Robbins-Monro and Kiefer-Wolfowitz processes with dependent noise. Ann. of Probab. 10, 1 (1982), 178–187.
  45. D. Ruppert. Stochastic approximation. In: Handbook of sequential analysis, Statist. Textbooks Monogr., vol. 118. New York, Dekker, 1991, 503-529.
  46. A. B. Tsybakov. Recurrent estimation of the mode of a multidimensional distribution Problemy Peredachi Informatsii 26, 1 (1990), 38–45 (in Russian); English translation in: Problems Inform. Transmission 26, 1 (1990), 31–37.
  47. G. Yin. On extensions of Polyak’s averaging approach to stochastic approximation, Stochastics Stochastic Rep., 36, 3–4 (1991),245–264.