A framework for adaptive MCMC targeting multimodal distributions

Emilia Pompe, Chris Holmes, Krzysztof ŁatuszyńskiThe Annals of Statistics 2020 · DOI

This paper, published in The Annals of Statistics, introduces a powerful new approach to one of the most persistent challenges in computational statistics: sampling from distributions with multiple "peaks" or modes.

TL;DR

The authors present JAMS (Jumping Adaptive Multimodal Sampler), a framework that splits MCMC sampling into two distinct tasks: finding the modes of a distribution and then adaptively sampling from them. By using an auxiliary variable to "remember" mode locations, the algorithm can efficiently jump between isolated high-probability regions and tune its own parameters on the fly, outperforming traditional methods like Parallel Tempering in high dimensions.

What Problem Does This Paper Address?

Standard Markov Chain Monte Carlo (MCMC) algorithms are the workhorses of Bayesian statistics, but they have a major Achilles' heel: multimodality. When a target distribution has multiple peaks separated by vast "valleys" of low probability, a standard MCMC chain gets stuck in one peak for a long time, failing to explore the others. This leads to "poor mixing" and biased results.

Existing solutions like Parallel Tempering (which uses "heated" versions of the distribution to flatten valleys) often struggle as the number of dimensions increases. The authors identify three core challenges that any robust multimodal sampler must solve:

  1. Finding where the modes are.
  2. Jumping between those modes across low-probability barriers.
  3. Sampling efficiently within each mode, accounting for their unique local shapes.

Methods

The authors introduce a new class of algorithms called Auxiliary Variable Adaptive MCMC (AV-AMCMC). The key innovation is augmenting the state space. Instead of just sampling a position $x$, the algorithm samples a pair $(x, i)$, where $i$ is an auxiliary variable representing the index of a specific mode.

The JAMS Algorithm:

  • Mode Finding (Burn-in): Before the main run, the algorithm uses optimization techniques (like the BFGS algorithm) to locate local maxima and estimate their local curvature (Hessian matrices).
  • Augmented Target: It defines a new target distribution $\tilde{\pi}$ on the augmented space. This distribution is designed so that the marginal distribution of $x$ is exactly the original target $\pi$, but the auxiliary variable $i$ helps the chain stay "assigned" to a specific region.
  • Two-Type Moves:
    • Local Moves: Standard Random Walk Metropolis steps that explore the current mode.
  • Jump Moves: Proposals to switch to a different mode index $k$. The authors propose "deterministic jumps" that use the estimated local geometry to map a point in one mode to a corresponding point in another, maintaining high acceptance rates.
  • Adaptivity: As the chain runs, it continuously updates its estimates of mode weights, covariance matrices, and jump probabilities.

Datasets

The framework was evaluated on three challenging scenarios:

  1. High-Dimensional Gaussian Mixtures: Synthetic distributions with two modes in up to 200 dimensions.
  2. Non-Elliptical Mixtures: A complex mixture of 15 $t$-distributions and 5 "banana-shaped" distributions, testing the algorithm's ability to handle non-standard geometries.
  3. Sensor Network Localisation: A real-world Bayesian inference problem where the locations of sensors must be determined based on noisy distance measurements, a problem known for its inherent multimodality and non-identifiability.

Key Insights and Ideas

  • Memory via Augmentation: Unlike tempering methods that must "re-discover" modes constantly, JAMS uses the auxiliary variable to remember where the modes are. This makes it much harder for the chain to "lose" a mode once found.
  • Geometry-Aware Jumps: The "deterministic jump" is a standout idea. By using the covariance structure of the modes, the algorithm doesn't just jump to a random spot in a new mode; it jumps to a mathematically "equivalent" spot, which significantly boosts the probability of the jump being accepted.
  • Theoretical Rigor: The authors don't just provide a heuristic; they prove general ergodicity results for the entire AV-AMCMC class. This provides a mathematical guarantee that the algorithm will eventually converge to the correct distribution, even as the target itself is being modified by the adaptive parameters.

Key Results

  • Superior Scaling: In the 200-dimensional Gaussian mixture test, JAMS maintained an acceptance rate for jumps between 0.64 and 0.97. In contrast, standard Adaptive Parallel Tempering (APT) struggled significantly to mix between modes in high dimensions.
  • Accuracy: On the "banana" distribution test, JAMS accurately captured the complex, non-linear shapes of the modes, whereas APT often failed to identify or represent all modes correctly within the same computational budget.
  • Efficiency: In the sensor localization problem, JAMS was roughly twice as computationally efficient as APT while providing a much more stable representation of the posterior distribution.

Limitations and Future Work

  • The Optimization Bottleneck: The algorithm's success relies heavily on the initial mode-finding step. If the optimization (BFGS) fails to find a mode during burn-in, JAMS essentially reverts to a standard sampler for that region.
  • Missed Modes: While JAMS "remembers" modes it has found, it doesn't have a specific mechanism to "scout" for entirely unknown modes during the main sampling phase (though local moves may eventually stumble upon them).
  • Future Directions: The authors suggest exploring more sophisticated local samplers (like HMC or MALA) within the JAMS framework and developing better strategies for sampling starting points for the initial optimization phase to ensure no modes are missed.

Summary updated

Abstract

We propose a new Monte Carlo method for sampling from multimodal distributions. The idea of this technique is based on splitting the task into two: finding the modes of a target distribution $\pi$ and sampling, given the knowledge of the locations of the modes. The sampling algorithm relies on steps of two types: local ones, preserving the mode; and jumps to regions associated with different modes. Besides, the method learns the optimal parameters of the algorithm, while it runs, without requiring user intervention. Our technique should be considered as a flexible framework, in which the design of moves can follow various strategies known from the broad MCMC literature. In order to design an adaptive scheme that facilitates both local and jump moves, we introduce an auxiliary variable representing each mode, and we define a new target distribution $\tilde{\pi}$ on an augmented state space $\mathcal{X}\times\mathcal{I}$, where $\mathcal{X}$ is the original state space of $\pi$ and $\mathcal{I}$ is the set of the modes. As the algorithm runs and updates its parameters, the target distribution $\tilde{\pi}$ also keeps being modified. This motivates a new class of algorithms, Auxiliary Variable Adaptive MCMC. We prove general ergodic results for the whole class before specialising to the case of our algorithm.
BibTeX
@article{pompe2020framework,
  author = {Emilia Pompe and Chris Holmes and Krzysztof Łatuszyński},
  title = {{A framework for adaptive MCMC targeting multimodal distributions}},
  journal = {The Annals of Statistics},
  year = {2020},
  doi = {10.1214/19-aos1916},
}
Figure