A Convergence Analysis for A Class of Practical Variance-Reduction Stochastic Gradient MCMC

Abstract

Stochastic gradient Markov Chain Monte Carlo (SG-MCMC) has been developed as a flexible family of scalable Bayesian sampling algorithms. However, there has been little theoretical analysis of the impact of minibatch size to the algorithm's convergence rate. In this paper, we prove that under a limited computational budget/time, a larger minibatch size leads to a faster decrease of the mean squared error bound (thus the fastest one corresponds to using full gradients), which motivates the necessity of variance reduction in SG-MCMC. Consequently, by borrowing ideas from stochastic optimization, we propose a practical variance-reduction technique for SG-MCMC, that is efficient in both computation and storage. We develop theory to prove that our algorithm induces a faster convergence rate than standard SG-MCMC. A number of large-scale experiments, ranging from Bayesian learning of logistic regression to deep neural networks, validate the theory and demonstrate the superiority of the proposed variance-reduction SG-MCMC framework.

References in corpus (18)

• Recurrent Neural Network Regularization
• Weight Uncertainty in Neural Networks
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Pointer Sentinel Mixture Models
• Stochastic Variance Reduction for Nonconvex Optimization
• A Complete Recipe for Stochastic Gradient MCMC
• Preconditioned Stochastic Gradient Langevin Dynamics for Deep Neural Networks
• On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators
• Variance Reduction for Faster Non-Convex Optimization
• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• Stop Wasting My Gradients: Practical SVRG
• Finite-sum Composition Optimization via Variance Reduced Gradient Descent
• Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
• Stochastic Quasi-Newton Langevin Monte Carlo
• Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
• Fast Langevin based algorithm for MCMC in high dimensions
• Trading-off variance and complexity in stochastic gradient descent

Cited by in corpus (6)

• On the Theory of Variance Reduction for Stochastic Gradient Monte Carlo
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling
• On Connecting Stochastic Gradient MCMC and Differential Privacy
• Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization
• Structured Logconcave Sampling with a Restricted Gaussian Oracle