Adaptive MCMC via Combining Local Samplers.

Kiárash Shaloudegi, András György

Abstract

Markov chain Monte Carlo (MCMC) methods are widely used in machine learning for Bayesian inference. One of the major problems with MCMC is the challenge of designing chains that mix fast over the whole state space, particularly in the presence of multimodality. This paper introduces KSD-MCMC-WR, an adaptive framework that uses multi-armed bandits to prioritize the best-performing local chains and a novel Rényi entropy-based weighting scheme to merge their samples into a globally accurate estimate.

Introduction

MCMC methods are the workhorse of Bayesian inference, but they face two significant hurdles. First, parameter tuning is critical; algorithms like Hamiltonian Monte Carlo (HMC) or Metropolis-Hastings require precise step sizes and proposal distributions to avoid slow exploration. Second, multimodality poses a severe challenge; in distributions with multiple peaks separated by low-probability regions, a single chain often becomes trapped in a local mode. While adaptive MCMC attempts to solve tuning issues, it often fails to address multimodality. Parallel methods like Parallel Tempering (PT) exist but can be computationally expensive and difficult to integrate with modern samplers like the No-U-Turn Sampler (NUTS).

Methodology

The authors propose a "divide and conquer" strategy called KSD-MCMC-WR (Kernel Stein Discrepancy - MCMC - with Reweighting). The algorithm consists of three main components:

  1. Local Sampling: Instead of a single global chain, the framework runs $M$ parallel chains, each potentially exploring a local region or single mode.
  2. The Racing Mechanism (KSD-UCB1): To allocate computational budget efficiently, the samplers are treated as "arms" in a multi-armed bandit problem. The Kernel Stein Discrepancy (KSD) serves as a reward signal, measuring how well a set of samples fits the target distribution without requiring the normalization constant.
  3. Rényi Entropy Weighting: To merge samples from different modes, the algorithm must estimate the relative probability mass of the regions explored. The authors utilize a graph-based estimator for Rényi entropy to derive these weights from unnormalized density values, allowing for a correct global reconstruction.

Experimental Evaluation

The method was evaluated on several challenging benchmarks:

  • Gaussian Mixtures: 2D distributions with 5 and 20 isotropic modes to test mode separation.
  • High-Dimensional Unimodal Gaussians: Testing performance overhead in up to 22 dimensions.
  • Sensor Localization: A realistic task involving determining sensor locations from noisy distance measurements, resulting in a highly multimodal posterior.

Key Results

Superiority in Multimodality

On the 20-mode Gaussian mixture, KSD-MCMC-WR significantly outperformed standard NUTS and other parallel variants. The adaptive mechanism ensures that computational resources are not wasted on chains that are stuck or poorly tuned. As shown in the figure below, the error decreases significantly as the number of samplers increases, with the proposed adaptive strategies (UCB1 and $\epsilon$-greedy) consistently outperforming uniform allocation.

Performance of different sampling strategies on a 20-mode Gaussian mixture.

Comparison with Established Methods

The proposed method consistently outperformed established parallel techniques such as Parallel Tempering (PT) and Sequential Monte Carlo (SMC). This advantage becomes more pronounced as the dimensionality of the problem increases. While PT and SMC show rising error rates in higher dimensions, KSD-MCMC-WR maintains a significantly lower mean squared error (MSE).

Comparison of KSD-MCMC-WR against Parallel Tempering (PT) and Sequential Monte Carlo (SMC) across varying dimensions.

Robustness and Efficiency

On unimodal problems, where a single NUTS chain is already optimal, the proposed method remained competitive, proving that the adaptive overhead is minimal. The algorithm also demonstrated low sensitivity to its own hyperparameters, such as the number of nearest neighbors used for clustering samplers.

Discussion and Limitations

While KSD-MCMC-WR shows great promise, it faces certain limitations. The Rényi entropy weight estimator theoretically scales poorly with very high dimensions ($d > 100$), suggesting a need for more dimension-robust estimators in future work. Additionally, calculating KSD has a computational cost of $O(n^2)$ relative to the number of samples, though this is partially mitigated by block-diagonal approximations. Finally, the current weighting scheme assumes modes are relatively well-separated; highly connected or overlapping modes may challenge the clustering heuristic.

Summary updated

Abstract

Markov chain Monte Carlo (MCMC) methods are widely used in machine learning. One of the major problems with MCMC is the question of how to design chains that mix fast over the whole state space; in...
BibTeX
@inproceedings{shaloudegi2019adaptive,
  author = {Kiárash Shaloudegi and András György},
  title = {{Adaptive MCMC via Combining Local Samplers.}},
  booktitle = {AISTATS},
  year = {2019},
  url = {https://openreview.net/forum?id=s8R0d1xgyZU},
}
Figure