×

Large deviations for the empirical measure of the zig-zag process. (English) Zbl 1482.60042

Summary: The zig-zag process is a piecewise deterministic Markov process in position and velocity space. The process can be designed to have an arbitrary Gibbs type marginal probability density for its position coordinate, which makes it suitable for Monte Carlo simulation of continuous probability distributions. An important question in assessing the efficiency of this method is how fast the empirical measure converges to the stationary distribution of the process. In this paper we provide a partial answer to this question by characterizing the large deviations of the empirical measure from the stationary distribution. Based on the Feng-Kurtz approach, we develop an abstract framework aimed at encompassing piecewise deterministic Markov processes in position-velocity space. We derive explicit conditions for the zig-zag process to allow the Donsker-Varadhan variational formulation of the rate function, both for a compact setting (the torus) and one-dimensional Euclidean space. Finally we derive an explicit expression for the Donsker-Varadhan functional for the case of a compact state space and use this form of the rate function to address a key question concerning the optimal choice of the switching rate of the zig-zag process.

MSC:

60F10 Large deviations
60J25 Continuous-time Markov processes on general state spaces

References:

[1] Andrieu, C., de Freitas, N., Doucet, A. and Jordan, M. I. (2003). An introduction to MCMC for machine learning. Mach. Learn. 50 5-43. · Zbl 1033.68081
[2] Andrieu, C. and Livingstone, S. (2019). Peskun-Tierney ordering for Markov chain and process Monte Carlo: Beyond the reversible scenario. arXiv preprint. Available at arXiv:1906.06197. · Zbl 1489.65005
[3] Arendt, W., Grabosch, A., Greiner, G., Groh, U., Lotz, H. P., Moustakas, U., Nagel, R., Neubrander, F. and Schlotterbeck, U. (1986). One-Parameter Semigroups of Positive Operators. Lecture Notes in Math. 1184. Springer, Berlin. · Zbl 0585.47030 · doi:10.1007/BFb0074922
[4] Asmussen, S. and Glynn, P. W. (2007). Stochastic Simulation: Algorithms and Analysis. Stochastic Modelling and Applied Probability 57. Springer, New York. · Zbl 1126.65001
[5] Bédard, M. and Rosenthal, J. S. (2008). Optimal scaling of Metropolis algorithms: Heading toward general target distributions. Canad. J. Statist. 36 483-503. · Zbl 1167.60344 · doi:10.1002/cjs.5550360401
[6] Bierkens, J. and Duncan, A. (2017). Limit theorems for the zig-zag process. Adv. in Appl. Probab. 49 791-825. · Zbl 1433.65008 · doi:10.1017/apr.2017.22
[7] Bierkens, J., Fearnhead, P. and Roberts, G. (2019). The zig-zag process and super-efficient sampling for Bayesian analysis of big data. Ann. Statist. 47 1288-1320. · Zbl 1417.65008 · doi:10.1214/18-AOS1715
[8] Bierkens, J. and Roberts, G. (2017). A piecewise deterministic scaling limit of lifted Metropolis-Hastings in the Curie-Weiss model. Ann. Appl. Probab. 27 846-882. · Zbl 1370.60039 · doi:10.1214/16-AAP1217
[9] Bierkens, J., Roberts, G. O. and Zitt, P.-A. (2019). Ergodicity of the zigzag process. Ann. Appl. Probab. 29 2266-2301. · Zbl 1467.60020 · doi:10.1214/18-AAP1453
[10] Bierkens, J. and Verduyn Lunel, S. M. (2019). Spectral analysis of the zigzag process. arXiv preprint. Available at arXiv:1905.01691.
[11] Birrell, J. and Rey-Bellet, L. (2019). Concentration inequalities and performance guarantees for hypocoercive MCMC samplers. arXiv preprint. Available at arXiv:1907.11973.
[12] Bouchard-Côté, A., Vollmer, S. J. and Doucet, A. (2018). The bouncy particle sampler: A nonreversible rejection-free Markov chain Monte Carlo method. J. Amer. Statist. Assoc. 113 855-867. · Zbl 1398.60084 · doi:10.1080/01621459.2017.1294075
[13] Bucklew, J. A. (2004). Introduction to Rare Event Simulation. Springer Series in Statistics. Springer, New York. · Zbl 1057.65002 · doi:10.1007/978-1-4757-4078-3
[14] Budhiraja, A. and Dupuis, P. (2019). Analysis and Approximation of Rare Events: Representations and Weak Convergence Methods. Probability Theory and Stochastic Modelling 94. Springer, New York. · Zbl 1427.60003 · doi:10.1007/978-1-4939-9579-0
[15] Davis, M. H. A. (1984). Piecewise-deterministic Markov processes: A general class of nondiffusion stochastic models. J. Roy. Statist. Soc. Ser. B 46 353-388. · Zbl 0565.60070
[16] Davis, M. H. A. (1993). Markov Models and Optimization. Monographs on Statistics and Applied Probability 49. CRC Press, London. · Zbl 0780.60002 · doi:10.1007/978-1-4899-4483-2
[17] Dembo, A. and Zeitouni, O. (1994). Large Deviations Techniques and Applications. Springer, New York. · Zbl 0793.60030
[18] Diaconis, P., Holmes, S. and Neal, R. M. (2000). Analysis of a nonreversible Markov chain sampler. Ann. Appl. Probab. 10 726-752. · Zbl 1083.60516 · doi:10.1214/aoap/1019487508
[19] Doll, J., Dupuis, P. and Nyquist, P. (2018). A large deviations analysis of certain qualitative properties of parallel tempering and infinite swapping algorithms. Appl. Math. Optim. 78 103-144. · Zbl 1397.65015 · doi:10.1007/s00245-017-9401-9
[20] Donsker, M. D. and Varadhan, S. R. S. (1975). Asymptotic evaluation of certain Markov process expectations for large time, I. Comm. Pure Appl. Math. 28 1-47. · Zbl 0323.60069
[21] Donsker, M. D. and Varadhan, S. R. S. (1975). Asymptotic evaluation of certain Markov process expectations for large time, II. Comm. Pure Appl. Math. 28 279-301. · Zbl 0348.60031
[22] Donsker, M. D. and Varadhan, S. R. S. (1975). On a variational formula for the principal eigenvalue for operators with maximum principle. Proc. Natl. Acad. Sci. USA 72 780-783. · Zbl 0353.49039 · doi:10.1073/pnas.72.3.780
[23] Donsker, M. D. and Varadhan, S. R. S. (1976). Asymptotic evaluation of certain Markov process expectations for large time, III. Comm. Pure Appl. Math. 29 389-461. · Zbl 0348.60032 · doi:10.1002/cpa.3160290405
[24] Donsker, M. D. and Varadhan, S. R. S. (1976). On the principal eigenvalue of second-order elliptic differential operators. Comm. Pure Appl. Math. 29 595-621. · Zbl 0356.35065 · doi:10.1002/cpa.3160290606
[25] Dupuis, P. and Lipshutz, D. (2018). Large deviations for the empirical measure of a diffusion via weak convergence methods. Stochastic Process. Appl. 128 2581-2604. · Zbl 1388.60067 · doi:10.1016/j.spa.2017.09.020
[26] Dupuis, P. and Liu, Y. (2015). On the large deviation rate function for the empirical measures of reversible jump Markov processes. Ann. Probab. 43 1121-1156. · Zbl 1325.60023 · doi:10.1214/13-AOP883
[27] Dupuis, P., Liu, Y., Plattner, N. and Doll, J. D. (2012). On the infinite swapping limit for parallel tempering. Multiscale Model. Simul. 10 986-1022. · Zbl 1261.65009 · doi:10.1137/110853145
[28] Ethier, S. N. and Kurtz, T. G. (2009). Markov Processes: Characterization and Convergence. Wiley, New York.
[29] Fearnhead, P., Bierkens, J., Pollock, M. and Roberts, G. O. (2018). Piecewise deterministic Markov processes for continuous-time Monte Carlo. Statist. Sci. 33 386-412. · Zbl 1403.62148 · doi:10.1214/18-STS648
[30] Feng, J. and Kurtz, T. G. (2006). Large Deviations for Stochastic Processes. Mathematical Surveys and Monographs 131. Amer. Math. Soc., Providence, RI. · Zbl 1113.60002 · doi:10.1090/surv/131
[31] Franke, B., Hwang, C.-R., Pai, H.-M. and Sheu, S.-J. (2010). The behavior of the spectral gap under growing drift. Trans. Amer. Math. Soc. 362 1325-1350. · Zbl 1187.35146 · doi:10.1090/S0002-9947-09-04939-3
[32] Frigessi, A., di Stefano, P., Hwang, C.-R. and Sheu, S. J. (1993). Convergence rates of the Gibbs sampler, the Metropolis algorithm and other single-site updating dynamics. J. Roy. Statist. Soc. Ser. B 55 205-219. · Zbl 0781.60039
[33] Hwang, C.-R., Hwang-Ma, S.-Y. and Sheu, S.-J. (2005). Accelerating diffusions. Ann. Appl. Probab. 15 1433-1444. · Zbl 1069.60065 · doi:10.1214/105051605000000025
[34] Mengersen, K. L. and Tweedie, R. L. (1996). Rates of convergence of the Hastings and Metropolis algorithms. Ann. Statist. 24 101-121. · Zbl 0854.60065 · doi:10.1214/aos/1033066201
[35] Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H. and Teller, E. (1953). Equation of state calculations by fast computing machines. J. Chem. Phys. 21 1087. · Zbl 1431.65006
[36] Monmarché, P. (2016). Piecewise deterministic simulated annealing. ALEA Lat. Am. J. Probab. Math. Stat. 13 357-398. · Zbl 1341.60091
[37] Peters, E. A. J. F. and De With, G. (2012). Rejection-free Monte Carlo sampling for general potentials. Phys. Rev. E (3) 85 1-5.
[38] Plattner, N., Doll, J. D., Dupuis, P., Wang, H., Liu, Y. and Gubernatis, J. E. (2011). An infinite swapping approach to the rare-event sampling problem. J. Chem. Phys. 135 134111.
[39] Rey-Bellet, L. and Spiliopoulos, K. (2015). Irreversible Langevin samplers and variance reduction: A large deviations approach. Nonlinearity 28 2081-2103. · Zbl 1338.60086 · doi:10.1088/0951-7715/28/7/2081
[40] Robert, C. P. and Casella, G. (2004). Monte Carlo Statistical Methods, 2nd ed. Springer Texts in Statistics. Springer, New York. · Zbl 1096.62003 · doi:10.1007/978-1-4757-4145-2
[41] Roberts, G. O. and Rosenthal, J. S. (2004). General state space Markov chains and MCMC algorithms. Probab. Surv. 1 20-71. · Zbl 1189.60131 · doi:10.1214/154957804100000024
[42] Rosenthal, J. S. (2003). Asymptotic variance and convergence rates of nearly-periodic Markov chain Monte Carlo algorithms. J. Amer. Statist. Assoc. 98 169-177. · Zbl 1048.60057 · doi:10.1198/016214503388619193
[43] Schaefer, H. H. (1971). Topological Vector Spaces. Springer, New York-Berlin. · Zbl 0212.14001
[44] Vialaret, M. and Maire, F. (2020). On the convergence time of some non-reversible Markov chain Monte Carlo methods. Methodol. Comput. Appl. Probab. 22 1349-1387 · Zbl 1460.60081 · doi:10.1007/s11009-019-09766-w
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.