Lazy ABC

Dennis PranglearXiv 2014 · DOI · arXiv

Abstract

Approximate Bayesian computation (ABC) performs statistical inference for otherwise intractable probability models by accepting parameter proposals when corresponding simulated datasets are sufficiently close to the observations. Producing the large quantity of simulations needed requires considerable computing time. However, it is often clear before a simulation ends that it is unpromising: it is likely to produce a poor match or require excessive time. This paper proposes lazy ABC, an ABC importance sampling algorithm which saves time by sometimes abandoning such simulations. This makes ABC more scalable to applications where simulation is expensive. By using a random stopping rule and appropriate reweighting step, the target distribution is unchanged from that of standard ABC. Theory and practical methods to tune lazy ABC are presented and illustrated on a simple epidemic model example. They are also demonstrated on the computationally demanding spatial extremes application of Erhardt and Smith (2012), producing efficiency gains, in terms of effective sample size per unit CPU time, of roughly 3 times for a 20 location dataset, and 8 times for 35 locations.

Introduction

In many scientific domains—ranging from genetics to epidemiology—researchers frequently encounter "intractable" models where the likelihood function is impossible to calculate, yet simulating data from the model is straightforward. Approximate Bayesian Computation (ABC) has emerged as the primary framework for these scenarios. In a standard ABC routine, researchers propose model parameters, run a full simulation, and "accept" the parameters if the resulting data closely matches real-world observations.

However, the primary bottleneck of ABC is its computational cost. Standard ABC algorithms are "diligent": they run every simulation to completion, even when it becomes evident mid-process that the simulation is unlikely to result in an acceptance. This paper introduces Lazy ABC, a method designed to mitigate this waste by strategically abandoning unpromising simulations early, thereby focusing computational resources where they are most likely to yield results.

The Lazy ABC Methodology

Lazy ABC transforms the simulation process into a multi-stage sequence where the algorithm can "opt-out" of expensive computations. The process follows four key steps:

  1. Initial Stage: The algorithm runs a preliminary, "cheap" portion of the simulation to generate an intermediate result ($x$).
  2. The Decision: Based on this intermediate state and the proposed parameters, the algorithm calculates a continuation probability ($\alpha$).
  3. The Probabilistic Stop: A biased coin is flipped with probability $\alpha$. If the result is a "loss," the simulation is terminated immediately and assigned a weight of zero. If it is a "win," the simulation proceeds to completion.
  4. Reweighting: To ensure the final statistical estimates remain unbiased, any simulation that is completed is assigned a weight of $1/\alpha$.

This reweighting mechanism is the critical innovation of the paper. It ensures that Lazy ABC targets the exact same posterior distribution as standard ABC, meaning the "laziness" does not introduce any additional approximation error beyond what is already inherent in ABC.

Theoretical Tuning and Efficiency

Lazy ABC introduces a fundamental trade-off between variance and computation time. By randomly stopping simulations, the algorithm increases the variance of the importance weights. However, the time saved by early stopping allows for significantly more iterations within the same CPU budget.

The paper defines efficiency as the Effective Sample Size (ESS) per unit of CPU time. The author provides a theoretical framework for optimal tuning—choosing $\alpha$ to maximize this ratio. In practice, the paper suggests a "conservative" tuning approach: being slightly more likely to continue simulations than the theoretical optimum to avoid the risk of high-weight outliers that could destabilize the importance sampling approximation.

Experimental Evaluation

The algorithm was tested on two distinct benchmarks to evaluate its performance across different levels of complexity:

1. SIR Epidemic Model

A Markovian Susceptible-Infectious-Recovered (SIR) model served as a proof-of-concept. By monitoring infection counts over time, the algorithm could identify simulations that deviated too far from observed trends early in the timeline. In this setting, Lazy ABC achieved a 3.5x to 4.7x increase in efficiency over standard ABC.

2. Spatial Extremes (Schlather Process)

To test the algorithm in a high-stakes environment, the author applied it to a spatial extremes model used for rainfall data. This application involves expensive Gaussian process calculations. Using datasets with 20 and 35 geographical locations, the efficiency gains were even more pronounced:

  • 20 Locations: 3x efficiency gain.
  • 35 Locations: 8x efficiency gain.

Crucially, across all tests, the posterior means and standard deviations remained within 4% of the standard ABC results, confirming that the efficiency gains do not come at the cost of scientific accuracy.

Conclusion and Future Directions

Lazy ABC offers a robust solution for scaling likelihood-free inference to computationally demanding models. While the method requires a "pilot run" to tune the continuation probabilities and currently relies on manual selection of "decision statistics," its ability to deliver up to an 8-fold speedup without sacrificing rigor makes it a valuable tool for modern Bayesian statistics. Future work may focus on automating the selection of decision statistics and extending the "lazy" framework to Markov chain Monte Carlo (MCMC) and Sequential Monte Carlo (SMC) variants of ABC.

Summary updated

Abstract

Approximate Bayesian computation (ABC) performs statistical inference for otherwise intractable probability models by accepting parameter proposals when corresponding simulated datasets are sufficiently close to the observations. Producing the large quantity of simulations needed requires considerable computing time. However, it is often clear before a simulation ends that it is unpromising: it is likely to produce a poor match or require excessive time. This paper proposes lazy ABC, an ABC importance sampling algorithm which saves time by sometimes abandoning such simulations. This makes ABC more scalable to applications where simulation is expensive. By using a random stopping rule and appropriate reweighting step, the target distribution is unchanged from that of standard ABC. Theory and practical methods to tune lazy ABC are presented and illustrated on a simple epidemic model example. They are also demonstrated on the computationally demanding spatial extremes application of Erhardt and Smith (2012), producing efficiency gains, in terms of effective sample size per unit CPU time, of roughly 3 times for a 20 location dataset, and 8 times for 35 locations.
BibTeX
@misc{prangle2014lazy,
  author = {Dennis Prangle},
  title = {{Lazy ABC}},
  year = {2014},
  eprint = {1405.7867},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1405.7867},
}
Figure