This is an important arXival by Alain Durmus and Eric Moulines. The title is slightly optimized for effect, as the paper actually contains non-asymptotic and asymptotic analysis.

The basic theme of the paper is in getting upper bounds on total variation (and more general distribution distances) between an uncorrected discretized Langevin diffusion wrt some target and itself. The discretization used is the common scheme with the scary name Euler-Maruyama:

Under a Foster-Lyapunov condition,  is a Markov kernel that admits a unique stationary distribution that is close to the desired in total variation distance and gets closer when decreases.

Now in the non-asymptotic case with fixed , the authors provide bounds that explicitly depend on dimensionality of the support of the target, the number of samples drawn and the chosen step size . Unfortunately, these bounds contain some unknowns as well, such as the Lipschitz constant of the gradient of the logpdf and some suprema that I am unsure how to get explicitly.

Durmus and Moulines particularly take a look at scaling with dimension under increasingly strong conditions on , getting exponential (in dimension) constants for the convergence when  is superexponential outside a ball. Better convergence can be achieved when assuming  to be log-concave or strongly log-concave. This is not surprising, nevertheless the theoretical importance of the results is clear from the fact that together with Arnak Dalalyan this is the first time that results are given for the ULA after the Roberts & Tweedie papers from 1996.

As a practitioner, I would have wished for very explicit guidance in picking   or the series . But hopefully with Alains paper as a foundation that can be the next step. As a non-mathematician, I had some problems in following the paper and at some point I completely lost it. This surely is in part due to the quite involved content. However, one might still manage to give intuition even in this case, as Sam Livingstones recent paper on HMC shows. I hope Alain goes over it again with readability and presentation in mind so that it will get the attention it deserves. Yet another task for something that already took a lot of work…

(photo: the Lipschitz Grill diner in Berlin – I don’t
know about their food, but the name is remarkable)