  Informed Markov chain Monte Carlo (MCMC) methods have been proposed as
scalable solutions to Bayesian posterior computation on high-dimensional
discrete state spaces, but theoretical results about their convergence behavior
in general settings are lacking. In this article, we propose a class of MCMC
schemes called informed importance tempering (IIT), which combine importance
sampling and informed local proposals, and derive generally applicable spectral
gap bounds for IIT estimators. Our theory shows that IIT samplers have
remarkable scalability when the target posterior distribution concentrates on a
small set. Further, both our theory and numerical experiments demonstrate that
the informed proposal should be chosen with caution: the performance of some
proposals may be very sensitive to the shape of the target distribution. We
find that the "square-root proposal weighting" scheme tends to perform well in
most settings.
