Accelerating MCMC Schemes

• Activity Number: 8
• Type: Invited
• Date/Time: Sunday, August 9, 2015 : 2:00 PM to 3:50 PM
• Sponsor: IMS
• Author(s): Christian P. Robert* and Marco Banterle and Clara Grazian and Randal Douc
• Companies: Université Paris-Dauphine and Université Paris-Dauphine and Université Paris-Dauphine and Telecom SudParis
• Keywords: MCMC algorithm ; Metropolis-Hastings algorithm ; computing costs ; convergence of MCMC algorithms ; prefetching ; multimodality

Abstract

First, MCMC algorithms such as Metropolis-Hastings algorithms are slowed down by the computation of complex target distributions, for instance due to huge datasets. We present here a generic approach to reduce the computational costs of those algorithms by a simple divide-and-conquer strategy. The idea behind the acceleration is to divide the acceptance step into several parts, aiming at a major reduction in computing time which surpasses the corresponding reduction in acceptance probability. The division decomposes the target density into a product of terms and each term is sequentially compared with a uniform variate, the first rejection signalling that the proposed value is considered no further. This approach can furthermore be incorporated within a prefetching algorithm, taking advantage of parallel features. Second, MCMC algorithms are also slowed down by multimodality, which may lead to trapping zones. We introduce here a second generic approach that improves mixing by folding an arbitrary MCMC transition kernel into a compact subset in such a way that the original target is preserved, while increasing convergence speed.