Adaptive Metropolis Algorithm Using Variational Bayesian Adaptive Kalman\n Filter

Isambi Sailon Mbalawata, Simo Särkkä, Matti Vihola, Heikki HaarioarXiv 2013 · DOI · arXiv

Abstract

Markov chain Monte Carlo (MCMC) methods are powerful computational tools for analysis of complex statistical problems. However, their computational efficiency is highly dependent on the chosen proposal distribution, which is generally difficult to find. One way to solve this problem is to use adaptive MCMC algorithms which automatically tune the statistics of a proposal distribution during the MCMC run. A new adaptive MCMC algorithm, called the variational Bayesian adaptive Metropolis (VBAM) algorithm, is developed. The VBAM algorithm updates the proposal covariance matrix using the variational Bayesian adaptive Kalman filter (VB-AKF). A strong law of large numbers for the VBAM algorithm is proven. The empirical convergence results for three simulated examples and for two real data examples are also provided.

Introduction

Markov chain Monte Carlo (MCMC) is the cornerstone of modern Bayesian statistics, enabling researchers to sample from complex, high-dimensional probability distributions. However, the performance of MCMC is notoriously sensitive to the proposal distribution—the mechanism that determines the size and direction of the "jumps" the algorithm takes through the parameter space.

If the proposal's steps are too small, the chain explores the space too slowly; if they are too large, the algorithm rejects almost every move and becomes stuck. Finding the optimal covariance matrix—the "Goldilocks" proposal—usually requires manual tuning or the use of Adaptive Metropolis (AM) algorithms. While standard AM algorithms use empirical estimates of past sample covariance, this paper proposes a more sophisticated approach: treating the adaptation of the proposal distribution as a recursive filtering problem.

The VBAM Framework

The core innovation of this research is the Variational Bayesian Adaptive Metropolis (VBAM) algorithm. Instead of simply calculating a running average of sample covariance, VBAM frames the estimation of the proposal covariance as a recursive Bayesian estimation problem within a state-space model.

The Engine: VB-AKF

To drive this adaptation, the authors employ the Variational Bayesian Adaptive Kalman Filter (VB-AKF). Unlike a standard Kalman filter, which estimates a hidden state given known noise, the VB-AKF simultaneously estimates both the "state" (the mean of the samples) and the "noise covariance" (the spread or covariance of the samples).

Because the exact Bayesian solution for an unknown covariance is mathematically intractable, the algorithm utilizes Variational Inference. This technique approximates complex distributions with simpler ones by minimizing the Kullback–Leibler (KL) divergence, allowing for efficient, real-time updates to the proposal distribution.

Theoretical Convergence

Beyond its practical implementation, the authors provide a formal proof of the Strong Law of Large Numbers for the VBAM algorithm. This theoretical rigor ensures that despite the continuously changing proposal distribution, the algorithm is guaranteed to converge to the correct target distribution, satisfying the necessary conditions for diminishing adaptation and bounded convergence.

Experimental Validation

The authors evaluated VBAM against the standard AM algorithm using five distinct benchmarks, ranging from synthetic tests to real-world biological models:

  1. Simulated 1D Projection: A 2D density function projected onto one dimension to test basic accuracy and bias.
  2. 100-Dimensional Gaussian: A high-dimensional benchmark to test how the algorithm scales as the parameter space grows.
  3. 20-Dimensional "Banana" Distribution: A classic, non-linear, twisted distribution that is notoriously difficult for standard MCMC to navigate due to its curvature.
  4. Chemical Reaction Model (Himmelblau): Real-world data involving the concentrations of six chemical species over time.
  5. Bacteria Growth Model: Experimental data fitted to a Monod growth model to estimate biological parameters.

Key Insights and Results

Adaptation as Filtering

The research demonstrates that MCMC adaptation is fundamentally a signal-processing task. By viewing the sequence of MCMC samples as a "noisy signal," the entire toolbox of Kalman filtering can be applied to tune the algorithm. This allows for faster stabilization; in 100-dimensional tests, VBAM reached the optimal suboptimality factor significantly faster than standard AM, suggesting it extracts more information from early samples.

Accuracy and Consistency

In the 1D projection tests, VBAM's estimates fluctuated tightly around the true density, whereas standard AM showed systematic biases. In real-world applications, such as the chemical kinetics and bacteria growth models, VBAM successfully recovered parameter estimates (e.g., reaction rates $k_1, k_2, k_3$) consistent with literature, while simultaneously identifying complex correlations between parameters through its adaptive covariance matrix.

Limitations and Future Directions

While VBAM offers superior efficiency, it introduces a higher computational cost per iteration. The VB-AKF step involves matrix inversions, resulting in a complexity of $O(d^3)$ where $d$ is the number of dimensions, compared to $O(d^2)$ for standard AM. While often negligible compared to complex likelihood evaluations, this could become a bottleneck in extremely high-dimensional settings.

Future work may explore the use of Unscented Kalman Filters (UKF) or Particle Filters within the VBAM framework to handle even more complex, non-linear adaptation dynamics, further refining the automation of Bayesian computation.

Summary updated

Abstract

Markov chain Monte Carlo (MCMC) methods are powerful computational tools for\nanalysis of complex statistical problems. However, their computational\nefficiency is highly dependent on the chosen proposal distribution, which is\ngenerally difficult to find. One way to solve this problem is to use adaptive\nMCMC algorithms which automatically tune the statistics of a proposal\ndistribution during the MCMC run. A new adaptive MCMC algorithm, called the\nvariational Bayesian adaptive Metropolis (VBAM) algorithm, is developed. The\nVBAM algorithm updates the proposal covariance matrix using the variational\nBayesian adaptive Kalman filter (VB-AKF). A strong law of large numbers for the\nVBAM algorithm is proven. The empirical convergence results for three simulated\nexamples and for two real data examples are also provided.\n
BibTeX
@misc{mbalawata2013adaptive,
  author = {Isambi Sailon Mbalawata and Simo Särkkä and Matti Vihola and Heikki Haario},
  title = {{Adaptive Metropolis Algorithm Using Variational Bayesian Adaptive Kalman\textbackslash\{\}n Filter}},
  year = {2013},
  eprint = {1308.5875},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1308.5875},
}
Figure