On the Theory of Variance Reduction for Stochastic Gradient Monte Carlo
arXiv:1802.05431
Abstract
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.
arXiv comment37 pages; 4 figures
References in corpus (10)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- Stochastic Gradient Hamiltonian Monte Carlo
- User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
- A Complete Recipe for Stochastic Gradient MCMC
- Underdamped Langevin MCMC: A non-asymptotic analysis
- Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm
- Convergence of Langevin MCMC in KL-divergence
- The True Cost of Stochastic Gradient Langevin Dynamics
- Variance Reduced Stochastic Gradient Descent with Neighbors
- A Convergence Analysis for A Class of Practical Variance-Reduction Stochastic Gradient MCMC
Cited by in corpus (10)
- On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness
- Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
- Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
- Breaking Reversibility Accelerates Langevin Dynamics for Global Non-Convex Optimization
- Stochastic Proximal Langevin Algorithm: Potential Splitting and Nonasymptotic Rates
- On stochastic gradient Langevin dynamics with dependent data streams in the logconcave case
- Stochastic Particle-Optimization Sampling and the Non-Asymptotic Convergence Theory
- Scalable Metropolis-Hastings for Exact Bayesian Inference with Large Datasets
- Laplacian Smoothing Stochastic Gradient Markov Chain Monte Carlo
- Aggregated Gradient Langevin Dynamics