Particle Metropolis adjusted Langevin algorithms for state space models

Christopher Nemeth, Paul FearnheadarXiv 2014 · DOI · arXiv

TL;DR

This paper introduces a new MCMC algorithm called Particle Metropolis Adjusted Langevin (pMALA) for analyzing complex state-space models. By leveraging information from particle filters, pMALA significantly improves sampling efficiency, reduces burn-in time, and leads to better exploration of the posterior distribution compared to existing methods.

What Problem Does This Paper Address?

Analyzing state-space models, which are common in fields like finance and engineering, often involves estimating parameters from observed data where the underlying system's state is not directly visible. Traditional Bayesian inference methods, like Markov Chain Monte Carlo (MCMC), struggle when the model's likelihood function is intractable, a frequent issue with state-space models. Particle MCMC (pMCMC) offers a solution by using particle filters to provide unbiased estimates of the likelihood. However, standard pMCMC algorithms often rely on simple random walk Metropolis proposals for parameter updates, which can be inefficient, leading to slow convergence and high autocorrelation in the samples. This paper addresses the challenge of improving the efficiency of pMCMC by developing a more sophisticated proposal mechanism.

Methods

The core innovation of this paper is the development of the Particle Metropolis Adjusted Langevin (pMALA) algorithm. This method builds upon the Particle Marginal Metropolis Hastings (PMMH) framework, which uses particle filters to estimate the likelihood. The key improvement lies in the proposal distribution used for updating model parameters. Instead of a simple random walk, pMALA utilizes an estimate of the gradient of the log posterior. This gradient information helps "steer" the proposed parameter values towards regions of higher probability in the posterior distribution, making them more likely to be accepted.

The paper leverages a computationally efficient method from Nemeth et al. (2013) to obtain these gradient estimates from the particle filter output. This approach has a computational cost linear in the number of particles, making it practical. The pMALA algorithm then integrates these gradient estimates into a Metropolis-Adjusted Langevin Algorithm (MALA) proposal. This contrasts with other approaches that might have a quadratic computational cost, making them less scalable.

Datasets

The paper evaluates the proposed pMALA algorithm on three simulated datasets representing:

  • A Linear Gaussian Model: This serves as a benchmark where exact likelihood and score estimates are available for comparison.
  • A GARCH(1,1) Model with noisy observations: This is a standard model used in financial econometrics.
  • A Stochastic Volatility Model with leverage: Another model commonly applied to financial time series data.

No new benchmark datasets were introduced; instead, standard models from the literature were used for evaluation.

Key Insights and Ideas

  • Gradient-Informed Proposals for Particle MCMC: The most significant insight is that using gradient information from the particle filter output can dramatically improve the efficiency of parameter sampling in pMCMC. This is analogous to how MALA improves standard MCMC.
  • Computational Efficiency is Key: The paper emphasizes the importance of computationally efficient methods for estimating the score (gradient). The chosen method by Nemeth et al. (2013) is crucial because it allows for more particles to be used, leading to lower variance estimates of the likelihood and score, which in turn improves MCMC mixing.
  • Reduced Burn-in Time: The gradient-informed proposals not only improve mixing but also help the MCMC sampler reach stationarity much faster, significantly reducing the "burn-in" period required before collecting reliable posterior samples.
  • Better Exploration of Posterior: The combination of improved acceptance rates and more directed proposals leads to a better exploration of the posterior distribution, reducing autocorrelation between samples and increasing the "jump distance" between successive states.

Key Results

The paper demonstrates the effectiveness of pMALA through simulation studies on the three models mentioned above. Key findings include:

  • Increased Efficiency: pMALA consistently showed improved efficiency compared to standard PMMH (using random walk Metropolis) across all models. This was measured by lower inefficiency (integrated autocorrelation time) and higher acceptance rates. For instance, in the Linear Gaussian example, pMALA achieved significantly lower inefficiency values.
  • Reduced Burn-in: Trace plots (e.g., Figure 1 for the $\mu$ parameter in the Linear Gaussian model) clearly show that pMALA reaches stationarity much faster than PMMH, often in less than 1,000 iterations compared to around 4,000 for PMMH.
  • Competitive with Existing Methods: When compared to other MALA-based particle MCMC methods (like Poyiadjis et al.'s O(N) and O(N²) algorithms), pMALA demonstrated comparable or superior efficiency, especially when considering equal computational effort. The O(N) version of pMALA was found to be more efficient, particularly as the dataset length increased.
  • Improved Squared Jump Distance: Metrics like squared jump distance (SJD) were generally higher for pMALA, indicating larger, more effective steps in the parameter space.

Limitations and Future Work

  • Theoretical Optimal Acceptance Rate: The paper notes that while empirical results are strong, theoretical results establishing the optimal acceptance rate for pMALA are still needed. Such results would aid in tuning the algorithm.
  • Second-Order MALA: The authors suggest that exploring second-order MALA proposals, which incorporate curvature information (observed information matrix), could further improve mixing. However, they acknowledge that estimating the observed information matrix can be challenging.
  • Generalizability: While tested on several models, further application to more complex state-space models would be beneficial.
  • Tuning: Like most MCMC algorithms, pMALA still requires some tuning, particularly the step-size parameter $\sigma^2$. The paper provides guidance based on empirical results and theoretical scaling.

Summary updated

Abstract

Particle MCMC is a class of algorithms that can be used to analyse state-space models. They use MCMC moves to update the parameters of the models, and particle filters to propose values for the path of the state-space model. Currently the default is to use random walk Metropolis to update the parameter values. We show that it is possible to use information from the output of the particle filter to obtain better proposal distributions for the parameters. In particular it is possible to obtain estimates of the gradient of the log posterior from each run of the particle filter, and use these estimates within a Langevin-type proposal. We propose using the recent computationally efficient approach of Nemeth et al. (2013) for obtaining such estimates. We show empirically that for a variety of state-space models this proposal is more efficient than the standard random walk Metropolis proposal in terms of: reducing autocorrelation of the posterior samples, reducing the burn-in time of the MCMC sampler and increasing the squared jump distance between posterior samples.
BibTeX
@misc{nemeth2014particle,
  author = {Christopher Nemeth and Paul Fearnhead},
  title = {{Particle Metropolis adjusted Langevin algorithms for state space models}},
  year = {2014},
  eprint = {1402.0694},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1402.0694},
}
Figure