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:
- Finding where the modes are.
- Jumping between those modes across low-probability barriers.
- 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:
- High-Dimensional Gaussian Mixtures: Synthetic distributions with two modes in up to 200 dimensions.
- 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.
- 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