Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm

By Alain Oliviero Durmus, Eric Moulines. 2015

484 citations recorded by the source corpus.

In this paper, we study a method to sample from a target distribution $\pi$ over $\mathbb{R}^d$ having a positive density with respect to the Lebesgue measure, known up to a normalisation factor. This method is based on the Euler discretization of the overdamped Langevin stochastic differential equation associated with $\pi$. For both constant and decreasing step sizes in the Euler discretization, we obtain non-asymptotic bounds for the convergence to the target distribution $\pi$ in total variation distance. A particular attention is paid to the dependency on the dimension $d$, to demonstrate the applicability of this method in the high dimensional setting. These bounds improve and extend the results of (Dalalyan 2014).

Subfields: Artificial Intelligence, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/a4df7e302f77f1fe0a1398589e7ed8fe4b61467d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient (2017, result): “, the LMC with Ozaki discretization (LMCO), needs O(p/ǫ) iterations to achieve a precision level ǫ. These results were improved and extended to the Wasserstein distance by (Durmus and Moulines, 2016; Durmus and Moulines, 2017). More precisely, they removed the condition of the warm start and proved ”
Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis (2017, background): “Durmus and Moulines (2015) reﬁned these results by establishing geometric convergence in total variation distance for convex and strongly convex objective functions.”
High-dimensional Bayesian inference via the unadjusted Langevin algorithm (2016, background): “This result improves the conclusion of [11] and 14 with respect to the precision parameter ε , which provides an upper bound of the number of iterations of order d log( d ) ( ε − 2 log 2 ( ε )).”
Quantitative Harris-type theorems for diffusions and McKean–Vlasov processes (2016, methodology): “Another possibility is to consider time discretizations as a perturbation of the diffusion process and to apply directly the contraction results for the diffusion; see [15, 18, 19] and also [23, 49, 51, 53, 55, 56].”
A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks (2019, background): “Recent results on ULA [44,56] have shown that, the required number of iterations to achieve the invariant measure often grows exponentially with the dimension p .”
Sampling from a strongly log-concave distribution with the Unadjusted Langevin Algorithm (2016, background): “Finally, we note that from the explicit expression of the bound in [8], that constant step sizes (α = 0) are again optimal.”
Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates (2019, methodology): “We first consider the stochastic gradient Langevin dynamics (SGLD) algorithm [33], then handle its full batch counterpart the (unadjusted) Langevin algorithm [9, 11], which we will refer to informally as Langevin dynamics (LD).”
Stochastic Gradient Markov Chain Monte Carlo (2019, background): “…, 2014; Dubey et al. , 2016; Baker et al. , 2019a) and theoretical developments (Teh et al. , 2016; Vollmer et al. , 2016; Dalalyan and Karagulyan, 2017; Durmus and Moulines, 2017) along with new application areas for these algorithms (Balan et al. , 2015; Gan et al. , 2015; Wang et al. , 2015).”
Bridging the gap between constant step size stochastic gradient descent and Markov chains (2017, methodology): “This method introduced by [45] combines SGD and the Euler-Maruyama discretization of the Langevin diffusion associated to a target probability measure [15, 9].”