Convergence Acceleration of Markov Chain Monte Carlo-based Gradient Descent by Deep Unfolding
This work addresses convergence issues in combinatorial optimization for researchers and practitioners, though it is incremental as it builds on the existing Ohzeki method.
The study tackled the slow convergence of MCMC-based gradient descent for combinatorial optimization by proposing a deep unfolding solver with trainable step sizes, achieving significant acceleration in convergence speed compared to the original method.
This study proposes a trainable sampling-based solver for combinatorial optimization problems (COPs) using a deep-learning technique called 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.