标题： Metropolis马尔可夫链与Picard映射的并行计算 显示英文标题

标题： Parallel computations for Metropolis Markov chains with Picard maps

摘要： 我们开发了基于Picard映射的零阶（即无梯度）Metropolis马尔可夫链的并行算法。对于针对定义在$\mathbb{R}^d$上具有对数凹分布$\pi$的随机游走Metropolis马尔可夫链，我们的算法使用$\mathcal{O}(\sqrt{d})$个处理器可以在$\mathcal{O}(\sqrt{d})$并行迭代内生成接近$\pi$的样本，从而将相应顺序实现的收敛速度提高$\sqrt{d}$倍。 此外，我们算法的一个修改版本能够在$\mathcal{O}(1)$次并行迭代和$\mathcal{O}(d)$个处理器上生成来自近似测度$ \pi_\epsilon$的样本。 我们在高维回归问题和梯度不可用的流行病模型中，经验性地评估了所提出算法的性能。 我们的算法易于实现，并且可能成为寻求仅通过点评估$\log\pi$和并行计算来从指定分布$\pi$抽样的从业者的一个有用的工具。 显示英文摘要

摘要： 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 $\pi$ on $\mathbb{R}^d$, our algorithm generates samples close to $\pi$ in $\mathcal{O}(\sqrt{d})$ parallel iterations with $\mathcal{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 $\mathcal{O}(1)$ parallel iterations and $\mathcal{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 $\pi$ using only point-wise evaluations of $\log\pi$ and parallel computing.