Adaptive random neighbourhood informed Markov chain Monte Carlo for high-dimensional Bayesian variable

We introduce a framework for efficient Markov Chain Monte Carlo (MCMC) algorithms targeting discrete-valued high-dimensional distributions, such as posterior distributions in Bayesian variable selection (BVS) problems. We show that many recently introduced algorithms, such as the locally informed sampler and the Adaptively Scaled Individual adaptation sampler (ASI), can be viewed as particular cases within the framework. We then describe a novel algorithm, the Adaptive Random Neighbourhood Informed sampler (ARNI), by combining ideas from both of these existing approaches. We show using several examples of both real and simulated datasets that a computationally efficient point-wise implementation (PARNI) leads to relatively more reliable inferences on a range of variable selection problems, particularly in the very large $p$ setting.