Stochastic Gradient Langevin Dynamics (SGLD) is a combination of a Robbins-Monro type algorithm with Langevin dynamics. In this paper, the SGLD method with fixed step size @math is considered in order to sample from a logconcave target distribution @math , known up to a normalisation factor. We assume that unbiased estimates of the gradient from possibly dependent observations are available. It is shown that, for all @math , the Wasserstein- @math distance of the @math th iterate of the SGLD algorithm from @math is dominated by @math with appropriate constants @math and @math , whereas for the case of i.i.d. data the upper bound is improved to @math .
Stochastic Gradient Langevin Dynamics (SGLD) is a popular variant of Stochastic Gradient Descent, where properly scaled isotropic Gaussian noise is added to an unbiased estimate of the gradient at each iteration. This modest change allows SGLD to escape local minima and suffices to guarantee asymptotic convergence to global minimizers for sufficiently regular non-convex objectives (Gelfand and Mitter, 1991). The present work provides a nonasymptotic analysis in the context of non-convex learning problems, giving finite-time guarantees for SGLD to find approximate minimizers of both empirical and population risks. As in the asymptotic setting, our analysis relates the discrete-time SGLD Markov chain to a continuous-time diffusion process. A new tool that drives the results is the use of weighted transportation cost inequalities to quantify the rate of convergence of SGLD to a stationary distribution in the Euclidean @math -Wasserstein distance. In this paper we consider a continuous-time method of approximating a given distribution using the Langevin diusion dLtdWt 1 2 r log (Lt)dt. We ®nd conditions under this diusion converges exponentially quickly to or does not: in one dimension, these are essentially that for distributions with exponential tails of the form (x) exp (y |x| , 0< <1, exponential convergence occurs if and only if 1. We then consider conditions under which the discrete approximations to the diusion converge. We ®rst show that even when the diusion itself converges, naive discretizations need not do so. We then consider a Metropolis-adjusted' version of the algorithm, and ®nd conditions under which this also converges at an exponential rate: perhaps surprisingly, even the Metropolized version need not converge exponentially fast even if the diusion does. We brie y discuss a truncated form of the algorithm which, in practice, should avoid the diculties of the other forms.