The True Cost of Stochastic Gradient Langevin Dynamics

Abstract

The problem of posterior inference is central to Bayesian statistics and a wealth of Markov Chain Monte Carlo (MCMC) methods have been proposed to obtain asymptotically correct samples from the posterior. As datasets in applications grow larger and larger, scalability has emerged as a central problem for MCMC methods. Stochastic Gradient Langevin Dynamics (SGLD) and related stochastic gradient Markov Chain Monte Carlo methods offer scalability by using stochastic gradients in each step of the simulated dynamics. While these methods are asymptotically unbiased if the stepsizes are reduced in an appropriate fashion, in practice constant stepsizes are used. This introduces a bias that is often ignored. In this paper we study the mean squared error of Lipschitz functionals in strongly log- concave models with i.i.d. data of growing data set size and show that, given a batchsize, to control the bias of SGLD the stepsize has to be chosen so small that the computational cost of reaching a target accuracy is roughly the same for all batchsizes. Using a control variate approach, the cost can be reduced dramatically. The analysis is performed by considering the algorithms as noisy discretisations of the Langevin SDE which correspond to the Euler method if the full data set is used. An important observation is that the 1scale of the step size is determined by the stability criterion if the accuracy is required for consistent credible intervals. Experimental results confirm our theoretical findings.

arXiv comment6 Figures

References in corpus (3)

• Stochastic Gradient Hamiltonian Monte Carlo
• A note on tamed Euler approximations
• Preconditioned Stochastic Gradient Langevin Dynamics for Deep Neural Networks

Cited by in corpus (18)

• On the Random Batch Method for second order interacting particle systems
• Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
• On the Theory of Variance Reduction for Stochastic Gradient Monte Carlo
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
• On Last-Layer Algorithms for Classification: Decoupling Representation from Uncertainty Estimation
• Random batch methods (RBM) for interacting particle systems
• Uniform in time estimates for the weak error of the Euler method for SDEs and a Pathwise Approach to Derivative Estimates for Diffusion Semigroups
• Langevin Markov Chain Monte Carlo with stochastic gradients
• No Free Lunch for Approximate MCMC
• Federated Stochastic Gradient Langevin Dynamics
• Online Sampling from Log-Concave Distributions
• Stochastic Gradient Langevin Dynamics Algorithms with Adaptive Drifts
• Structured Logconcave Sampling with a Restricted Gaussian Oracle
• sgmcmc: An R Package for Stochastic Gradient Markov Chain Monte Carlo
• Perturbation Analysis of Markov Chain Monte Carlo for Graphical Models
• Variational Bayes Neural Network: Posterior Consistency, Classification Accuracy and Computational Challenges
• Variance reduction for dependent sequences with applications to Stochastic Gradient MCMC
• Aggregated Gradient Langevin Dynamics