Accelerating Convergence of Replica Exchange Stochastic Gradient MCMC via Variance Reduction

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

TL;DR

This paper introduces VR-reSGLD, a method that speeds up the convergence of Bayesian neural networks by making "replica exchange" (swapping between different simulation temperatures) much more efficient. By applying variance reduction to energy estimators, the authors enable more frequent swaps between models, allowing the algorithm to escape local minima and explore complex energy landscapes faster and more accurately than previous methods.

Training deep neural networks is akin to finding the lowest point in a vast, rugged mountain range—the "energy landscape"—while blindfolded. Standard tools like Stochastic Gradient Langevin Dynamics (SGLD) use mini-batches of data to navigate, but they often get trapped in local valleys (modes).

Sample trajectories on an energy landscape showing exploration, exploitation, and swapping.

To solve this, researchers use Replica Exchange (reSGLD): running multiple simulations at different "temperatures." High-temperature simulations broadly explore the landscape, while low-temperature ones exploit deep valleys. Occasionally, these simulations swap positions. However, because mini-batches are used, the estimate of how deep a valley is becomes noisy. To avoid mathematical bias, previous methods required a massive correction factor that made these swaps incredibly rare. If swaps are rare, exploration stalls, and the algorithm's acceleration vanishes.

The VR-reSGLD Approach

The authors propose Variance-Reduced Replica Exchange SGLD (VR-reSGLD). The core innovation is applying variance reduction specifically to the energy estimators used for swapping, rather than just the gradients used for moving.

  1. Control Variates: Similar to VR-SGLD, the method periodically calculates a "full" energy estimate to "anchor" the noisy mini-batch estimates. This makes the calculated energy difference between two models much more precise.
  2. Increased Swap Rate: Because the noise is significantly lower, the required correction factor shrinks. This leads to vastly more successful swaps (jumping from ~5 to ~100 in some experiments), allowing the low-temperature chain to effectively "tunnel" between distant modes.
  3. New Theoretical Framework: Most proofs in this field rely on Gronwall’s inequality, suggesting errors grow exponentially over time. The authors instead use a generalized Girsanov theorem to prove a much tighter error bound that only grows polynomially, providing a stronger theoretical foundation for long-running simulations.

Experimental Setup

The authors evaluated their method across three distinct scales:

  • Synthetic Gaussian Mixtures: A 1D toy problem to visualize how the algorithm bridges distinct modes that standard SGLD cannot.
  • Image Classification: CIFAR-10 and CIFAR-100 using ResNet-20, 32, and 56 architectures.
  • Uncertainty Quantification: The SVHN (Street View House Numbers) dataset was used as out-of-distribution data to test if a CIFAR-10 trained model could correctly identify unfamiliar inputs.

Key Insights

  • Energy vs. Gradient: While most variance reduction research focuses on gradients to speed up optimization, this paper identifies that for sampling and exploration, the energy estimator is the true bottleneck. Reducing noise here unlocks the power of parallel tempering.
  • The Swap Bottleneck: Even if a swap is stochastically valid, a noisy estimator makes the probability of that swap exponentially small. Cleaning up the noise transforms a stuck simulation into a fluidly jumping one.

Key Results

The variance reduction mechanism reduced the variance of energy estimators by hundreds of times compared to the baseline. This directly translates into the faster exponential convergence predicted by their theory.

Graph demonstrating faster exponential convergence in Wasserstein distance for VR-reSGLD compared to SGLD and reSGLD.
  • Superior Accuracy: On CIFAR-100 with a ResNet-56, the variance-reduced version (VR-reSGHMC) achieved 80.62% accuracy, outperforming standard replica exchange (79.86%) and standard SGD with momentum (78.76%).
  • Better Uncertainty Quantification: In the SVHN test, VR-reSGLD provided the highest entropy (uncertainty) for unknown samples, proving 7% better at identifying out-of-distribution data than standard replica exchange methods.

Limitations and Future Work

  • Computational Overhead: Calculating control variates requires an occasional full pass over the data. Updating the control variate every 2 epochs increased training time by about 40%.
  • Memory Constraints: There is a trade-off between memory/compute and convergence speed. The authors suggest exploring lightweight versions (like SAGA-style estimators) in future work.
  • Hyperparameter Tuning: The update frequency and swapping intensity still require tuning, though the authors provide standard settings that performed well across their experiments.

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 convergence 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 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