UCPH Statistics Seminar: Sebastiano Grazzi

In this talk, I will present parallel algorithms for simulating zeroth-order (aka 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 $O(\sqrt{d})$ parallel iterations with $O(\sqrt{d})$ processors, therefore speeding up the convergence of the corresponding sequential implementation by a factor $\sqrt{d}$. Furthermore, a modification of our algorithm generates samples from an approximate measure $\pi_\epsilon$ in $O(1)$ parallel iterations and $O(d)$ processors. We empirically assess the performance of the proposed algorithms in high-dimensional regression problems and an epidemic model where the gradient is unavailable.

This is joint work with Giacomo Zanella.