Limit theorems for sequential MCMC methods

Axel Finke, Arnaud Doucet, Adam M. JohansenOpenReview 2021 · OpenReview

TL;DR

This paper introduces and analyzes sequential Markov Chain Monte Carlo (MCMC) methods, a class of algorithms that combine the strengths of particle filters and MCMC. The authors establish theoretical guarantees (strong law of large numbers and central limit theorem) for these methods, showing they can offer improved efficiency over standard particle filters in certain scenarios, particularly for complex state-space models.

What Problem Does This Paper Address?

Traditional Sequential Monte Carlo (SMC) methods, also known as particle filters (PFs), are widely used for approximating expectations with respect to a sequence of probability distributions. They work by maintaining a set of particles, each representing a possible state, and updating them over time. A key assumption is that particles are sampled independently at each time step. However, for some problems, especially those involving complex models or informative measurements, standard PFs can become computationally expensive or inefficient.

Sequential MCMC (MCMC-PF) methods offer an alternative by using MCMC kernels to sample particles, allowing for more flexible and potentially more efficient exploration of the state space. While empirical evidence suggests their superiority in some applications, a rigorous theoretical understanding of their convergence properties and performance compared to standard PFs has been lacking. This paper aims to fill that gap by providing theoretical guarantees for MCMC-PFs and analyzing their asymptotic variance.

Methods

The core of this work lies in establishing theoretical convergence results for MCMC-PFs. The authors develop:

  • Strong Law of Large Numbers (SLLN): This guarantees that as the number of particles increases, the estimators produced by MCMC-PFs converge to the true values.
  • Central Limit Theorem (CLT): This describes the asymptotic distribution of the estimation errors, showing they are approximately Gaussian. This is crucial for constructing confidence intervals and understanding the uncertainty in the estimates.

To achieve these results, the paper relies on:

  • Feynman-Kac models: These provide a general framework for defining the target distributions and the structure of the sequential inference problem.
  • MCMC kernels: The analysis carefully considers the properties of the MCMC kernels used for particle sampling, particularly their ergodicity and mixing properties.
  • Martingale approximations and telescoping sums: These are standard tools in the analysis of sequential Monte Carlo methods, adapted here to handle the dependencies introduced by MCMC kernels.
  • Analysis of variance decomposition: The authors break down the total variance of MCMC-PF estimators into components related to standard PFs and an additional "penalty" term arising from the autocorrelation of MCMC draws.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses toy models for illustration.

Key Insights and Ideas

  • MCMC-PFs offer a powerful alternative: By relaxing the independent sampling assumption of standard PFs, MCMC-PFs can be more efficient, especially when standard PFs struggle with complex models or informative observations.
  • Theoretical guarantees are now established: The paper provides the first rigorous SLLN and CLT for MCMC-PFs, building confidence in their use.
  • Variance trade-off: While MCMC-PFs introduce an "autocorrelation penalty" compared to standard PFs, they can still achieve lower overall asymptotic variance if they target a more efficient distribution flow. This means the benefit of targeting a better distribution can outweigh the cost of correlated samples.
  • Flexibility in kernel choice: The framework allows for various MCMC kernels (Metropolis-Hastings, Langevin, etc.), offering practitioners a wide range of options.
  • MCMC-FA-APF is broadly applicable: The paper highlights that MCMC versions of advanced particle filters like the Fully-Adapted Auxiliary Particle Filter (FA-APF), which are often difficult to implement, become much more accessible with MCMC-PFs.

Key Results

  • Proposition 2 (SLLN): For MCMC-PFs, the estimators of both normalized and unnormalized target distributions converge almost surely to their true values as the number of particles increases.
  • Proposition 3 (CLT): Under certain conditions, the estimation errors of MCMC-PFs converge in distribution to a multivariate Gaussian distribution, allowing for asymptotic variance analysis.
  • Variance Decomposition (Section 4.1): The asymptotic variance of MCMC-PF estimators is shown to be the variance of standard PF estimators multiplied by an Integrated Autocorrelation Time (IACT) factor, which quantifies the "penalty" from correlated MCMC draws.
  • Comparison with Standard PFs (Section 4.2): The paper demonstrates through examples that MCMC-PFs can achieve lower asymptotic variance than standard PFs, especially when targeting more efficient distribution flows (like FA-APF) where standard PFs are difficult to implement. Figure 1 illustrates this trade-off.
  • Example 2 (Linear Gaussian State-Space Model, Section 4.3): A numerical example shows that MCMC-FA-APF can outperform standard BPF in terms of marginal likelihood estimation, even with modest MCMC mixing properties.

Limitations and Future Work

  • Assumptions: The theoretical results rely on strong assumptions about the MCMC kernels (e.g., uniform ergodicity, Lipschitz conditions). The authors acknowledge that these assumptions are "strong and rarely hold for non-compact spaces" and that relaxing them would significantly complicate the proofs.
  • Time-uniform bounds: While the paper establishes time-uniform bounds under additional assumptions (B1-B3), these assumptions are also quite restrictive.
  • Future Work: The authors suggest that exploring weaker conditions for the MCMC kernels is a promising direction for future research. Additionally, further investigation into the practical performance of MCMC-PFs across a wider range of applications and models would be valuable. The paper also hints at the possibility of extending these results to more general settings beyond Feynman-Kac models.

Summary updated

Abstract

Sequential Monte Carlo (SMC) methods, also known as particle filters (PFs), constitute a class of algorithms used to approximate expectations with respect to a sequence of probability distributions as well as the normalising constants of those distributions. Sequential Markov chain Monte Carlo (MCMC) methods are an alternative class of techniques addressing similar problems in which particles are sampled according to an MCMC kernel rather than conditionally independently at each time step. These methods were introduced over twenty years ago by Berzuini et al. (1997). Recently, there has been a renewed interest in such algorithms as they demonstrate an empirical performance superior to that of SMC methods in some applications. We establish a strong law of large numbers and a central limit theorem for sequential MCMC methods and provide conditions under which errors can be controlled uniformly in time. In the context of state-space models, we provide conditions under which sequential MCMC methods can indeed outperform standard SMC methods in terms of asymptotic variance of the corresponding Monte Carlo estimators.
BibTeX
@misc{finke2021limit,
  author = {Axel Finke and Arnaud Doucet and Adam M. Johansen},
  title = {{Limit theorems for sequential MCMC methods}},
  year = {2021},
  url = {https://openreview.net/forum?id=7AOQOShc6G4},
  howpublished = {OpenReview},
}
Figure