Parallel computations for Metropolis Markov chains with Picard maps

Summary We develop parallel algorithms for simulating zeroth-order, also known as gradient-free, Metropolis Markov chains based on the Picard map. For random-walk Metropolis Markov chains targeting log-concave distributions $ \pi $ on $ \mathbb{R}^{d} $, our algorithm generates samples close to $ \pi $ in $ \mathcal{O}(\surd{d}) $ parallel iterations using $ \mathcal{O}(\surd{d}) $ processors, thereby speeding up the convergence of the corresponding sequential implementation by a factor $ \surd{d} $. Furthermore, a modification of our algorithm generates samples from an approximate measure $ \pi_{r} $ in $ \mathcal{O}(1) $ parallel iterations and $ \mathcal{O}(d) $ processors. We empirically assess the performance of the proposed algorithms in high-dimensional regression problems, an epidemic model where the gradient is unavailable and a real-word application in precision medicine. Our algorithms are straightforward to implement and may constitute a useful tool for practitioners seeking to sample from a prescribed distribution $ \pi $ using only pointwise evaluations of $ \log\pi $ and parallel computing.