Rejection-Free and Partial Neighbor Search MCMC Algorithms

The Metropolis algorithm involves producing a Markov chain to converge in distribution 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 parallel 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. Partial Neighbor Search can be applied efficiently despite the number of neighbors. Especially for continuous cases with uncountable many neighbors, Partial Neighbor Search can be applied easily and samples efficiently while Rejection-Free is not feasible, and the Metropolis algorithm is slow. Both algorithms can be used in many other circumstances as well, such as the optimization question. In combinatorial optimization, Simulated Annealing using Metropolis steps at decreasing temperatures are widely used to solve complex problems. In order to improve its efficiency, we can also use the Rejection-Free version of the Metropolis algorithm, which avoids the inefficiency of rejections by considering all the neighbors at every step. In addition, in optimization questions, Partial Neighbor Search can not only be helpful when being applied on parallel hardware, but it can also avoid the algorithm from becoming stuck in local extreme areas, and thus Partial Neighbor Search for optimization finds the optimal solution much faster than the other two algorithms. For both sampling and optimization, we demonstrate the superior performance of the Rejection-Free and Partial Neighbor Search algorithms by applying these methods to several examples, such as the Ising mode, the QUBO question, the Knapsack problem, the 3R3XOR problem, the quadratic programming, etc.

Department dc:contributor.department

Statistics

Year dc:date.issued

2023

Author dc:creator

• Chen, Sigeng

Advisor dc:contributor.advisor

• Rosenthal, Jeffrey

• MCMC
• Metropolis Algorithm
• Partial Neighbor Search
• QUBO
• Rejection-Free
• Unbiased PNS

Handle dc:identifier.uri

http://hdl.handle.net/1807/130097

OAI identifier oai:identifier

oai:utoronto.scholaris.ca:1807/130097