  Yang et al. (2016) proved that the symmetric random walk Metropolis--Hastings
algorithm for Bayesian variable selection is rapidly mixing under mild
high-dimensional assumptions. We propose a novel MCMC sampler using an informed
proposal scheme, which we prove achieves a much faster mixing time that is
independent of the number of covariates, under the same assumptions. To the
best of our knowledge, this is the first high-dimensional result which
rigorously shows that the mixing rate of informed MCMC methods can be fast
enough to offset the computational cost of local posterior evaluation.
Motivated by the theoretical analysis of our sampler, we further propose a new
approach called "two-stage drift condition" to studying convergence rates of
Markov chains on general state spaces, which can be useful for obtaining tight
complexity bounds in high-dimensional settings. The practical advantages of our
algorithm are illustrated by both simulation studies and real data analysis.
