Stochastic Variance-Reduced Hamilton Monte Carlo Methods

Abstract

We propose a fast stochastic Hamilton Monte Carlo (HMC) method, for sampling from a smooth and strongly log-concave distribution. At the core of our proposed method is a variance reduction technique inspired by the recent advance in stochastic optimization. We show that, to achieve $\epsilon$ accuracy in 2-Wasserstein distance, our algorithm achieves $\tilde{O}(n+{\kappa }^2{d}^{1/2}/\epsilon +{\kappa }^{4/3}{d}^{1/3}{n}^{2/3}/{\epsilon }^{2/3})$ gradient complexity (i.e., number of component gradient evaluations), which outperforms the state-of-the-art HMC and stochastic gradient HMC methods in a wide regime. We also extend our algorithm for sampling from smooth and general log-concave distributions, and prove the corresponding gradient complexity as well. Experiments on both synthetic and real data demonstrate the superior performance of our algorithm.

arXiv comment23 pages, 3 figures, 4 tables. In ICML 2018

References in corpus (16)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Stochastic Gradient Hamiltonian Monte Carlo
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• Non-convex Finite-Sum Optimization Via SCSG Methods
• On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators
• Bayesian Posterior Sampling via Stochastic Gradient Fisher Scoring
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm
• Convergence of Langevin MCMC in KL-divergence
• A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
• Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization
• Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
• Couplings and quantitative contraction rates for Langevin dynamics
• Theoretical guarantees for approximate sampling from smooth and log-concave densities

Cited by in corpus (3)

• Modified Hamiltonian Monte Carlo for Bayesian inference
• Stochastic Gradient Hamiltonian Monte Carlo with Variance Reduction for Bayesian Inference
• Aggregated Gradient Langevin Dynamics