×

Variance reduction using nonreversible Langevin samplers. (English) Zbl 1343.82036

Summary: A standard approach to computing expectations with respect to a given target measure is to introduce an overdamped Langevin equation which is reversible with respect to the target distribution, and to approximate the expectation by a time-averaging estimator. As has been noted in recent papers (cf. [C.-R. Hwang et al., Stochastic Processes Appl. 125, No. 9, 3522–3540 (2015; Zbl 1323.60105)], [T. Lelièvre et al., J. Stat. Phys. 152, No. 2, 237–274 (2013; Zbl 1276.82042)], [L. Rey-Bellet and K. Spiliopoulos, “Irreversible Langevin samplers and variance reduction: a large deviation approach”, arXiv:1404.0105], [S.-J. Wu et al., J. Stat. Phys. 155, No. 3, 571–590 (2014; Zbl 1297.82028)]), introducing an appropriately chosen nonreversible component to the dynamics is beneficial, both in terms of reducing the asymptotic variance and of speeding up convergence to the target distribution. In this paper we present a detailed study of the dependence of the asymptotic variance on the deviation from reversibility. Our theoretical findings are supported by numerical simulations.

MSC:

82C31 Stochastic methods (Fokker-Planck, Langevin, etc.) applied to problems in time-dependent statistical mechanics
60F05 Central limit and other weak theorems
82B80 Numerical methods in equilibrium statistical mechanics (MSC2010)
65C05 Monte Carlo methods

Software:

BayesDA
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Asmussen, S., Glynn, P.W.: Stochastic Simulation: Algorithms and Analysis, vol. 57. Springer, New York (2007) · Zbl 1126.65001
[2] Avellanada, M., Majda, A.J.: Stieltjes integral representation and effective diffusivity bounds for turbulent transport. Phys. Rev. Lett. 62, 753-755 (1989) · doi:10.1103/PhysRevLett.62.753
[3] Avellaneda, M., Majda, A.J.: An integral representation and bounds on the effective diffusivity in passive advection by laminar and turbulent flows. Commun. Math. Phys. 138(2), 339-391 (1991) · Zbl 0731.76082 · doi:10.1007/BF02099496
[4] Bhatia, R.: Matrix Analysis, vol. 169. Springer, New York (1997) · Zbl 0863.15001
[5] Bhattacharya, R.: A central limit theorem for diffusions with periodic coefficients. Ann. Probab. 13(2), 385-396 (1985) · Zbl 0575.60075 · doi:10.1214/aop/1176992998
[6] Bhattacharya, R.N.: On the functional central limit theorem and the law of the iterated logarithm for Markov processes. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 60(2), 185-201 (1982) · Zbl 0468.60034 · doi:10.1007/BF00531822
[7] Bhattacharya, R.N.: Multiscale diffusion processes with periodic coefficients and an application to solute transport in porous media. Ann. Appl. Probab. 9(4), 951-1020 (1999) · Zbl 0956.60080 · doi:10.1214/aoap/1029962863
[8] Bhattacharya, R.N., Gupta, V.K., Walker, H.F.: Asymptotics of solute dispersion in periodic porous media. SIAM J. Appl. Math. 49(1), 86-98 (1989) · Zbl 0664.60079 · doi:10.1137/0149005
[9] Bierkens, J.: Nonreversible Metropolis-Hastings. arXiv:1401.8087 (2014) · Zbl 1360.65040
[10] Bovier, A., Eckhoff, M., Gayrard, V., Klein, M.: Metastability in reversible diffusion processes: sharp asymptotics for capacities and exit times. Technical report, WIAS, Berlin (2002) · Zbl 1076.82045
[11] Bovier, A., Gayrard, V., Klein, M.: Metastability in reversible diffusion processes. II. Precise asymptotics for small eigenvalues. J. Eur. Math. Soc. 7(1), 69-99 (2005) · Zbl 1105.82025 · doi:10.4171/JEMS/22
[12] Cattiaux, P., Chafaı, D., Guillin, A.: Central limit theorems for additive functionals of ergodic Markov diffusions processes. ALEA 9(2), 337-382 (2012) · Zbl 1277.60047
[13] Constantin, P., Kiselev, A., Ryzhik, L., Zlato, A.: Diffusion and mixing in fluid flow. Ann. Math. 168(2), 643-674 (2008) · Zbl 1180.35084 · doi:10.4007/annals.2008.168.643
[14] Dellaportas, P., Kontoyiannis, I.: Control variates for estimation based on reversible Markov chain Monte Carlo samplers. J. R. Stat. Soc. B 74(1), 133-161 (2012) · Zbl 1411.62056 · doi:10.1111/j.1467-9868.2011.01000.x
[15] Diaconis, P., Holmes, S., Neal, R.M.: Analysis of a nonreversible Markov chain sampler. Ann. Appl. Probab. 10(3), 726-752 (2000) · Zbl 1083.60516 · doi:10.1214/aoap/1019487508
[16] Douc, R., Fort, G., Guillin, A.: Subgeometric rates of convergence of f-ergodic strong Markov processes. Stoch. Processes Appl. 119(3), 897-923 (2009) · Zbl 1163.60034 · doi:10.1016/j.spa.2008.03.007
[17] Down, D., Meyn, S.P., Tweedie, R.L.: Exponential and uniform ergodicity of Markov processes. Ann. Probab. 23(4), 1671-1691 (1995) · Zbl 0852.60075 · doi:10.1214/aop/1176987798
[18] Franke, B., Hwang, C.R., Pai, H.M., Sheu, S.J.: The behavior of the spectral gap under growing drift. Trans. Am. Math. Soc. 362(3), 1325-1350 (2010) · Zbl 1187.35146 · doi:10.1090/S0002-9947-09-04939-3
[19] Gelman, A., Carlin, J.B., Stern, H.S., Rubin, D.B.: Bayesian Data Analysis, vol. 2. Taylor & Francis, Boca Raton (2014) · Zbl 1279.62004
[20] Girolami, M., Calderhead, B.: Riemann manifold Langevin and Hamiltonian Monte Carlo methods. J. R. Stat. Soc. B 73(2), 123-214 (2011) · Zbl 1411.62071 · doi:10.1111/j.1467-9868.2010.00765.x
[21] Glynn, P.W., Meyn, S.P.: A Liapounov bound for solutions of the Poisson equation. Ann. Probab. 24(2), 916-931 (1996) · Zbl 0863.60063 · doi:10.1214/aop/1039639370
[22] Golden, K., Papanicolaou, G.: Bounds for effective parameters of heterogeneous media by analytic continuation. Commun. Math. Phys. 90(4), 473-491 (1983) · doi:10.1007/BF01216179
[23] Haario, H., Saksman, E., Tamminen, J.: Adaptive proposal distribution for random walk Metropolis algorithm. Comput. Stat. 14(3), 375-396 (1999) · Zbl 0941.62036 · doi:10.1007/s001800050022
[24] Helffer, B.: Spectral Theory and Its Applications, vol. 139. Cambridge University Press, Cambridge (2013) · Zbl 1279.47002
[25] Helland, I.S.: Central limit theorems for martingales with discrete or continuous time. Scand. J. Stat. 9(2), 79-94 (1982) · Zbl 0486.60023
[26] Hennequin, G.; Aitchison, L.; Lengyel, M.; Ghahramani, Z. (ed.); Welling, M. (ed.); Cortes, C. (ed.); Lawrence, ND (ed.); Weinberger, KQ (ed.), Fast sampling-based inference in balanced neuronal networks, 2240-2248 (2014), New York
[27] Hukushima, K., Sakai, Y.: An irreversible Markov-chain Monte Carlo method with skew detailed balance conditions. J. Phys. 473, 012012 (2013)
[28] Hwang, C.R., Hwang-Ma, S.Y., Sheu, S.J.: Accelerating Gaussian diffusions. Ann. Appl. Probab. 3(3), 897-913 (1993) · Zbl 0780.60074 · doi:10.1214/aoap/1177005371
[29] Hwang, C.R., Hwang-Ma, S.Y., Sheu, S.J., et al.: Accelerating diffusions. Ann. Appl. Probab. 15(2), 1433-1444 (2005) · Zbl 1069.60065 · doi:10.1214/105051605000000025
[30] Hwang, C.-R., Normand, R., Wu, S.-J.: Variance reduction for diffusions. arXiv:1406.4657 (2014) · Zbl 1323.60105
[31] Jacod, J., Shiryaev, A.N.: Limit Theorems for Stochastic Processes, vol. 1943877. Springer, Berlin (1987) · Zbl 0635.60021 · doi:10.1007/978-3-662-02514-7
[32] Kipnis, C., Varadhan, S.R.S.: Central limit theorem for additive functionals of reversible Markov processes and applications to simple exclusions. Commun. Math. Phys. 104(1), 1-19 (1986) · Zbl 0588.60058 · doi:10.1007/BF01210789
[33] Komorowski, T., Landim, C., Olla, S.: Fluctuations in Markov Processes: Time Symmetry and Martingale Approximation. Springer, Heidelberg (2012) · Zbl 1396.60002 · doi:10.1007/978-3-642-29880-6
[34] Krengel, U.: Ergodic Theorems. de Gruyter Studies in Mmathematics, vol. 6. Walter de Gruyter & Co., Berlin (1985) · Zbl 0575.28009 · doi:10.1515/9783110844641
[35] Leimkuhler, B., Reich, S.: Simulating Hamiltonian Dynamics, vol. 14. Cambridge University Press, Cambridge (2004) · Zbl 1069.65139
[36] Lelievre, T.; Cangiani, A. (ed.); Davidchack, RL (ed.); Georgoulis, E. (ed.); Gorban, AN (ed.); Levesley, J. (ed.); Tretyakov, MV (ed.), Two mathematical tools to analyze metastable stochastic processes, 791-810 (2013), New York · Zbl 1272.82027 · doi:10.1007/978-3-642-33134-3_83
[37] Lelièvre, T., Nier, F., Pavliotis, G.A.: Optimal non-reversible linear drift for the convergence to equilibrium of a diffusion. J. Stat. Phys. 152(2), 237-274 (2013) · Zbl 1276.82042 · doi:10.1007/s10955-013-0769-x
[38] Lelièvre, T., Stoltz, G., Rousset, M.: Free Energy Computations: A Mathematical Perspective. World Scientific, Singapore (2010) · Zbl 1227.82002 · doi:10.1142/9781848162488
[39] Liu, J.S.: Monte Carlo Strategies in Scientific Computing. Springer, New York (2008) · Zbl 1132.65003
[40] Lorenzi, L., Bertoldi, M.: Analytical Methods for Markov Semigroups. CRC Press, New York (2006) · Zbl 1109.35005 · doi:10.1201/9781420011586
[41] Ma, Y.-A., Chen, T., Fox, E.: A complete recipe for stochastic gradient mcmc. In: Advances in Neural Information Processing Systems, pp. 2899-2907 (2015) · Zbl 0731.76082
[42] MacKay, D.J.C.: Information Theory, Inference and Learning Algorithms. Cambridge University Press, Cambridge (2003) · Zbl 1055.94001
[43] Majda, A.J., Kramer, P.R.: Simplified models for turbulent diffusion: theory, numerical modelling, and physical phenomena. Phys. Rep. 314(4), 237-574 (1999) · doi:10.1016/S0370-1573(98)00083-0
[44] Majda, A.J., McLaughlin, R.M.: The effect of mean flows on enhanced diffusivity in transport by incompressible periodic velocity fields. Stud. Appl. Math. 89(3), 245-279 (1993) · Zbl 0820.76078 · doi:10.1002/sapm1993893245
[45] Martin, J., Wilcox, L.C., Burstedde, C., Ghattas, O.: A stochastic newton MCMC method for large-scale statistical inverse problems with application to seismic inversion. SIAM J. Sci. Comput. 34(3), A1460-A1487 (2012) · Zbl 1250.65011 · doi:10.1137/110845598
[46] Mattingly, J.C., Stuart, A.M., Higham, D.J.: Ergodicity for SDEs and approximations: locally Lipschitz vector fields and degenerate noise. Stoch. Processes Appl. 101(2), 185-232 (2002) · Zbl 1075.60072 · doi:10.1016/S0304-4149(02)00150-3
[47] Mattingly, J.C., Stuart, A.M., Tretyakov, M.V.: Convergence of numerical time-averaging and stationary measures via Poisson equations. SIAM J. Numer. Anal. 48(2), 552-577 (2010) · Zbl 1217.65014 · doi:10.1137/090770527
[48] Meyn, S.P., Tweedie, R.L.: Stability of Markovian processes III: Foster-Lyapunov criteria for continuous-time processes. Adv. Appl. Probab. 25(3), 518-548 (1993) · Zbl 0781.60053 · doi:10.2307/1427522
[49] Meyn, S. P., Tweedie, R. L.: A survey of Foster-Lyapunov techniques for general state space Markov processes. In: Proceedings of the Workshop on Stochastic Stability and Stochastic Stabilization, Metz, France. Citeseer (1993)
[50] Mira, A.: Ordering and improving the performance of Monte Carlo Markov chains. Stat. Sci. 16(4), 340-350 (2001) · Zbl 1127.60312 · doi:10.1214/ss/1015346319
[51] Neal, R.M.: Sampling from multimodal distributions using tempered transitions. Stat. Comput. 6(4), 353-366 (1996) · doi:10.1007/BF00143556
[52] Neal, R. M.: Improving asymptotic variance of MCMC estimators: nonreversible chains are better. arXiv:math/0407281 (2004) · Zbl 1216.82022
[53] Neal, R.M.: MCMC Using Hamiltonian Dynamics. Handbook of Markov Chain Monte Carlo, vol. 54. CRC Press, Boca Raton (2010)
[54] Ohzeki, M., Ichiki, A.: Simple implementation of Langevin dynamics without detailed balance condition. arXiv:1307.0434 (2013)
[55] Pardoux, E., Veretennikov, A.Y.: On the Poisson equation and diffusion approximation I. Ann. Probab. 29(3), 1061-1085 (2001) · Zbl 1029.60053 · doi:10.1214/aop/1015345596
[56] Pavliotis, G.: Stochastic Processes and Applications: Diffusion Processes, the Fokker-Planck and Langevin Equations, vol. 60. Springer, New York (2014) · Zbl 1318.60003
[57] Pavliotis, G. A.: Homogenization Theory for Advection—Diffusion Equations with Mean Flow, Ph.D Thesis. Rensselaer Polytechnic Institute, Troy, NY (2002) · Zbl 1277.60047
[58] Pavliotis, G.A.: Asymptotic analysis of the Green-Kubo formula. IMA J. Appl. Math. 75, 951-967 (2010) · Zbl 1223.35045 · doi:10.1093/imamat/hxq039
[59] Peskun, P.H.: Optimum Monte-Carlo sampling using Markov chains. Biometrika 60(3), 607-612 (1973) · Zbl 0271.62041 · doi:10.1093/biomet/60.3.607
[60] Revuz, D., Yor, M.: Continuous Martingales and Brownian Motion, vol. 293. Springer, New York (1999) · Zbl 0917.60006
[61] Rey-Bellet, L., Spiliopoulos, K.: Irreversible Langevin samplers and variance reduction: a large deviation approach. arXiv:1404.0105 (2014) · Zbl 1338.60086
[62] Rey-Bellet, L., Spiliopoulos, K.: Variance reduction for irreversible Langevin samplers and diffusion on graphs. arXiv:1410.0255 (2014) · Zbl 1347.60015
[63] Robert, C., Casella, G.: Monte Carlo Statistical Methods. Springer, New York (2013) · Zbl 0935.62005
[64] Roberts, G.O., Stramer, O.: Langevin diffusions and Metropolis-Hastings algorithms. Methodol. Comput. Appl. Probab. 4(4), 337-357 (2002) · Zbl 1033.65003 · doi:10.1023/A:1023562417138
[65] Roberts, G.O., Tweedie, R.L.: Exponential convergence of langevin distributions and their discrete approximations. Bernoulli 2(4), 341-363 (1996) · Zbl 0870.60027 · doi:10.2307/3318418
[66] Schütte, C., Sarich, M.: Metastability and Markov State Models in molecular Dynamics: Modeling, Analysis, Algorithmic Approaches. American Mathematical Society, Providence (2013) · Zbl 1305.60004
[67] Strang, G.: On the construction and comparison of difference schemes. SIAM J. Numer. Anal. 5(3), 506-517 (1968) · Zbl 0184.38503 · doi:10.1137/0705041
[68] Sun, Y.; Schmidhuber, J.; Faustino, JG; Lafferty, JD (ed.); Williams, CKI (ed.); Shawe-Taylor, J. (ed.); Zemel, RS (ed.); Culotta, A. (ed.), Improving the asymptotic performance of Markov chain Monte-Carlo by inserting vortices, 2235-2243 (2010), New York
[69] Suwa, H., Todo, S.: General construction of irreversible kernel in Markov Chain Monte Carlo. arXiv:1207.0258 (2012)
[70] Talay, D., Tubaro, L.: Expansion of the global error for numerical schemes solving stochastic differential equations. Stoch. Anal. Appl. 8(4), 483-509 (1990) · Zbl 0718.60058 · doi:10.1080/07362999008809220
[71] Turitsyn, K.S., Chertkov, M., Vucelja, M.: Irreversible Monte Carlo algorithms for efficient sampling. Phys. D 240(4), 410-414 (2011) · Zbl 1216.82022 · doi:10.1016/j.physd.2010.10.003
[72] Wu, S.J., Hwang, C.R., Chu, M.T.: Attaining the optimal Gaussian diffusion acceleration. J. Stat. Phys. 155(3), 571-590 (2014) · Zbl 1297.82028 · doi:10.1007/s10955-014-0963-5
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.