Bounding the Error of Discretized Langevin Algorithms for Non-Strongly Log-Concave Targets

Arnak S. Dalalyan, Avetik Karagulyan, Lionel Riou-Durand

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

In this paper, we provide non-asymptotic upper bounds on the error of sampling from a target density over R p 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 twicedifferentiable potentials (KLMC2). The main focus is on the target densities that are smooth and log-concave on 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.
Original languageEnglish (US)
JournalJournal of Machine Learning Research
Volume23
StatePublished - Sep 2022

Bibliographical note

KAUST Repository Item: Exported on 2023-06-21
Acknowledgements: This work was partially supported by the grant Investissements d’Avenir (ANR-11-IDEX0003/Labex Ecodec/ANR-11-LABX-0047). LRD was partially supported by the EPSRC grant EP/R034710/1.

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Statistics and Probability
  • Control and Systems Engineering

Fingerprint

Dive into the research topics of 'Bounding the Error of Discretized Langevin Algorithms for Non-Strongly Log-Concave Targets'. Together they form a unique fingerprint.

Cite this