Fast replica exchange stochastic gradient Langevin dynamics

Abstract Application of the replica exchange (i.e., parallel tempering) technique to Langevin Monte Carlo algorithms, especially stochastic gradient Langevin dynamics (SGLD), has scored great success in non-convex learning problems, but one potential limitation is the computational cost caused by running multiple chains. Upon observing that a large variance of the gradient estimator in SGLD essentially increases the temperature of the stationary distribution, we propose expediting tempering schemes for SGLD by directly estimating the bias caused by the stochastic gradient estimator. This simple idea enables us to simulate high-temperature chains at a negligible computational cost (compared to that of the low-temperature chain) while preserving the convergence to the target distribution. Our method is fundamentally different from the recently proposed m-reSGLD (multi-variance replica exchange SGLD) method in that the latter suffers from the low accuracy of the gradient estimator (e.g. the chain can fail to converge to the target) while our method benefits from it. Further, we derive a swapping rate that can be easily evaluated, providing another significant improvement over m-reSGLD. To theoretically demonstrate the advantage of our method, we develop convergence bounds in Wasserstein distances. Numerical examples for Gaussian mixture and inverse PDE models are also provided, which show that our method can converge quicker than the vanilla multi-variance replica exchange method.