Asymptotic normality of randomly truncated stochastic algorithms

Jérôme Lelong

ESAIM: Probability and Statistics (2013)

  • Volume: 17, page 105-119
  • ISSN: 1292-8100

Abstract

top
We study the convergence rate of randomly truncated stochastic algorithms, which consist in the truncation of the standard Robbins–Monro procedure on an increasing sequence of compact sets. Such a truncation is often required in practice to ensure convergence when standard algorithms fail because the expected-value function grows too fast. In this work, we give a self contained proof of a central limit theorem for this algorithm under local assumptions on the expected-value function, which are fairly easy to check in practice.

How to cite

top

Lelong, Jérôme. "Asymptotic normality of randomly truncated stochastic algorithms." ESAIM: Probability and Statistics 17 (2013): 105-119. <http://eudml.org/doc/274364>.

@article{Lelong2013,
abstract = {We study the convergence rate of randomly truncated stochastic algorithms, which consist in the truncation of the standard Robbins–Monro procedure on an increasing sequence of compact sets. Such a truncation is often required in practice to ensure convergence when standard algorithms fail because the expected-value function grows too fast. In this work, we give a self contained proof of a central limit theorem for this algorithm under local assumptions on the expected-value function, which are fairly easy to check in practice.},
author = {Lelong, Jérôme},
journal = {ESAIM: Probability and Statistics},
keywords = {stochastic approximation; central limit theorem; randomly truncated stochastic algorithms; martingale arrays},
language = {eng},
pages = {105-119},
publisher = {EDP-Sciences},
title = {Asymptotic normality of randomly truncated stochastic algorithms},
url = {http://eudml.org/doc/274364},
volume = {17},
year = {2013},
}

TY - JOUR
AU - Lelong, Jérôme
TI - Asymptotic normality of randomly truncated stochastic algorithms
JO - ESAIM: Probability and Statistics
PY - 2013
PB - EDP-Sciences
VL - 17
SP - 105
EP - 119
AB - We study the convergence rate of randomly truncated stochastic algorithms, which consist in the truncation of the standard Robbins–Monro procedure on an increasing sequence of compact sets. Such a truncation is often required in practice to ensure convergence when standard algorithms fail because the expected-value function grows too fast. In this work, we give a self contained proof of a central limit theorem for this algorithm under local assumptions on the expected-value function, which are fairly easy to check in practice.
LA - eng
KW - stochastic approximation; central limit theorem; randomly truncated stochastic algorithms; martingale arrays
UR - http://eudml.org/doc/274364
ER -

References

top
  1. [1] B. Arouna, Adaptative Monte Carlo method, a variance reduction technique. Monte Carlo Methods Appl.10 (2004) 1–24. Zbl1063.65003MR2054568
  2. [2] A. Benveniste, M. Métivier and P. Priouret, Adaptive algorithms and stochastic approximations. Springer-Verlag, Berlin. Appl. Math. 22 (1990). Translated from the French by Stephen S. Wilson. Zbl0752.93073MR1082341
  3. [3] C. Bouton, Approximation Gaussienne d’algorithmes stochastiques à dynamique Markovienne. Ph.D. Thesis, Université Pierre et Marie Curie, Paris 6 (1985). Zbl0611.62103
  4. [4] R. Buche and H.J. Kushner, Rate of convergence for constrained stochastic approximation algorithms. SIAM J. Control Optim. 40 (2001) 1011–1041 (electronic). Zbl1011.62082MR1882723
  5. [5] H.-F. Chen, Stochastic approximation and its applications, Kluwer Academic Publishers, Dordrecht. Nonconvex Optim. Appl. 64 (2002). Zbl1008.62071MR1942427
  6. [6] H. Chen and Y. Zhu, Stochastic Approximation Procedure with randomly varying truncations. Scientia Sinica Series (1986). Zbl0613.62107MR869196
  7. [7] B. Delyon, General results on the convergence of stochastic algorithms. IEEE Trans. Automat. Contr.41 (1996) 1245–1255. Zbl0867.93075MR1409470
  8. [8] M. Duflo, Algorithmes stochastiques (Mathématiques et Applications). Springer (1996). Zbl0882.60001MR1612815
  9. [9] M. Duflo, Random Iterative Models. Springer-Verlag Berlin and New York (1997). Zbl0868.62069MR1485774
  10. [10] H.J. Kushner and G.G. Yin, Stochastic approximation and recursive algorithms and applications, Applications of Mathematics. Springer-Verlag, New York, 2nd edition 2003. Stoch. Model. Appl. Probab. 35 (2003). Zbl1026.62084MR1993642
  11. [11] B. Lapeyre and J. Lelong, A framework for adaptive Monte–Carlo procedures. Monte Carlo Methods Appl. (2011). Zbl1223.65003
  12. [12] J. Lelong, Almost sure convergence of randomly truncated stochastic agorithms under verifiable conditions. Stat. Probab. Lett. 78 (2009). Zbl1147.62072MR2542461
  13. [13] V. Lemaire and G. Pagès, Unconstrained Recursive Importance Sampling. Ann. Appl. Probab.20 (2010) 1029–1067. Zbl1207.65007MR2680557
  14. [14] M. Pelletier, Weak convergence rates for stochastic approximation with application to multiple targets and simulated annealing. Ann. Appl. Probab.8 (1998) 10–44. Zbl0965.62065MR1620405
  15. [15] H. Robbins and S. Monro, A stochastic approximation method. Ann. Math. Statistics22 (1951) 400–407. Zbl0054.05901MR42668

NotesEmbed ?

top

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.