Parallel computations for Metropolis Markov chains with Picard maps

2025/06/11 by Grazzi, Sebastiano, Zanella, Giacomo · 3 citations
#60J22 #65C05 #Computation (stat.CO) #FOS: Computer and information sciences #Methodology (stat.ME)

paper · doi:10.48550/arxiv.2506.09762

Abstract

We develop 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 π on ℝ^d, our algorithm generates samples close to π in O(√(d)) parallel iterations with O(√(d)) processors, therefore speeding up the convergence of the corresponding sequential implementation by a factor √(d). Furthermore, a modification of our algorithm generates samples from an approximate measure π_ε 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. Our algorithms are straightforward to implement and may constitute a useful tool for practitioners seeking to sample from a prescribed distribution π using only point-wise evaluations of logπ and parallel computing.

Cited by

• Zeroth-order parallel sampling
• A Unifying Framework for Parallelizing Sequential Models with Linear Dynamical Systems
• Parallelizing MCMC Across the Sequence Length

Related

• Distributed Metropolis Sampler with Optimal Parallelism
• Zeroth-order parallel sampling
• Using parallel computation to improve Independent Metropolis--Hastings based estimation
• Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models
• Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers