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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Ben Goodrich Mar 29 '16 at 13:32
  • $\begingroup$ @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? $\endgroup$ – Sycorax Mar 29 '16 at 19:59
  • $\begingroup$ 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. $\endgroup$ – Ben Goodrich Mar 30 '16 at 2:30

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.

  • $\begingroup$ > "Parallelism in MCMC is hard because MCMC is inherently an iterative algorithm." I guess this hits the nail on the head then, although "serial" instead of "iterative" might be a better word here, since in my mind at least, there many iterative algorithms that are straight-forward to parallelize (like SGD), given certain assumptions (like convexity of the function). Are there relaxations like convexity that allow us to perform MCMC in parallel? $\endgroup$ – Bar Mar 29 '16 at 16:18
  • $\begingroup$ In my first draft, I had serial and changed to iterative since I was using the term iteration later. Updated the answer to use serial. $\endgroup$ – jaradniemi Mar 29 '16 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.