Sampling via Rejection-Free Partial Neighbor Search

Abstract

The Metropolis algorithm involves producing a Markov chain to converge to a specified target density π. To improve its efficiency, we can use the Rejection-Free version of the Metropolis algorithm, which avoids the inefficiency of rejections by evaluating all neighbors. Rejection-Free can be made more efficient through parallelism hardware. However, for some specialized hardware, such as Digital Annealing Unit, the number of neighbors being considered at each step is limited. Hence, we propose an enhanced version of Rejection-Free known as Partial Neighbor Search, which only considers a portion of the neighbors. This method will be tested on several examples to demonstrate its effectiveness and advantages under different circumstances. Our method has already been used in the industry.

Keywords:

• Metropolis algorithm
• Partial Neighbor Search
• qUBO
• Rejection-Free
• Unbiased PNS

Mathematical Subject Classification:

• 60J22
• 62D05

Acknowledgments

The authors thank Fujitsu Ltd. and Fujitsu Consulting (Canada) Inc. for providing financial support. The authors thank the reviewers and editors for very careful readings and helpful comments which have greatly improved the manuscript.

Disclosure statement

No potential conflict of interest was reported by the author(s).