User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient

By Arnak S. Dalalyan, Avetik G. Karagulyan. Stochastic Processes and their Applications, 2017

338 citations recorded by the source corpus.

In this paper, we study the problem of sampling from a given probability density function that is known to be smooth and strongly log-concave. We analyze several methods of approximate sampling based on discretizations of the (highly overdamped) Langevin diffusion and establish guarantees on its error measured in the Wasserstein-2 distance. Our guarantees improve or extend the state-of-the-art results in three directions. First, we provide an upper bound on the error of the first-order Langevin Monte Carlo (LMC) algorithm with optimized varying step-size. This result has the advantage of being horizon free (we do not need to know in advance the target precision) and to improve by a logarithmic factor the corresponding result for the constant step-size. Second, we study the case where accurate evaluations of the gradient of the log-density are unavailable, but one can have access to approximations of the aforementioned gradient. In such a situation, we consider both deterministic and stochastic approximations of the gradient and provide an upper bound on the sampling error of the first-order LMC that quantifies the impact of the gradient evaluation inaccuracies. Third, we establish upper bounds for two versions of the second-order LMC, which leverage the Hessian of the log-density. We nonasymptotic guarantees on the sampling error of these second-order LMCs. These guarantees reveal that the second-order LMC algorithms improve on the first-order LMC in ill-conditioned settings.

Subfields: Radiology, Nuclear Medicine and Imaging, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/0c2c11db8a43964e139c65b23e02af31deb81be8

How researchers see this paper

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

In Radiology, Nuclear Medicine and Imaging

In Statistics and Probability

Citations in the corpus

Underdamped Langevin MCMC: A non-asymptotic analysis (2017, background): “Recently [6, 7] also analyzed convergence of overdamped Langevin MCMC with stochastic gradient updates.”
Stochastic Gradient Markov Chain Monte Carlo (2019, methodology): “There are a series of results for both ULA and SGLD in the literature (Dalalyan, 2017; Dalalyan and Karagulyan, 2017; Durmus and Moulines, 2017; Chatterji et al. , 2018; Brosse et al. , 2018).”
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].”
Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices (2019, background): “When ⌫ is strongly logconcave and smooth, it is known how to control the bias and prove a convergence guarantee on KL divergence along ULA [17, 21, 22, 24].”
Computational Optimal Transport (2018, methodology): “The convergence of these schemes (so-called Langevin Monte Carlo) to the stationary distribution can in turn be quantified in terms of Wasserstein distance; see, for instance, [Dalalyan and Karagulyan, 2017].”