Accelerating Nonconvex Learning via Replica Exchange Langevin Diffusion

Langevin diffusion is a powerful tool for nonconvex optimization problems, which can be used to find the global minima. However, the standard Langevin diffusion driven by a single temperature suffers from the tradeoff between “global exploration” and “local exploitation”, corresponding the high and low temperatures, respectively. In order to bridge such a gap, we propose to use the replica exchange Langevin diffusion for the purpose of nonconvex optimization, where two Langevin diffusions run simultaneously with positions swapping. We show that, compared with the standard Langevin diffusion, replica exchange enables us to approach the global minima faster through accelerating the convergence of Langevin diffusion. We also propose a novel optimization algorithm by discretizing the replica exchange Langevin diffusion.