Bounding the error of discretized Langevin algorithms for non-strongly log-concave targets

Abstract

In this paper, we provide non-asymptotic upper bounds on the error of sampling from a target density using three schemes of discretized Langevin diffusions. The first scheme is the Langevin Monte Carlo (LMC) algorithm, the Euler discretization of the Langevin diffusion. The second and the third schemes are, respectively, the kinetic Langevin Monte Carlo (KLMC) for differentiable potentials and the kinetic Langevin Monte Carlo for twice-differentiable potentials (KLMC2). The main focus is on the target densities that are smooth and log-concave on ${\mathbb{R}}^p$, but not necessarily strongly log-concave. Bounds on the computational complexity are obtained under two types of smoothness assumption: the potential has a Lipschitz-continuous gradient and the potential has a Lipschitz-continuous Hessian matrix. The error of sampling is measured by Wasserstein-$q$ distances. We advocate for the use of a new dimension-adapted scaling in the definition of the computational complexity, when Wasserstein-$q$ distances are considered. The obtained results show that the number of iterations to achieve a scaled-error smaller than a prescribed value depends only polynomially in the dimension.

References in corpus (13)

• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• Quantitative bounds on convergence of time-inhomogeneous Markov chains
• Sparse Regression Learning by Aggregation and Langevin Monte-Carlo
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm
• Convergence of Langevin MCMC in KL-divergence
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• Is There an Analog of Nesterov Acceleration for MCMC?
• Langevin Monte Carlo and JKO splitting
• Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
• Nonconvex sampling with the Metropolis-adjusted Langevin algorithm

Cited by in corpus (7)

• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm
• On the cost of Bayesian posterior mean strategy for log-concave models
• Black-box sampling for weakly smooth Langevin Monte Carlo using p-generalized Gaussian smoothing
• Penalized Langevin dynamics with vanishing penalty for smooth and log-concave targets
• Wasserstein distance estimates for the distributions of numerical approximations to ergodic stochastic differential equations
• An entropic approach for Hamiltonian Monte Carlo: the idealized case