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:
- Local Sampling: Instead of a single global chain, the framework runs $M$ parallel chains, each potentially exploring a local region or single mode.
- 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.
- 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.
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).
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