Convergence rate of multiple-try Metropolis independent sampler

The multiple-try Metropolis method is an interesting extension of the classical Metropolis-Hastings algorithm. However, theoretical understanding about its usefulness and convergence behavior is still lacking. We here derive the exact convergence rate for the multiple-try Metropolis Independent sampler (MTM-IS) via an explicit eigen analysis. As a by-product, we prove that an naive application of the MTM-IS is less efficient than using the simpler approach of thinned independent Metropolis-Hastings method at the same computational cost. We further explore more variants and find it possible to design more efficient algorithms by applying MTM to part of the target distribution or creating correlated multiple trials.

Automated summary

The multiple-try Metropolis method is an extension of the classical Metropolis-Hastings algorithm, but lacks theoretical understanding about usefulness and convergence behavior. We derive the exact convergence rate for the multiple-try Metropolis Independent sampler (MTM-IS) through explicit eigen analysis. We prove that a naive application of MTM-IS is less efficient than using the simpler approach of thinned independent Metropolis-Hastings method at the same computational cost and explore more variants.