Accelerating Convergence of Replica Exchange Stochastic Gradient MCMC via Variance Reduction

Wei Deng, Qi Feng, Georgios Karagiannis, Guang Lin, Faming Liang

Abstract

Replica exchange stochastic gradient Langevin dynamics (reSGLD) has shown promise in accelerating the convergence in non-convex learning; however, an excessively large correction for avoiding biases from noisy energy estimators has limited the potential of the acceleration. To address this issue, we study the variance reduction for noisy energy estimators, which promotes much more effective swaps. Theoretically, we provide a non-asymptotic analysis on the exponential acceleration for the underlying continuous-time Markov jump process; moreover, we consider a generalized Girsanov theorem which includes the change of Poisson measure to overcome the crude discretization based on the Gr"{o}wall's inequality and yields a much tighter error in the 2-Wasserstein ($\mathcal{W}_2$) distance. Numerically, we conduct extensive experiments and obtain the state-of-the-art results in optimization and uncertainty estimates for synthetic experiments and image data.

Introduction

In Bayesian deep learning, sampling from complex, highly non-convex posterior distributions is essential for understanding model uncertainty. While Stochastic Gradient Langevin Dynamics (SGLD) is a standard tool, it frequently becomes trapped in local optima. Replica exchange (reSGLD) attempts to solve this by running multiple Markov chains at different temperatures: high-temperature chains explore the global landscape, while low-temperature chains exploit local minima. Periodically, these chains swap parameters to share information.

Replica exchange mechanism showing exploration and exploitation trajectories with chain swaps on an energy landscape.

However, a significant bottleneck exists: the swap decision requires calculating the "energy" (loss) of parameters. In deep learning, these are estimated via noisy mini-batches. To avoid bias, standard reSGLD applies a massive correction factor that often rejects nearly all swaps, causing the algorithm to revert to the slow behavior of standard SGLD.

Methods: VR-reSGLD

This paper introduces Variance-Reduced Replica Exchange Stochastic Gradient Langevin Dynamics (VR-reSGLD). The core innovation is the use of control variates to stabilize energy estimates. Every $m$ iterations, the algorithm computes an exact energy at a reference parameter, which is then used to anchor mini-batch estimates in subsequent steps.

A key design choice is applying variance reduction only to the energy estimators for swapping, not to the gradients themselves. In non-convex optimization, gradient noise is often beneficial for escaping local minima. By preserving this noise, VR-reSGLD maintains exploratory power while fixing the parallel tempering bottleneck.

Theoretical Contributions

The authors provide a non-asymptotic analysis proving that reducing energy estimator variance leads to exponential acceleration of the continuous-time Markov process. Furthermore, they derive a tighter bound on discretization error using a generalized Girsanov theorem and a change of Poisson measure. This approach bypasses the limitations of Gr"{o}wall’s inequality, yielding an error bound in the 2-Wasserstein distance that scales polynomially with time.

Experimental Results

Experiments on CIFAR-10 and CIFAR-100 demonstrate that VR-reSGLD significantly reduces energy estimator variance (up to 20x) and increases the number of successful swaps from ~5 to over 100.

Comparison of convergence rates in 2-Wasserstein distance, showing the acceleration achieved by VR-reSGLD over SGLD and standard reSGLD.

On CIFAR-100 with ResNet-56, VR-reSGHMC achieved a state-of-the-art accuracy of 80.62%. Additionally, the method excels in uncertainty quantification; when tested on out-of-distribution SVHN data, it provided superior predictive entropy and Brier scores (0.27 vs 0.33 for M-SGD), avoiding the overconfidence typical of standard neural networks.

Conclusion

VR-reSGLD effectively addresses the swap-rejection problem in replica exchange methods by targeting variance reduction at the energy estimators. This leads to faster convergence and better uncertainty estimates without sacrificing the benefits of stochastic gradients. Future work may explore memory-efficient variance reduction techniques to further reduce the computational overhead of periodic full-batch evaluations.

Summary updated

Abstract

Replica exchange stochastic gradient Langevin dynamics (reSGLD) has shown promise in accelerating the convergence in non-convex learning; however, an excessively large correction for avoiding biases from noisy energy estimators has limited the potential of the acceleration. To address this issue, we study the variance reduction for noisy energy estimators, which promotes much more effective swaps. Theoretically, we provide a non-asymptotic analysis on the exponential acceleration for the underlying continuous-time Markov jump process; moreover, we consider a generalized Girsanov theorem which includes the change of Poisson measure to overcome the crude discretization based on the Gr\"{o}wall's inequality and yields a much tighter error in the 2-Wasserstein ($\mathcal{W}_2$) distance. Numerically, we conduct extensive experiments and obtain the state-of-the-art results in optimization and uncertainty estimates for synthetic experiments and image data.
BibTeX
@inproceedings{deng2021accelerating,
  author = {Wei Deng and Qi Feng and Georgios Karagiannis and Guang Lin and Faming Liang},
  title = {{Accelerating Convergence of Replica Exchange Stochastic Gradient MCMC via Variance Reduction}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=qUrobU0UVT},
}
Figure