Exponential inequalities for unbounded functions of geometrically ergodic Markov chains: applications to quantitative error bounds for regenerative Metropolis algorithms

References

• Dedecker J, Gouëzel S. Subgaussian concentration inequalities for geometrically ergodic Markov chains. Electron Commun Probab. 2015;20:1–12. doi: 10.1214/ECP.v20-3966
   Web of Science ®Google Scholar
• Adamczak R. A tail inequality for suprema of unbounded empirical processes with applications to Markov chains. Electron J Probab. 2008;13(34):1000–1034. doi: 10.1214/EJP.v13-521
   Web of Science ®Google Scholar
• Audibert J.-Y, Munos R, Szepesvâri C. Variance estimates and exploration function in multi-armed bandit. 2007. (CERTIS Research Report 07–31).
   Google Scholar
• de la Pena VH, Klass MJ, Lai TL. Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws. Ann Probab. 2004;32:1902–1933. doi: 10.1214/009117904000000397
   Web of Science ®Google Scholar
• Bertail P, Clémençon S. Sharp bounds for the tails of functionals of Markov chains. Theory Probab Appl. 2010;54:505–515. doi: 10.1137/S0040585X97984401
   Web of Science ®Google Scholar
• Adamczak R, Bednorz W. Exponential concentration inequalities for additive functionals of Markov chains. ESAIM: P&S. 2015;19:440–481. doi: 10.1051/ps/2014032
   Web of Science ®Google Scholar
• Nagaev AV. Large deviations for a class of distributions. Limit Theorems Theory Probab. 1963;71–88.
   Google Scholar
• Latuszynski K, Miasojedow B, Niemiro W. Nonasymptotic bounds on the estimation error of MCMC algorithms. Bernoulli. 2013;19(5A):2033–2066. doi: 10.3150/12-BEJ442
   Web of Science ®Google Scholar
• Gyori BM, Paulin D. Non-asymptotic confidence intervals for MCMC in practice. 2012; arXiv preprint arXiv:1212.2016.
   Google Scholar
• Brockwell AE, Kadane JB. Identification of regeneration times in MCMC simulation, with application to adaptive schemes. J Comput Graph Stat. 2005;14(2):436–458. doi: 10.1198/106186005X47453
   Web of Science ®Google Scholar
• Joulin A, Ollivier Y. Curvature, concentration and error estimates for Markov chain Monte Carlo. Ann Probab. 2010;38(6):2418–2442. doi: 10.1214/10-AOP541
   Web of Science ®Google Scholar
• Hairer M, Mattingly JC. Yet another look at Harris' ergodic theorem for Markov chains. In: Seminar on stochastic analysis, random fields and applications; Springer Basel, VI. 109–117, 2011.
   Google Scholar
• Wintenberger O. Weak transport inequalities and applications to exponential inequalities and oracle inequalities. EJP. 2015;20:1–27.
   Google Scholar
• Meyn SP, Tweedie RL. Markov chains and stochastic stability. London: Springer; 1993.
   Google Scholar
• Feigin PD, Tweedie RL. Random coefficient autoregressive processes: a Markov chain analysis of stationarity and finiteness of moments. J Time Series Anal. 1985;6:1–14. doi: 10.1111/j.1467-9892.1985.tb00394.x
   Google Scholar
• McDiarmid C. On the method of bounded differences. In: Siemons J, editors. Surveys of combinatorics. lecturer notes series 141, London Math. Soc.; 1989.
   Google Scholar
• Samson P-M. Concentration of measure inequalities for Markov chains and Φ-mixing processes. Ann Probab. 2000;28(1):416–461. doi: 10.1214/aop/1019160125
   Web of Science ®Google Scholar
• Rio E. Inégalités de Hoeffding pour les fonctions lipschitziennes de suites dépendantes. C R Acad Sci Paris Sér I Math. 2000;330:905–908. doi: 10.1016/S0764-4442(00)00290-1
   Google Scholar
• Rosenthal JS. Asymptotic variance and convergence rates of nearly-periodic Markov chain Monte Carlo algorithms. JASA. 2003;98(461):169–177. doi: 10.1198/016214503388619193
   Web of Science ®Google Scholar
• Marton K. A measure concentration inequality for contracting Markov chains. Geom Funct Anal. 1996;6(3):556–571. doi: 10.1007/BF02249263
   Web of Science ®Google Scholar
• Boucheron S, Lugosi G, Massart P. Concentration inequalities: a nonasymptotic theory of independence. Oxford: Oxford University Press; 2013.
   Google Scholar
• Villani C. Optimal transport, old and new. Berlin: Springer-Verlag; 2009.
   Google Scholar
• Djellout H, Guillin A, Wu L. Transportation cost-information inequalities and applications to random dynamical systems and diffusions. Ann. Probab. 2004;32B(3):2702–2732.
   Google Scholar
• Roberts GO, Rosenthal JS. General state space Markov chains and MCMC algorithms. Probab Surv. 2004;1:20–71. doi: 10.1214/154957804100000024
   Google Scholar
• Mykland P, Tierney L, Yu B. Regeneration in Markov chain samplers. J Am Stat Assoc. 1995;90:233–241. doi: 10.1080/01621459.1995.10476507
   Web of Science ®Google Scholar
• Mengersen KL, Tweedie RL. Rates of convergence of the Hastings and Metropolis algorithms. Ann Stat. 1996;24:101–121. doi: 10.1214/aos/1033066201
   Web of Science ®Google Scholar
• Brockwell AE. Parallel Markov chain Monte Carlo simulation by pre-fetching. J Comput Graph Stat. 2006;15(1):246–261. doi: 10.1198/106186006X100579
   Web of Science ®Google Scholar
• Baxendale PH. Renewal theory and computable convergence rates for geometrically ergodic Markov chains. Ann Appl Probab. 2005;15:700–738. doi: 10.1214/105051604000000710
   Web of Science ®Google Scholar
• Latuszynski K, Niemiro W. Rigorous confidence bounds for MCMC under a geometric drift condition. J Complexity. 2011;27:23–38. doi: 10.1016/j.jco.2010.07.003
   Web of Science ®Google Scholar
• Jerrum MR, Valiant LG, Vizirani VV. Random generation of combinatorial structures from a uniform distribution. Theoret Comput Sci. 1986;43:169–188. doi: 10.1016/0304-3975(86)90174-X
   Web of Science ®Google Scholar
• Ibragimov IA. Some limit theorems for stationary processes. Theory Probab Appl. 1962;7:349–382. doi: 10.1137/1107036
   Google Scholar