Computational Complexity of Tempering for Multimodal Distributions

Multimodal posterior distributions are possible even with very simple
statistical models.  Sampling from these distributions is challenging,
and standard Metropolis-Hastings MCMC can perform extremely poorly.
Although Metropolis-Hastings is guaranteed to eventually provide
virtually independent samples, it may have extremely long running time
in obtaining these samples.

Tempering is a general-purpose tool for improving the performance of
MCMC on multimodal distributions.  Its benefits for some distributions
have been demonstrated empirically.  However, it is not clear on which
types of distributions these techniques are most effective.  In
addition, tempering requires the specification of a temperature
"ladder," and it is not known how to choose this setting optimally.

Bounds on running time can be found for some MCMCs.  We use this
technique to compare the running time of standard Metropolis-Hastings
to tempered Metropolis-Hastings for a particular multimodal
distribution.  We show that as this distribution becomes more
multimodal the running time of tempered Metropolis-Hastings decreases
relative to standard Metropolis-Hastings.  We also show the effect of
the choice of temperature on running time for this distribution.