  A Kernel Adaptive Metropolis-Hastings algorithm is introduced, for the
purpose of sampling from a target distribution with strongly nonlinear support.
The algorithm embeds the trajectory of the Markov chain into a reproducing
kernel Hilbert space (RKHS), such that the feature space covariance of the
samples informs the choice of proposal. The procedure is computationally
efficient and straightforward to implement, since the RKHS moves can be
integrated out analytically: our proposal distribution in the original space is
a normal distribution whose mean and covariance depend on where the current
sample lies in the support of the target distribution, and adapts to its local
covariance structure. Furthermore, the procedure requires neither gradients nor
any other higher order information about the target, making it particularly
attractive for contexts such as Pseudo-Marginal MCMC. Kernel Adaptive
Metropolis-Hastings outperforms competing fixed and adaptive samplers on
multivariate, highly nonlinear target distributions, arising in both real-world
and synthetic examples. Code may be downloaded at
https://github.com/karlnapf/kameleon-mcmc.
