What makes parallel/distributed probabilistic inference difficult to implement?

Question

My knowledge of probabilistic inference is severely limited, so coming from a Computer Science background I'm trying to understand what makes probabilistic inference difficult to implement in a parallel/distributed manner.

For MCMC at least I know there has been a lot of work in parallel and distributed implementations with recent work from the labs of Ryan Adams (FlyMC, Predictive Prefetching) and Erik Xing. The approaches also seem to differ in whether they take an asymptotically exact approach, or an exact approach.

Probabilistic programming languages like Stan use parallelism but only across chains (i.e. run one chain per process). For example in this (admittedly old) answer by one of the core devs of Stan he mentions:

There is no explicitly parallel code in Stan or rstan but neither is there any code that prevents the binary from being executed by several processes simultaneously.

So this is my naive question: What makes it difficult to do probabilistic inference in a distributed/parallel manner?

Would it be possible to do probabilist programming in a distributed setting for example, or are there core limitations in the nature of 'universal inference engines' that make them impossible/inefficient to distribute?

Answer 1

I think your question is overly broad since it indicates "probabilistic inference", but I'll answer the question relative to Markov chain Monte Carlo (MCMC).

Parallelism in MCMC is hard because MCMC is inherently a serial algorithm. That is, given a current value $\theta^{(t)}$ in a Markov chain, an MCMC algorithm determines a set of steps to obtain the next value $\theta^{(t+1)}$. No amount of parallelism can avoid this fundamental nature of the algorithm.

Nonetheless, for some MCMC algorithms, parallelism can play a huge role in reducing the computational costs associated with the steps in each iteration of the algorithm. In the links that you included there is a huge cost with evaluating the likelihood because there is so much data, but the contribution to the likelihood for each datum (or group of data) can be evaluated independently and in parallel. As mentioned in the comments, each iteration of Stan requires evaluating a large number of derivatives that could potentially be calculated in parallel. There are other approaches, but most involve speeding up the steps within an iteration.

I mentioned that your question is too broad because there are other approaches to probabilistic inference, e.g. importance sampling, that are not iterative and therefore could be more amenable to parallelism. These approaches are generally poor for high dimensional target distributions, and these high dimensional target distributions are often the cause for computational bottlenecks that have you considering parallelism in the first place.