Convergence Acceleration of Markov Chain Monte Carlo-based Gradient Descent by Deep Unfolding

The proposed solver is based on the Ohzeki method that combines Markov-chain Monte-Carlo (MCMC) and gradient descent, and its step sizes are trained by minimizing a loss function. In the training process, we propose a sampling-based gradient estimation that substitutes auto-differentiation with a variance estimation, thereby circumventing the failure of back propagation due to the non-differentiability of MCMC. The numerical results for a few COPs demonstrated that the proposed solver significantly accelerated the convergence speed compared with the original Ohzeki method. Combinatorial optimization problems (COPs) comprising discrete variables are considered hard to solve exactly in polynomial time, which relates to the well-known P vs. NP problem. Along with deterministic approximation algorithms, samplers such as Markovchain Monte-Carlo (MCMC) have been applied to COPs. However, the convergence time for obtaining reasonable approximate solutions is long.