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 .
The convergence rate of the Euler-Maruyama scheme ) to its stationary distribution is comparable to that of the Langevin SDE ), see @cite_20 or the discussion after Proposition 3.2 of @cite_23 . However, @cite_23 proved the exponential convergence of ) under condition that the inverse temperature parameter @math satisfies @math , where @math appears in the dissipativity condition @math of @cite_23 , [ m >0, b 0: , h ( ,z) m | |^2 -b, R ^ d . ] Let us consider the same setting with strongly convex @math and @math . The constant @math , which controls the quadratic term, plays a similar role to @math in our Assumption . In @cite_23 , @math has to be larger than @math , i.e., outside a compact set, the function @math should be sufficiently convex. From the present paper it becomes clear that for the approximation ) to work, strong convexity ( @math ) is enough. Our result is stronger and not included in @cite_23 , however, it requires global convexity. Note also that the dimension @math has different effects on convergence rate: it is @math in @cite_23 and @math in our case, see Lemma .
@cite_23 @cite_20
2590513847 1983452151
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.