# What makes parallel/distributed probabilistic inference difficult to implement?

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?

• In the case of Stan, there are technical obstacles to performing auto-differentiation in parallel within a chain. As far as I understand it, the expression tree that Stan walks through to evaluate the gradient of the log-posterior with respect to the parameters (currently) has to be handled serially to ensure that it works correctly. There is some movement, or at least interest, in parallelizing some parts of Stan that internally handle the derivatives analytically rather than relying on the auto-differentiations mechanism. The other probabilistic programming languages do not face this issue. – Ben Goodrich Mar 29 '16 at 13:32
• @BenGoodrich Welcome to CV! You're probably the most qualified CV user, if not the single most-qualified person, to comment on how Stan works, so perhaps this comment could be submitted as an answer? – Sycorax Mar 29 '16 at 19:59
• I didn't think it answered the heart of the OP's question, but I would change it to an answer if @Bar wanted me to. – Ben Goodrich Mar 30 '16 at 2:30

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.