On sequential Monte Carlo, partial rejection control and approximate Bayesian computation

Gareth W. Peters, Yanan Fan, Scott A. Sisson

Abstract

This paper introduces a novel Sequential Monte Carlo (SMC) sampler variant incorporating a partial rejection control (PRC) mechanism. By treating this mechanism as a modified mutation kernel, the authors demonstrate that the sampler can significantly reduce the variance of incremental importance weights compared to standard SMC methods. The framework is particularly effective when adapted for Approximate Bayesian Computation (ABC)—a "likelihood-free" modeling environment—where it demonstrates superior performance over existing samplers by more efficiently managing computational resources.

Introduction

In Bayesian statistics, Sequential Monte Carlo (SMC) methods are essential for sampling from a sequence of probability distributions. However, these methods frequently encounter "particle depletion" (or degeneracy), where the importance weights of most particles collapse toward zero, leaving only a few particles to represent the target distribution. This leads to high-variance estimates and inefficient use of computational power.

This challenge is amplified in Approximate Bayesian Computation (ABC). ABC is used when the likelihood function is computationally intractable; instead of evaluating the likelihood, we simulate data and compare it to observations. Traditional ABC-SMC algorithms are often "leaky," wasting significant CPU time on simulations that result in zero-weight particles. This paper, published by Peters, Fan, and Sisson (2009), addresses these inefficiencies by merging SMC with Partial Rejection Control (PRC).

The SMC-PRC Framework

The core innovation of this research is the SMC Sampler PRC algorithm. The algorithm introduces a threshold-based retry mechanism to ensure that the particles being propagated are of sufficient quality.

1. Partial Rejection Control (PRC)

Unlike standard SMC, where a particle is moved and assigned a weight regardless of its value, the PRC variant sets a threshold ($c_t$). If a mutated particle's weight falls below this threshold, it is probabilistically rejected. The algorithm then retries the mutation from the previous state until a particle with a weight exceeding the threshold is generated. This prevents the sampler from wasting effort on low-probability regions of the state space.

2. Modified Mutation Kernels

A key theoretical contribution is the proof that this rejection-and-retry process is mathematically equivalent to using a modified mutation kernel ($M^*_t$). This allows the authors to maintain the rigorous convergence properties of standard SMC samplers while benefiting from the variance reduction of PRC.

3. Adaptation for ABC

The authors adapt this framework specifically for the "likelihood-free" context. By using PRC within ABC, researchers can move beyond simple 0/1 "accept/reject" steps and utilize smooth, non-parametric kernels (such as Gaussian kernels). This provides greater modeling flexibility and more accurate posterior approximations.

Theoretical Insights

The paper provides several critical theoretical results:

  • Variance Reduction: Theorem 3.1 proves that applying PRC within the SMC framework will never increase the variance of the importance weights and will almost always improve it.
  • The "AliveSMC" Connection: The authors establish a link to "AliveSMC" algorithms used in rare-event simulation. This connection proves that the number of rejection attempts required to find a viable particle is almost surely finite, ensuring the algorithm's stability.
  • Normalizing Constants: The authors address the challenge of calculating normalizing constants for the new kernels, proposing Monte Carlo estimation and specific "global" kernel choices that simplify the implementation for practical use.

Empirical Evaluation

The algorithm was tested against two primary benchmarks:

Simulated Gaussian Study

Using a controlled toy model with a Gaussian posterior, the authors benchmarked the Effective Sample Size (ESS) and weight variance. The results showed a dramatic increase in ESS as the PRC threshold increased, confirming that the quality of the particle set improved significantly compared to standard samplers.

Actuarial Case Study: Stochastic Claims Reserving

The method was applied to real-world insurance data using a "claims development triangle." This is a distribution-free problem where the goal is to predict future payouts without assuming a specific shape for the underlying noise. The PRC-ABC approach successfully recovered the estimates of classical deterministic models (like the "chain ladder" model) while providing a full posterior distribution. This allows actuaries to calculate sophisticated risk metrics, such as Value-at-Risk (VaR) and Expected Shortfall, which are unavailable in traditional models.

Conclusion and Future Work

The SMC-PRC algorithm represents a significant step forward in making likelihood-free inference more computationally viable. While the method requires more simulations per successful particle, the resulting increase in particle quality often outweighs the extra cost.

Future research directions include the automation of threshold selection ($c_t$), which currently requires manual tuning or heuristics. Additionally, while the framework supports arbitrary kernels, identifying the optimal backward kernel for high-dimensional, complex problems remains an open challenge. Despite these areas for refinement, the integration of PRC into SMC provides a robust solution for some of the most difficult problems in modern Bayesian computation.

Summary updated

Abstract

We present a sequential Monte Carlo sampler variant of the partial rejection control algorithm, and show that this variant can be considered as a sequential Monte Carlo sampler with a modified mutation kernel. We prove that the new sampler can reduce the variance of the incremental importance weights when compared with standard sequential Monte Carlo samplers. We provide a study of theoretical properties of the new algorithm, and make connections with some existing algorithms. Finally, the sampler is adapted for application under the challenging "likelihood free," approximate Bayesian computation modelling framework, where we demonstrate superior performance over existing likelihood-free samplers.
BibTeX
@article{peters2012sequential,
  author = {Gareth W. Peters and Yanan Fan and Scott A. Sisson},
  title = {{On sequential Monte Carlo, partial rejection control and approximate Bayesian computation}},
  journal = {Stat. Comput.},
  year = {2012},
  doi = {10.1007/s11222-012-9315-y},
}
Figure