×

Constructing sampling schemes via coupling: Markov semigroups and optimal transport. (English) Zbl 1454.60118

Summary: In this paper we develop a general framework for constructing and analyzing coupled Markov chain Monte Carlo samplers, allowing for both (possibly degenerate) diffusion and piecewise deterministic Markov processes. For many performance criteria of interest, including the asymptotic variance, the task of finding efficient couplings can be phrased in terms of problems related to optimal transport theory. We investigate general structural properties, proving a singularity theorem that has both geometric and probabilistic interpretations. Moreover, we show that those problems can often be solved approximately and support our findings with numerical experiments. For the particular objective of estimating the variance of a Bayesian posterior, our analysis suggests using novel techniques in the spirit of antithetic variates. Addressing the convergence to equilibrium of coupled processes we furthermore derive a modified Poincaré inequality.

MSC:

60J35 Transition functions, generators and resolvents
47D07 Markov semigroups and applications to diffusion processes
35Q62 PDEs in connection with statistics
65C05 Monte Carlo methods
65C35 Stochastic particle methods

Software:

EnsembleQN
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] I. Amemiya and K. Shiga, {\it On tensor products of Banach spaces}, Kōdai Math. Sem. Rep., 9 (1957), pp. 161-178, . · Zbl 0079.32404
[2] C. Andrieu, A. Doucet, and R. Holenstein, {\it Particle Markov chain Monte Carlo methods}, J. R. Stat. Soc. Ser. B. Stat. Methodol., 72 (2010), pp. 269-342. · Zbl 1184.65001
[3] L. Angiuli, G. Metafune, and C. Spina, {\it Feller semigroups and invariant measures}, Riv. Math. Univ. Parma (N.S.), 1 (2010), pp. 347-406. · Zbl 1223.47042
[4] W. Arendt, A. Grabosch, G. Greiner, U. Groh, H. P. Lotz, U. Moustakas, R. Nagel, F. Neubrander, and U. Schlotterbeck, {\it One-Parameter Semigroups of Positive Operators}, Lecture Notes in Math. 1184, Springer-Verlag, Berlin, 1986, .
[5] R. Assaraf, B. Jourdain, T. Lelièvre, and R. Roux, {\it Computation of sensitivities for the invariant measure of a parameter dependent diffusion}, Stoch. Partial Differ. Equ. Anal. Comput., 6 (2018), pp. 125-183. · Zbl 1401.37087
[6] D. Bakry, I. Gentil, and M. Ledoux, {\it Analysis and Geometry of Markov Diffusion Operators}, Springer Science & Business Media, New york, 2013. · Zbl 1376.60002
[7] P. H. Baxendale, {\it Statistical equilibrium and two-point motion for a stochastic flow of diffeomorphisms}, in Spatial Stochastic Processes, Progr. Probab. 19, Birkhäuser, Boston, MA, 1991, pp. 189-218. · Zbl 0744.60063
[8] R. N. Bhattacharya, {\it On the functional central limit theorem and the law of the iterated logarithm for Markov processes}, Z. Wahrsch. Verw. Gebiete, 60 (1982), pp. 185-201, . · Zbl 0468.60034
[9] J. Bierkens and A. Duncan, {\it Limit theorems for the zig-zag process}, Adv. in Appl. Probab., 49 (2017), pp. 791-825, . · Zbl 1433.65008
[10] J. Bierkens, P. Fearnhead, and G. Roberts, {\it The Zig-Zag Process and Super-Efficient Sampling for Bayesian Analysis of Big Data}, , 2016. · Zbl 1417.65008
[11] J. Bierkens, G. Roberts, and P.-A. Zitt, {\it Ergodicity of the Zigzag Process}, , 2018. · Zbl 1467.60020
[12] N. Bonneel, M. Van De Panne, S. Paris, and W. Heidrich, {\it Displacement interpolation using Lagrangian mass transport}, ACM Trans. Graphics, 30 (2011), 158.
[13] B. Böttcher, R. Schilling, and J. Wang, {\it Lévy Matters. III}, Lecture Notes in Math., 2099 Springer, Cham, 2013, .
[14] N. Bou-Rabee, A. Eberle, and R. Zimmer, {\it Coupling and Convergence for Hamiltonian Monte Carlo}, , 2018. · Zbl 07325608
[15] N. Bou-Rabee and J. M. Sanz-Serna, {\it Randomized Hamiltonian Monte Carlo}, Ann. Appl. Probab., 27 (2017), pp. 2159-2194, .
[16] A. Bouchard-Côté, S. J. Vollmer, and A. Doucet, {\it The bouncy particle sampler: A non-reversible rejection-free Markov chain Monte Carlo method}, J. Amer. Statist. Assoc. 113 (2018), pp. 855-867, . · Zbl 1398.60084
[17] S. Boyd and L. Vandenberghe, {\it Convex Optimization}, Cambridge University Press, UK, Cambridge, 2004, . · Zbl 1058.90049
[18] M.-F. Chen, {\it Eigenvalues, Inequalities, and Ergodic Theory}, Probab. Appl., Springer-Verlag, London, UK, 2005. · Zbl 1079.60005
[19] C. Cotar, G. Friesecke, and C. Klüppelberg, {\it Density functional theory and optimal transportation with Coulomb cost}, Comm. Pure Appl. Math., 66 (2013), pp. 548-599, . · Zbl 1266.82057
[20] P. Courrège, {\it Sur la forme intégro-différentielle des opérateurs de \({C}^∞_k\) dans \(C\) satisfaisant au principe du maximum}, Séminaire Brelot-Choquet-Deny. Théorie du potentiel, 10 (1965-1966), pp. 1-38, .
[21] R. V. Craiu and C. Lemieux, {\it Acceleration of the multiple-try Metropolis algorithm using antithetic and stratified sampling}, Stat. and Comput., 17 (2007), p. 109.
[22] R. V. Craiu and X.-L. Meng, {\it Multiprocess parallel antithetic coupling for backward and forward Markov chain Monte Carlo}, Ann. Statist., 33 (2005), pp. 661-697, . · Zbl 1068.62090
[23] G. Da Prato and J. Zabczyk, {\it Ergodicity for Infinite-Dimensional Systems}, London Math. Soc. Lecture Note Series 229, Cambridge University Press, Cambridge, UK, 1996, . · Zbl 0849.60052
[24] M. H. A. Davis, {\it Piecewise-deterministic Markov processes: A general class of nondiffusion stochastic models}, J. Roy. Statist. Soc. Ser. B, 46 (1984), pp. 353-388. · Zbl 0565.60070
[25] M. H. A. Davis, {\it Markov Models and Optimization}, Monogr. Statist. Appl. Probab. 49, Chapman & Hall, London, UK, 1993, . · Zbl 0780.60002
[26] P. Del Moral, {\it Mean Field Simulation for Monte Carlo Integration}, Monogr. Statist. Appl. Probab. 126, CRC Press, Boca Raton, FL, 2013. · Zbl 1282.65011
[27] P. Dellaportas and I. Kontoyiannis, {\it Control variates for estimation based on reversible Markov chain Monte Carlo samplers}, J. R. Stat. Soc. Ser. B. Stat. Methodol., 74 (2012), pp. 133-161. · Zbl 1411.62056
[28] A. B. Duncan, T. Lelièvre, and G. A. Pavliotis, {\it Variance reduction using nonreversible Langevin samplers}, J. Stat. Phys., 163 (2016), pp. 457-491, . · Zbl 1343.82036
[29] A. B. Duncan, N. Nüsken, and G. A. Pavliotis, {\it Using perturbed underdamped Langevin dynamics to efficiently sample from probability distributions}, J. Stat. Phys., 169 (2017), pp. 1098-1131, . · Zbl 1387.35580
[30] A. Durmus, A. Guillin, and P. Monmarché, {\it Piecewise Deterministic Markov Processes and Their Invariant Measure}, , 2018. · Zbl 1484.60083
[31] A. Eberle, {\it Stochastic Analysis}. Lecture Notes, 2015. , accessed 12/03/2018.
[32] A. Eberle, {\it Reflection couplings and contraction rates for diffusions}, Probab. Theory Related Fields, 166 (2016), pp. 851-886. · Zbl 1367.60099
[33] K.-J. Engel and R. Nagel, {\it One-Parameter Semigroups for Linear Evolution Equations}, Grad. Texts, in Math. 194, Springer-Verlag, New York, 2000.
[34] S. N. Ethier and T. G. Kurtz, {\it Markov processes}, Wiley Ser. Probab. Statist., John Wiley & Sons, New York, 1986, . · Zbl 0592.60049
[35] P. Fearnhead, J. Bierkens, M. Pollock, and G. O. Roberts, {\it Piecewise Deterministic Markov Processes for Continuous-Time Monte Carlo}, , 2016. · Zbl 1403.62148
[36] A. Frigessi, J. Gasemyr, and H. Rue, {\it Antithetic coupling of two Gibbs sampler chains}, Ann. Statist., 28 (2000), pp. 1128-1149. · Zbl 1105.65303
[37] R. Ghanem, D. Higdon, and H. Owhadi, {\it Handbook of Uncertainty Quantification}, Springer, Cham, 2017. · Zbl 1372.60001
[38] M. B. Giles, {\it Multilevel Monte Carlo methods}, Acta Numer., 24 (2015), pp. 259-328, , . · Zbl 1316.65010
[39] P. W. Glynn and S. P. Meyn, {\it A Liapounov bound for solutions of the Poisson equation}, Ann. Probab. 24 (1996), . · Zbl 0863.60063
[40] P. W. Glynn and C. Rhee, {\it Exact estimation for Markov chain equilibrium expectations}, J. Appl. Probab., 51 (2014), pp. 377-389. · Zbl 1312.65003
[41] J. B. Goodman and K. K. Lin, {\it Coupling control variates for Markov chain Monte Carlo}, J. Comput. Phys., 228 (2009), pp. 7127-7136. · Zbl 1175.65005
[42] M. Hairer and J. C. Mattingly, {\it Yet another look at Harris’ ergodic theorem for Markov chains}, in Seminar on Stochastic Analysis, Random Fields and Applications VI, Progr. Probab. 63, Birkhäuser, Basel, 2011, pp. 109-117, . · Zbl 1248.60082
[43] E. J. Hall, M. A. Katsoulakis, and L. Rey-Bellet, {\it Uncertainty quantification for generalized Langevin dynamics}, J. Chem. Phys., 145 (2016), 224108.
[44] J. Heng, A. Doucet, and Y. Pokern, {\it Gibbs Flow for Approximate Transport with Applications to Bayesian Computation}, , 2015. · Zbl 07555260
[45] J. Heng and P. E. Jacob, {\it Unbiased Hamiltonian Monte Carlo with Couplings}, , 2017. · Zbl 1435.62287
[46] C. Holmes and A. Jasra, {\it Antithetic methods for Gibbs samplers}, J. Comput. Graph. Statist., 18 (2009), pp. 401-414.
[47] C.-R. Hwang, S.-Y. Hwang-Ma, and S.-J. Sheu, {\it Accelerating diffusions}, Ann. Appl. Probab., 15 (2005), pp. 1433-1444, . · Zbl 1069.60065
[48] N. Jacob, {\it Pseudo Differential Operators and Markov Processes. Vol. I}, Imperial College Press, London, UK, 2001, . · Zbl 0987.60003
[49] V. E. Johnson, {\it Studying convergence of Markov chain Monte Carlo algorithms using coupled sample paths}, J. Amer. Statist. Assoc., 91 (1996), pp. 154-166. · Zbl 0870.62024
[50] V. E. Johnson, {\it A coupling-regeneration scheme for diagnosing convergence in Markov chain Monte Carlo algorithms}, J. Amer. Statist. Assoc., 93 (1998), pp. 238-248. · Zbl 0918.60064
[51] O. Kallenberg, {\it Foundations of Modern Probability}, 2nd ed., Springer-Verlag, New York, 2002, . · Zbl 0996.60001
[52] W. Kliemann, {\it Recurrence and invariant measures for degenerate diffusions}, Ann. Probab., 15 (1987), pp. 690-707. · Zbl 0625.60091
[53] T. Komorowski, C. Landim, and S. Olla, {\it Fluctuations in Markov processes}, Grundlehren Math. Wiss. 345, Springer, Heidelberg, 2012, . · Zbl 1396.60002
[54] D. P. Kroese, T. Taimre, and Z. I. Botev, {\it Handbook of Monte Carlo Methods}, John Wiley & Sons, New York, 2013. · Zbl 1213.65001
[55] F. Kühn, {\it Lévy Matters. VI}, Lecture Notes in Math., Springer, Cham, 2017. · Zbl 1442.60002
[56] F. Kühn, {\it Existence of (Markovian) Solutions to Martingale Problems Associated with Lévy-Type Operators}, , 2018.
[57] J. Kwak et al., {\it An antithetic coupling approach to multi-chain based CSMA scheduling algorithms}, in Proceedings of the 35th Annual IEEE International Conference on Computer Communications, IEEE, 2016, pp. 1-9.
[58] B. Leimkuhler, C. Matthews, and G. Stoltz, {\it The computation of averages from equilibrium and nonequilibrium Langevin molecular dynamics}, IMA J. Numer. Anal., 36 (2016), pp. 13-79, . · Zbl 1347.65014
[59] B. Leimkuhler, C. Matthews, and J. Weare, {\it Ensemble preconditioning for Markov chain Monte Carlo simulation}, Stat. Comput., 28 (2018), pp. 277-290, . · Zbl 1384.65004
[60] T. Lelièvre, M. Rousset, and G. Stoltz, {\it Free Energy Computations}, Imperial College Press, London, UK, 2010, .
[61] T. Lelièvre and G. Stoltz, {\it Partial differential equations and stochastic methods in molecular dynamics}, Acta Numer., 25 (2016), pp. 681-880, . · Zbl 1348.82065
[62] V. Lemaire, G. Pagès, and F. Panloup, {\it Invariant measure of duplicated diffusions and application to Richardson-Romberg extrapolation}, Ann. Inst. Henri Poincaré Probab. Stat., 51 (2015), pp. 1562-1596, . · Zbl 1329.60281
[63] T. Lindvall, {\it Lectures on the Coupling Method}, Dover Publications, Mineola, NY, 2002. · Zbl 1013.60001
[64] Q. Liu and D. Wang, {\it Stein variational gradient descent: A general purpose Bayesian inference algorithm}, in Advances In Neural Information Processing Systems 29, 2016, pp. 2378-2386.
[65] L. Lorenzi and M. Bertoldi, {\it Analytical Methods for Markov Semigroups}, Pure Appl. Math. (Boca Raton) 283, Chapman & Hall/CRC, Boca Raton, FL, 2007. · Zbl 1109.35005
[66] R. J. McCann, B. Pass, and M. Warren, {\it Rectifiability of optimal transportation plans}, Canad. J. Math., 64 (2012), pp. 924-934, . · Zbl 1248.49060
[67] M. Michel, S. C. Kapfer, and W. Krauth, {\it Generalized event-chain Monte Carlo: Constructing rejection-free global-balance algorithms from infinitesimal steps}, J. Chem. Phys., 140 (2014), p. 054116, .
[68] M. Michel and S. Sénécal, {\it Forward Event-Chain Monte Carlo: A General Rejection-Free and Irreversible Markov Chain Simulation Method}, , 2017.
[69] A. Mijatović and J. Vogrinc, {\it On the Poisson equation for Metropolis-Hastings chains}, Bernoulli, 24 (2018), pp. 2401-2428. · Zbl 1429.65010
[70] R. M. Neal, {\it Suppressing random walks in Markov chain Monte Carlo using ordered overrelaxation}, in Learning in Graphical Models, Springer, 1998, pp. 205-228. · Zbl 0920.60055
[71] R. M. Neal, {\it Circularly-Coupled Markov Chain Sampling}, , 2017.
[72] R. M. Neal, {\it MCMC using Hamiltonian dynamics}, in Handbook of Markov Chain Monte Carlo, Chapman & Hall/CRC, Boca Raton, FL, 2011, pp. 113-162. · Zbl 1229.65018
[73] R. M. Neal and R. L. Pinto, {\it Improving Markov Chain Monte Carlo Estimators by Coupling to an Approximating Chain}, Technical Report No. 0101, Department of Statistics, University of Toronto, Toronto, Canada, 2001.
[74] B. Øksendal, {\it Stochastic Differential Equations}, 6th ed., Universitext, Springer-Verlag, Berlin, 2003, .
[75] M. Ottobre, {\it Markov chain Monte Carlo and irreversibility}, Rep. Math. Phys., 77 (2016), pp. 267-292. · Zbl 1387.60116
[76] G. A. Pavliotis, {\it Stochastic Processes and Applications: Diffusion Processes, the Fokker-Planck and Langevin Equations}, Springer, Cham, 2014. · Zbl 1318.60003
[77] G. Peyré and M. Cuturi, {\it Computational optimal transport}, Found. Trends Mach. Learn., 11 (2019), pp. 355-607.
[78] R. Pinnau, C. Totzeck, O. Tse, and S. Martin, {\it A consensus-based model for global optimization and its mean-field limit}, Math. Models Methods Appl. Sci., 27 (2017), pp. 183-204. · Zbl 1388.90098
[79] J. Propp and D. Wilson, {\it Coupling from the past: a user’s guide}, in Microsurveys in Discrete Probability American Mathematical Society, Providence, RI, 1998, pp. 181-192. · Zbl 0916.65147
[80] S. Reich and C. Cotter, {\it Probabilistic Forecasting and Bayesian Data Assimilation}, Cambridge University Press, New York, 2015, . · Zbl 1314.62005
[81] C. R. Reeves and J. E. Rowe, {\it Genetic Algorithms-Principles and Perspectives}, Springer, Cham, 2004.
[82] L. Rey-Bellet and K. Spiliopoulos, {\it Improving the convergence of reversible samplers}, J. Stat. Phys., 164 (2016), pp. 472-494, . · Zbl 1348.82046
[83] F. Rigat and A. Mira, {\it Parallel hierarchical sampling: A general-purpose interacting markov chains monte carlo algorithm}, Comput. Statist. Data Anal., 56 (2012), pp. 1450-1467. · Zbl 1246.65026
[84] J. Roussel and G. Stoltz, {\it Spectral methods for Langevin dynamics and associated error estimates}, ESAIM Math. Model. Numer. Anal., 52 (2018), pp. 1051-1083. · Zbl 1404.82050
[85] M. Rousset and G. Stoltz, {\it An Interacting Particle System Approach for Molecular Dynamics}. preprint, Aug. 2005, .
[86] R. Schilling, {\it Conservativeness and extensions of Feller semigroups}, Positivity, 2 (1998), pp. 239-256, . · Zbl 0919.47033
[87] R. C. Smith, {\it Uncertainty Quantification: Theory, Implementation, and Applications}, SIAM, Philadelphia PA, 2013.
[88] T. J. Sullivan, {\it Introduction to Uncertainty Quantification}, Springer, Cham, 2015. · Zbl 1336.60002
[89] G. Teschl, {\it Mathematical Methods in Quantum Mechanics}, Grad. Stud. Math., American Mathematical Society, Providence, RI, 2014.
[90] H. Thorisson, {\it Coupling, Stationarity, and Regeneration}, Probab. Appl. (N. Y.), Springer-Verlag, New York, 2000, .
[91] P. Vanetti, A. Bouchard-Côté, G. Deligiannidis, and A. Doucet, {\it Piecewise Deterministic Markov Chain Monte Carlo}, , 2017.
[92] C. Villani, {\it Topics in Optimal Transportation}, Grad. Stud. Math. 58, American Mathematical Society, Providence, RI, 2003, . · Zbl 1106.90001
[93] C. Villani, {\it Hypocoercivity}, American Mathematical Society, Providence, RI, 2009.
[94] C. Villani, {\it Optimal Transport}, Grundlehren Math. Wiss. 338, Springer-Verlag, Berlin, 2009, . · Zbl 1156.53003
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.