Stochastic Variance-Reduced Hamilton Monte Carlo Methods

2018/02/13 by Difan Zou, Pan Xu, Zou, Difan +3 · 1 citation
Computer Science · Mathematics · #Computation (stat.CO) #FOS: Computer and information sciences #Generative Adversarial Networks and Image Synthesis #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1802.04791

openalex publication_date 2018/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 ε accuracy in 2-Wasserstein distance, our algorithm achieves O(n+κ²d^1/2/ε+κ^4/3d^1/3n^2/3/ε^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.

Citations

• Stochastic Gradient Hamiltonian Monte Carlo
• Bayesian Posterior Sampling via Stochastic Gradient Fisher Scoring
• On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a\n nonasymptotic analysis
• Convergence of Langevin MCMC in KL-divergence
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Theoretical guarantees for approximate sampling from smooth and log-concave densities
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly\n Convex Composite Objectives
• Couplings and quantitative contraction rates for Langevin dynamics
• Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm

Cited by

• Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown

Related

• A New Framework for Variance-Reduced Hamiltonian Monte Carlo
• Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random steps
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly\n Logconcave Distributions
• Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo