The Langevin Algorithm in the Non Smooth Log-Concave Case
Joseph Lehec, Université Paris-Dauphine
Zoom
We prove polynomial time convergence of the Langevin Monte Carlo algorithm for a log-concave measure supported on an arbitrary convex set. The convergence holds in the Wasserstein distance sense, and depends only on the following parameters: the dimension, the Lipschitz constant of the potential on its domain, the log-Sobolev constant of the target measure, as well as a mild restriction on the starting point. The potential is thus assumed to be Lipshitz on its domain but not gradient Lipschitz. So typically it could be the maximum of a finite number of affine functions on some arbitrary convex set. This is the main originality of this work, most (if not all) sampling results for log-concave measures require the potential to be gradient Lipschitz. If time abides we shall also discuss how the log-Sobolev constant can be estimated, as well as an extension of the main result in which the Lipschitz potential hypothesis is relaxed to a less stringent condition.