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

Arnak S. Dalalyan, Avetik G. Karagulyan

Abstract

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.

Introduction

Sampling from high-dimensional probability distributions is a cornerstone of modern statistics and machine learning, particularly in Bayesian inference. The Langevin Monte Carlo (LMC) algorithm is often considered the sampling equivalent of gradient descent: it moves toward the mode of a distribution while adding Gaussian noise to explore the space. However, existing theoretical guarantees for LMC often suffer from the "horizon problem," where a constant step-size requires knowing the target precision ($\epsilon$) in advance. Additionally, in large-scale applications, exact gradients are often unavailable, necessitating robust bounds for noisy or biased gradient estimates.

This paper provides "user-friendly" guarantees—mathematical bounds that are easy to interpret, hold under realistic conditions, and lead to clear practical choices for iteration counts and step-sizes.

Methodology

The authors analyze several variants of LMC, measuring error using the Wasserstein-2 ($W_2$) distance, which provides direct guarantees on the accuracy of first and second moments. The primary methods studied include:

  • Varying-step LMC: A specific schedule for decreasing step-sizes that makes the algorithm "horizon-free."
  • Noisy LMC (nLMC): An analysis of gradient evaluations with deterministic bias ($\delta$) and stochastic variance ($\sigma^2$).
  • Second-order LMC (LMCO & LMCO'): Methods leveraging the Hessian of the log-density. The authors introduce LMCO', a variant that achieves high accuracy without the computational burden of expensive matrix inversions.

The proofs rely on "synchronous coupling," comparing the discrete LMC Markov chain to a continuous-time Langevin diffusion process.

Theoretical Guarantees and Results

A major contribution of this work is the elimination of the $\log(1/\epsilon)$ error factor present in previous constant-step results. By using a varying step-size, the authors show that a precision $\epsilon$ can be reached in $O(p/\epsilon^2)$ iterations.

Comparison of iteration complexity bounds (log scale) versus dimension $p$ for different precision levels $\epsilon$.

As illustrated in the figure above, the bounds derived in Theorem 1 and Theorem 2 (the proposed results) consistently require fewer iterations than the existing DM (Dalalyan & Karagulyan) bounds across various dimensions $p$ and precision levels $\epsilon$. This visualization confirms that the new theoretical framework provides tighter, more efficient guarantees for practitioners.

Key results include:

  • Theorem 2 (Varying Step-size): Provides a bound independent of the target precision level, allowing users to run the algorithm longer for increased accuracy without restarting.
  • Theorem 4 (Noisy Gradients): Establishes that sampling error scales linearly with gradient bias and the square root of variance, offering a tighter result than previous literature.
  • Theorem 6 (Second-order LMC): Shows that LMCO' achieves a convergence rate of $O(p/\epsilon)$ iterations in ill-conditioned settings, a significant speedup over first-order methods.

Discussion and Limitations

While the paper significantly advances the state-of-the-art for strongly log-concave distributions, several challenges remain. The current bounds require the potential function to be strongly convex and, for second-order methods, the Hessian to be Lipschitz continuous. Future work may focus on establishing lower bounds for sampling—determining the absolute minimum number of iterations required—and extending these user-friendly guarantees to non-smooth or multi-modal distributions.

Summary updated

Abstract

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.
BibTeX
@misc{dalalyan2017user,
  author = {Arnak S. Dalalyan and Avetik G. Karagulyan},
  title = {{User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient}},
  year = {2017},
  eprint = {1710.00095},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1710.00095},
}
Figure