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

arXiv: https://arxiv.org/abs/1710.00095 · HTML: https://mlsanity.com/paper/1710.00095/

## Key facts

- Cited by 116 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Sep 2017.

## Built on by (most cited first, 30 of 116)

- [Convergence for score-based generative modeling with polynomial complexity](https://mlsanity.com/paper/2206.06227/) (2022)
- [Restart Sampling for Improving Generative Processes](https://mlsanity.com/paper/2306.14878/) (2023)
- [Estimating High Order Gradients of the Data Distribution by Denoising](https://mlsanity.com/paper/2111.04726/) (2021)
- [Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo](https://mlsanity.com/paper/2202.05214/) (2022)
- [Optimal score estimation via empirical Bayes smoothing](https://mlsanity.com/paper/2402.07747/) (2024)
- [Convergence Analysis for General Probability Flow ODEs of Diffusion Models in Wasserstein Distances](https://mlsanity.com/paper/2401.17958/) (2024)
- [KALE Flow: A Relaxed KL Gradient Flow for Probabilities with Disjoint Support](https://mlsanity.com/paper/2106.08929/) (2021)
- [The Mirror Langevin Algorithm Converges with Vanishing Bias](https://mlsanity.com/paper/2109.12077/) (2021)
- [Conformalized-DeepONet: A Distribution-Free Framework for Uncertainty Quantification in Deep Operator Networks](https://mlsanity.com/paper/2402.15406/) (2024)
- [Time-independent Generalization Bounds for SGLD in Non-convex Settings](https://mlsanity.com/paper/2111.12876/) (2021)
- [QLSD: Quantised Langevin stochastic dynamics for Bayesian federated learning](https://mlsanity.com/paper/2106.00797/) (2021)
- [Improved Convergence of Score-Based Diffusion Models via Prediction-Correction](https://mlsanity.com/paper/2305.14164/) (2023)
- [Langevin Monte Carlo for Contextual Bandits](https://mlsanity.com/paper/2206.11254/) (2022)
- [Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling](https://mlsanity.com/paper/2210.08448/) (2022)
- [Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion](https://mlsanity.com/paper/2402.17886/) (2024)
- [The query complexity of sampling from strongly log-concave distributions in one dimension](https://mlsanity.com/paper/2105.14163/) (2021)
- [Interacting Particle Langevin Algorithm for Maximum Marginal Likelihood Estimation](https://mlsanity.com/paper/2303.13429/) (2023)
- [Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Condition](https://mlsanity.com/paper/2206.00508/) (2022)
- [On Convergence of Federated Averaging Langevin Dynamics](https://mlsanity.com/paper/2112.05120/) (2021)
- [Sampling from Bayesian Neural Network Posteriors with Symmetric Minibatch Splitting Langevin Dynamics](https://mlsanity.com/paper/2410.19780/) (2024)
- [When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint](https://mlsanity.com/paper/2110.01827/) (2021)
- [Low-Precision Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2206.09909/) (2022)
- [Kinetic Langevin MCMC Sampling Without Gradient Lipschitz Continuity -- the Strongly Convex Case](https://mlsanity.com/paper/2301.08039/) (2023)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [DG-LMC: A Turn-key and Scalable Synchronous Distributed MCMC Algorithm via Langevin Monte Carlo within Gibbs](https://mlsanity.com/paper/2106.06300/) (2021)
- [Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm](https://mlsanity.com/paper/2312.08823/) (2023)
- [Non-asymptotic estimates for TUSLA algorithm for non-convex learning with applications to neural networks with ReLU activation function](https://mlsanity.com/paper/2107.08649/) (2021)
- [Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited](https://mlsanity.com/paper/2306.08494/) (2023)
- [Particle-based Variational Inference with Generalized Wasserstein Gradient Flow](https://mlsanity.com/paper/2310.16516/) (2023)
- [Accelerating Approximate Thompson Sampling with Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2401.11665/) (2024)

## Abstract (arXiv)

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 provide 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.