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

arXiv:2402.13608v1 Announce Type: cross
Abstract: 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 …

abstract arxiv cond-mat.dis-nn convergence cops cs.lg gradient markov mcmc monte-carlo optimization sampling solver stat.ml study type