EVENTS

Seminar: Lower Bounds on the Mixing Time of Adaptive MCMC Methods (Dawn Woodard)

Seminar

Department of Statistics

Thursday, 24 September 2009 at 3:30PM

Sidney Smith Hall, Room 1086

Lower Bounds on the Mixing Time of Adaptive MCMC Methods

Professor Dawn Woodard

Cornell University

We consider the convergence (``mixing'') time of some adaptive Markov chain Monte Carlo (MCMC) techniques proposed recently in the statistics literature. Although these methods produce non-Markovian, time-inhomogeneous stochastic processes, we show that bounds can be obtained using ideas of hitting time and conductance from the theory of Markov chains.

Our bounds suggest and in some cases prove that these adaptive MCMC methods are not able to provide a speed-up from slow to rapid mixing relative to their non-adaptive counterparts (although some of them may successfully optimize over a family of non-adaptive methods). We use our bounds to show slow mixing on multimodal examples: a mixture of normals and the mean-field Potts model. The methods we consider include the Adaptive Metropolis method by Haario, Saksman, and Tamminen (2001), Inter-chain Adaptation by Craiu, Rosenthal, and Yang (2009), the Equi-Energy Sampler (Kou, Zhou, and Wong 2006), and the Importance-Resampling MCMC algorithm (Atchade 2009).