Rapid Mixing of Parallel MCMC

• Activity Number: 8
• Type: Invited
• Date/Time: Sunday, August 9, 2015 : 2:00 PM to 3:50 PM
• Sponsor: IMS
• Author(s): Douglas VanDerwerken* and Scott Schmidler
• Companies: Duke University and Duke University
• Keywords: Markov chain convergence ; rapid mixing ; parallel MCMC

Abstract

The mixture of two normals has served as a canonical example for testing the efficiency of Markov chain Monte Carlo samplers. MCMC efficiency is measured qualitatively in terms of rapid versus slow mixing. Very briefly, a sampler is rapidly mixing if it can sample within $\epsilon$ of the target (in total variation distance) in a number of steps that grows no faster than polynomially in the dimension $d$; slow mixing occurs when the sampling time is at least exponential in $d$. The Metropolis--Hastings ball walk can be shown to be slowly mixing under this setup, and recent work (Woodard, Schmidler, and Huber (2009); Schmidler and Woodard (2010)) has shown that several sophisticated variants---including adaptive MCMC, parallel tempering, and simulated tempering---are slowly mixing. In this talk I prove that the parallel MCMC approach of VanDerwerken and Schmidler (2013) is, with high probability, rapidly mixing on the normal mixture.