This paper provides a Central Limit Theorem (CLT) for a process satisfying a stochastic approximation (SA) equation of the form ; a CLT for the associated average sequence is also established. The originality of this paper is to address the case of controlled Markov chain dynamics and the case of multiple targets. The framework also accomodates (randomly) truncated SA algorithms. Sufficient conditions for CLT’s hold are provided as well as comments on how these conditions extend previous works (such as independent and identically distributed dynamics, the Robbins−Monro dynamic or the single target case). The paper gives a special emphasis on how these conditions hold for SA with controlled Markov chain dynamics and multiple targets; it is proved that this paper improves on existing works.
DOI : 10.1051/ps/2014013
Mots clés : Stochastic approximation, limit theorems, controlled markov chain
@article{PS_2015__19__60_0, author = {Fort, Gersende}, title = {Central limit theorems for stochastic approximation with controlled {Markov} chain dynamics}, journal = {ESAIM: Probability and Statistics}, pages = {60--80}, publisher = {EDP-Sciences}, volume = {19}, year = {2015}, doi = {10.1051/ps/2014013}, mrnumber = {3374869}, zbl = {1333.60029}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ps/2014013/} }
TY - JOUR AU - Fort, Gersende TI - Central limit theorems for stochastic approximation with controlled Markov chain dynamics JO - ESAIM: Probability and Statistics PY - 2015 SP - 60 EP - 80 VL - 19 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ps/2014013/ DO - 10.1051/ps/2014013 LA - en ID - PS_2015__19__60_0 ER -
%0 Journal Article %A Fort, Gersende %T Central limit theorems for stochastic approximation with controlled Markov chain dynamics %J ESAIM: Probability and Statistics %D 2015 %P 60-80 %V 19 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ps/2014013/ %R 10.1051/ps/2014013 %G en %F PS_2015__19__60_0
Fort, Gersende. Central limit theorems for stochastic approximation with controlled Markov chain dynamics. ESAIM: Probability and Statistics, Tome 19 (2015), pp. 60-80. doi : 10.1051/ps/2014013. http://www.numdam.org/articles/10.1051/ps/2014013/
C. Andrieu, G. Fort and M. Vihola, Quantitative Convergence Rates for sub-geometric Markov chains. Technical report arXiv:1309.0622v2 (2014). | MR
Stability of Stochastic Approximation under Verifiable Conditions. SIAM J. Control Optim. 44 (2005) 283–312. | MR | Zbl
, and ,M. Benaim, Dynamics of stochastic approximation algorithms. In Séminaire de Probabilités, XXXIII, vol. 1709 of Lect. Notes Math. Springer, Berlin (1999) 1–68. | MR | Zbl
A. Benveniste, M. Metivier and P. Priouret, Adaptive Algorithms and Stochastic Approximations. Springer Verlag (1987). | MR | Zbl
Performance of a Distributed Stochastic Approximation Algorithm. IEEE Trans. Inform. Theory 59 (2013) 391–405. | MR
, and ,V.S. Borkar, Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press (2008). | MR | Zbl
Approximation gaussienne d’algorithmes stochastiques à dynamique markovienne. Ann. Inst. Henri Poincaré 24 (1988) 131–155. | MR | Zbl
,Rate of Convergence for Constrained Stochastic Approximation Algorithms. SIAM J. Control Optim. 40 (2001) 1011–1041. | MR | Zbl
and ,H. Chen, Stochastic Approximation and its Applications. Kluwer Academic Publishers (2002). | MR | Zbl
H.F. Chen, L. Guo and A.J. Gao, Convergence and robustness of the Robbins−Monro algorithms truncated at randomly varying bounds. Stoch. Proc. Appl. (1988). | MR | Zbl
B. Delyon, Stochastic Approximation with Decreasing Gain: Convergence and Asymptotic Theory. Technical report. Publication interne 952, IRISA (2000).
Convergence of a Stochastic Approximation Version of the EM Algorithm. Ann. Statist. 27 (1999) 94–128. | MR | Zbl
, and ,M. Duflo, Algorithmes stochastiques. Springer (1996). | MR | Zbl
On asymptotically efficient recursive estimation. Ann. Statist. 6 (1978) 854–866. | MR | Zbl
,G. Fort, B. Jourdain, E. Kuhn, T. Lelièvre and G. Stoltz, Convergence of the Wang-Landau algorithm. Technical report. LTCI and CERMICS (2013). Submitted in Math. Comput. (2014).
Convergence of Adaptive and Interacting Markov Chain Monte Carlo Algorithms. Ann. Statist. 39 (2012) 3262–3289. | MR | Zbl
, and ,P. Hall and C.C. Heyde, Martingale Limit Theory and its Application. Academic Press, New York, London (1980). | MR | Zbl
O. Hernandez−Lerma and J.B. Lasserre, Markov Chains and Invariant Probabilities. Birkhäuser (2003). | Zbl
R.A. Horn and C.R. Johnson, Topics in matrix analysis. Cambridge University Press (1994). | MR | Zbl
Stochastic approximation: a survey. Wiley Interdisciplinary Reviews: Comput. Statist. 2 (2010) 87–96.
,Rates of convergence for Stochastic Approximation type algorithms. SIAM J. Control Optim. 17 (1979) 607–617. | MR | Zbl
and ,H.J. Kushner and G.G. Yin, Stochastic Approximation and Recursive Algorithms and Applications. Springer (2003). | MR | Zbl
Asymptotic normality of randomly truncated stochastic algorithms. ESAIM: PS 17 (2013) 105–119. | MR | Zbl
,S.P. Meyn and R.L. Tweedie, Markov Chains and Stochastic Stability. Cambridge University Press (2009). | MR | Zbl
Weak convergence rates for stochastic approximation with application to multiple targets and simulated annealing. Ann. Appl. Probab. 8 (1998) 10–44. | MR | Zbl
,Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. 30 (1992) 838–855. | MR | Zbl
and ,D. Ruppert, Handbook of Sequential Analysis, chapter Stochastic Approximation. Marcel Decker (1991). | MR | Zbl
J.C. Spall, Introduction to Stochastic Search and Optimization. Wiley-Interscience (2003). | MR | Zbl
Asymptotic Normality for a Vector Stochastic Difference Equation with Applications in Stochastic Approximation. J. Multivariate Anal. 57 (1996) 101–118. | MR | Zbl
,Cité par Sources :