Click here to flash read.
Langevin diffusions are rapidly convergent under appropriate functional
inequality assumptions. Hence, it is natural to expect that with additional
smoothness conditions to handle the discretization errors, their
discretizations like the Langevin Monte Carlo (LMC) converge in a similar
fashion. This research program was initiated by Vempala and Wibisono (2019),
who established results under log-Sobolev inequalities. Chewi et al. (2022)
extended the results to handle the case of Poincar\'e inequalities. In this
paper, we go beyond Poincar\'e inequalities, and push this research program to
its limit. We do so by establishing upper and lower bounds for Langevin
diffusions and LMC under weak Poincar\'e inequalities that are satisfied by a
large class of densities including polynomially-decaying heavy-tailed densities
(i.e., Cauchy-type). Our results explicitly quantify the effect of the
initializer on the performance of the LMC algorithm. In particular, we show
that as the tail goes from sub-Gaussian, to sub-exponential, and finally to
Cauchy-like, the dependency on the initial error goes from being logarithmic,
to polynomial, and then finally to being exponential. This three-step phase
transition is in particular unavoidable as demonstrated by our lower bounds,
clearly defining the boundaries of LMC.
No creative common's license