Theoretical guarantees for approximate sampling from smooth and log‐concave densities

By Arnak S. Dalalyan. 2014

600 citations recorded by the source corpus.

Sampling from various kinds of distribution is an issue of paramount importance in statistics since it is often the key ingredient for constructing estimators, test procedures or confidence intervals. In many situations, exact sampling from a given distribution is impossible or computationally expensive and, therefore, one needs to resort to approximate sampling strategies. However, there is no well‐developed theory providing meaningful non‐asymptotic guarantees for the approximate sampling procedures, especially in high dimensional problems. The paper makes some progress in this direction by considering the problem of sampling from a distribution having a smooth and log‐concave density defined on Rp , for some integer p>0. We establish non‐asymptotic bounds for the error of approximating the target distribution by the distribution obtained by the Langevin Monte Carlo method and its variants. We illustrate the effectiveness of the established guarantees with various experiments. Underlying our analysis are insights from the theory of continuous time diffusion processes, which may be of interest beyond the framework of log‐concave densities that are considered in the present work.

Subfields: Artificial Intelligence, Statistics and Probability

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

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

On Last-Layer Algorithms for Classification: Decoupling Representation from Uncertainty Estimation (2020, background): “In this setting, convergence properties of SGLD have been studied [Dal17, DK17] and its behaviour has been shown to be close to SGD [NDH + 17, BDM18].”
Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints (2017, methodology): “The techniques are closely related to the continuous-time interpolation and KL calculation based on Girsanov theorem in (Dalalyan, 2017; Raginsky et al., 2017).”
High-dimensional Bayesian inference via the unadjusted Langevin algorithm (2016, result): “tion π and provides explicit convergence bounds. A particular attention is paid 2 to the dependency of the proposed bounds on the dimension. These results complete and improve the results obtained by [10] and [11]. The paper is organized as follows. In Section 2, we study the convergence in the Wass”
SVGD as a kernelized Wasserstein gradient flow of the chi-squared divergence (2020, unknown): “The Unadjusted Langevin Algorithm (ULA) [Dal17b,DM17] is the most common discretization of the Wasserstein gradient ﬂow for the KL divergence, but it is unclear whether it is the most eﬀective one.”
Stochastic Gradient Markov Chain Monte Carlo (2019, background): “There are a series of results for both ULA and SGLD in the literature (Dalalyan 2017; Durmus and Moulines 2017; Brosse, Durmus, and Moulines 2018; Chatterji et al. 2018; Dalalyan and Karagulyan 2019).”
Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis (2017, methodology): “We ﬁrst upper-bound the relative entropy D µ z ,k ν z ,kη ) via a change-of-measure argument following Dalalyan and Tsybakov (2012) (see also Dalalyan (2016)), except that we also have to deal with the error introduced by the stochastic gradient oracle.”
Underdamped Langevin MCMC: A non-asymptotic analysis (2017, background): “[5] obtained results similar to those in [3] when the error is measured by KL-divergence.”
A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics (2017, methodology): “Recent works focus on bounding the mixing time (i.e. the time for converging to µ ) of LMC and SGLD. Bubeck et al. [10], Dalalyan [12] and Bonis [8] prove that on convex functions, LMC converges to the stationary distribution in polynomial time.”
Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm (2015, methodology): “Our results complete and extend the recent works by [13] and [12].”
Bridging the gap between constant step size stochastic gradient descent and Markov chains (2017, methodology): “This method introduced by [61] combines SGD and the Euler-Maruyama discretization of the Langevin diffusion associated to a target probability measure [14, 20].”
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].”
Log-concave sampling: Metropolis-Hastings algorithms are fast! (2018, methodology): “In order to construct Π̃, we use a scheme previously suggested by Dalalyan [11].”
Quantitative Central Limit Theorems for Discrete Stochastic Processes (2019, background): “Authors such as Dalalyan (2017) and Durmus and Moulines (2016) were able to prove quantitative convergence results for Langevin MCMC by bounding its discretization error from the Langevin SDE.”