Central limit theorems for stochastic approximation with controlled Markov chain dynamics

Fort, Gersende

ESAIM: Probability and Statistics, Tome 19 (2015), pp. 60-80

This paper provides a Central Limit Theorem (CLT) for a process $\{\theta {}_n,n\ge 0\}$ satisfying a stochastic approximation (SA) equation of the form $\theta {}_{n+1}=\theta {}_n+\gamma {}_{n+1}H(\theta {}_n,X_{n+1})$; 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 $\{X_n,n\ge 0\}$ 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.

Classification : 62L20, 60F05, 60J20
Keywords: Stochastic approximation, limit theorems, controlled markov chain

C. Andrieu, G. Fort and M. Vihola, Quantitative Convergence Rates for sub-geometric Markov chains. Technical report arXiv:1309.0622v2 (2014). | MR

C. Andrieu, E. Moulines and P. Priouret, Stability of Stochastic Approximation under Verifiable Conditions. SIAM J. Control Optim. 44 (2005) 283–312. | MR | Zbl

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

P. Bianchi, G. Fort and W. Hachem, Performance of a Distributed Stochastic Approximation Algorithm. IEEE Trans. Inform. Theory 59 (2013) 391–405. | MR

V.S. Borkar, Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press (2008). | MR | Zbl

C. Bouton, Approximation gaussienne d’algorithmes stochastiques à dynamique markovienne. Ann. Inst. Henri Poincaré 24 (1988) 131–155. | MR | Zbl

R. Buche and H.J. Kushner, Rate of Convergence for Constrained Stochastic Approximation Algorithms. SIAM J. Control Optim. 40 (2001) 1011–1041. | MR | Zbl

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).

B. Delyon, M. Lavielle and E. Moulines, Convergence of a Stochastic Approximation Version of the EM Algorithm. Ann. Statist. 27 (1999) 94–128. | MR | Zbl

M. Duflo, Algorithmes stochastiques. Springer (1996). | MR | Zbl

V. Fabian, 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).

G. Fort, E. Moulines and P. Priouret, Convergence of Adaptive and Interacting Markov Chain Monte Carlo Algorithms. Ann. Statist. 39 (2012) 3262–3289. | MR | Zbl

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

H. Kushner, Stochastic approximation: a survey. Wiley Interdisciplinary Reviews: Comput. Statist. 2 (2010) 87–96.

H. Kushner and H. Huang, Rates of convergence for Stochastic Approximation type algorithms. SIAM J. Control Optim. 17 (1979) 607–617. | MR | Zbl

H.J. Kushner and G.G. Yin, Stochastic Approximation and Recursive Algorithms and Applications. Springer (2003). | MR | Zbl

J. Lelong, 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

M. Pelletier, Weak convergence rates for stochastic approximation with application to multiple targets and simulated annealing. Ann. Appl. Probab. 8 (1998) 10–44. | MR | Zbl

B.T. Polyak and A.B. Juditsky, Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. 30 (1992) 838–855. | MR | Zbl

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

Y. Zhu, Asymptotic Normality for a Vector Stochastic Difference Equation with Applications in Stochastic Approximation. J. Multivariate Anal. 57 (1996) 101–118. | MR | Zbl