SMC Is All You Need: Parallel Strong Scaling

In the general framework of Bayesian inference, the target distribution can only be evaluated up-to a constant of proportionality. Classical consistent Bayesian methods such as sequential Monte Carlo (SMC) and Markov chain Monte Carlo (MCMC) have unbounded time complexity requirements. We develop a fully parallel sequential Monte Carlo (pSMC) method which provably delivers parallel strong scaling, i. e. the time complexity (and per-node memory) remains bounded if the number of asynchronous processes is allowed to grow. More precisely, the pSMC has a theoretical convergence rate of MSE = O (1/NR), where N denotes the number of communicating samples in each processor and R denotes the number of processors. In particular, for suitably-large problem-dependent N, as R the method converges to infinitesimal accuracy MSE=O (²) with a fixed finite time-complexity Cost=O (1) and with no efficiency leakage, i. e. computational complexity Cost=O (^-2). A number of Bayesian inference problems are taken into consideration to compare the pSMC and MCMC methods.