# A New Framework for Variance-Reduced Hamiltonian Monte Carlo

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 27 references that are in the map.
- First posted on arXiv 9 Feb 2021.

## Builds on (most cited first, 18 of 18)

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Stochastic Gradient Hamiltonian Monte Carlo](https://mlsanity.com/paper/1402.4102/) (2014)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [A Complete Recipe for Stochastic Gradient MCMC](https://mlsanity.com/paper/1506.04696/) (2015)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient](https://mlsanity.com/paper/1710.00095/) (2017)
- [Convergence of Langevin MCMC in KL-divergence](https://mlsanity.com/paper/1705.09048/) (2017)
- [Non-convex Learning via Replica Exchange Stochastic Gradient MCMC](https://mlsanity.com/paper/2008.05367/) (2020)
- [Control Variates for Stochastic Gradient MCMC](https://mlsanity.com/paper/1706.05439/) (2017)
- [On the Theory of Variance Reduction for Stochastic Gradient Monte Carlo](https://mlsanity.com/paper/1802.05431/) (2018)
- [Is There an Analog of Nesterov Acceleration for MCMC?](https://mlsanity.com/paper/1902.00996/) (2019)
- [Accelerating Nonconvex Learning via Replica Exchange Langevin Diffusion](https://mlsanity.com/paper/2007.01990/) (2020)
- [Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo](https://mlsanity.com/paper/1802.08898/) (2018)
- [Accelerating Variance-Reduced Stochastic Gradient Methods](https://mlsanity.com/paper/1910.09494/) (2019)
- [Stochastic Variance-Reduced Hamilton Monte Carlo Methods](https://mlsanity.com/paper/1802.04791/) (2018)
- [Stochastic Gradient Hamiltonian Monte Carlo with Variance Reduction for Bayesian Inference](https://mlsanity.com/paper/1803.11159/) (2018)

## Abstract (arXiv)

We propose a new framework of variance-reduced Hamiltonian Monte Carlo (HMC) methods for sampling from an L-smooth and m-strongly log-concave distribution, based on a unified formulation of biased and unbiased variance reduction methods. We study the convergence properties for HMC with gradient estimators which satisfy the Mean-Squared-Error-Bias (MSEB) property. We show that the unbiased gradient estimators, including SAGA and SVRG, based HMC methods achieve highest gradient efficiency with small batch size under high precision regime, and require tildeO(N + kappa2 d^frac12 varepsilon-1 + N^frac23 kappa^frac43 d^frac13 varepsilon^-frac23 ) gradient complexity to achieve ε-accuracy in 2-Wasserstein distance. Moreover, our HMC methods with biased gradient estimators, such as SARAH and SARGE, require tildeO(N+√N kappa2 d^frac12 varepsilon-1) gradient complexity, which has the same dependency on condition number kappa and dimension d as full gradient method, but improves the dependency of sample size N for a factor of N^frac12. Experimental results on both synthetic and real-world benchmark data show that our new framework significantly outperforms the full gradient and stochastic gradient HMC approaches. The earliest version of this paper was submitted to ICML 2020 with three weak accept but was not finally accepted.