On the stability of some controlled Markov chains and its applications to stochastic approximation with Markovian dynamic. (English) Zbl 1317.65004

Andrieu, Christophe; Tadić, Vladislav B.; Vihola, Matti

Ann. Appl. Probab. 25, No. 1, 1-45 (2015).

A model of controlled Markov chains is considered in which the transition probabilities \(P_\vartheta(x,A)\) depend on some parameter \(\vartheta\). The conditional distribution of the chain at the (\(i+1\))-th step given the past is \(X_{i+1}|(\vartheta_0,X_0,\dots,X_i)\sim P_{\vartheta_i}(X_i,\cdot)\), and \(\vartheta_{i+1}=\varphi_{i+1}(\vartheta_0,X_0,\dots,X_{i+1})\), where \(\varphi_i\), \(i=1,2\dots\) is a family of nonrandom mappings. A Lyapunov function technique is used to establish recurrence of the joint process \((\vartheta_i,X_i)\) to a set. The authors describe how to combine a joint Lyaunov function from two individual functions for \(X\) and \(\vartheta\). The technique applies even in situations where the dynamics exhibits a time-scale separation.
The results are applied to the stability analysis of Robbins-Monro stochastic approximation algorithms and adaptive Markov chain Monte Carlo algorithms.

Reviewer: R. E. Maiboroda (Kyïv)

MSC:

65C05	Monte Carlo methods
60J22	Computational methods in Markov chains
60J05	Discrete-time Markov processes on general state spaces
65C40	Numerical analysis or methods applied to Markov chains

Keywords:

Lyaunov function; reccurent Markov Chain; stability; controlled Markov Chain; Robbins-Monro stochastic approximation; adaptive Markov chain Monte Carlo algorithms

References:

[1]	Andrieu, C. and Moulines, É. (2006). On the ergodicity properties of some adaptive MCMC algorithms. Ann. Appl. Probab. 16 1462-1505. · Zbl 1114.65001 · doi:10.1214/105051606000000286
[2]	Andrieu, C., Moulines, É. and Priouret, P. (2005). Stability of stochastic approximation under verifiable conditions. SIAM J. Control Optim. 44 283-312. · Zbl 1083.62073 · doi:10.1137/S0363012902417267
[3]	Andrieu, C. and Robert, C. P. (2001). Controlled MCMC for optimal sampling. Technical Report 0125, Cahiers de Mathématiques du Ceremade, Univ. Paris-Dauphine.
[4]	Andrieu, C. and Vihola, M. (2014). Markovian stochastic approximation with expanding projections. Bernoulli 20 545-585. · Zbl 1316.62124 · doi:10.3150/12-BEJ497
[5]	Atchadé, Y. and Fort, G. (2010). Limit theorems for some adaptive MCMC algorithms with subgeometric kernels. Bernoulli 16 116-154. · Zbl 1215.60046 · doi:10.3150/09-BEJ199
[6]	Atchadé, Y. F. and Rosenthal, J. S. (2005). On adaptive Markov chain Monte Carlo algorithms. Bernoulli 11 815-828. · Zbl 1085.62097 · doi:10.3150/bj/1130077595
[7]	Benveniste, A., Métivier, M. and Priouret, P. (1990). Adaptive Algorithms and Stochastic Approximations. Applications of Mathematics ( New York ) 22 . Springer, Berlin. Translated from the French by Stephen S. Wilson. · Zbl 0752.93073
[8]	Delyon, B. and Juditsky, A. (1993). Accelerated stochastic approximation. SIAM J. Optim. 3 868-881. · Zbl 0801.62071 · doi:10.1137/0803045
[9]	Gelman, A., Roberts, G. O. and Gilks, W. R. (1996). Efficient Metropolis jumping rules. In Bayesian Statistics , 5 ( Alicante , 1994) 599-607. Oxford Univ. Press, New York.
[10]	Haario, H., Saksman, E. and Tamminen, J. (1999). Adaptive proposal distribution for random walk Metropolis algorithm. Comput. Statist. 14 375-395. · Zbl 0941.62036 · doi:10.1007/s001800050022
[11]	Haario, H., Saksman, E. and Tamminen, J. (2001). An adaptive Metropolis algorithm. Bernoulli 7 223-242. · Zbl 0989.65004 · doi:10.2307/3318737
[12]	Jarner, S. F. and Hansen, E. (2000). Geometric ergodicity of Metropolis algorithms. Stochastic Process. Appl. 85 341-361. · Zbl 0997.60070 · doi:10.1016/S0304-4149(99)00082-4
[13]	Meyn, S. P. and Tweedie, R. L. (1993). Markov Chains and Stochastic Stability . Springer, London. · Zbl 0925.60001
[14]	Saksman, E. and Vihola, M. (2010). On the ergodicity of the adaptive Metropolis algorithm on unbounded domains. Ann. Appl. Probab. 20 2178-2203. · Zbl 1209.65004 · doi:10.1214/10-AAP682
[15]	Vihola, M. (2011). On the stability and ergodicity of adaptive scaling Metropolis algorithms. Stochastic Process. Appl. 121 2839-2860. · Zbl 1234.65017 · doi:10.1016/j.spa.2011.08.006
[16]	Younes, L. (1999). On the convergence of Markovian stochastic algorithms with rapidly decreasing ergodicity rates. Stochastics Stochastics Rep. 65 177-228. · Zbl 0949.65006 · doi:10.1080/17442509908834179