# On the Theory of Variance Reduction for Stochastic Gradient Monte Carlo

arXiv: https://arxiv.org/abs/1802.05431 · HTML: https://mlsanity.com/paper/1802.05431/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2018.

## Built on by (most cited first, 19 of 19)

- [Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo](https://mlsanity.com/paper/2202.05214/) (2022)
- [Fed-CBS: A Heterogeneity-Aware Client Sampling Mechanism for Federated Learning via Class-Imbalance Reduction](https://mlsanity.com/paper/2209.15245/) (2022)
- [Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization](https://mlsanity.com/paper/2203.16217/) (2022)
- [Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Condition](https://mlsanity.com/paper/2206.00508/) (2022)
- [Sampling from Bayesian Neural Network Posteriors with Symmetric Minibatch Splitting Langevin Dynamics](https://mlsanity.com/paper/2410.19780/) (2024)
- [When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint](https://mlsanity.com/paper/2110.01827/) (2021)
- [Balance is Essence: Accelerating Sparse Training via Adaptive Gradient Correction](https://mlsanity.com/paper/2301.03573/) (2023)
- [ELF: Federated Langevin Algorithms with Primal, Dual and Bidirectional Compression](https://mlsanity.com/paper/2303.04622/) (2023)
- [Federated Averaging Langevin Dynamics: Toward a unified theory and new algorithms](https://mlsanity.com/paper/2211.00100/) (2022)
- [Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk](https://mlsanity.com/paper/2410.05700/) (2024)
- [Random Reshuffling for Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2501.16055/) (2025)
- [Quantum Speedups for Sampling and Non-convex Optimization with Stochastic Oracles](https://mlsanity.com/paper/2504.03626/) (2025)
- [Improved Guarantees for Langevin Monte Carlo with Average Smoothness](https://mlsanity.com/paper/2605.31413/) (2026)
- [Constrained Ensemble Langevin Monte Carlo](https://mlsanity.com/paper/2102.04279/) (2021)
- [On the SAGA algorithm with decreasing step](https://mlsanity.com/paper/2410.03760/) (2024)
- [A New Framework for Variance-Reduced Hamiltonian Monte Carlo](https://mlsanity.com/paper/2102.04613/) (2021)
- [Preferential Subsampling for Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2210.16189/) (2022)
- [Continuous-time Riemannian SGD and SVRG Flows on Wasserstein Probabilistic Space](https://mlsanity.com/paper/2401.13530/) (2024)
- [Scalable Monte Carlo for Bayesian Learning](https://mlsanity.com/paper/2407.12751/) (2024)

## Abstract (arXiv)

We provide convergence guarantees in Wasserstein distance for a variety of variance-reduction methods: SAGA Langevin diffusion, SVRG Langevin diffusion and control-variate underdamped Langevin diffusion. We analyze these methods under a uniform set of assumptions on the log-posterior distribution, assuming it to be smooth, strongly convex and Hessian Lipschitz. This is achieved by a new proof technique combining ideas from finite-sum optimization and the analysis of sampling methods. Our sharp theoretical bounds allow us to identify regimes of interest where each method performs better than the others. Our theory is verified with experiments on real-world and synthetic datasets.