A Repelling–Attracting Metropolis Algorithm for Multimodality

ABSTRACT

Although the Metropolis algorithm is simple to implement, it often has difficulties exploring multimodal distributions. We propose the repelling–attracting Metropolis (RAM) algorithm that maintains the simple-to-implement nature of the Metropolis algorithm, but is more likely to jump between modes. The RAM algorithm is a Metropolis-Hastings algorithm with a proposal that consists of a downhill move in density that aims to make local modes repelling, followed by an uphill move in density that aims to make local modes attracting. The downhill move is achieved via a reciprocal Metropolis ratio so that the algorithm prefers downward movement. The uphill move does the opposite using the standard Metropolis ratio which prefers upward movement. This down-up movement in density increases the probability of a proposed move to a different mode. Because the acceptance probability of the proposal involves a ratio of intractable integrals, we introduce an auxiliary variable which creates a term in the acceptance probability that cancels with the intractable ratio. Using several examples, we demonstrate the potential for the RAM algorithm to explore a multimodal distribution more efficiently than a Metropolis algorithm and with less tuning than is commonly required by tempering-based methods. Supplementary materials are available online.

KEYWORDS:

• Auxiliary variable
• Equi-energy sampler
• Forced Metropolis transition
• Markov chain Monte Carlo
• Parallel tempering
• Tempered transitions

Acknowledgments

This project was conducted under the auspices of the CHASC International Astrostatistics Center. CHASC is supported by the NSF grants DMS 1208791, 1209232, 1513484, 1513492, and 1513546. Xiao-Li Meng acknowledges partial financial support from the NSF grants given to CHASC. Hyungsuk Tak acknowledges partial support from the NSF grants DMS 1127914 and 1638521 given to SAMSI. David A. van Dyk acknowledges support from a Wolfson Research Merit Award (WM110023) provided by the British Royal Society and from a Marie-Curie Career Integration Grant (FP7-PEOPLE-2012-CIG-321865) provided by the European Commission. The authors thank the associate editor and two referees for their insightful comments and suggestions that significantly improved the presentation. We also thank Christian P. Robert, Pierre E. Jacob, Art B. Owen, and Natesh S. Pillai for very helpful discussions and Steven R. Finch for his proofreading.

Notes

1 This normalizing constant $A^{\mathrm{D}}\left(x^{\left(i\right)}\right)$ is finite if q is a proper density, that is, ∫q(x′∣x⁽ⁱ⁾)dx′ < ∞, because ${\alpha }_{ϵ}^{\mathrm{D}}(x^{\text{'}}\mid x^{\left(i\right)})$ is bounded between 0 and 1. Similarly, $A^{\mathrm{U}}\left(x^{\text{'}}\right)$ appearing later is also finite if q is proper.

2 The average number of proposals required by the forced downhill transition is 1.01 in case (a) and 1.06 in case (b), that of the uphill proposals is 4.70 in case (a) and 2.57 in case (b), and that of the downhill auxiliary variables is 1.39 in case (a) and 1.35 in case (b).

3 With a caching strategy, PT evaluates the target once for a Metropolis transition under each of five temperature levels and evaluates it twice for a swap at the end of each iteration.

4 We remove some locations and adjust observed distances to make a simpler model, yet the resulting posterior distributions have more complicated shapes.

5 We use an MH within Gibbs sampler equipped with an independent Metropolis kernel (Tierney 1994) that is invariant to π₁₁. The jumping rule for this kernel is Uniform[400, 450] with probability 0.1 and from Uniform[1050, 1178.939] otherwise. We emphasize that this algorithm would not be feasible without prior knowledge of the size and location of the two posterior modes.

6 https://xianblog.wordpress.com/2016/01/28/love-hate-metropolis-algorithm/

Additional information

Funding

National Science Foundation [DMS 1127914, DMS 1208791, DMS 1209232, DMS 1513484, DMS 1513492, DMS 1513546, DMS 1638521]; Wolfson Research Merit Award [WM110023]; Marie-Curie Career Integration [FP7-PEOPLE-2012-CIG-321865]