  The availability of data sets with large numbers of variables is rapidly
increasing. The effective application of Bayesian variable selection methods
for regression with these data sets has proved difficult since available Markov
chain Monte Carlo methods do not perform well in typical problem sizes of
interest. The current paper proposes new adaptive Markov chain Monte Carlo
algorithms to address this shortcoming. The adaptive design of these algorithms
exploits the observation that in large $p$ small $n$ settings, the majority of
the $p$ variables will be approximately uncorrelated a posteriori. The
algorithms adaptively build suitable non-local proposals that result in moves
with squared jumping distance significantly larger than standard methods. Their
performance is studied empirically in high-dimensional problems (with both
simulated and actual data) and speedups of up to 4 orders of magnitude are
observed. The proposed algorithms are easily implementable on multi-core
architectures and are well suited for parallel tempering or sequential Monte
Carlo implementations.
