Reducing Complexity of Pseudo-Marginal Sequential Monte Carlo via Hierarchical Tempering

The Bayesian approach to inverse problems provides a powerful framework for inferring unknown parameters from noisy observations. Among the computationally most challenging statistical inference problems are problems with intractable likelihoods, especially if no unbiased likelihood estimator is available. We focus on a class of such problems, where a biased likelihood estimator is obtained through a stochastic approximation of a forward map (stochastic solver). Obtaining an empirical posterior approximation in applications is very expensive due to the repeated stochastic solver evaluations required by standard sampling methods. To address this computational bottleneck, we develop a novel algorithm based on a density-tempered marginalized Sequential Monte Carlo (SMC) sampler. Our approach (hierarchical SMC) accelerates inference by leveraging a hierarchy of stochastic solvers with increasing accuracy both along the tempering sequence and within mutation stages of the SMC sampler. We establish, under additional assumptions, that the asymptotic speedup is proportional to the number of tempering stages $T$. We demonstrate computational gains on several examples, including a nonlinear, high-contrast inverse problem arising in photoacoustic medical imaging. On this problem, we demonstrate a speedup by a factor of 14.3, reducing the inference wall-clock time from about 4.6 days to 7.7 hours on an NVIDIA A40 GPU.