ON APPROXIMATE SAMPLING FROM NON-LOG-CONCAVE
NON-SMOOTH DISTRIBUTIONS VIA A LANGEVIN-TYPE MONTECARLO ALGORITHMSHOGO NAKAKITA

Abstract. We propose a Langevin-type Monte Carlo algorithm for approximate samplingfrom distributions whose potentials are non-convex and non-smooth. We show thesampling complexity of the algorithm to iterate samples whose distributions are close
to target distributions in 2-Wasserstein distance. The key tools to analyze the complexity are (i) mollification of the potentials of target distributions, (ii) tractability of
random sampling from a distribution with its density equal to a mollifier, and (ii) theLiptser–Shiryeav approach for change of measures.
Keywords: diffusion processes; discrete observations; misspecified models; online gradient descent; simultaneous ergodicity; stochastic differential equations; stochastic mirror
descent

1. Introduction
We consider the problem of sampling from a Gibbs distribution π(dx) ∝ exp(−U (x))dx
on (Rd , B(Rd )), where U : Rd → [0, ∞) is a non-negative potential function. One of theextensively used types of algorithms for the sampling is the Langevin type motivated by
the Langevin dynamics, the solution of the following d-dimensional stochastic differential
equation (SDE):√(1.1)
dXt = −∇U (Xt ) dt + 2dBt , X0 = ξ,where {Bt }t≥0 is a d-dimensional Brownian motion and ξ is a d-dimensional random
vector with |ξ| < ∞ almost surely. Since the 2-Wasserstein or total variation distance
between π and the law of Xt is convergent under mild conditions, we expect that thelaws of Langevin-type algorithms inspired by Xt should converge to π. However, most of
the theoretical guarantees for such algorithms are based on the convexity of U , the twice
continuous differentiability of U , or the Lipschitz continuity of the gradient ∇U , which do
not hold in some modelling in statistics and machine learning. The main interest of thisstudy is proposal of a Langevin-type algorithm whose convergence can be given underminimal assumptions.
To see what diﬀiculties we need to deal with, we review a typical analysis [23] based on
the smoothness of U , that is, the twice continuous differentiability of U and the Lipschitz
continuity of ∇U . Firstly, the twice continuous differentiability simplifies discussions or
plays significant roles in studies of functional inequalities such as Poincaré inequalities
and logarithmic Sobolev inequalities [e.g., 2, 7]. Since the functional inequalities for π
are essential in analysis of Langevin algorithms, the assumption that U is of class C 2
frequently appears in previous studies. In the second place, the Lipschitz continuity
combined with weak conditions ensures the representation of the likelihood ratio between
Komaba Institute for Science, University of Tokyo, 3-8-1 Komaba, Meguro-ku, Tokyo
153-8902, Japan
E-mail address: nakakita@g.ecc.u-tokyo.ac.jp.
The author was supported by JSPS KAKENHI Grant Number JP21K20318 and JST CREST Grant
Numbers JPMJCR21D2 and JPMJCR2115.
12

S NAKAKITA{Xt } and {Yt }, which is critical when we bound the Kullback–Leibler divergence. Liptser
and Shiryaev [17] exhibit much weaker conditions than Novikov’s or Kazamaki’s condition
for the explicit representation if (1.1) has the unique strong solution. Since the Lipschitz
continuity of ∇U is suﬀicient for the existence and the uniqueness of the strong solutionof (1.1), the framework of Liptser and Shiryaev [17] is applicable.
Our approaches to overcome the non-smoothness of U are mollification, a classicalapproach to dealing with non-smoothness in differential equations, and the ‘misuse’ ofmoduli of continuity for possibly discontinuous functions. We consider the convolutionŪr := U ∗ ρr on U with a weak gradient, and some suﬀiciently smooth non-negative
function ρr with compact support in a ball of centre 0 and radius r ∈ (0, 1]. We canlet Ūr be of class C 2 and obtain bounds for the constant of Poincaré inequalities forπ̄ r (dx) ∝ exp(−Ūr (x))dx, which suﬀice to show the convergence of the law of the mollified
dynamics {X̄tr } defined by the SDE√dX̄tr = −∇Ūr X̄tr dt + 2dBt , X̄0r = ξ
to the corresponding Gibbs distribution π̄ r in 2-Wasserstein distance owing to Bakry
et al. [2], Liu [18], and Lehec [16]. Since the convolution ∇Ūr is Lipschitz continuous
if the modulus of continuity of a representative ∇U is finite (the convergence to zerois unnecessary), a concise representation of the likelihood ratios between the mollified
dynamics {X̄tr } and {Yt } is available, and we can evaluate the Kullback–Leibler divergence
under weak assumptions.
As our analysis relies on mollification, the bias–variance decomposition in estimation of∇Ūr rather than ∇U is crucial. This decomposition enables us to propose new algorithms
for U without continuous differentiability. Concretely speaking, we propose a new algorithm named the spherically smoothed Langevin Monte Carlo (SS-LMC) algorithm,
whose errors can be arbitrarily small under the dissipativity of U and the boundedness ofthe modulus of continuity of weak gradients. In addition, we argue zeroth-order versionsof these algorithms which are naturally obtained via integration by parts.
1.1. Related works. Non-asymptotic analysis of Langevin-based algorithms under convex potentials has been one of the subjects of much attention and intense research[10, 11, 12], and one without convexity has also gathered keen interest [23, 25, 14]. Whilst
most previous studies are based on the Lipschitz continuity of the gradients of potentials, several studies extend the settings to those without global Lipschitz continuity. We
can classify the settings of potentials in those studies into three types: (1) potentials
with convexity but without smoothness [22, 8, 16]; (2) potentials with Hölder continuous
gradients and degenerate convexity at infinity or outside a ball [13, 21, 9]; and (3) potentials with local Lipschitz gradients [6, 26]. We review the results (1) and (2) as our study
gives the error estimate of a Langevin-type algorithm with gradients whose discontinuity
is uniformly bounded.
Pereyra [22], Chatterji et al. [8], and Lehec [16] study Langevin-type algorithms under the convexity and the non-smoothness of potentials. Pereyra [22] presents proximal
Langevin-type algorithms for potentials with convexity but without smoothness, which
use the Moreau approximations and proximity mappings instead of the gradients. The
algorithms are stable in the sense that they have exponential ergodicity for arbitrary step
sizes. Chatterji et al. [8] propose the perturbed Langevin Monte Carlo algorithm for nonsmooth potential functions and show its performance to approximate Gibbs distributions.
The difference between perturbed LMC and ordinary LMC is the inputs of the gradients;
we need to add Gaussian noises not only to the gradients but also to their inputs. The
main idea of the algorithm is to use Gaussian smoothing of potential functions studied

SAMPLING FROM NON-LOG-CONCAVE NON-SMOOTH DISTRIBUTIONS

3

in Nesterov and Spokoiny [20]; the expectation of non-smooth convex potentials with inputs perturbed by Gaussian random vectors is smoother than the potentials themselves.
Lehec [16] investigates the projected LMC for potentials with convexity, global Lipschitz
continuity and discontinuous bounded gradients. The analysis is based on convexityand estimate for local times of diffusion processes with reflecting boundaries. The study
also generalizes the result to potentials with local Lipschitz by considering a ball as the
support of the algorithm and letting the radius diverge.
Erdogdu and Hosseinzadeh [13], Chewi et al. [9], and Nguyen [21] estimate the error of LMC under non-convex potentials with degenerate convexity, weak smoothness,
and weak-dissipativity. Erdogdu and Hosseinzadeh [13] show convergence guarantees of
LMC under the degenerate convexity at infinity and weak dissipativity of potentials with
Hölder continuous gradients, which are the assumptions for modified logarithmic Sobolev
inequalities. Nguyen [21] relaxes the condition of Erdogdu and Hosseinzadeh [13] by considering the degenerate convexity outside a large ball and the mixture weak smoothnessof potential functions. Chewi et al. [9] analyse the convergence with respect to the Rényi
divergence under either Latała–Oleszkiewics inequalities or modified logarithmic Sobolev
inequalities.
Note that our proof of the results uses approaches similar to the smoothing of Chatterji
et al. [8] and the control of the radius of Lehec [16], whilst our motivations and settings
are close to those of the studies under non-convexity.
1.2. Contributions. Theorem 4.1, the main theoretical result of this paper, gives an upper bound for the 2-Wasserstein distance between the law of an algorithm we propose andthe target distribution π under weak conditions without the convexity, continuous differentiability, or bounded gradients of U . The proposed algorithms are useful for samplingfrom posterior distributions for some modelling in statistics and machine learning whose
potentials are dissipative and weakly differentiable but neither convex nor continuously
differentiable (e.g., some losses with elastic net regularization in nonlinear regression androbust regression). Furthermore, we can use the zeroth-order versions of them inspiredby the recent study of Roy et al. [24] for black-box sampling with guaranteed accuracy
from distributions whose potentials are not convex or smooth.
2. Notations and assumptions
We give some notation and assumptions before the main result.
2.1. Compact polynomial mollifier. We consider a compact polynomial mollifier [1]ρ : Rd → [0, ∞) of class C 1 as follows: πd/2 (d/2,3) −1
2(1 − |x|2 ) if |x| ≤ 1,
Γ(d/2)
ρ(x) =(2.1)
0otherwise,
where (·, ·) is the beta function and Γ(·) is the gamma function. Note that ∇ρ has an
explicit L1 -bound, which is the reason to adopt ρ as the mollifier in our analysis. Letρr (x) = r−d ρ(x/r) with r > 0.
2.2. Assumptions on potentials. Let us set the following assumptions on U .
1,∞(C1) U ∈ Wloc
(Rd ), that is, U is a locally Lipschitz continuous function.
(C2) |∇U (0)| < ∞ and the modulus of continuity of ∇U is bounded, that is,ω∇U (r) :=for some r ∈ (0, 1].

supx,y∈Rd :|x−y|≤r|U (x) − U (y)| < ∞4

S NAKAKITA(C3) There exist m, b > 0 such that for all x ∈ Rd ,⟨x, ∇U (x)⟩ ≥ m |x|2 − b.
2.2.1. Concrete class of potentials functions with the regularity conditions. We show asimple class of potential functions satisfying (C1)–(C3) and some examples in Bayesianinference; assume = 1 for simplicity of interpretation. Let us consider a possibly nonconvex loss with elastic net regularization such that
λ1
U (x) = L (x) + √ R1 (x) + λ2 R2 (x) ,d1,∞where L : Rd → [0, ∞) is in Wloc
(Rd ) with a weak gradient ∇L satisfying ∥∇L∥∞ < ∞,Pd
λ1 ≥ 0, λ2 > 0, R1 (x) = i=1 |x(i) | with x(i) indicating the i-th component of x, andR2 (x) = |x|2 . Fix a weak gradient of R1 as ∇R1 (x) = (sgn(x(1) ), . . . , sgn(x(d) )); thenω∇U (1) ≤ 2(∥∇L∥∞ + λ1 + λ2 ) < ∞ and ⟨x, ∇U (x)⟩ ≥ λ2 |x|2 − ∥∇L∥2∞ /4λ2 since⟨x, ∇R1 (x)⟩ ≥ 0 for all x ∈ Rd . Note that regularization corresponds to the potentials
of prior distributions in Bayesian inference; for instance, letting λ1 = 0 is equivalent tochoosing a Gaussian prior N (0, (2λ2 )−1 Id ) on x.
Non-convex losses with bounded weak gradients often appear in nonlinear and robust
regression. We first examine a squared loss for nonlinear regression (or equivalently
nonlinear regression with Gaussian errors) such that

1 X
(yℓ − ϕℓ (x))2 ,LNLR (x) = 2
2σ ℓ=1N

1,∞(Rd ) with ∥ϕℓ ∥∞ + ∥∇ϕℓ ∥∞ < ∞ forwhere N ∈ N, σ > 0 is fixed, yℓ ∈ R, and ϕℓ ∈ Wloc
some ∇ϕℓ ; for example, a two-layer neural network with clipped ReLU activation such
that
W
1 X
ϕℓ (x) =aw φ[0,c] (⟨xw , fℓ ⟩),W w=1

where φ[0,c] (t) = (0 ∨ t) ∧ c with t ∈ R, aw ∈ {−1, 1} and c > 0 are fixed, fℓ ∈ RF ,x = (x1 , . . . , xW ) ∈ RF W , F, W ∈ N, and d = F W . This LNLR indeed satisfies
1 X∥∇LNLR ∥∞ ≤ 2(|yℓ | + ∥ϕℓ ∥∞ )∥∇ϕℓ ∥∞ < ∞.
σ ℓ=1
NAnother example is a Cauchy loss for robust linear regression (or equivalently linear
regression with Cauchy errors) such that
LRLR (x) =NXlog(1 + |yℓ − ⟨fℓ , x⟩|2 /σ 2 )ℓ=1
dlog(1 + t2 /σ 2 )| =, where N ∈ N, σ > 0 is fixed, yℓ ∈ R, and fℓ ∈ Rd . The fact | dt
P
|2t/(t2 + σ 2 )| ≤ 1/σ for all t ∈ R yields ∥∇LRLR ∥∞ ≤ Nℓ=1 |fℓ |/σ < ∞.

3. Spherically smoothed Langevin Monte Carlo (SS-LMC) algorithm
We propose an algorithm named spherically smoothed Langevin Monte Carlo.

SAMPLING FROM NON-LOG-CONCAVE NON-SMOOTH DISTRIBUTIONS

5

3.1. Basic idea. The core idea of the algorithm is approximate sampling from distributions with smoother potentials than the target distribution π rather than direct approximate sampling from π. Concretely speaking, we approximate π(dx) ∝ exp(−U (x))dx
with π̄ r (dx) ∝ exp(−Ūr (x))dx, where Ūr (x) := (ρr ∗ U )(x). This π̄ r has the properties
such that π ≈ π̄ r for suﬀiciently small r and π̄ r has a smooth potential Ūr ∈ C 2 for all1,∞
r > 0 if U ∈ Wloc
. Therefore, we expect that sampling from π̄ r must be easier thansampling from π itself and it approximates π if r ≪ 1.
Whilst the standard LMC algorithm aims at the Euler–Maruyama discretization of thesolution (Langevin dynamics) of the SDE such as√
dXt = −∇U (Xt ) dt + 2dBt ,we propose an algorithm being a discretization of the solution of the following mollified
SDE:√dX̄tr = −∇Ūr X̄tr dt + 2dBt .
Under mild conditions, D(L(X̄tr )∥π̄ r ) → 0 as t → ∞.
If we knew ∇Ūr , the following Langevin-type Monte Carlo algorithm would work:
p
r
ŷi+1
= ŷir − η∇Ūr (ŷir ) + 2ηzi , ŷ0r = ξ, i = 0, . . . , k − 1,
where k ∈ N is the number of iteration, η ∈ (0, 1] is the stepsize, r ∈ (0, 1] is the radiusof mollification, and zi ∼i.i.d. N (0, Id ). However, the computation of ∇Ūr is anotherintegration problem and we do not know its explicit representation except for some special
cases such as U (x) = |x|2 .
Alternatively, we consider a Monte Carlo approximation of the integral ∇Ūr . Notethat the mollifier ρ is also the probability density function of a random variable ζ =√τ1 τ2 , where τ1 ∼ Unif(Sd−1 ) and τ2 ∼ Beta(d/2, 3) are independent random variables.
Therefore, we can consider spherical smoothing with the random variables whose density
is ρr as an analogue to Gaussian smoothing of Chatterji et al. [8]. A Monte Carloapproximation of ∇Ūr can be given as
(3.1)

NB
1 X
G(x, {ζj }) :=∇U (x + rζj ) ,NB j=1

where NB ∈ N is the minibatch size of the Monte Carlo approximation and ζj ∼i.i.d. ρ.
Under Assumptions (C1) and (C2), it holds that for all x ∈ Rd ,hi (2ω (r))2
2
∇U
(3.2)
.
E [G(x, {ζj })] = ∇Ūr (x), E G (x, {ζj }) − ∇Ūr (x) ≤NB
Hence we can approximate ∇Ūr if NB is suﬀiciently large.
Based on these analyses, we propose the spherically smoothed Langevin Monte Carloalgorithm (Algorithm 1) using G as an approximation of ∇Ūr .
4. Convergence analysis of SS-LMC
We give a convergence analysis of the proposed algorithm. We first assume the warm
start of the algorithm as follows.
R(A0) The initial value ξ has the law µ0 (dx) = ( Rd exp(−Ψ(x))dx)−1 exp(−Ψ(x))dx
with Ψ : Rd → [0, ∞) and ψ0 , ψ2 > 0 such that (2∨(|∇U (0)|+ω∇U (1)))|x|2 −ψ0 ≤Ψ(x) ≤ ψ2 |x|2 + ψ0 for all x ∈ Rd .
The following theorem gives an error estimate of the SS-LMC algorithm. Let µiη denotethe law of yi .

6

S NAKAKITA

Algorithm 1 SS-LMC algorithm [19]Input: k, n ∈ N, η, r > 0, y0 = ξ
1: i ← 0
2: while i < k do
3:
j←0
4:
G←0
5:
while j < n do
6:
ζj ∼ ρ
7:
G ← G + n−1 ∇U (yi + rζj )8:
j ←j+19:
end while
10:zi ∼ N (0, Id )√11:
yi+1 ← yi − ηG + 2ηzi
12:
i←i+1
13: end while
Output: {yi : i = 1, . . . , k}

Theorem 4.1 (error estimate of SS-LMC, [19]). Under (C1)–(C3) and (A0), there exists
a constant C ≥ 1 independent of NB , r, k, η, d, cP such that for all k ∈ N, η ∈ (0, 1 ∧(m/(4(ω∇U (1))2 ))], r ∈ (0, 1], and NB ∈ N with (d2 (ω∇U (r)/r)η + (ω∇U (r))2 /NB )kη +rω∇U (r) ≤ 1,
s



√ 4
(ω∇U (r))2ω∇U (r)kη
Cd2W2 (µkη , π) ≤ C dη+dkη + rω∇U (r) + e exp −
,
r
NB
CcP
where cP is the Poincaré constant of π.
4.1. The sampling complexity of SS-LMC. We analyse the behaviour of SS-LMC;
to see that the convergence ω∇U (r) ↓ 0 is unnecessary, we consider a rough version of theupper bound by replacing ω∇U (r) with the constant ω∇U (1).
Corollary 4.2. Under (C1)–(C3) and (A0), there exists a constant C ≥ 1 independent
2of NB , r, k, η, d, cP such that for all NB ∈ N, k ∈ N, η ∈ (0, 1 ∧ (m/(4(ω∇U (1)) ))], and−12 −1
r ∈ (0, 1] with d r η + NB kη + r ≤ 1,


√ q

kη
4
−1
Cd
2
−1
.
W2 (µkη , π) ≤ C d d r η + NB kη + r + e exp −CcP
We yield the following estimate of the sampling complexity.
Proposition 4.3. Assume (C1)–(C3) and (A0) and fix ϵ ∈ (0, 1]. If r = ϵ4 /48C 4 d2 ,NB ≥ 48C 4 d2 (CcP (log(2/ϵ) + Cd) + 1)/ϵ4 , and η satisfies
m
rϵ4
η ≤1∧
,
∧
4 (ω∇U (1))2 48C 4 d4 (CcP (log(2/ϵ) + Cd) + 1)
then W2 (µkη , π) ≤ ϵ for k = ⌈CcP (log(2/ϵ) + Cd)/η⌉.
Since the complexities of NB and k are given as NB = O(d2 cP (log ϵ−1 + d)/ϵ4 ) andk = O(d6 c2P (log ϵ−1 + d)2 /ϵ8 ), we obtain the sampling complexity of SS-LMC as NB k =e ignores logarithmic factors.
e 11 c3 /ϵ12 ), where O
O(d8 c3P (log ϵ−1 + d)3 /ϵ12 ) or NB k = O(dPSAMPLING FROM NON-LOG-CONCAVE NON-SMOOTH DISTRIBUTIONS

7

4.2. Bounds for Poincaré constants. Whilst we give the sampling complexity in termsof d, ϵ, and cP , it is diﬀicult to obtain dimension-free estimates for cP in general. If we
set only Assumptions (C1)–(C3), we obtain cP = O(exp(O(d))) ([23, 19]) and it is quite
loose in the dimension d. We introduce some known assumptions on potentials to givetighter bounds on the constants.
4.2.1. Bounded perturbation of potentials. The following result of the perturbation theory[3] is fundamental and essential: if µ(dx) ∝ exp(−V (x))dx has a finite Poincaré constantcP , then distributions µF (dx) ∝ exp(−F (x) − V (x))dx with ∥F ∥L∞ < ∞ have Poincaré
constants cP (µF ) such that
(4.1)

cP (µF ) ≤ exp(ess sup F − ess inf F )cP (µ).

For instance，
we consider U (x) = F̄ ∧F (x)+|x|2 /2, where |x|2 /2 is the potential function of1,∞
the d-dimensional standard Gaussian distribution, a nonnegative loss function F ∈ Wloc
and a clipping constant F̄ > 0. Since the Poincaré constant of thed-dimensional standard
Gaussian distribution is 1, a Poincaré constant cP of the distribution π with this potential
U satisfies(4.2)
cP ≤ exp F̄ .
If F satisfies supx∈X |∇F (x)| < ∞ with the sublevel set X := {x ∈ Rd : F (x) ≤ F̄ }, thefollowing estimate holds by regarding F̄ as a constant:(4.3)
nk = Õ d11 ϵ−12 .
4.2.2. Miclo’s trick. If a distribution satisfies a logarithmic Sobolev inequality with aconstant cLS , then the distribution satisfies a Poincaé inequality with a constant cP (≤ cLS ).
Using this fact, we give an estimate via the Miclo’s trick ([4]). Assume that the potential
U has a representation U = Uc + Ul , where Uc ∈ C 2 (Rd ) satisfies ∇2 Uc ≥ λId , λ > 0 and
Ul is M -Lipschitz. Then it holds that
√ !
2
4
4M 2d
√
(4.4)
cP ≤ cLS ≤ expλλ π
For instance, by setting Uc = |x|2 /2 as the potential of a prior distribution and a Lipschitz
continuous function as the potential of a likelihood function, we obtain (C1)–(C3) since
Lipschitz continuous functions have bounded weak gradient [15]. Therefore, under thissetting, we obtain the following complexity estimate: √ 
−12(4.5)
nk = Õ exp Od ϵWhilst it diverges faster than any polynomial functions of d, it improves the order incomparison to that given only by Assumptions (C1)–(C3).
5. Remark on a zeroth-order version of the algorithm
First-order algorithms are sometimes prohibitive when gradients are not available or
their derivation is computationally expensive; hence it motivates us to consider zerothorder (or gradient-free) sampling algorithms. Let us consider a zeroth-order version of
SS-LMC as an analogue to Roy et al. [24] with the following G0 , an estimator of ∇Ūr ,under (C1)–(C3) and the assumption |U (x)| < ∞ for all x ∈ Rd :
NB
1 X
4ζj
U (x + rζj ) − U (x)G0 (x, {ζj }) :=,NB j=1r(1 − |ζj |2 )

8

S NAKAKITA

where NB ∈ N, r ∈ (0, 1], and {ζj } is an i.i.d. sequence of random variables with thedensity ρ. The fact thatU (x + rζj ) − U (x)4ζj
U (x + rζj ) − U (x) −∇ρ (ζj )=,2r(1 − |ζj | )rρ (ζj )
the symmetricity of ρ, and approximation of ρ ∈ C01 (Rd ) ∩ W 1,∞ (Rd ) yield that for allx ∈ Rd ,Z
U (x + rz) − U (x) −∇ρ (z)E [G0 (x, {ζj })] =ρ (z) dz
r
ρ (z)
Rd
Z
U (x + rz) − U (x)=−∇ρ (z) dzrRdZ y 
1=−(U (x + y) − U (x))∇ρdy(r)d+1r
Rd
Z=∇U (x + y) ρr (y) dy
Rd= ∇Ūr (x) .
Therefore, G0 (x, {ζj }) also gives an unbiased estimation of ∇Ūr (x). By evaluating thevariance of G0 (x, {ζj }), we can obtain the result that W2 (µkη , π) ≤ ϵ with arbitrary ϵ > 0
for the zeroth-order algorithm adopting this G0 as the estimator of ∇Ūr . Note that thecomplexity deteriorates by a factor of O(d3 ) in comparison to SS-LMC; this is a worse
cost than O(d) which is the deterioration of the zeroth-order algorithm proposed by Roy
et al. [24] with respect to the Langevin Monte Carlo algorithm.
6. Sketch of the proof of Theorem 4.1
Let us review the proof of Theorem 4.1 briefly. We decompose the 2-Wasserstein
distance as follows:rr
W2 (µkη , π) ≤ W2 (µkη , ν̄kη
) + W2 (ν̄kη, π̄ r ) + W2 (π̄ r , π),

where ν̄ r is the law of X̄tr . If kη is suﬀiciently large, then the second term on the righthand side converges to zero by the exponential decay of entropy and the Talagrand’s
inequality. The third term also converges to zero as r → 0 due to the convergence of the
Kullback–Leibler divergence. Hence the key term in the analysis is the first term on theright-hand side.
We can reduce the problem to an estimate of the Kullback–Leibler divergence of µkη
rfrom ν̄kηowing to Bolley and Villani [5]. The Liptser–Shiryaev approach [17] plays asignificant role in the estimate of the divergence. It gives an explicit representation of
the likelihood ratio of the solutions of SDEs given that one of the SDEs has a uniquestrong solution and the other one has a unique weak solution; for details, see Chapter
7 of [17]. Roughly speaking, they use a Brownian motion of the weak solution as thedriving process of the SDE with a unique strong solution after a change of measures; it
is possible because the unique strong solution can exist for any Brownian motion.
We obtain the following estimate via a slight change of the discussion of [17].
Lemma 6.1 ([19]). For some C ≥ 1, for any k ∈ N and η ∈ (0, 1/C], it holds true thatω∇U (r)2r
2 ω∇U (r)D(µkη ∥ν̄kη ) ≤ C d
η+
kη.
r
NB
Using this estimate, we can bound the 2-Wasserstein distance.

SAMPLING FROM NON-LOG-CONCAVE NON-SMOOTH DISTRIBUTIONS

9References[1] Anderson, C. R. (2014). Compact polynomial mollifiers for Poisson’s equation. Technical report, Department of Mathematics, UCLA, Los Angeles, California.
[2] Bakry, D., Barthe, F., Cattiaux, P., and Guillin, A. (2008). A simple proof of the
Poincaré inequality for a large class of probability measures. Electronic Communicationsin Probability, 13:60–66.
[3] Bakry, D., Gentil, I., and Ledoux, M. (2014). Analysis and Geometry of Markov
Diffusion Operators. Springer.
[4] Bardet, J.-B., Gozlan, N., Malrieu, F., and Zitt, P.-A. (2018). Functional inequalities for Gaussian convolutions of compactly supported measures: explicit bounds anddimension dependence. Bernoulli, 24(1):333–353.
[5] Bolley, F. and Villani, C. (2005). Weighted Csiszár-Kullback-Pinsker inequalities
and applications to transportation inequalities. Annales de la Faculté des sciences deToulouse: Mathématiques, 14(3):331–352.
[6] Brosse, N., Durmus, A., Moulines, É., and Sabanis, S. (2019). The tamed unadjusted
Langevin algorithm. Stochastic Processes and their Applications, 129(10):3638–3663.
[7] Cattiaux, P., Guillin, A., and Wu, L.-M. (2010). A note on Talagrand’s transportation
inequality and logarithmic Sobolev inequality. Probability Theory and Related Fields,
148:285–304.
[8] Chatterji, N., Diakonikolas, J., Jordan, M. I., and Bartlett, P. (2020). Langevin Monte
Carlo without smoothness. In Proceedings of the Twenty Third International Conferenceon Artificial Intelligence and Statistics, pages 1716–1726.
[9] Chewi, S., Erdogdu, M. A., Li, M., Shen, R., and Zhang, S. (2022). Analysis ofLangevin Monte Carlo from Poincare to Log-Sobolev. In Proceedings of Thirty Fifth
Conference on Learning Theory, pages 1–2.
[10] Dalalyan, A. S. (2017). Theoretical guarantees for approximate sampling fromsmooth and log-concave densities. Journal of the Royal Statistical Society: Series B(Statistical Methodology), 79(3):651–676.
[11] Durmus, A. and Moulines, E. (2017). Nonasymptotic convergence analysis for theunadjusted Langevin algorithm. The Annals of Applied Probability, 27(3):1551 – 1587.
[12] Durmus, A. and Moulines, E. (2019). High-dimensional Bayesian inference via theunadjusted Langevin algorithm. Bernoulli, 25(4A):2854–2882.
[13] Erdogdu, M. A. and Hosseinzadeh, R. (2021). On the convergence of LangevinMonte Carlo: The interplay between tail growth and smoothness. In Proceedings ofThirty Fourth Conference on Learning Theory, pages 1776–1822.
[14] Erdogdu, M. A., Mackey, L., and Shamir, O. (2018). Global non-convex optimization
with discretized diffusions. 32nd Conference on Neural Information Processing Systems.
[15] Evans, L. C. (2010). Partial Differential Equations, volume 19. American Mathematical Society.
[16] Lehec, J. (2021). The Langevin Monte Carlo algorithm in the non-smooth logconcave case. To appear in the Annals of Applied Probability.
[17] Liptser, R. S. and Shiryaev, A. N. (2001). Statistics of Random Processes: I. General
theory. Springer, 2nd edition.
[18] Liu, Y. (2020). The poincaré inequality and quadratic transportation-variance inequalities. Electronic Journal of Probability, 25(1):1–16.
[19] Nakakita, S. (2023). Non-asymptotic analysis of Langevin-type Monte Carlo algorithms. arXiv:2303.12407.
[20] Nesterov, Y. and Spokoiny, V. (2017). Random gradient-free minimization of convex
functions. Foundations of Computational Mathematics, 17:527–566.

10

S NAKAKITA[21] Nguyen, D. (2022). Unadjusted Langevin algorithm for sampling a mixture of weaklysmooth potentials. Brazilian Journal of Probability and Statistics, 36(3):504–539.
[22] Pereyra, M. (2016). Proximal Markov chain Monte Carlo algorithms. Statistics andComputing, 26:745–760.
[23] Raginsky, M., Rakhlin, A., and Telgarsky, M. (2017). Non-convex learning via
stochastic gradient Langevin dynamics: a nonasymptotic analysis. In Proceedings of the2017 Conference on Learning Theory, pages 1674–1703.
[24] Roy, A., Shen, L., Balasubramanian, K., and Ghadimi, S. (2022). Stochastic zerothorder discretizations of langevin diffusions for bayesian inference. Bernoulli, 28(3):1810–
1834.
[25] Xu, P., Chen, J., Zou, D., and Gu, Q. (2018). Global convergence of Langevindynamics based algorithms for nonconvex optimization. 32nd Conference on Neural
Information Processing Systems.
[26] Zhang, Y., Akyildiz, Ö. D., Damoulas, T., and Sabanis, S. (2023). Nonasymptotic estimates for Stochastic Gradient Langevin Dynamics under local conditions in nonconvex
optimization. Applied Mathematics & Optimization, 87(2):25.