From stability of Langevin diffusion to convergence of proximal MCMC for non-log-concave sampling
Authors: Marien Renaud
Valentin De Bortoli
Arthur Leclaire
Nicolas Papadakis
Venue: NeurIPS 2025 poster ()
Keywords: Sampling
Langevin diffusion
Monte Carlo Markov Chain
Inverse Problem
Primary area: probabilistic_methods
TL;DR: We demonstrate the stability of Langevin diffusion and use it to derive the first proof of convergence for Proximal Stochastic Gradient Langevin Algorithm in a non-convex setting.

Abstract: We consider the problem of sampling distributions stemming from non-convex potentials with Unadjusted Langevin Algorithm (ULA). We prove the stability of the discrete-time ULA to drift approximations under the assumption that the potential is strongly convex at infinity. In many context, e.g. imaging inverse problems, potentials are non-convex and non-smooth.  Proximal Stochastic Gradient Langevin Algorithm (PSGLA) is a popular algorithm to handle such potentials. It combines the forward-backward optimization algorithm with a ULA step. Our main stability result combined with properties of the Moreau envelope allows us to derive the first proof of convergence of the PSGLA for non-convex potentials. We empirically validate our methodology on synthetic data and in the context of imaging inverse problems. In particular, we observe that PSGLA exhibits faster convergence rates than Stochastic Gradient Langevin Algorithm for posterior sampling while preserving its restoration properties.

From stability of Langevin diffusion to convergence of proximal MCMC for non-log-concave sampling
Marien Renaud*
Univ. Bordeaux, CNRS, Bordeaux INP, IMB, UMR 5251 F-33400 Talence, France
Valentin de Bortoli ENS, CNRS, PSL University Paris, 75005, FRANCE
Arthur Leclaire
LTCI, Télécom Paris, IP Paris, France
Nicolas Papadakis Univ. Bordeaux, CNRS, INRIA, Bordeaux INP, IMB, UMR 5251 F-33400 Talence, France
Abstract
We consider the problem of sampling distributions stemming from non-convex po- tentials with Unadjusted Langevin Algorithm (ULA). We prove the stability of the discrete-time ULA to drift approximations under the assumption that the potential is strongly convex at infinity. In many context, e.g. imaging inverse problems, po- tentials are non-convex and non-smooth. Proximal Stochastic Gradient Langevin Algorithm (PSGLA) is a popular algorithm to handle such potentials. It combines the backward optimization algorithm with ULA step. Our main stabil- ity result combined with properties of the Moreau envelope allows us to derive the first proof of convergence of the PSGLA for non-convex potentials. We empir- ically validate our methodology on synthetic data and in the context of imaging inverse problems. In particular, we observe that PSGLA exhibits faster conver- gence rates than Stochastic Gradient Langevin Algorithm for posterior sampling while preserving its restoration properties. The code associated with the paper can be found in github.
Introduction
Sampling probability distribution ग - on Rd fundamental task in machine learning [2, 10, 13, 28, 42. 51, 91]. It becomes challenging when the potential V is non-convex [39, 43]. A well-known approach is solve the Langevin stochastic differential equation [59, 79], defined by
dx; VV + 2dw,
(1)
where (w:)220 is Wiener process [53] on R4. This process can be seen as a continuous gradient descent V randomly perturbed by v2dw,. Under mild assumptions, equation (1) admits as its invariant distribution [79]. Moreover, the solution converges geometrically in law to π when i goes to infinity if V is strongly convex infinity [30, 23). In Section 4 we discuss alternative methods that have been developed to sample π, such as Gibbs Sampling [17] or Diffuusion Models [87].
As the function VV - log is often unknown [74], is approximated by drift function b R + Rd such that VV. In practice, the Marurama discretization of equation (1)
"corresponding author: marien.renaud @ -rod.u-bordeaux.fr
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

f non-convex
Proxg inexact
W₂ metric
W metric
TV metric
p
129, 84, 85]
X
X
X
[33]
X
X
X
X
This paper
/
/
Table I: Existing convergence results in the literature for PSGLA (3).
leads to the inexact Unadjusted Langevin Algorithm (iULA)
Xx+1 Xx 1 76(Xx) + 227Zk+11
with step-size y > O and Z++1 Ia) iid. It is called inexact because b is inexact approximation VV and unadjusted because the invariant law of this Markov Chain is и up to a discretization error (see Theorem in Section 2). This Langevin Markov Chain could be adjusted by adding Metropolis-Hastinge measure supported the iterates (Xx N will be used quality of iÜLA, there is a need to quantify the shift between the invariant law of the MCMC and the target distribution This leads to investigate the stability of iULA invariant law to shift in the drift Existing stability results [98, 75] are limited by discretization error. With a new proof strategy, we overcome this limitations in Theorem 1 in Section
accept-reject step [78, 70]. With ergodic MCMC, the uniform
estimator for æ. To evaluate the
In many applications the potential has a composite form V = g. For instance in Bayesian inverse problems [73, 15, 36]. the goal is to sample the posterior distribution with f the negative log-likelihood, which usually smooth and possibly non-convex, and g the regularization, which might be non-smooth and non-convex. Due the non-smoothness of V. iULA that relies on evalu- ation of VV can not be implemented. A popular solution to design forward-backwar Langevin scheme [9, 7, 85, IJ, with the so-called Proximal Stochastic Gradient Langevin Algorithm (PS- GLA) [29, 84] defined by
Xx+1 = Prox (Xx- (V-())((X)) + v22
(3)
where the proximal operator defined by Proxyg (z) arg min min Red - + can be seen as an implicit gradient step. PSGLA has recently been studied [84, 33] in the convex setting. However,
to our knowledge, there is no convergence analysis in the non-convex setting (see Table 1). We fill this gap by providing convergence proof based our stability result for Langevin Markov Chain in the case of f smooth and non-smooth and weakly convex (Theorem 3 in Section 3).
1.1 Contributions
(1) We prove the first stability result for inexact Unajusted Langevin Algorithm (iULA defined in equation (2)) with respect to the drift without discretization errors (Theorem in Section 2). (2) We give the discretization error of FULA in various metrics including p- Wasserstein and Total Variation (Theorem 2 in Section 2). (3) Leveraging properties the Moreau envelope, we demonstrate the first convergence proof of Proximal Stochastic Gradient Langevin Algorithm (PSGLA defined in equation (3)) (Theorem in Section 3) and Inexact PSGLA (Theorem 4 in Section 3) for non- convex potentials.
(4) We apply our theory to posterior sampling and show empirically that the mixing time of PSGLA is significantly shorter that the iULA (Section 5). In particular, we propose a Plug-and-Play version PSGLA for image restoration that achieves state-of-the art restoration.
1.2 Notations and definitions
For a distribution on IRd and function o Rd + R. we denote (uΦ) = Sga odl. For two distributions on IRd, the Total Variation (TV) writes
|| - vllrv = sup - - v(d).
(4)
o: -R
For a measurable function Φ .dd Rdd the forh-forward of a probability distribution y by denoted by o is the distribution defined for measurable set A C Rd by @# = (

---

The Wasserstein distance between μ and v is defined, for p 2 1, by
Wy(m,)) min (EE JR'Rd
|| - y11 8)
(5)
with II the set of probability law 3 on Fd x Fd with marginals μ and V.
A function is p-weakly convex, with > 0, if and only if + 51 112 is convex. This notion is also called semi-convexity [18, 49]. A twice-difierentiable function 9 is m-strongly convex at infinity if and only if there exists R 2 0 such that Vi E RR, if ||:|| 2 R. then V²g(z) ž ula- Note that we define the strong convexity infinity only for twice differentiable functions, which is sufficient for this paper. This non-trivial notion of strong convexity on non-convex sets is discussed in Appendix E.
A Markov Chain (Kx)k20 has an invariant law there exists μ probability distribution on I2 such that if Xg μ4, then vk 2 0, Xx ~ μ.. A Markov Chain (X&) x2) is said to be geometrically ergodic, the law of Xx converges geometrically to the invariant law, i.e. there exist A 2 0, p E (0, 1), an invariant law μu, such that W (P) S Ap with px, the law of Xx-
2 Sampling stability and discretization error
In this section, we study the sampling stability to drift errors of the inexact Unadjusted Langevin Algorithm (iUL.A) defined in equation (2). The sampling stability result (Theorem 1) and the dis- cretization error bound (Theorem 2) demonstrated in the section will be the key ingredients for the PSGLA convergence analysis in Section 3. We introduce two iULA with two arbitrary drifts as
X x 76' (xx) + V 227Z++1
(6)
for E {1,2), with the step-size 7 > 0, 7 (O, Ta) i.i.d. and the drifts D' E CQ(RR, Rd). Assumption 1. There exist L, R 2 0 and m > 0 such that the drift b verifies
(i) b is L-Lipschitz, iee. Vx, y Rd [b(z)) b(v)1l = L||z vll
(ii) Vx, y E IRd such that || vll 2 R. we have (b(x) b(y), x a) 2 ml|x y/1
Assumption 1(i) imposes that the drift is sufficiently regular, without uncontrolled variations. In particular, if b = VV, the I-Lipschitzness on b involves that the potential V is L-weakly convex If b = VV, Assumption I(ii) is relaxation of the strong convexity assumption on V, as it only holds for couple of points sufficiently far away Assumption (ii)) is called weak dissipativity [24, 62] or distant dissipativity [67]. Note that if the drift is m-strongly convex at infinity and L-weakly convex then it weakly dissipative.
We define the (2( distance between two functions f1, : Rd + R by
Ilfi fellez()) (Ey~ (I1i(Y)) f2(())12))
Theorem 1. Let b² and b? satisfy Assumption 1. X and X2 that satisfy equation (6) two geometrically ergodic Markev Chains with invariant laws nī. ma.. Then for no I and p E N+ there exist Cp: C 2 O such that Vy E (0, vo].
we have
W WT m²) s Cp,lbb' 1000-~b211200 11
(8)
|| - I C1|b* -b?lles(7?))
(9)
The proof of Theorem can be found in Appendix F.4. Theorem 1 shows that errors in the drifts do not accumulate, moreover if two drifts are close (in Eg distance) then the corresponding sampled distributions are close. We also demonstrate a similar result in the V-norm, a generalization of the TV (see Theorem 5 in Appendix F.3). More importantly, contrary to [75], our bound does not contain any discretization error. Theorem 1 does not only refine existing works, it also
generalizes to Wp the bounds of [75], which were WI =²?) S C1 - b²ll), + Drys for equation (8) in the case p 1 and ||]] zol|rv C1|b 6² (ll22))))) + Dryà for equation (9).
3

---

Sketch of the Proof of Theorem / First, we prove that x X are geometrically ergodic. Then by using the triangle inequality and the geometric ergodicity we control the shift between the asymptotic laws by shift between finite time laws. Finally this finite time shift is controlled by the shift between drifts by applying the Girsanov theory with the core Lemma 20 in Appendix F.2.
Theorem 2. Let b VV verifies Assumption and & e Then, for n I and ạ (0, 70) the Markov Chain defined in (2) with the drift b = VV has an invariant law n4y and is geometrically ergodic. Moreover for p Nº, there exist Dy. D 2 0 such that Vy E (0, 70l. we have
W WTy x) Dpy 2
|T +/lrv Dy
Theorem is proved in Appendix F66 by following the same strategy as Theorem with continuous- time Markov process instead of discrete-time Markov Chain. It provides result on the discretization error of the Unadjusted Langevin A Algorithm, which has been extensively studied the literature for
finite time [67], in the strongly convex setting [20, 8], in TV -distancee [27] or K K--divergence [12]. To our knowledge, formulating this discretization error in Wp for all p E IN and in TV under weak dissipativity (Assumption ((i)) is novelty with respect to the literature.
We quantified the sampling shifts due to drift approximations in Theorem and the discretization error in Theorem 2 for iULA. We can now put together these results.
Let b and VV verify Assumption and π x e-V. Then for % = m the Markov Chain defined in equation (2) with drift b is geometrically ergodic with invariant law Tyy Moreover for E N², there exist Cp. Dp. C, D 2 0 such that Vy E (0, v0l. we have
Corollary 1.
12, and r E (0, 70),
W #x) Cp VV
VV (et)) + D,y
| - क 1||rV S C VV lea(s.) + D.
Corollary is direct consequence of Theorem I combined with Theorem 2. It quantifies the preci- sion of sampling x e with the practical algorithm (2) instead of the continuous process defined in equation (1). Corollary extends previous known results established in W2 in the strongly convex setting [8] to strongly convex at infinity setting with various metrics. The pseudo-metric |lea(*.)) appears to be the appropriate metric to quantify the difference between drifts.
3 Convergence of Proximal Stochastic Gradient Langevin Algorithm for non-convex potentials
We now apply the results of Section 2 to derive in Theorem 3 the first convergence result for PS- GLA (3), summarized in Algorithm 1, in the non-convex setting specified by Assumption Then, in Theorem 4 deduce the convergence of Inexact PSGLA (3) when approximating the proximal operator of the non-convex potential.
Assumption 2. The potential V is composite, i.e. V = f + where
(i) f is Ly-smooth, i.e. Vf is Ly-isschiiz.
(ii) g is p-weakly convex with p 0, i.e. g Gll 112 convex.
In the case of posterior sampling, which will be detailed in Section 5, f is typically the negative log-likelihood and g the regularization. Under Assumption 2(), can be non-convex, as is the case in image despeckling [25] or black-hole interferometrie imaging [89]. The weak convexity of g ensures that the proximal operator Prox-g well defined as soon as 7 < 1. Assumption 2(i)) verified for various convex regularizations total- varriaait [83] or for some non-convex deep regularizers [47, 86, 40].
p*
On the Moreau envelope To analyse PSGLA under Assumption 2, we will need properties on the proximal operator and the Moreau envelope g² of defined for y > 0 and E R by (x) inf infyeed 2y || y/ + g(y). Notice that if g is p- p-weakly convex and py < 1, then the Moreau envelope is well defined. In the following Lemma we provide important properties relative to the proximal operator and the Moreau envelope of weakly convex functions.

---

Algorithm Proximal Stochastic Gradient Langevin Algorithm (PSGLA)
1: input: N > 0, E RT Xo E R
2: for k 0..... N-
do
3: Zk+1 ~ (0, Ta)
4: X8+1 f Prox (Xx - >VV((() + v27
5: end for
6: output: (Xx))EJO,N)
Lemma 1. For a p-weakly convex function 9 and 7p < 1, we have the the following properties:
(i) If is differentiable
then we have Proxag (x + (Vg(x))
(ii) The proximal operator is gradient-descent step the Moreau envelope, i.e. Proxag (a) = x ~V
(iii) The proximal operator Prox.g is 1 I- Lipschitz.
(iv) The image of the proximal operator is almost convex, Leb(Con((roxxng (R²)) Proxig (R*)) O, with Leb the Lebesgue measure and Conv(Prox, (R4) is the con- envelop of Prox,g (Rd).
In this lemma, we adapt to the weakly convex case results known in the convex setting [65, 80, 46, 3, 41, 50]. In particular point (iv) requires subtle adaptation with respect to the convex case. All proofs are postponed in Appendix D, where we provide self-contained analysis the Moreau envelope for weakly convex functions.
ULA and PSGLA:
two discretizations of the same continuous process in the case of differ- entiable. First, the Buler-Maruynnn discretization of equation (1) with stepsize y > 0 leads to the Unadjusted Langevin Algorithm (ULA) [27, 59], defined by
XR+1 = Xx - (V((x) (X)( + 22
(10)
with ZR+11 (N la) i.i.d This Markov Chain has been shown sample the target law x e-v [59] for a non-convex potential V, up to a discretization error (see Theorem 2 in Section 2). ULA adds noise at each iteration to the iterate Xş leading to noisy samples. Taking advantage of the composite nature of V, PSGLA (3) appears to be good candidate for producing high quality samples. Indeed, for PSGLA the iterate Xg is obtained after applying Prox.gg which, in practice, often corresponds to a denoising operator [92]. However PSGLA has not yet been shown to sample the law for non-convex potential.
Secondly, semi-implicit discretization of equation (1) with E (0, ?) and Lemma 1(i) gives
Xx+1 = Xs vVI(Xx) (Vg(Xe+1) + Zx+1
(Ia + Dg) (X++1) = X5 (V-V([(X)) + /227
X Prox,g - (V((e) + 227
Our postulate as follows. As the ULA and PSGLA are two discretizations of the same continuous process, expect that PSGLA also approximately samples the target distribution æ x V
Reformulation of PSGLA as a two-point algorithm
PSGLA (3) can reformulated as
Yo+1 = Xx - 7 <V[(X))+ + Z27Z
X Prox (Yv-1).
By Lemma ((ii, we get that the iterates YE verify the equation
Y = Proxxy (Yx) - V (Yx)) + 22
= Yr 76--60 (YE) ) + 22
5

---

where the drift 6 is defined for y F as
("()) = Voy=v\ly-~Vpp
+ Vg)
(11)
Therefore, the shadow sequence Yx verifies Markov Chain of the form of equation (2) with drift
that depends on the step-size 7 > 0. In order to apply the result of Section 2, we need to make additional technical assumptions on g-
Assumption 3.
(i) Vy E (0, g is Lm-sthoth on Proxyg (R*).
(ii) g" is j-strrongly convex at infinity with μ 8Lg + ALg. i.e. there exists n > 0 and Ro such that Vyy n.). Vrg ž pls. on R Ro).
Assumption 3() is verified by non-smooth functions such as the characteristic function of a convex set. This assumption is not usual for g that is generally not expected to be smooth a subset of Rd [84, 29, 33]. Note that Prox,g (Rd) can be a non-convex set if g is not finite everywhere. However, Lemma 1(iv) shows that Prox,g (R") only differs from being convex by a negligible set.
Assumption 3(ii) is key ensure that Y& is geometrically ergodic. Assumption 3(ii) could be moved by slightly modifying PSGLA as detailed in Appendix B. Lemma 16 in Appendix E shows that if 9 is strongly convex infinity and globally smooth, such as Gaussian mixture models, then Assumption 3(i) is verified.
Theorem 3. Under Assumptions 2-3, there exist r E (0, 1), C1, E R4 such that Vy E (0, 7] with 7 = min ( "t, +2, 20 7) ). where Lugs Top " are defined in Assumptions 2-3, and vk E N. we have
1.
WplPr. S Cirhy C27 with Pv, the distribution of Y2 and He, & f-
(12)
Moreover there exist C3, C4 R4 such that Vy E (0, 5) and vk E N. we have
Wplpxe, S Osr + C,
(13)
with px, the distribution of Xx and By x #e- f-9-
Theorem 3 is proved in Appendix G.2. It shows the convergence of PSGLA (3) in non-convex setting. This convergence exponential with an asymptotic bias due to discretization errors. Theo- rem 3 can also be proved in TV -distance following the same reasoning. Note that the distribution Hhy and V4 are not exactly the target distribution ग, the following Proposition fills this gap by showing that Myy and by both converge to when goes to zero.
Sketch of the proof of Theorem 3 First, we prove that under Assumptions 2-3, the drift 6% verifies Assumption with constants independent of 7. So we can apply the results of Section 2. In particu- lar, (Y+)x20 is geometrically ergodic, with invariant law Poo- Then we apply Theorem I quantify the distance between Pos and the invariant law of the MCMC with the drift V + Vg", named py.
Finally, we apply Theorem 2 to quantify the distance between Py and Mly ε e f=g" The triangle inequality and Lemma ((ii) conclude the proof.
Proposition 1.
With π x e f-9, My x xe 5-9" and V. = Por 2 1, we have
lim W () = lim W, (y., x) =0. 7+0
7
Moreover, if g L-Lipcchitz there exists Ep E RR such that Vy E [0, 7,2
Wplny; m) (T2 Wp(y,, m) < (L2r) + In.
Proposition I is proved in Appendix G.3. We choose to separate Proposition 1 from Theorem 3 as g is not T.-Lipschitz is many applications. Moreover, Proposition is only based on the Moreau envelope approximation study, independently from the Markov Chain context of this paper.

---

Inexact PSGLA In practice, many functions 9. such as the Mara--Vaiationn regularisation [83], have no closed-form Prox,g Therefore, the proximal operator is approximated by an operator S. C RR)) such that Sy = Proxyg. The authors of [33] studied the inexact PSGLA defined by
X+11= = Sy
2772x+11)
(14)
with Zu+1 ~ (O Ia) iid. We now extend the convergence result of [33, Theorem 3.14] obtained in convex setting to the strong convexity at infinity assumption. To that end, we observe that the 27 verifies equation (2) with the drift (0(y)
shadow sequence Y3 = Xx - -Vxx(((Xx)) +
ffly - Gv()) + (v), where G., =y (Ia (x)
Theorem 4. Under Assumption 2-3, of verifies Assumption 1, there exist ÿ > 0 and Cs. Cs. C7 e R2 such that Vy E (0, the shadow sequence Yt has an invariant law fhy and vk E N, the distribution Px, of Xx defined in equation (14) verifies
Wplpx, My) Csr + Coy + CT 111,, Prox (os()))
Theorem 4 is proved in Appendix G.4 by reformulating inexact PSGLA two-point algorithm and applying Theorem 3. Theorem 4 states that approximations in the proximal operator evaluation do not accumulate and imply quantified shift in the PSGLA law Px.-
4 Related Works
An alternative method to sample composite potential is Gibbs sampling that have been developed in [38, 88). Gibbs sampler splits the sampling problem into two easier sampling sub-problems. More recently, the authors of [94, 17, 60] propose Gibbs sampler that, combined with deep learning, provides accurate sampling. However their theoretical guarantees are only developed in the convex setting. A non-convex proof of a coarse Gibbs algorithm, without annealing, is proposed in [89].
For image applications, diffusion models [87] are another recent strategy to sample a law with convergence guarantees [11, 22]. Many works have focused on adapting diffusson models for image posterior sampling, see for instance [54, 15, 14, 82, 101]. However, our knowledge, there is no drift stability results have been shown in this setting, therefore preventing the establishment of con- vergence results for posterior sampling. More details on related works are provided in Appendix A.
Application to posterior sampling
Recovering a signal E Rd from degraded observation of this signal E Rm with typically m < d, is called inverse problem. many settings, degradation model given, i.e. y = A(xx) +n, with some noise. Even though our approach is not limited to this setting, for the sake of simplicity, in this section we will focus on the linear inverse problem = Ar + n with A E gmdd and additive Gaussian noise (0, o² La).
In a Bayesian paradigm, we suppose that x is a realization of random variable having the density p(z), called prior distribution. Then, we aim to sample the distribution p(zly). called posterior distribution. The Bayes formula gives that p(xly) x p(y)=)p(z) and the physical model implies
that p(y(z) e d ||A By denoting f(z) 1 212 and g(z) = -lgg(()), we get that
p e V(s)
with V = f + composite potential. Thus, we can use inexact ULA (2) (with b = V + Vg) or PSGLA (3) (with V and Prox.g)), to sample this posterior distribution.
Plug-and-Play Sampling the posterior distribution is challenging task as it can be high dimen- sion problem (e.g. image inverse problems) as the prior distribution p(æ) often unknown. There- fore, it is not possible to compute V Prox The authors of [92] proposed to replace Prox. by
7

---

PHP-ILA
Figure I: Posterior Sampling with PnP-ULA (top row) and PSGLA (boltow row) with three different Gaussian Mixture prior distributions (in blue) and three observations (in red) leading to three pos- terior distributions (in black, mode probabilities are represented by transparency). Algorithms are run with 10, 000 steps. Quantitative metrics, discrete Wasserstein distance and L2 distance between the estimated density and the true density, computed for each algorithm output. The Wasserstein distance during the iterations (right column) is averaged between the three experiments. Note that PnP-PSGLA succeeds sample the posterior distribution even if there are various modes and the convergence is faster than PnP-ULA.
a pretrained denoiser D yT. learnt to remove additive Gaussian noise standard-deviation v > 0. In fact, (r) = arg min yeR 2y | yl + s(y) is the maximum-a-posteree denoising with noise level /7 and prior distribution e e Replacing Prox-g by pretrained denoiser D DV is called Plug- Plug-and-Pa aaa--anddayyyyy Play (PnP) and D implicitly encodes the prior knowledge.
We thus introduce the PnP-PSGLA algorith algorithm defined by
Xx+1 = DVr Xx A (X(x)) 2272x+1)
(15)
with À a regularization parameter. DVv a pre-trained denoiser of noise-level V and Z (O, La). This parameter can be seen as temperature parameters by replacing the prior p by 'p which leads to sample a distribution proportional to e / instead of e This parameter allows more flexibility practice to improve PnP-PSGLA performance. Note that at each iteration, inject /2 times more noise than we denoise; therefore,
expect the algorithm explore the space. If we injected as much noise as we denoise, we would expect the algorithm to behave like stochastic optimization method rather than sampling algorithm as detailed in [58, 76, 77].
6 Experiments
In this section, we present numerical validation of PnP-PSGLA (15) for posterior sampling, More details and additional experiments are provided in Appendix C.
Gaussian Mixture in 2D In order to test experimentally the quality of PnP-PSGLA, compared to PnP-ULA [59], we first look at a simplified case with a Gaussian Mixture prior in 2D. PnP-ULA is a Plug-and- version of the ULA (10). In this case, the posterior distribution, Vg and the MMSE denoiser can be written in closed form. Therefore,
and compare the sampling algorithms PnP-PSGLA and PnP-ULA with the exact prior information.
As illustrated in Figure 1, PnP- -PGLA outperforms PnP-ULa both quantitatively and qualitatively on this Gaussian mixture problem. More precisely, PnP-ULA fails discover minor modes of the posterior distribution in N 10* steps, whereas PnP-PSGLA successfully identifies them. Our experiments suggest that the mixing time of PnP-PSGLA shorter than for PnP-ULA. the proximal operator is interpreted as a projection operator, PnP-PSGLA rigidly project the iterates on the "clean data" manifold, whereas PnP-ULA softly guides the iterates. This might help PnP- PSGLA to discover modes faster that PnP-ULA.

---

Ground Truth
Observation
DIMPIR
PnP ULA
PmP-PSGLA TV
PoP-A DACNN
PSNR SSIM
720000
30. 1 7/0.90
96/0.99
28. 78.09/0.91
29.91/0.93
Figure 2: Qualitative result for image inpainting with 50% masked pixels and a noise level of a 1/253. PnP-ULA is run with 1,000,000 iterations and PSGLA with 10,000 iterations.
Algorithm DifPIR [101]
Denoiser
PSNR
SSIM f
LPIPS 4
N 1
time (s) 1
convergent
GSDRUNet
29.99
0.88
0.06
20
1
X
RED [81]
DaCNN
30.49
0.89
0.06
500
RED [81]
GSDRUNet
29.26
0.88
0.12
500
20
PnP [92]
DaCNN
30.50
0.91
0.06
S00
6
PnP [92]
GSDRUNet
30,52
0.92
0.07
500
20
PnP-ULA [59]
DrCNN
27.89
0.82
0.12
100,000
1,200
PnP-PSGLA [33]
TV
29.24
0.89
0.08
1,000
25
PaP-PSGLA
D&CNN
30.81
0.92
0.05
10,000
Table 2: Quantitative results for image inpainting with 50% masked pixels on CBSD68 dataset. The
number inference of the denoiser N and the time of restoration in second on one GPU NVIDIA A100 Tensor Core are given for one image. Best and second best results respectively displayed in bold and underlined. Note that PaP-PSGLA (15) has comparable performances with state-of-the art methods DiffPIR and PnP and is significantly faster that PnP-ULA.
Image restoration with Plug-and-Play approach We use the Denoising Convolutional Neural Network (DnCNN) denoiser proposed by the authors of [71] and trained to be firmly non-expansive
This denoiser has been trained for level of noise //7 2/255, which fixes the step-size ? of PSGLA. We also considered the proximal deep neural network denoiser of [48], based on the DRUNet architecture [99]. Interestingly. we found that the choice of denoiser greatly influences the quality of the result. As DnCNN provided much better results than DRUnet we consistently use this architecture and report DRUNet restoration results Appendix C.2.1.
In Figure 2, we present restorations with different methods and denoisers. DifiPIR [101] is a innfpieoo-innspredd algorithm restore images. It uses the denoiser with various noise levels, ex- cluding the use of the DrCNN network [71] trained with only one level of noise. Plug-and-Play Unajusted Langevin Algorithm (PиP-ULA) [59] is a Plug-and-Play adaptation of the Unajusted Langevin Algorithm (10) that is proved to sample the posterior distribution. PnP-PSGLA is run with two denoisers. The Total Variation (TV) denoiser [83] is classical denoising method that leads to staircasing effects and over-smoothe, the denoised image. We use TV-denoiser as baseline with limited computational time. PnP-PSGLA run with the DnCNN denoiser proposed by [71] to improve the restoration quality. Note that PnP-PSGLA, when run with DnCNN, achieves good perceptual quality using 100 times fewer steps than PnP-ULA. We again interpret this acceleration by the ability of PnP-PSGIAA to rigidly project the iterates whereas PnP-ULA softly guides them.
present quantitative comparisons between various restoration methods on the CBSD68 dataset [64]. Results are presented with two distortion metrics, Peak Signal to Noise Ratio (PSNR) and Structural Similarity (SSIM) [95], and one deep perceptual metric, Learned Per- ceptual Image Patch Similarity (LPIPS) [100]. Regularization by Denoising (RED) [81] and Plug- and-Play (PnP) [92] are restoration algorithms that solve an optimization problem to find the most probable image knowing the degraded observation. The Gradient-Ster Step DRUNet (GSDRUNet) [47] denoiser, based on the DRUNet architecture [99], is a deep neural network denoiser that ensures convergence for RED and PnP algorithms. For PnP-ULA and PnP-PSGLA, the mean of the iter- ates taken as an estimator of the expectation of the posterior distribution. Note that PnP-PSGIAA with DnCNN achieves performances that are competitive with sfate-of-ther the-art methods. Moreover,
On Table 2,

---

the PnP-PSGLLA achieves better performances that PnP-ULA in less iterations. PnP-PSGLLA with DrCNN requires more computational resourees than DifiPIR, PnP or RED. Using the TV-denoiser is an alternative to accelerate PNP-PSGLA at the expense of visual performance.
7 Conclusion
In this paper, aim to sample distribution e-V with non-convex potential V. We improve existing results for the stability (Theorem in Section 2) and the discretization error (Theorem 2 in Section 2) of iULA (2). We use these results derive the first convergence proof of PSGLA (3) for non-log-concave sampling (Theorem 3 in Section 3). We apply our theoretical findings to posterior sampling and show the experimental benefit, especially in computational time, of PSGLA with respect to the original iULA. We also propose a Plug-and-Play version of PSGLA (PnP-PSGLA) that achieves state-of-the art image restoration.
PnP-PSGLA is limited by its computational time, as is the case with most Markov Chain Monte Carlo (MCMC) methods. Annealing methods [89] directions for future works to reduce the computational time of PnP-PSGLA. From a theoretical point of view, identify two main limitations of this work that might motivate future research. The first one is to obtain theoretical insights, such as accelerated convergence rate, of the superiority of PSGLA over ULA. The second one is to analysis the tightness of the constants involve in Theorem 1- 2 that are partially implicit in the current work. Convergent posterior sampling algorithms could have a positive societal impact by providing image restoration with quantified uncertainty. Also, such deep image restoration algorithm could also have negative societal impacts as it may hallucinate details and might be used generate false information.
efficient denoisers could offer promising
Acknowledgements
This study has been carried out with financial support from the French Direction Générale de I' I'Armement and the French National Research Agency through Projects PEPR PDE-AL, ANR-19- CE40-005 MISTIC and ANR-23-CE40-0011 SOCOT. Experiments presented this paper were car- ried out using the PlaFRIM experimental testbed, supported by Inria, CNRS (LABRI and IMB), Uni- versité de Bordeaux, Bordeaux INP and Conseil Régional d' Aquitaine (see
We thank Andrés Almansa, Pascal Bianchi, Kaplan Desbouis, Gersende Fort, Erell Gachon, Julien Hermant, Samuel Hurault, Rémi Laumont, Éloan Rapion and Adrien Richou for their time and discussions.
References
[1] Patrice Abry, Gersende Fort, Barbara Pascal, and Nelly Pustelník. Credibility intervals for the reproduction number of the Covid-19 pandemic using proximal Langevin samplers. In 31th Earopean Signal Processing Conference (EUSIPCO), 2023.
[2] Guillaume Alain and Yoshua Bengio. What regularized auto-encoders learn from the data- generating distribution. The Journal of Machine Learning Research, 15(1):3563-3593, 2014.
[3] Heinz H Bauschke, Patrick Combettes, Heinz Bauschke, and Patrick L. Combettes. Cor- rection to: convex analysis and monotone operator theory in Hilbert spaces. Springer, 2017.
[4] Matej Benko, Iwona Chlebicka, Jorgen Endal, and Blažej Miasojedow. Langevin Monte Carlo beyond Lipschitz gradient continuity. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 15541-15549, 2025.
[5] Espen Bernton. Langevin Monte Carlo and JKO splitting. In Conference on Learning Theory, pages 1777-1798. PMLR, 2018.
[6] Radu Ioan Bot and Axel Böhm. Alternating proximal-gradient steps for (stochastic) nonconvex-coneave minimax problems. SIAM Journal on Optimization, 2023.
10

---

[7] Nicolas Brosse, Alain Durmus, Éric Moulines, and Marcelo Pereyra. Sampling from log- concave distribution with compact support with proximal Langevin Monte Carlo. In Confer- ence on Learning Theory, pages 319-342. PMLR, 2017.
[8] Nicolas Brosse, Alain Durmus, Éric Moulines, and Sotirios Sabanis. The tamed unadjusted Langevin algorithm. Stochastic Processes and their Applications, 129(10):3638-33)) 3663,, 2019.
[9] Sebastien Bubeck, Ronen Eldan, and Joseph Lehec. Finite-time analysis of projected Langevin Monte Carlo. Advances in Neural Information Processing Systems, 28, 2015.
[10] Olivier Cappé, Simon J Godsill, and Eric Moulines. An overview of existing methods and recent advances in sequential monte carlo. Proceedings of the IEEE, 95(5):899-924, 2007.
[11] Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. arXiv preprint 22X1:2220.112155 2022.
[12] Xiang Cheng and Peter Bartlett. Convergence of Langevin MCMC in KL-divergence. In Algorithmic learning theory, pages 186-211. PMLR, 2018
[13] Sinho Chewi, Murat A Erdogdu, Mufan Li, Ruoqi Shen, and Shunshi Zhang. Analysis of Langevin Monte Carlo from Poincare to Log-Sobolev. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceed- ings of Machine Learning Research, pages 1-2. PMLR, 02-05 Jul 2022.
[14] Hyungjin Chung and Jong Chul Ye. Score-based diffusion models for accelerated mri. Med- ical image analysis, 80:102479, 2022.
[15] Hyungjin Chung, Jeongsol Kim, Michael Thompson Mccann, Mare Louis Klasky, and Jong Chul Ye. Diffusion posterior sampling for general noisy inverse problems. In The Eleventh International Conference on Learning Representations, 2022.
[16] Frank H Clarke. Nonsmooth analysis and optimization. In Proceedings of the international congress of mathematicians, volume 5, pages 847-853. Citeseer, 1983.
[17] Florentin Coeurdoux, Nicolas Dobigeon, and Pierre Chainais. Plug-and-pla split gibbs sam- pler: embedding deep generative priors in bayesian inference. IEEE Transactions on Image Processing, 2024.
[18] Michael Crandall, Hitoshi Ishii, and Pierre-Louis Lions. User's guide to viscosity solutions of second order partial differential equations. Bulletin of the American mathematical society, 27(1): 1992.
[19] Francesca R Crucinio, Alain Durmus, Pablo Jiménez, and Gareth O Roberts. Optimal scaling results for Morcau-Yosida Metropolis-adjusted Langevin algorithms. Bernoulli, 1188):1889- 1907, 2025.
[20] Amak Dalalyan and Avetik Karagulyan. User-friendly guarantees for the langevin monte carlo with inaccurate gradient. Stochastic Processes and their Applications, 129(12))527- $311,2019
[21] Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):007-339 2019.
[22] Valentin De Bortoli. Convergence of denoising diffuusinn models under the manifold hypoth- esis. Transactions on Machine Learning Research, 2022.
[23] Valentin De Bortoli and Alain Durmus. Convergence of diffusions and their discretizations: from continuous to discrete processes and back, 2019. URL. https://arxii www.aiiww.................oowwot org/abs/ abs/ 1904. 09808.
[24] Amaud Debussche, Ying Hu, and Gianmario Tessitore. Ergodic bsdes under weak dissipative assumptions. Stochastic Processes and their applications, 127 2011.
11

---

[25] Charles-Alban Deledalle, Loic Denis, Sonia Tabti, and Florence Tupin. Mulog, or how to apply gaussian denoisers multi-channel sar speckle reduction? IEEE Transactions on Image Processing, (6(9):4389-4400) 2017.
[26] Randal Douc, Eric Moulines, Pierre Priouret, Philippe Soulier, Randal Douc, Eric Moulines, Pierre Priouret, and Philippe Soulier. Markov chains: Basic definitions. Springer, 2018.
[27] Alain Durmus and Eric Moulines. Nonasymptotic convergence analysis for the unadjusted Langevin algorithm. The Annals of Applied Probability, 2017.
[28] Alain Durmus, Eric Moulines, and Marcelo Pereyra. Efficient bayesian computation by prox- imal markov chain monte carlo: when langevin meets moreau. SIAM Journal on Imaging Sciences, 11(1):73-556, 2018.
[29] Alain Durmus, Szymon Majewski, and Blažej Miasojedow. Analysis of Langevin Monte Carlo via convex optimization. Journal of Machine Learning Research, 20(73):1 2019.
[30] Andreas Eberle. Reflection couplings and contraction rates for diffusions. Probability theory and related fields, 166:851-886 2016.
[31] David A Edwards. On the kantorovich-rubinet theorem. Expositiones Mathematicae, 29 (4):387-398, 2011.
[32] Bradley Efron. Tweedie's formula and selection bias. Journal of the American Statistical Association, 106(496);1602-66144 2011.
[33] Matthias J Ehrhardt, Lorenz Kuger, and Carola-Bibiane Schönlieb. Proximal Langevin sam- pling with inexact proximal mapping. SIAM Journal on Imaging Sciences, 17(3)1729-1760. 2024.
[34] Paula Cordero Encinar, Francesca R Crucinio, and O Deniz Akyildiz. Proximal interacting particle langevin algorithms, 2024. URL ptattts:///rxivv org/ abs aaa/a/as////60 14292.
[35] Rémi Flamary. Nicolas Courty, Alexandre Gramfort, Mokhtar Alaya, Aurélie Boisbunon, Stanislas Chambon, Lactitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, et al. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1-8, 2021.
[36] Gersende Fort, Barbara Pascal, Patrice Abry, and Nelly Pustelnik. Covid19 reproduction number: Credibility intervals by blockwise proximal monte carlo samplers. IEEE Transac- tions on Signal Processing, 71:888-900 2023.
[37] Anne Gagneux, Mathurin Massias, Emmanuel Soubies, and Rémi Gribonval. Convexity in ReLU Neural Networks: beyond ICNNs?, 2025. URL https://arzie: aarziv.org/abs/25500 03017.
[38] Stuart Geman and Donald Geman. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Trunsactions on puttern analysis and machine intelligence, 1984.
[39] Wally R Gilks, Nicky G Best, and Keith KC Tan. Adaptive rejection metropolis sampling within gibbs sampling. Journal of the Royal Statistical Society Series C: Applied Statistics. 44(4):455-472, 1995.
[40] Alexis Goujon, Sebastian Neumayer, and Michael Unser. Learning weakly convex regulariz- ers for convergent image-reconstruutton algorithms. SIAM Journal on Imaging Sciences, 17 (1):91-115, 2024.
[41] Rémi Gribonval and Mila Nikolova. A characterization of proximity operators. Journal of Mathematical Imaging and Vision, 62(6):773-789 2020.
[42] Bichuan Guo, Yuxing Han, and Jiangtao Wen. Agem: Solving linear inverse problems via
deep priors and sampling. Advances in Neural Information Processing Systems, 32, 2019.
[43] Wei Guo, Molei Tao, and Yongxin Chen. Provable benefit of annealed Langevin Monte Carlo for non-log-concave sampling. International Conference of Learning Representation, 2025.
12

---

[44] Mert Gurbuzbalaban, Yuanhan Hu, and Lingjiong Zhu. Penalized overdamped and under- damped langevin monte carlo algorithms for constrained sampling. Journal of machine learn- ing research, 25(263):1-67, 2024.
[45] Jean-Baptiste Hiriart-Urrut and Claude Lemaréchal. Convex analysis and minimization al- gorithms I: Fundamentals, volume 305. Springer science & business media, 1996.
[46] Tim Hoheisel, Maxime Laborde, and Adam Oberman. On proximal point-type algorithms for weakly convex functions and their connection the backward euler method. Optimization Online, 2010.
[47] Samuel Hurault, Arthur Leclaire. and Nicolas Papadakis. Gradient step denoiser for con- vergent houg-and-paay International Conference on Learning Representations (ICLR'22) 2022.
[48] Samuel Hurault, Antonin Chambolle, Arthur Leclaire, and Nicolas Papadakis. Convergent plug-and-play with proximal denoiser and unconstrained regularization parameter. Journal of Mathematical Imaging and Vision, pages 1-23, 2024.
[49] Tim Johnston, losif Lytras, Nikolaos Makras, and Sotirios Sabanis. the unadjusted langevin algorithm without smoothness assumptions. arXiv preprint arXiv:2502.0345 034458 2025.
The performance
[50] Valdines Leite de Sousa Junior, Lucas Vidal de Meireles, Samara Costa Lima, and Gilson do Nascimento Silva. Local convergence of an inexact proximal algorithm for weakly convex functions, 2023. URL https: //avivv///ii/i//// org/ hts///bb/230..... 02014.
[51] Zahra Kadkhodaie and Eero Simoncelli. Stochastic solutions for linear inverse problems using the prior implicit in denoiser. Advances in Neural Information Processing Systems, 34:13242-13254 2021.
[52] Leonid Vasilevich Kantorovich and SG Rubinshtein. On a space of totally additive functions. Vestmik of the St. Petersburg University: Mathematics, 13(7):52-59, 1958.
[53] Ioannis Karatzas and Steven Shreve. Brownian motion and stochastic calculus, volume 113. Springer Science & Business Media, 1991.
[54] Bahjat Kawar, Michael Elad, Stefano Ermon, and Jiaming Song. Denoising diffusion restora- tion models. Advances Neural Information Processing Systems, 35:235933 2022.
[55] Teresa Klatzer, Paul Dobson, Yoann Altmann, Marcelo Pereyra, Jesús María Sanz-Serna, and Konstantinos C Zygalakis. Accelerated Bayesian imaging by relaxed proximal-pon Langevin sampling. SIAM Journal on Imaging Sciences, 17()) 2024.
[56] Andrew Lamperski. Projected stochastic gradient Langevin algorithms for constrained sam- pling and non-convex learning. In Conference Learning Theory, pages 2891-2937. PMLR, 2021.
[57] Robert Lang. A note on the measurability of convex sets. Archiv der Mathematik, 47:90-92, 1986.
[58] Rémi Laumont, Valentin De Bortoli, Andrés Almansa, Julie Delon, Alain Durmus, and Marcelo Pereyra. On maximum posteriori estimation with plug & play priors and stochastic gradient descent. Journal of Mathematical Imaging and Vision, 65(1):140-163, 2023.
[59] Rémi Laumont, Valentin De Bortoli, Andrés Almansa, Julie Delon, Alain Durmus, and Marcelo Pereyra. Bayesian imaging using Plug & Play Priors: When Langevin meets Tweedie. SIAM Journal on Imaging Sciences, (512)
[60] Jiaming Liang and Yongxin Chen. A proximal algorithm for sampling from non-smooth potentials. In 2022 Winter Simulation Conference (WSC), pages 3229 -2400, 2022.
[61] Robert Liptser, Albert Nikolaevich Shiriaev, and Albert N Shiryaev. Statistics of random processes: I. General theory, volume 1. Springer Science & Business Media, 2001.
13

---

[62] Pierre- Yves Madec. Ergodic bsdes and related pdes with neumann boundary conditions under weak dissipative assumptions. Stochastic Processes and their Applications. 125(5):1821- 1860, 2015.
[63] Xuerong Mao. Stochastic differential equations and applications. Elsevier, 2007.
[64] David Martin, Charless Fowlkes, Doron Tal, and Jitendra Malik. A database of human seg- mented natural images and its application to evaluating segmentation algorithms and measur- ing ecological statistics. In Proceedings eighth IEEE international conference on computer vision. ICCV 2001, volume 2, pages 416-423. IEEE, 2001.
[65] Jean-Jacques Moreau. Proximité et dualité dans un espace hilbertien. Bulletin de la Société mathématique de France, 93:273-299 1965.
[66] Jean Jacques Moreau. Inf-convolution, sous-additivité, convexité des fonctions numériques. Journal de Mathématiques Pures el Appliquées, 1970.
[67] Wenlong Mou, Nicolas Flammarion, Martin Wainwright, and Peter Bartlett. Improved bounds for discretization of Langevin diffusions: Near-optimal rates without convexity. Bernoulli, 2873):15771601, 2022.
[68] Dao Nguyen, Xin Dang, and Yixin Chen. Unadjusted langevin algorithm for non-convex weakly smooth potentials, 2021. URL https: http:://axxvvvvoo wrg/ abs/ 06369.
[69] Nina Ovcharova. Second-order analysis of the moreau yosida and the lasry lions regulariza- tions. Optimization Methods & Software, 25(1): 116, 2010.
[70] Marcelo Pereyra. Proximal markov chain monte carlo algorithms. Statistics and Computing, 26:745-760, 2016.
[71] Chan-Chrittophe Pesquet, Audrey Repetti, Matthieu Terris, and Yves Wiaux. Learning max- imally monotone operators for image recovery. SIAM Journal on Imaging Sciences, 14(3): 1206-1237, 2021.
[72] Natesh S Pillai. Optimal scaling for the proximal Langevin algorithm in high dimensions. Journal of Machine Learning Research, 25 2024.
[73] Roland Potthast. A survey on sampling and probe methods for inverse problems. Inverse Problems, 22(2):R1, 2006.
[74] Miklós Rásonyi and Kinga Tikosi. On the stability of the stochastic gradient Langevin algo- rithm with dependent data stream. Statistics & Probability Letters, 182: 2022.
[75] Marien Renaud, Jiaming Liu, Valentin De Bortoli, Andrés Almansa, and Ulugbek S Kamilov. Plug-and-pla, posterior sampling under mismatched measurement and prior models. The Twelfth International Conference on Learning Representations, 2023.
[76] Marien Renaud, Jean Prost, Arthur Leclaire, and Nicolas Papadakis. Plug-and-play image restoration with Stochastic deNOising REgularization, Forty-first International Conference on Machine Learning, 2024.
[77] Marien Renaud, Julien Hermant, and Nicolas Papadakis. Convergence analysis of proximal stochastic denoising regularization algorithm. In International Conference on Scale Space and Variational Methods in Computer Vision, pages 17-29. Springer, 2025.
[78] Gareth O Roberts and Osnat Stramer. Langevin diffusions and Metropolis- Metropolis-Hasttnns algo- rithms. Methodology and computing in applied probability, 4:337-357, 2002.
[79] Gareth Roberts and Richard L Tweedie. Exponential convergence of Langevin distributions and their discrete approximations. Bernoulli, pages 341-363, 1996.
[80] R Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Sci- ence & Business Media, 2009.
J-B
14

---

[81] Yaniv Romano, Michael Elad, and Peyman Milanfar. The little engine that could: Regular- ization by denoising (red). SIAM Journal on Imaging Sciences, 10(4):1804-1844 2017.
[82] Litu Rout, Negin Raoof, Giannis Daras, Constantine Caramanis, Alex Dimakis, and Sanjay Shakkottai. Solving linear inverse problems provably via posterior sampling with latent dif- fusion models. Advances in Neural Information Processing Systems, 36:49960-49990) 2023.
[83] Leonid I Rudin, Stanley Osher, and Emad Fatemi. Nonlinear total variation based noise removal algorithms. Physica D: nonlinear phenomena, 60(1-4):259-266 1992.
[84] Adil Salim and Peter Richtarik. Primal dual interpretation of the proximal stochastic gradient langevin algorithm. Advances in Neural Information Processing Systems, 13:3786-37999 2020.
[85] Adil Salim, Dmitry Kovalev, and Peter Richtárik. Stochastic proximal Langevin algorithm: Potential splitting and nonasymptotic rates. Advances in Neural Information Processing Sys- tems, 32, 2019.
[86] Zakhar Shumaylov, Jeremy Budd, Subhadip Mukherjee, and Carola-Bibiane Schönlieb. Weakly convex regularisers for inverse problems: Convergence of critical points and primal- dual optimisation. Forty-first International Conference on Machine Learning, 2024.
[87] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
[88] D Andersen Sorensen, S Andersen, D Gianola, and I Korsgaard. Bayesian inference in thresh- old models using gibbs sampling. Genetics Selection Evolution, 27(3):229-22) 249, 1995.
[89] Yu Sun, Zihui Wu, Yifan Chen, Berthy Feng, and Katherine Bouman. Provable prob- abilistic imaging using score-based generative priors. IEEE Transactions on Computational Imaging, 2024.
[90] J Tachella, D Chen, S Hurault, M Terris, and A Wang. Deepinverse: A deep learning frame- work for inverse problems in imaging. url: https://deepiny github. io/deepinv 2023.
[91] Aki Vehtari, Daniel Simpson, Andrew Gelman, Yuling Yao, and Jonah Gabry. Pareto smoothed importance sampling. Journal of Machine Learning Research, 25(7)):1-58, 2024.
[92] Singanallur V Venkatakrishnan, Charles A Bouman, and Brendt Wohlberg. Plug-and-play priors for model based reconstruction. In 2013 IEEE global conference on signal and infor- mation processing, pages 945-948. IEEE, 2013.
[93] Cédric Villani et al. Optimal transport: old and new, volume 338. Springer, 2008
[94] Maxime Vono, Nicolas Dobigeon, and Pierre Chainais. Split-and-augmented gibbs sam- pler-application to large-scale inference problems. IEEE Transactions on Signal Process- ing, 67(6)) 2019..
[95] Zhou Wang, Alan C Bovik, Hamid R Sheikh, and Eero P Simoncelli. Image quality assess- ment: from error visibility to structural similarity. IEEE transactions on image processing. (3(4):600-612, 2004.
[96] Deliang Wei. Peng Chen, and Fang Li. Learning pseudo- contractioeeeeeeeeeeeeeeeeeeeeee denoisers for inverse problems. In Forty-first International Conference on Machine Learning, 2024.
[97] Andre Wibisono. Sampling as optimization in the space of measures: The Langevin dynamics as composite optimization problem. In Conference on Learning Theory, pages 2093-3027. PMLR, 2018
[98] Kaylee Yingxi Yang and Andre Wibisono. Convergence of the inexact Langevin algorithm and score-based generative models in KI. divergence. NeurIPS 2022 Workshop on Score- Based Methods, 2022.
15

---

[99] Kai Zhang, Yawei Li, Wangmeng Zuo. Lei Zhang, Luc Van Gool, and Radu Timofte. Plug- and-play image restoration with deep denoiser prior. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(10))6300-633 6376, 2021.
[100] Richard Zhang, Phillip Isola, Alexei A Efros, Eli Shechtman, and Oliver Wang. The unrea- sonable effectiveness of deep features as perceptual metric. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 586-595, 2018.
[101] Yuanzhi Zhu, Kai Zhang, Jingyun Liang, Jiezhang Cao, Bihan Wen, Radu Timofte, and Luc Van Gool. Denoising diffusion models for blug-and-pla image restoration. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1219- 2023.
Appendix
In the Appendix, provide all the proof for the theoretical results of the paper, additional details on experiments and more intuition on the theoretical objects that appears in the paper. In Appendix A, detail related works on Langevin MCMC with a focus on Proximal Langevin methods. In Ap- pendix B, we discuss each assumptions in details. In Appendix C, we provide additional experiments and implementation details. In Appendix D. we give self-contained analysis of the Moreau enve- lope in the weakly convex setting. In Appendix E, we discuss our notion of strong convexity on non-convex sets. In Appendix F, we prove all the results of Section 2 and give intuition on Markov Chain and Markoc Process analysis. In Appendix G, we prove the convergence results of Section 3 for PSGLA.
A Related works
In this part, detail related works Langevin Diffusion with focus methods involving proximal steps.
On the stability of inexact Unajusted Langevin Algorithm The authors of [98] study the stabil- ity of inexact Unajusted Langevin Algorithm (iULA defined in equation (2)) with respect to the KL divergence. This study can be seen complementary to analysis developed in p- Wnssersstein and Total Variation distance. Note that our strategy does not generalize easily to KL divergence as it relies massively on the triangle inequality that is verified by the KL divergence. The proof strategy of [98] relies on the log-Sobolev inequality for the potential V and bounds between the inexact drift b and VV making this stability analysis less general than our analysis. The stability of iULA has been analysed in the same setting than ours by the authors of [75]. However, their stability analysis is only provided in the 1-Wasserstein and Total Variation distances, and yields coarser bound than Theorem 1, which in particular implies discretization error.
PnP-ULA
The authors of [59] propose a Plug-and- Play strategy based on inexact ULA and the Tweedie formula [32], named PnP-ULA, and defined by
X = Xs - (X)()) 7r (Xx - D.(X.)) 7 (X₂ Ig( - - 22 Z
(16)
a
with Zo+1 ~ NNOO, D. a pretrained denoiser of noise-level e > O, IIs the projection on the convex set S C. IRd and X > O the regularization weight. The term 2/ (X₂ Dx is used to encode the prior information. The projection term (X₂ [Is))))). controlled by the weight parameter > 0, added to ensure that the sampled potential is strongly convex at infinity for convergence properties. This Markov Chain has slow mixing time shown on Figure 5 where it needs more than 5.10 10 iterations to converge.
MYULA The authors of [70, 28] propose the Moreau-Yoshice Unadjusted Langevin Algorithm (MYULA) defined by
X Xx -VV(s)) 7 (X, Proxa, (Xx)) + v Zx+1
16

---

to sample e e-f-a* with O² the Moreau transform of g. This algorithm is based the Moreau envelope approximation (see more details Appendix D) to approximate Vg using the proximal operator Prox It is particularly relevant if the proximal operator ! can be computed easily. Contrary to PSGLAA in MYULA, the noise is added outside the proximal operator. Recently the authors of [55] consider algorithms based on MYULA to accelerate Langevin samplers. Note that if pre-trained denoiser is plugged in place the proximal operator, then we recover PnP-ULA.
Gibbs sampling The authors of [94, 17] propose another strategy to sample composite func- tion, named Gibbs sampling. A Gibbs sampler [38, 88] splits the sampling problem into two easier sampling sub-pre cub-problmms. The first sub-prot sub-problem encodes the prior information and the second the degradation model, following the Plug-and-Play idea. However no convergence guarantee given for this algorithm. The authors of [89] propose a similar algorithm with some theoretical results in the non-convex setting. However, they employ annealing techniques, and it is unclear how these af- fect convergence. Finally, the authors of [60] propose another Gibbs sampler and derive convergence guarantees only in the case of convex potentials.
Proximal Langevin Monte Carlo (PLMC) sequence defined by
The authors of [5] study the Proximal Langevin Monte Carlo
X = Prox (Xx) + / 72
to sample e with y convex everywhere. The authors of [4] study the same sequence and focus on developing convergence results beyond the Lipschitz Gradient continuity. PLMC is particular case of MYULA in the case of = y. A Metropolis- Hasting mechanism thas also been proposed in [72, 19] to accelerate PLMC MYULA in the case of convex potentials.
Projected Langevin particular case of PSGLA, where the function g is the characteristic func- tion of convex set K, leads to the projected Langevin algorithm defined by
X ( 7 (Xx)) + (2,7
which was introduced over a decade ago [9, 44J. This paper studies the convergence in the log- concave setting, i.c. if the potential f is convex. The author [56] studies a generalization this algorithm when ff is estimated randomly. In this paper, convergence guarantees are provided if K is convex and V f is Lipschitz and perturbed by Gaussian noise.
Symmetrized Langevin Algorithm The Symmetrized Langevin Algorithm (SLA) defined by X Prox.v (X& > VV 24yZx+1) has been proposed by the authors of [97]. This algorithm does not sample from a composite potential, but instead targets the distribution propor- tional to -V This algorithm is studied for the 2- Wasserstein metric in the case of a strongly convex potential V.
The PSGLA (3) was first introduced in [29], with an analysis for strongly convex potentials V = f g. The authors of [85] study a generalization of PSGLA with multiple proximal operators applied in sequence. Their analysis also assume that is strongly con- vex and g convex. Another convergence proof with f strongly convex and convex was derived by making an analogy between PSGLA and the
Other articles on PSGLA
scheme [84]. If the proximal map- ping can only been approximated, the authors of [33] show that the algorithm is stable in the case of convex potentials V. Recently, particle interaction algorithm based on PSGLA has been pro- posed [34] to improve the sampling quality. The convergence of this particle interaction algorithm have been derived in the strongly convex setting.
B Detailed discussion on assumptions
In this section, we discuss in details the different assumptions made in the paper.
Assumption (()) Assumption 1(i) is standard to obtain the existence of the strong solution the stochastic differentiable equation (I), see [53, Theorem 2.5] for instance. It implies
in particular that the drift b is sub-linear, i.e. there exists [[b(z)]] < [|B(0]] + L||-//|-
Moreover, if b = VV, the potential V T.-weakly convex. Assumption 1(i) is equivalent to - LLa = bb Lla.
17

---

Assumption 1(i). It is called weak dissipativity [24, 62] or distant dissipativity [67] in the stochastic differentiable equation community. In order to have a geometric ergodicity of the Markov Chain, it is necessary to control the drift in the tails of the sampled distribution. Assumption 1(i)) is a relaxation of the strong convexity of b that allows to control the behavior of the MCMC at infinity. In particular, having form of strong convexity at infinity the drift, with Assumption I ensures that the MCMC is bounded and has all its moments bounded [23, 59]. If the drift is m-strongly convex at infinity and L-weakly convex then it is weakly dissipative.
Assumption 2()). It is verified for convex functions f such as negative log- bog-likelihood terms associated to linear inverse problems with additive Gaussian noise (xx = || Ar - y/l² or non-convex f. as it is the case in image despeckling [25] or black-hole interferometric imaging [89]. This condition is standard in posterior sampling [59, 75, 55] or in imaging inverse problems [76, 96].
Assumption 2(ii). Many works have focused on convex regularizations [83, 71, 37.. How- ever, it is known that the non-convexity allows to made better restoration [47]. There- fore, we only assume in this paper that the regularization is p p-weakly convex. It ensures that the proximal operator Proxkg is defined for pp 1. Assumption 2(ii) is then veri- fied for all convex regularization and some state-of-the art deep neural networks regulariz- ers [71, 47, 86, 40].
Assumption 3()). Assumption 3()) can be verified by non-smooth functions g such as the characteristic function of convex set. It is not usual to assume that the function which is proximal operator is smooth on subset of Rdd [84, 29, 33]. However, the Moreau envelope study leads naturally to look at the behavior of on the set Prox(IR") as detailed Appendix D.7. Moreover, the deep neural network denoiser proposed in [48] has been demonstrated to verify Assumption 3(i). Assumption 3(i) ensures that the drift b is Lipschitz to verify Assumption 1(i) (based on Lemma in Appendix D.7). Note that Prox 1g (R4) can be non-convex set if is not finite everywhere. However, Proposition 2 in Appendix D.7 shows that Prox (IE)) only differs from being convex by negligible set.
Assumption 3(i)) Assumption 3(ii) implies that the potential V is strongly convex in- finity, which ensures that the drift 6" verifies Assumption (ii). Lemma 16 in Appendix shows that if g is strongly convex infinity and globally smooth, then Assumption 3(i) is verified. Assumption 3(ii) is technical and hard to verify in practice but it is impor- tant to study PSGLA. An alternative to this assumption is modify PSGLA by adding projection term as in [59] leading to the Projected PSGLA
1 Prox-y (Xs- (Xx-TV -V--VV-- 2 (Xx - [x(())) /272x+1). a
with IK the projection on the convex set K C Rd. As detailed in [59, Appendix F.2). by choosing a small enough a > O, this additional projection term ensures that the drift of the shadow sequence of Projected PSGLA ff(y (v)) + Vg + 1 (y - (v) - II (y ~VV verifies Assumption 1(i). Therefore, it is pos- sible to demonstrate the convergence of Projected PSGLA with a small enough parameter a > O without Assumption 3(i). Note that if X is an image, typically in [0. 1]d, then choosing K- = 1-1, 2] as in [59] involves the projection term being rarely activated. How- ever, in this paper, we chose not to modify the PSGLA, so Assumption 3(i)) is necessary.
C More details on experiments
C.1 Experiments with Gaussian Mixture prior in 2D
We suppose that the prior is a Gaussian Mixture, that can be expressed as
p(x) = Σ P. Et).
18

---

with (a; m., 2.)
(2 (x-m=)) 2, (x-mi) and Σ; E I symmetric positive-
(2m
definite covariance matrixcovariance matrix, my E I the mean of the distribution and p; E [0, the mode weights, such that Ei=
Then the gradient of the log prior is
DE P. - Ma)) 2.) Di=1 P.NP mi; mi, Ex)
V logp(x)
Thanks to the Tweedie formula [32], the Minimum Mean Square Error (MMSE) denoiser D. can be computed by
De(x) V (x)
with the noise level and p. = p=== PO, (2)) the convolution between p and the centered Gaussian kernel (0, e0 Ta).
Due to the specific form of p. we know that
V Vlogp((>) D ( m: Ma,) Ei 2e
DiN m;, Eg + (2Ta)
Thus the closed-form expression of the MMSE denoiser
De = x Di P (x (x, (1; Σ, (()))
m,, E, + ea1a)
For Gaussian Mixture prior, the gradient of the regularization log and the denoiser D. are known in closed-form. Therefore, we can compute PnP-ULA and PnP-PSGLA exactly.
Parameters setting We run PnP-ULA and PnP-PSGLA for 2D denoising problem, i.c. = 2, A 1z and 1. PnP-ULA defined in equation (16) is run with step-size a regularization parameter distribution is log-concave at infinity. Therefore, projection. PSGLA run with a step-size 7 = 0.3 and a regularization parameter À = 0.67. These parameters have been chosen to maximize the performance of each method.
0.1, 1.5 and denoiser parameter e 0.5. In this case, the sampled
choose to set
+o0, i.e. there is
Metrics We compute two quantitative metric between the discrete uniform measure supported on the iterates and the exact posterior. The first one the discrete Wasserstein distance computed using the Python Optimal Transport (POT) library [35]. The second one is the &g distance between the empirical density estimated using Gaussian kernels and the exact posterior density. This l distance is compute on a square including most of the density ([-8, 8]2 in our experiments).
C.2 More details on image restoration experiments
In this section, present details the experiments for image restoration. First recall the definition of each compared method. Then we give the parameters setting and additional exper- iments.
PnP We compare PSGLA into method that are mixing information from learning and the physics of degradation, named Hlu-andd-lay (PnP). This algorithm has been proposed for image restoration by [92] and is defined by
X D. (X+ T((x))
The authors of [71] shows that with a maximal monotone DnCNN denoiser PnP converges. The convergence of this algorithm have been extensively studied, see a detailed review [47, Part 2]. This algorithm have been design to optimize and compute an approximation of the most probable image knowing the degraded observation. Thus, PnP is not sampling the posterior distribution and there is information about uncertainty that can be extracted from this algorithm.
19

---

Parameters
GEDRUNN
RED DeCNN
PnP GSDRUNNT
PAP DOCNN
PRP-DLA A DECNN
ESGLA TV PSGLA DRONN
255
10
70,
156, DOU
0.5
IO
1.10
1.00
Table 3:
Parameters setting for image inpainting for the different implemented methods. is the noise level of the denoiser, the regularization parameter, y the step-size. The parameter settings for PnP-ULA are those suggested in the original paper [59].
RED Another optimization algorithm based mixing prior information and physical information Regularization by Denoising (RED). This algorithm has been proposed for image restoration by [81] and is defined by
X Xx
Dx()))).
The authors of [47] shows that with Gradient-Step denoiser RED converges.
DiffPIR DifPPIR definition is detailed Algorithm 2. This algorithm is based on a diffusion model method applied to image restoration. To our knowledge, no theoretical analysis of this al- gorithm has been provided and it is not clear this algorithm is solving an optimization problem sampling a target law. This algorithm requires denoiser trained with various level of noise. We use the Gradient-Step DRUNet in our experiment with the pre-trained weights provided by the authors of [47]. The precomputed parameters (αε)o<eETT, (o))a<<<T and (Pr)aCtET' set pro- posed in [101]. In our experiments for image inpainting, we set T 1000, ttat 200, = 0.13, < 0.999. These parameters have been chosen after running grid-search to maximize the PSNR on the 3 natural images (butterfly, leaves and starfish) from the set3c dataset [47].
Algorithm 2 DiAPIR [101]
1: input: denoiser D. T" > 0, y E R 0 < tstart < T, C O, (Be)oCreT, A>
2: Initialize Er ,0, La), pre-calculate (ār)octeT, (0t)oceCT and (p:)octsT
3: Fbu.: Vastant/ + /1= Stan
4: for t tstatt tatant
1,..., do
5: z f Do. (xt)
6:
Io + Prox2f6) (x%)
7:
ēt (I:- vāyzu / //I de
8:
6 - C-N00,, Ia)
9: Ih Vārto" + VI - ae (VI- V(a)
end for
Parameters setting In Table 3, we provide the parameter choices used in our experiments for the implemented methods.
Computational time In Table 2, we give the mean computation time to restore one image on a GPU NVIDIA A100 Tensor Core. The total computational time generate this table thus around 27 hours of computational time on a GPU NVIDIA A100 Tensor Core. Note that the PnP-ULA requires most of the computational resources for poor restoration quality. The total computational time for PnP-PSGLA with DnCNN to restore the CBSD68 dataset is 136 minutes. The computa- tional cost of the entire project, including the parameter grid search, has been rigorously com- puted. We estimate it to be around 40 hours of computational time on an NVIDIA A Tensor Core GPU.
On the denoiser choice In this paper, we only use pre-trained denoisers with open-source weights. We focus on a few denoisers that are known be stable and provide good restoration. First the DrCNN with the weights trained by [71] is a maximal monotone operator, thus it is the proxi- mal operator of some convex regularization g. Therefore our theory (Theorem 3) applies with this denoiser. We also run the methods with the Gradient Step denoiser [47], a denoiser based on the DRUNet architecture [99], that known to provide state-of-the-an restoration for Plug-and- Play methods. As this denoiser is trained natural images with various noise level [0, 22)55,
20

---

Ground Truth
Observation
PnP
DiffPIR
PnP-PSGLA
42.670001
MIM
MIKO
8310.21
$7.05/0
29.0.91
40:0.44 S4
9.450.11
31 000 57
29 5010 BT
E1 7140 57
63/0
03
20VO
11 2010.14 14
PA P.0NO 90
P9 20A0.00 B7
F9 AAV 90
53/0.30
33.0.88
Figure 3: Qualitative result for image inpainting with 50% masked pixels and a noise level of a 1/255 with PnP, DifiPIR and PnP-PSGLA methods.
can use it for the DifIPIR algorithm. The open access weights of the DrCNN and the GSDRUNet used in our experiment for natural color images can be found in the library DeepInv [90] in this link. order to reduce the computational time of PnP-PSGLA, we also use the TV denoiser [83]. The Total-Variation regularization has not closed form proximal operator so we use iterative al- gorithm (implemented in the library DeepInv [90]) with 10 inner iterations, which is enough in experiments obtain the best restoration with TV By using such approximation of PnP-PSGLA with the Total Variation denoiser, we recover the restoration algorithm proposed in [33].
C.2.1 Why we not use Prox-DRUNet with PSGLA
Based on the architecture of Gradient-Step DRUNet, the authors of [48] proposed a denoiser that proximal operator. This proximal operator satisfies Assumption 2(ii) and Assumption 3(). The DRUNet architecture [99] is also known to provide state-of-the-art denoiser. Thus Prox- DRUNet seems be ideal denoiser candidate for applying theory and having empirical performances. However, we observe in our experiments some instabilities with the weight provided by the authors [48].
On Figure 4, we observe the restored image and the standard deviation of the Markov Chain run twice on the same observation with two seed in the randomness of the PSGLA. A different area of
21

---

Observation
Seed
Seed 2
Std Seed 1 rançe [0.28, 7.00]
Std Seed 2 range [0.28. 6.39
Ground Truth PSNR SSIM 7
range -0.022 1.01
range
[4 12, 7 71
range (-3 46, 6. 6.74]
72/0 03
20.3 25/35/0.11 75
21, 76/0 75
Figure 4: Restoration of PSGLA with Prox DRUNet for 50% missing pixels and a 1/255. We chose the aggressive parameters e 50/255. stability. PSGLA is run twice on the same observation with two seed in the randomness of the algorithm. Note that the Markov Chain explore outside the image space [0, 1] and the instability depend of the realization of the noise. This algorithm is not stable.
5000 to over-smooth the solution for more
the image is not restored properly and the Markov Chain explores outside the image space [o, 1jd with a large standard deviation in these areas. The mosaic motif that appears may be due to periodic colorization outside [0, 1]d. The fact that the problematic areas depend of the realization of the noise indicates that the issue lies with the instability of the algorithm, not with the conditioning of the target distribution. Then, adding projection in [0, 1] at each iteration of X5 does not prevent from these instabilities. Moreover, these instabilities appear for all the parameters setting that we test in our large grid-search. Finally, compare with DrCNN, trained with fix level of noise, PSGLA with Prox- -RUNet has more parameters to fine-tune. For all these arguments, we chose to not use PSGLA with the Prox-DRUNet denoiser.
C.2.2 PSGLA seems to effectively sample the posterior law
For image inverse problem, as the posterior distribution is unknown, it is not possible to evaluate if an algorithm effectively samples the posterior distribution. A standard strategy [59, 55] to have an indication of the sampling performance of a particular algorithm is to look at the standard-deviation of the Markov Chain.
In Figure 5, we present the mean and the standard deviation of the PSGLA Markov Chain for different numbers of iterations. We observe that when the Markov Chain is too short (N 10*) the mean is relevant but the standard deviation is not informative. On the other hand, when the number of iterations is large (N 10%), the standard deviation is both informative and relevant. One can thus observe that the image edges are more uncertain than uniform areas, such as the sky. The posterior distribution in image inverse problems is known concentrate uncertainty in the edges [59, 55]. This is good indication that the PSGLA might sample the posterior distribution practice. In order to compute relevant uncertainty information, N 10 seems to be a good compromise between computational efficiency and accuracy.
In Figure 6, we show the standard deviation of the MMSE estimator. We observe that the MMSE es- timator has small standard deviation compared with the standard deviation of the PSGLA Markov Chain. Moreover the standard deviation of the MMSE estimator decreases with the number of iter- ations. This observation support the fact the MMSE estimator is deterministic and that the PSGLA effectively solves sampling problem.
C.2.3 PnP-ULA is slow to converge
In Table 2, we observe that the performance of PnP-ULA is significantly lower than that of the other methods. However, the authors of [59, 75] show that PnP- can provide good restoration. This apparent paradox is explained by the fact that PnP-ULA does not succeed to converge in N = 1 iterations. On Figure 5, we observe that the Markov Chain indeed converges in approximately 5. iterations. In order to save computational resources, we choose to not run with such a large number of iterations PnP-ULA on the whole CBSD68 dataset to generate Table 2.
22

---

Std N
Stdl Wim 30"
Std N- 30t
rarou (0.01. 0.39)
Earque (0.01,
Eartaa 10.01
ceriin
POW Se0
BATAMART
PIP
10" 100
101
DO D0000.00
Pri PSS-L
Figure 5: PnP-ULA and PSGLA with DrCNN for 50% missing pixels and 1/255 with various number of iterations N E [10*, 10 10%). The standard deviation of the Markov Chains are shown for each number of iterations and the evolution of the PSNR for N [0, 10%). Note that the PnP- ULA Markov Chain is slow to converge. The effective convergence seems to occur around 5. iterations. Note that the PSGLA Markov Chain seems well explore the posterior distribution as the uncertainty relies on the edges and the background, as the blue uniform sky, is certain.
MMSE Estimator Seed 0, N- 10
MMSE Estimator, 10
MMSE Estimater Seed M- 10
MMSE Estimator, 10 (3.00. 0.02)
Ground Truth
Observation
10.00, 0 0.06)
PSNR SSIM
63
94
Figure 6: PSGLA with DcCNN for 50% missing pixels and a 1/255 with two number of iter- ations N {10*, 10º). We run PSGLA with 100 random seeds in the algorithm randomness for 10 and 10 random seeds in the algorithm randomness for N = 10 on the same observation. We can compute an estimator of the standard deviation of the MMSE estimator. This MMSE re- stored image is expected to be deterministic,
we expect this standard deviation to be significatly smaller than the standard deviation of the Markov Chain itself (see in Figure 5). Note that the stan- dard deviation of the estimator is 10 times smaller than the standard deviation of PSGLA Markoy Chain.
23

---

D On the Moreau envelope for weakly convex function
In this section, recall and detail results the Moreau envelope, also called Moreau-Yosida envelop, in the case of weak convexity. For clarity of this paper, we detail all the proofs. More details on the Moreau envelope of convex function can be found in [80, Part I.G] or [65]; and on the inf-convolution in [66].
All the following results are known by experts in the field. However, to knowledge, there is no reference that states and proves all the results given in this appendix. especially for weakly convex functions. Different proofs can be found in [65, 80, 46, 3, 41, 50]. For simplicity, introduce the Clarke sub-differential [16] which is necessary to analyse the Moreau envelope with non-differentiable functions. Therefore, some of the proofs (Lemma 11 and Lemma 13) only given for differentiable functions, references being given for the general case.
choose not to
D.1 Definitions
We first define the notion of inf-convolution as well as the Moreau envelope. Definition 1.
The inf-convolution between two functions f.g g:::: IRd + R is defined for x E Rd by (f(i)) = inf f(y) + g(x - y);
(17)
yeRd
with the convention (fTg)(z) = -o if the right-hand-a of equation (17) is not bounded from below.
Definition 2. For > O, the Moreau envelope of Rd R. noted 9" is defined for E Rd by
(x) inf 1 yER
g (x)) [ 27
27 | yl + g(u)-
(18)
The Moreau envelope finite on IR if g is p-weakly convex, i.e. > and + 21ll 112 convex, y1 -1 + g(v) is ( -)) strongly convex so admits unique minimum for 7pp < 1. The minimal point is called the proximal point Prox-g (x) = arg min + - y/1² + g The Moreau envelope is an approximation of g in the sense that Vr E Rd, lim g (x) g(x) (see Lemma 2) and it is regularization as g² is differentiable (see Lemma 12) even if is not.
with 7p < 1. In fact, the function + -
D.2 On the dependence of g² in >
The following result shows the monotonicty of g" in and the fact that the Moreau envelope is an approximation g when y +
Lemma 2. If is p-weakly convex and continuous, then for Red, y (0. :) + g²(x) is decreasing and
lim (=x
(19)
7-20
Moreover, 7 E (0, - g(Proxng (z)) is decreasing and
lim ((rox (x)) = g(x).
(20)
7-10
Lemma 2 can been generalized in the case where g is lower semicontinuous instead of continuous.
Proof. We need 7 $ p to ensure that the Moreau envelope well defined. We obtain from the definition of the Moreau envelope (see relation (18)) that + (xx( is decreasing and g² (x) < g(x)). The rest of the proof generalization of [3, Proposition 12.33] in the weakly convex case.
For r,y IRd, we denote by = Prox (x) and, with E (0, 1), Pa = ay + (1 - a)p. By definition of the proximal operator, we have
1
g(p)
||0 pl1 S g(pa) + || Pa 11.
2y
2y
24

---

By the previous inequality and the p-weak convexity of we get
1 | Pax 1
1
g()) S p(pa)= + 2
_ | pll
27
P.y p) + a²
Lgg + (1- a)g(p) + f aa a)lly -pl22
11y pll
2
2
By rearranging the terms, we get
afr - p.y p) S arg(()) -rg(p) 22 + (1)1la))ll pl12
By dividing by and taking - 0, we get
P.y - p) (9(4) 7g(p) + YP 11 p12
2
For p > p 2 7, define q Prox,g (x)). By the same reasoning, have that Vy E Rd.
(x - 4 g) 79(6) 79(4) + p4
2 y - a/1
Taking respectively y g and y = p in the two previous inequalities, we obtain
PP |19 p|1
(q p. - p) S (9(4) (g(p)
(p - q, g) S mg(p) pg(1)) + 2 lp a11
np
By summing these two relations and rearranging the terms, we get
(1 (1-S(m-)) 11l- g11 (u 7) (glp) -(()))
Therefore, if 7M (0, 1), for μ 2 y, we get g(Prox (x)) s g(Proxng (z)). proves that Y (0, - ((Prong (r)) is decreasing.
Now, we prove that g² + g(x) when + 0. We denote M = sup (x), we have Vy E (0, 1).
M 2 (x) = g(Prox (x)) + 27
|| - Proxyg (x) 11?
Since, y - g(v) p||> - y/1 is p-strongly convex thus coercive and given that Prox-g (z) has a value lower than M, we get that m = sup ).) Prox-g (r) < +00. Moreover, the function + fll 2 is convex and lower bounded by an affine function. So there exist e Id and E R, such that Vx E Rd. g(x) + 1|==112 (01,2) a2. Combining the previous facts, we get
1 M z (Prox (x)) + 27
| Prox,g (x) 1|2
(01, Prox (x)) +
P
Proxy (x) 112 27 || - Prox.g (z) 1|?
2
||a || a2 2
p
m²
1
|| Prox (x) 112.
2
So we get lim -o ||x - Prox,g g (x) || = Finally, by the continuity of we have
((x) > lim (xx) 7-2
2 lim g (Prox (x)) = g(z).
which proves the desired result.
25

---

D.3
On the convexity and weak-convexity of the Moreau envelope
In this part, we prove that the Moreau envelope preserves the convexity and ceakeccnny proper- ties.
We will first need the general result of Lemma 3.
Lemma 3. If the function (x, E x B - f(x, y), with A, B convex sets, is convex on the variable (x, 2) E A x B, then the function E A in (xx v) is convex.
Proof. By the convexity of f. we get that Vt E [0, 1]. x; x' E A. U.Y. E B,
f(1x + (1 ()x'', + (1 - ()y') - (f + (1-11))11 (11-))(d'''))
By taking the infimum on 3/ E B, we get
inf f(x (1 f)a² by (1 t)y') S inf far v) + (1 1) inf f fa" y)) wEEB
W
vEB
Because B is convex, (ty+ y/ E B} c B, so inf y f(xx+(111))) t)x', (1-+((11))) 2
infyEB ftx + (1 (1-t)a t)x', 3) and we get the convexity of x A yEB f( y).
Lemma 4. If g is convex, then for all 0, 96 is convex.
Proof. We denote v(2,,) y) = 2/2 || - y + g For x, a, u.u Rdd we have
v(Ax+ + (1 - A)2', xy + (1 A)y')
1 |x - v) + (1 1)(2' - 2/11 + s(>y + (1 A)y'). 27
From the convexity of || 212 and g. we get that is convex in (2,8) E Idd x Rd. Then by applying Lemma 3, we get that g is convex.
In order to study the weak convexity of the Moreau envelope, we will need the following technical lemma.
Lemma 5. If is p-weakly convex, and denoting 9p = -1ll - 112 which is convex, we have
9 (z)
9p
T-T
(-pp) pr
2(1 - p7) |
P
and
Proxyg (x) = Proxx 23p0 Prox,_mp.
9r
1 7p
Proof. Let us denote as 9p the convex function Up g 111.11..
One has = - 11112.
so
(x) inf 9o(v) P
|1y11
+
1
||x
y/1
(21)
y
27
(v( + 1 1 PY
2
1
inf
||v12
(x, v) + (1 pr)p ||:|1
27
I
p7
1
1
||
27
(1 pm
()( + 1 - Py
1
inf
1/
2(1 mn) |
(22)
27
p7
||-
yp
1 py
2(1 p7)
Then, by the definition of the proximal operator as the minimum point y E RRd in the previous optimizations problems (21) and (22), we get
Prox (x) Prox 1-3p do 1 7p/
26

---

Lemma 6. g is p-weakly convex, with yp < 1, then 9 is I->p weakky convex.
Lemma 6 generalizes Lemma 4, for > 0. Note that the Moreau envelope of g is less weakly convex that g because I->p p.
Proof. We give two proofs of Lemma 6. The first one is more technical and requires g to be twice differentiable, based on an Hessian computation. This proof will be useful for future analysis. The second proof is more elegant and straightforward.
Proof in the case where is twice differentiable We introduce v(z, + || By definition, (xx) inf yeR v(x, y).
yl1 + g(v).
For À > 0, we study the Hessian of the function 2, y E IRd + v(x, v) + ||1001 that writes
( (2) Ia -la
Ia
( v)
+la + (2g(w))
For 2, E Rd,, by the p-weakly convexity of g, we have
(= (4) M(x.y)
2
1
x
||=1
2 - =11011 + V
8
7
7
1
2 rt +
1 { p) ||&112.
z
||=1|
Moreover, Ya > 0, 22 2||=|||t||| z - py > 0, we get
|| + allt|1 By applying this inequality with
(2)) M M
2
(1 mn) |=||2 (1 - p7)
|1412 + ( -p)) (2-p)
A
||=1|2-
p) |1d12
7
?
||
So, we get that for \ T-py the matrix M (x, y) is positive. Then the function (xr, y) E Rd x Rd + v(x, y)+ +)+ ||x|| is convex (r,y) y) E Rd x Rd. From Lemma 3, we get that g P weakly convex.
General proof Let denote as Ip the convex function 9p = g + f1..112. By Lemma 5, we get
g xx) (xx 9p T-10
2(1 py) |
1 pr)
Since 9p is convex, does 9p convex, that gd is - wweakly convex for yp < 1.
for 7p < Hence get that g² 221>pp) ll 112 is
1-p7
D.4 The intrinsic link between the Moreau envelope and the convex conjugate
In this part, we introduce the convex conjugate and shows its link with the Moreau envelope. In particular, Lemma shows duality result between the convex conjugate and the Proximal operator. Definition 3. The convex conjugate of proper function f : IRd - R, denoted by f*, is defined for x R by
(x)) = sup (z. y) - f(y)-
yER
The notion convex conjugate of f is related with the inf-convolution and the Moreau envelope, as shown by the following Lemmas 7 to 9.
27

---

Lemma 7. For :: + R, proper function, we have the following properties
(i) f* is convex.
(ii) For f.g: Rd + R convex, then (f(lg)* f + g.
(ii)) ʃ Rdd - Rd is convex if and only if 1 = S-
(iv) (0ll 113) 2x IP.
Note that, by Lemma 7(1), f* is convex even if f is non-convex. Moreover, Lemma 7(i)) shows the compatibility of the convex conjugate with the inf-convolution operation.
Proof. For x; y E RRd and À E [0, 1]. we have
f' + (1- - A)y) = sup (Ar + (1 - A)y, 2) - f(2)
=ER"
sup A ((z, - f(z)) + (1 - A) ((v, 2) - f(2))
=ER"
À sup ((x,2) - f(=)) + +1- sup ((V,2) f()))
=ERe
EER
S Af" (x) + (V))
which shows the convexity of f* (ii) For R4.
(z) = sup (a, y) - (f[ (y)
yERU
sup (a, v)
inf f(2) + g(y 2)
VER*
ZER
sup sup (a, 3) f(z) gly - 2)
WERd =ERd
sup (() + sup (I, v) gyy =)
zER"
yERd
sup - -[()) + (xt 2) + sup (x, v - 2) - g(v 2)
zERd
yERd
sup - -f()) + (z,2) + gz)
sERd
(xx + (x))
(iii) If f** = f. then by point (i), f is convex.
If f is convex, we have
f(x) sup (a.x) + b, (a.b)E
with Σ = b() E Rd x RR E Rd, (a, x) + S f(x)} (a, E E, if and only if Vo E Rd,
(a.z) - f(z) - i.c. -b (a). Then, we have
f(x) = sup (a, + h
sup
(a.x) b
(a.ijE
aERd aE (()
= sup (a, x) - (r) = (x). aERd
(iv) For x E IRd, (1])=
(uPyERe(A,U). -3 11y.122 The sup is reached at y 2, so that
(gll 112)* + 11.
Lemma 8. For f Idd + I a proper function, we have the following properties
(i) Vz, y Rd, f(x) + (v) > (z. v)
28

---

(ii) For f convex and differentiable and E R with y = Vf(z), we have f(z) + f*
(a,y). V/-
(iii) For f convex and differentiable, we have y = V fx) if and only if (V)
(iv) For f convex and differentiable, f is p-strongly cowvex and only if f is 1/ p-soohh.h.
Lemma 8(ii)) be reformulated as ff Vf*= Ia-
Proof. (i) For 2, y E Rd
[ sup (v, f(x) [(z) 2 (v,
=E
(ii) If y = Vz(z), then by the convexity f. we get, V2 E RRd
f(z) 2 f(x) + -
(z, v) f(z) 2 (v.2) - f(z)
(x, 1) f(x) 2 (()).
So, by definition of f*, we get ('() = (x. v) - f(z).
(iii) If y = (x)) by the point (ii), we have f(x) + f*(() = (z.z). Then for all E Rd
(t) sup (4,5) f(s)
SERd
2 (1, x) - -((x)
2 (t v. + (y,x)) - f(x)
2 (t y, x) f*(y).
Thanks to Lemma 7(1) f* is convex. Hence get that f The reverse is true because is convex so f** = f by Lemma 7(ii).
(iv) We denote u(x, v) = (x, u) f(v). The j-strong convexity of f implies that Vz, y E Rd. (Vf(x) Vf(w), v) ul|x - y/
(23)
Thus Vf : IRd - Rd is injective. As is strongly concave w.r.t. y. it admits unique maximal point denoted by yo- On this point the optimal condition gives Vzu(z, yo) = so f r. Therefore, Vf is surjective, it is a bijective function and
f' (a) = (z,, (V (x))) - f((VF) (x)).
(24)
By applying Equation (23) with (V we get Va, Rdd
(Ir y. (V (z) (V))) 2 /I((v)) (xx) - (VS)
The Cauchy-Schwarg inequality then gives
(x) (vf) - 1 vll
(25)
/1
Using (24), we have for x, h E Rd
(x - (x)
(v ((V ()) - (v))
+ +(((
(v (==+ + ((([
(h, (, h))
By denoting u = (Vf)- (V))) we know that ((hl)) thanks to Equation (25).
Thus, we get
fx + - (z)
= -(x,u) + (h, (V,() + (h, u) [2)
= =x,,) + (4, (v/) + (/, u) -V
(())
29

---

Therefore f is differentiable and Vf* (Vf)-* Combining this result with equation (25) proves that f* is -smooth.
Conversely, if I is L -mooohh, then Va, E Idd
(v) (y) y) 2 )lV ())ll
(26)
By denoting 2 = V f (x) and = (y) by Lemma 8(ii), we have = f2) and y ftt),, so
(= - Vf(=)) 2 م|| - t12
which implies that f is u-strongly convex.
Lemma ([65)). For convex and x. 2 Rd, the two following statements are equivalent
(i) 2 = x + and (xx) + ("( = (xr,y).
(ii) x Proxy (z) and y = Proxy- (z).
Lemma 9 shows the intrinsic link between the proximal operator and the convex conjugate. In particular, it shows that the inequality of Lemma 8(i) is attained only for couple that are of the form (Proxy (z). Proxy- (z)). Moreover, it shows also the equality Proxy (2) + Proxy. (2) = 2.
Proof. (i) =
(ii) For E Rdd by the convex conjugate definition, we have (v) 2 (u, v) f(u).
By using that ((x) + (2) = (r. y). we get
(x. f()) ž (u, v) f(u).
Then, using the previous incquality and = = x + y,
1
| 2|1 + f(x) = ||| + ||||
(z, + f(x)
2
2
2
< 2 ||||| +
|=||2 (x, + (x, 4) + +(u) -(u,
$ 2 | 1
||0|| + f(u) - ((,,2) (u, |=|| 111]
+
11 (w) マリ1 1| u1l
Then, necessarily x is the only minimum of the functional + 1 ||u - =112 f(u), which means
that x = Proxy (z). A similar computation gives that = proxy" (z).
(ii) (i) We note yf' = x, with Prox (z). By the convexity of f. for E (0, 1) and Rdd have
[lu (1 1)x) S (f()) + (1 (1-1)/ ()))).
Then, because x = Prox (z), we have Vu E IRd and VI E (0,1),
2 || 2||² fx) - 2 |tuu + (1 - t)z - 2|| + f(u + (1 - t)z).
By combining the two previous inequalitics, we get
| - =|12+ + [(x) < マ 1/u + (1 - (1-1)x =112 + 1f(1) + (1- ()(()
t
2 1u =1 + t(u x. v2) - - -f(x))
By dividing by and letting O, we obtain that for all u R2d
(u - x, v/) < f(u) f(x) (u. fw)) < (x, f(x).
So
('('') = (x.5) f(x),
which ends the proof.
30

---

D.5 Properties of the proximal operator
Based on the previous link between the convex conjugate and the Moreau envelope, can now deduce some properties on the proximal operator (Corollary (2) and Lemma 11) of weakly con- vex functions. Moreover, we will study how the Moreau envelope preserves strong convexity (Lemma 10).
Corollary 2. For p-weakly convex with < and differentiable at a E R we have
Proxyg (x + [V(())
Corollary leads the notation Proxyg (Ia + 7Vg)
Proof. We first demonstrate the relation for convex functions g and then use for weakly convex ones.
For g convex and x E Rd, by Lemma 8(ii,, we have for y = Vg(z). + +g" (r, y)- Then by Lemma 9, get Proxy (x + Vg(x)). Then, if is convex, 7g is convex and we get Vy > 0,
Proxyy (x + VV((z)) = I.
(27)
If is p-weakly convex with pp < 1, then we introduce the convex function 9p = = 211-111
By Lemma 5, we have
Proxyg (I) Prox 10 80
1 (-7p)
Then
1 + 7Vg(x)
Prox,g (I (V+>V)(z)) Prox 2ap
- YP
# x 7 [Vg 7p
Prox To
1 1 7p
7
Prox Pap 9r
x
go (x)
1 Yp
g.
The last equality is obtained by applying (27) on the convex function 9p-
Lemma 10. For a function 9 p-strongly convex, then g" is Ifyp strongly convex.
Note that g² is less strongly convex than g as 1t7p
Proof. Assume that g is p-strongly convex, then, thanks to Lemma 7(i) and Lemma 7(iv,, (g7)* 1 |0]|²)* = g" + I ||x|| that is convex and 1 (gD) 24
p + = 1+27 smooth thanks to Lemma 8(iv). Combining Lemma 8(iv) and Lemma 8(ii), we deduce that (* g" is o 14 strongly convex.
Lemma 11. For p-weakly convex with 7p Prox, is 1-7p Lipschitz.
Note that particular, if g is convex, then p and Vy 0. Prox.g is 1-Lipschitz. The fact that the proximal operator is Lipschitz is important for guaranteeing its stability.
Proof. The general proof of this Lemma 11 can be found in [41, Proposition 2] where the authors used [65, Proposition 5.b]. We provide here a more direct proof in the case of differentiable function g.
31

---

As is p-weakly convex and differentiable, then Vz, RR,, we have by the convexity of g g -11111
g(x) + 2 |= + (Vg(a) + pp. S ( + 2 |lvll
(Vg(z), S (vv - g(x) + b1100 - y
For x' E Rd, we denote 2 = Prox (z) and Σ' = Prox,s و (x'), we get
- 2) g(z') - -0()) + 2 || - 211
(V)(z') 2/) 5 g(z) - g(²²) + P || 2' 11?
By the optimal condition of the proximal operator, we also have
1 ?
(2 x) Vg(2)
(z' x') + Vo(=)) 0,
Combining the two previous sets of equations, we obtain
1 (x - z, ,'= - 2) S g( g(z) +
2 f1] 2
(x' 2d-2.22 2) s ( g( / 2'112
2
By summing the two previous inequalities and using the Cauchy-Schwer inequality, we get
- =p|== 2112 < : - 2' - x + 22
(1 - YP) || 2 < (x' x, 2/ - 2)
(1- - 7p) || z' 2112 < | - x' $111 z'11-
Therefore, we get that, Vx, E Rdd
|Proxy (x) Proxyg (a') 11 5 1 7p
||0 - =2'l.
which proves that Proxyg is 1->p Lipschitz.
D.6 Proximal operator as a gradient step
Now, we can prove the main results of this appendix, that allows to interpret the proximal operator gradient descent step on the Moreau envelope. Note that Lemma 12 also proves that the Moreau envelope is differentiable even g is not.
Lemma 12. For a function g p-weakly convex, for 7p < 1, we have
(x)
(x
-roxx (x))
Proof. Our proof is based on the strategy detailed in [80, Theorem 2.26] for convex, that generalize for g p-weakly convex. This Lemma formulated in the weakly-convex setting in [6, Lemma 2.2] and in [21, Lemma 2.2] without proofs.
For E Rdd. we introduce v = Prox-g (z), w (a - u) and huu)) (x+ ())"+))'"((x) ->x (w, u). We aim to prove that g is differentiable at a with Vg" w. which equivalent differentiable at 0 and Vh( 0.
32

---

By definition of the Moreau envelope, since = Prox.g (x), we have g²(x)) = 2 || - -v12 + g()
and g²(x - u) S 전 I +
- v112 + g(v). So, we get
h(())=
< 27
x + u - -112 27
|| - w112- (w,, u)
-
|uul
+ - (x v, u) - (w, u)
2
?
- 24
|
Moreover, as (2 + u) is
1-py -weakly convex by Lemma 6, then h(u) +
p
P 2(1-p>) ||u|/2 = gx +
u) 2-- p3) |u|| -g²
(w, u) is convex in u. Therefore
1 2 (((u) +
P
||21|2 + 1((w)( +
2p)- [lul2)
P
2 h(0)) =
2(1 - p7)
2(1 - p7)
h(u) 2 (1 - p7)
P
|u||2 h(-u)= 2
p ||u||3
1 - pyi 27
So, get
P 1
- PY 27
||al2 $ h(u) - 27
/11
Therefore h is differentiable at and Vh(0)= 0. This concludes the proof.
We can deduce that the Moreau envelope is smooth, i.c. Vg² is Lipschitz.
Lemma 13. If g is p-weakly convex, with xp < 1, then g is max (2 ( smooth.
Proof. By Lemma 6, g is - weeakly convex. Moreover, for f a convex function, by [3, Propo- sition 23.8), + Prox,, (x) is 1-Lipschitz. We prove this fact for f convex and differentiable. For 2, I2 and u = Prox, (x), v = Prox,; (y), we get by the optimal condition of the proximal operator
((x - u) - (y v), v) 1 (VS(w) - -V(()) o) 20,
by convexity of f. Then
x - y/ 2 = ||(x u) (v v) u/|
[| u) (y == + ||u u1| + 2((x u) (y v), u)
2 [1x u) (y w)|l ||w-wlll u|| u
So [ u) (y w)ll < || vll- which means that x + x Prox,// (z) is 1-Lipschitz.
Combining the previous property with Lemma 12, we get that V is 1 L-pischhitz. So, we have the inequality,
1 - v) - -1x y/1
(28)
However, Lemma 5 gives that
9" = 9p
x.
||0||
1 m
2(1 pY)
33

---

As 9p is convex, we can apply equation (28) and obtain
(Vg) (x)
Vgz
I
y)
1
( 9p
I
Vgg
1)
p
2/1
my
7p
70
70
1 1
$
11
y/
x
y11
1 - py 7
pp
W
æ yl?
With the weak convexity of g² (Lemma 6), get
P
1| y/1²
1 -111x- y11²
1-2p
So, get that Vgg is max (T)
smooth.
D.7 Second derivative of the Moreau envelope and convexity of the image of the proximal operator
We can now prove that the Moreau envelope is twice differentiable if is twice differentiable and Lipschitz on the image of the proximal operator. Moreover, we will also show that the border of the the convex envelop of Prox.. (R4) is of measure zero (Proposition 2). In other words, the image of weakly convex function almost convex.
the proximity operator
Lemma 14. Let g be a p-weakly convex function. Assume that that is C² and Lg smooth on Prox.n (I2)) with pry < and L < 1. Then we get, for E Rd
VProx (x) (Ta + 7V gProxnn (x)))
1 [L (Ia + V (2))) -)
V (x)
Proof. This proof is an adaptation of [69, Theorem 3.4] for weakly convex functions.
By the optimal condition of the proximal operator, we get that (Prox (x) - x) (Proxn (x)) O.
Combined with Lemma 12, we get that
(g) Vi(Proxyo (x)).
(29)
Then for all Jr, h E IRdd
V (or h) (x) (g(ooo (xr h)) Vg((rox,,)) (x))
= (Proor (z)) (Proxyg (x + h) - Prox,y (=)) + o(I Proxys (x - h) - Proxyg (x) II).
However, by Lemma 11, Proxyg
1 -Lischiiz Therefore o( Prox (x h) Prox (1r) I]) I-yp
o(]h))). Then, we get
Vg (x) = v2g (Pronng (x)) (Prox (x + h)) - Prox (z)) + o(lbi]).
Injecting the characterization from Lemma 12 in the left part of the previous equation, we get
h (Prox (x + h) Prox-g (z))
2 (Proxon (z)) (Proxyg (xr fi) Proxig (x)) + o([(b]])
1 h (1 + v2 (Proxx (o)) (Proxya (x + h) Proxyg (x)) o([[/]))
(1
Prox (x + h)) Prox (z) 7
Ia V'g(Prox,g (a:)) (h) o((A)]),
34

---

where Id + grr(pn (x)) is invertible because is Sm-oth at the point Proxeg (a) e Proxyg (Rd) with Rb, < 1. The last equation shows that Proxyg is differentiable and its gradi- ent is
Vroox = (La + vV2 Prox.o)
Then, we differentiate Equation (29) to get
(x) = v (Prox (x)) (x)
v2 g(Proxg (I)) (1) VV2 g(Proxnn (x)))
TTa (Ta 7 (x))) -1)
which shows the second part of Lemma 14.
We can now deduce that for sufficiently small the Moreau envelope is smooth (with a constant independent 7) on all TRd if the function g smooth on Prox.g (IR").
Lemma 15. Let g be a p-weakly convex function. Assume thas is C² and Lm-othoth on Proxyg (Rd) with Log S 2 and pY < 1. Then 9 is LLg-ohooth on Rdd
Proof. By Lemma 14, we have
(x) -1a (la V (x)))
As assume that - -LgTd d V2g( (z)) 1 Ld Idl get
1
1
La 42 (x)
Ia
7
1 Log
7
1 Lg
T.g
T.g Id
La 9 1 L
1 - Lg?
=u(+)
:=(())
Since v'(7) (1- 2?= S O, is decreasing. As u( 1 = -2Lg. we obtain that u(7) 2 2Lgg
123
for all 7 E [0, 2t In the same way, v'()) (1+b,
1,a
S 0. so v decreasing. Since v0) = Lg
for y 2 0, we have v(y) $ Lg. Finally, for ? [0, 2L, we get
-2yId I V2g = LyLa-
So g" is smooth on Rd Proposition 2. Let g be a p-weakly convex function with p7 We have
Leb(dom(g) \ Prox [ 0. with Leb the Lebesgue measure, dom(g) {i E Rd g(x) < +00). Moreover, we have that Leb(Conv(Prox, (RR \ Prox.g (R.)) O,
(30)
(31)
where Conv (Pox(p (Rd)) is the conver envelop of Proxyg (R.))
Proof. We denote by dom(g) the set where g < +00. By the weak convexity of g. we know that dom(g) is convex. By [57, Theorem 1], because dom(g) is convex, have that Leb(dom(g)
int(dom(g)) 0.
By [45, Theorem 4.2.3] convex function is differentiable almost everywhere on the interior of its domain. As + Ell 1|2 is convex, thus differentiable almost everywhere on the interior of its domain. As consequence g is differentiable almost everywhere on the interior of its domain,
35

---

0
f not defined
f f=
f=
Figure 7: Representation of the function f defined Equation (32).
int(dom(g)) (g)). Denoting as r C int(dom(g)) the subset on which g is differentiable, we thus have Leb(in((dom(g)) (T) =0
т. is differentiable x, by Corollary Proxiy (xr + 7 (x)) E Prox-y (R4). So we get C Proxyy (R4). Therefore, we can deduce that Leb(in((dom(g)) Prox,g (R*) 0.
Moreover, for x
have
Combining the fact that Leb(dom(g) \ int(dom(g))) we get that Leb(dom(g) \ Prox,s (R2)) 0. It shows equation (30).
0 and Leb(int(dom(g)) \ Proxxg (R*) = 0,
E dom(g), by definition of the proximal operator, we get g (Proxx (x)) - 27 || - Prox,g (z) 112 S g + +| - y1l². So g(Prox,g (2)) < +00, which
Moreover for x E IR and
1
gives that Prox,g (R2) dom(g). Because dom(g) is convex, get that Conv Conv(Prox,g (R*)) C
dgm Combining with equation (30), it gives equation (31).
E On the strong convexity on non-convex sets
Definition For an open subset C TRdd and μ 2 0, a function f E C.)( said to be ju-strongly convex on S if and only vf E S, 72 = pla-
function that is p-strongly convex S with p is called convex on S.
Proposition 3. For convex open set S and function f E CS, RR, f is convex on S if and only if't E [0, 1]. Vx, y E S. f(t (1 - t)y) I tf(x) + (1- f))
Proposition 3 is standard and we let the proof to the reader.
Remark 1. S non-comve,, then even if is convex on S, the inequality Vt E [0, 1]. Vz, y E S, f(t (1 t)y) I tz) (1 (11+t)f tz) is not necessarily verified.
This is for instance the case with = {2 E RRd || < 1 U E R > 2} and f defined by f(x) 1f <1
(32)
f(x) = 0 | 2,
(33)
see Figure 7 for a representation of f. Then, Vr S, v so f is convex on S. However, for E Rd such that |uu| 1, we have
1 f() fl 3u + 2 (-3u)) > f(3) )33))
1 , f--u)) 0.
Lemma 16. !f smooohh Rd with Lhg and there exists R >> O, such that g is p--ttrongly convex Rdd B(0, R), i.e. V²9(x) 2 pla then there exists Ro 0, such that Vry [0, 2L. g" is Itay -strongly convex on pd (00, Ro).
36

---

Proof. As is strongly convex on R (0,, R),, it is coercive, so g is lower bounded on IR, i.e. there exists Jinf = min g(x) > xo such that Vo E Rdd g(x) 2 Jinf- We recall that the Moreau envelope of g defined as
gx)x) inf || y/1² g(y).
(34)
yER* 2
For Rdd, such that ||:|||
2 R + 1, for y E Rd. such that |yy x 2 ||||||
1, we have
x yll + g(v) 2 2
(1 R - 1)² + Jinf-
(35)
27
Since Vy is T Lipshiiht we get that
g(x) S s(0) (Vg(0), Lg |0s|?
(36)
Due to Lg < 5: we get that asymptotically 24 (1==1| - P- 1)2 + Jinf is larger than g + La
(Vg(O), x) +
| More formally, we study the quadratic form
((0) + (Vo(0), + Lg |100 2
[||=||
R - 1)² + gins
27
1
R+1 1
||a||| (Vg(0), ginf 9(0) + (R + 1)2
Lg
|10||
2 7
27
1
(1
R +
(R + 1)²
Lg
||/11
[Vo(0)]]
||>|| + gins - x(0)
2 7
7
27
1 (1 1
1g7
||
R +
+ +1Vx((01)
||>||
4 7
1
g(0) (R 1)²
Lg ||~||/
ginf
27
Then, the previous quadratic form is non negative if æ E Rd verifies
R+1
Vo(O)]
| 4
7
Ly
.(0) + (R+1)²
and || 2 2
ginf
27
1 Lg
7
By defining
R+1 + |V((0)]
Yinf g(0) + (R+1)²
max
4 7
Lg
2,
1
Lg
7
we get that Vz E Rd B(0, r.,),
Tog |
1
o(0) (Vg(0),
(||=|| R 1)2 ginf-
2 2%
Moreover, for y < 2b
11 1 Tog 2 T.g and 1 - 7Tggg
2 2.
So we get that
8(R + 1) + 4 Vg(0|]
ginf - g(0)
rg < Ro max
Lg 2/
+ + 1)2
Lg
Therefore, we get from (36) that Vy E [0,
and Vr E IRd
BB0, Ro).
2T.,!
T.g
1
((x) = (0)) <V)(0),
|| 1
(1æ1 - R 1)2 ginf-
2
2x
37

---

By combining the previous inequality and Equation (35), we get that for x E R B(0, Ro) and for y such that lly -
R 1, we have
1 27 |x
g
+ +g))
Hence for x E Rd
[00, Ro), the infimum in the computation of g² (see relation 34) is reached inside the ball (xx, | R - 1), i.e.
1 || y/1² + 9(v).
inf VER-. peee.ly>>llst -+11 R-1 2
Moreover, B1x, ||]|| - R - 1) c Ed B(0, R) and Baz, ||س||| - R - 1) is a convex set. As we
assumed that g is p-strongly convex on IR B(0 Rt), then (x, y) E [R x B(x, |
R - 1) H
My | yll² + g(v) शाエ ||=||² is convex. Then, by Lemma 3. 2[1ト) |
is convex on
Rd B(0, Ro) which ends the proof.
Proof of Section 2
E1
Introduction to Markov Process and Markov Chain: definition and concepts
In this part, we introduce the tools of Markov Chain and Markov processes that will be useful for our analysis. We refer to the book of [26] for detailed introduction.
We define a continuous-time Markov stochastic differential equation by
dx2, d( + /2dw,
(37)
Xp ~ Jt,
(38)
where dw; is Wiener process and μ probability law on Rd. The deterministic part of the equation b(X.) is called the drift. If the drift b is Lipschitz, then the previous equation has a strong solution, i.e. there is unique solution (Xx)120 up to negligible fluctuation. In this paper, we will always be in the case Lipschitz which ensures that the previous equation is well defined and defines a unique X2.
The constant standard deviation of /2 ensures that if 6(X,) f(x,) and is Lipschitz, then
the process converges in law to x e- [79]. The following tools not restricted to the case of this constant standard deviation case. In the case of μ 6,, we say that the process X, starts on æ.
We will study the law of X. for each time L 2 0. To explore these laws, we introduce the Markov semi group Pe defined for x E IRd and A a measurable set by
Po(x, A) = P [X, E A|X, = x]
(39)
(a A) quantifies the probability that the process starting at the point x and following the stochastic equation (37) is in the set A at time l. is called a semi-group because if we define (P.Ps) (zz A) Jau Pr A) (zz, dy), then we have Vt, s 2 0. P.P.- = Pete. We introduce two operations with the object P,. For a distribution on R&, we define (P)(A) = fge Pe(ar, A)dz(z). Thus pP: is the distribution X, on Ted knowing that X, follow μr. In particular Po(x. A) 5,(()
(A) and PPo n. For function á Rd + E, we define Pio(z) == fR.. Pi dy) = E (o(X,)
2). Thus P& is a function of Rd to R. In particular Poo- = db. The two previous operations can be combined together to get pP. = E (d(X)))X ~ p))
With a step-size 7 > 0, the Markov process (37) can be discretized with the Maruy-aa scheme leading
X = X + 7b(x)) + 27
(40)
Xo 14, with ZE+1 ~ AN 1z). This process is Markov Chain. The deterministic part b(Xx) is called the drift. Similarly to the Markov semi-group, we introduce the Markov kernel R. defined for Rd and A Red by (x, A) TP [X, A|X, zr). We also define
(41)
RT, A) = P [Xx E A|Xo = x|.
(42)
38

---

This Markov kernel R,, (z. A) quantifies the probability of being in set A at step k for the Markov Chain starting at point z. We have semi-group property in the sense that Vn, m 0, R Ri RRt It can be seen as a transition matrix if the state space is not IRd but a finite space. In fact, for probability distribution 14, we define p fE. Rt (ar, A)du((:) the probability distribution of the discrete-time process Xg at time knowing that Xo μ.. In particular RO, (2, A) (A) and P.R.. = j..
We can also define the application of the Markov kernel on a function é: R R by RM Jaa Q(y) R (z, dy). In particular R. = Φb
The Markov kernel will be the core object to study the evolution of the law of the iterates X
For function V Rd + +o0), we introduce the V-norm between two distributions μa, v defined on Rd by
1 - v/1v = sup d +R lolsv
Bdd - dv),
(43)
The supremum is taken on f measurable. Note that the function V that defines the V-norm has nothing to do with the potential V of the law e-V V that aim sample. We keep the notation V-norm as it is standard in the literature [26, 59]. In particular for = 1, it defines the total variation norm defined by
|| - vllzv ==
sup d:k -R Ra 0
oldp - dv).
(44)
Note that, for any V 2 1, we have || u||TV ||w- u||v.
F.2 Technical lemmas
In this section we present technical lemmas that link the V-norm the Wp distance or the TV- distance and an application of Girsanov's 's theorem that will be useful for our analysis.
Lemma 17. [26, Theorem 19.1.7] For V : Rd + to)), we have E ((V ((Y)) || v/lv (X,Y)=BE
inf
with the infimum taken on the sel IT of coupling 3 between ja and v. A coupling between p and v is probability law 3 on Rdd x Rdd with marginals i and v.
Lemma 18. For 2 and μs, v two probubility measures defined on (Rd, B((R))), we have
Wp(H, v) S 22-111 ullv,
with V, = 1 1+ 11
Proof. By definition of the Wasserstein distance, we have
W)( = inf E ([IX-Y1P)) (X,Y)=B
where the inf is taken on the set of coupling 3 between μ and v. Using that the function æ + z² is convex, we have that (x + v) < 2 (IP y²) and Lemma 17. This leads to
WZ(Hv)) = inf
E ((I - Y1P)1xx4)
(x
< 2P
inf
E [(]] P + || (x
(X
< 2--1
inf
E ( + X + 1 [
(X.Y)~B
28-1 1| u/|v;
with V 1 P1.
39

---

Lemma 19. For nt, v two distributions on R., we have
1 - ullv I (n(V2) + v(V3)) l1- -1u-vlivv
Proof. By Lemma 17 and the
inequality, we get
|| vllv
inf E +VX)) (X,Y)~
inf E ((V(XX + + ((xx))))))))()))))))))))))))))))
(x
I inf
E ((())) B
(x,8)=
S (un(V2) + v(V2))) $ I|w- l
using that || v/22v = ( E 1(1xx (LxxY).
Lemma 20. For T let let b,,,b" C(10, 7,, T,, x [0, T Bed be two drifts such that Vi E (1,2), dxt 8 (((c))uejoo) l)dt + /2dw, admits a strong solution with zó ~ p with the Markav semi- group (P)),ER, (see definition equation (39)) and (w))220 a Wiener process. Moreover, assume that [10 ((W((()ee)))))) t)]? + | [D(((wa)eEooo)) d) < +00 = 1. Let V :R + +00) measurable, then we have
(I" (166)(()))))) 1000--2((aan ((1 t) de ||uPt - uPfllv & + (L"
Lemma 20 is generalization of [59, Lemma 19] for any distribution on Ie instead of Dirac distributions dz.
Proof. We follow the sketch of the proof of [59, Lemma 19). For i E {1,2). we denote by je the distribution of (Xi) on the Wiener space (C((0, ((C Tj. R))), with vb ~ f and dr; (((=)))e t)dt + v2dw,. We denote by pw the distribution of (we)xe(O.T) the Wiener process.
By the generalized Pinsker's inequality [27, Lemma 24), we have 1|pt - pPfllv S v2 (uP) )V2 KL (4 122).
(45)
We assumed P [1o" ( 1) ((w,(()) +)]l 2
+00 for any
21. Hence we can apply Girsanov's Theorem [61, Theorem 7.7] and get pw-almost surely that
du² dew
1
...
(- || ((wa))uue)) !)
((ww ((ww)u5(0.27))) exp
(b ((w) (www)eeuur)) 1), dur))
2
dpw d ((ww))E(o.77))) = exp
1 {'" | ( 1)
(b2 (ww())) 1), dwr) + 4
where (..)) is the canonic scalar product on Rd. Note that fo (b' (b'((W)uet) t), dwz), for i e (1, are stochastic integrals.
Hence, we get
KL(Ø* (1)) E log du' पμर (( ((=)))) (u(o.,))).
1
[" [lbb] ((=n)e)00)))) -b² ((E
(46)
4
By putting together equation (45) and equation (46), we get the desired result.
40

---

F.3 Sampling stability for Markov Chain in Vg-norm
In this part, we demonstrate the sampling stability of discrete Markov processes in the Vg-norm. Theorem 5 is significant refinement of [75, Theorem 1] as it does not involve any discretization error and it generalizes previous known results in W, and TV-nome to the Vp-norms, which will imply the result in 7orm and W distance for any p E N'
We introduce two discrete-time Markov Chains X i E {1,2), defined for step-size > by
X X (xx) + 22
(47)
with Zk+1 No0, Ta), two independent standard Gaussian distributions, and two drifts of CO (R RR).
We will show similar result than Theorem in V,, norm for V = 1 ||=]|0 with p E N and then deduce Theorem TVV-oom and W, (see Section F.4).
Theorem Ifb and 62 satisfy Assumption 1, the two Markov Chains X and X3 are geometrically ergodic, with invariant laws Thy Th. Moreover. for % 12, with L, defined in Assumption I, p E No and (z(x) = 1 1+ | I., there exists Gp 2 0 such that Vy E (0, 70l. we have
| lll,, S GGp (Ey (1)
Note that the pseudo-distance between the drift |b] - 1o2-bylleaa (ll22()))) (By (100 &
not symmetric in the drifts 6¹,6² which allows to evaluate this pseudo-distance only by sampling ny, see [75] for empirical evaluations. It could be symmetries with min
||b 6 (1)((())) instead of l - bllle2(=)))
Proof. Scheme of the Proof
In first part, we demonstrate that the two discrete-time Markov Chains X X3 are geometrically ergodic. Thus, we can define and study their invariant laws n., and T.y.
In second part, we study the distance between these two invariant laws. The idea is approximate them by the law of the processes at finite time ky starting at a point x E TR i.e. 6g R 1 and 8 R,, Then the ergodicity allows us quantify the distance between the two laws at finite time by by the distance between the two laws at a bounded time (my ze 1 in the proof). The Girsanov theorem (Lemma 20) gives quantification of the two laws at bounded time by distance the drift. Finally, we look at the asymptotic k + +oo of the obtained control to get the desired result on the invariant laws.
To simplify the notations, without loss of generality, we assume that and b² verify Assumption with the same constants L, R 2 0 and > 0.
An introduction to Markov continuous-time processes and Markov discrete-time processes given in Appendix F.1 and technical lemmas proofs can be founded in Appendix F.2.
Proof that X X3 geometrically ergodic
First, by [23, Corollary 2] and under Assumption 1 with "oo L2 (see [23, Proposition 12) for the expression of 7o). there exist E (0, 1) and D 2 0 such that Vyy E 7o]. Vi E (1,2), we have
W (8, 6,,,,,,,, 8, S Dp w/1,
(48)
with 6, the dirac distribution on æ E Rdd and Ry the Markov kernel of the Markov Chain defined in equation (47) as introduced Appendix F.I. Note that 6, R represents the law of the Markov Chain X at step ls knowing that X = x. We want to generalize the previous inequality for any distributions μ., v on Rd instead oz, 5y. We denote 3 the optimal transport plan from to v, by definition of the W, distance, we have
Wi(, x
|| - x2 (dx1,, drz)-
(49)
41

---

By the Bettoroviich-RRubister Theorem [31, Theorem 4.1] [52], the dual formulation of the W distance writes
W Wi(H,)) sup diB" JR Lip(0)
o(dp dv),
with Lip(Ø) the Lipschitz constant of Φ.
Then, by equation (48), equation (49) and the dual formulation of W1 and the fact that de, ( = R (21, dx) thanks to the Markov kernel definition (42), we get
/ JEAXRS 1pt - x2110 (ell@t(dam (dx1, dr2)
Dp WI =
1 Jdxxe xRd
W6 Re Sag R 3) (dx dz2))
J Jud xad
J ((x) (16., R (ddx) (6., (d)))))))))) 3rr (doi,, daz)
sup
oiR" -R
Lip(
/ (152, R (dxx) - (5.,, RC (dxr) for (dxi, dx2)
2 sup
g ((x))
R
fi RR L1
Φ(z) /
(1), (z) - R (22, dz)) frr (dx), dx2)
sup ond Rdd (ip(d)
RRURd
(bx) (1RR (dx) (vRtt,) (do))
sup oRR RR Rdd Li
W, (uR* Rh
So we get for any distributions Je, v on Rddd
Wi (n S Dp WDttTWiC Wi (w,
This proves that for & large enough, the Markov kernel R is contractive with respect to the 1- Wasserstein distance. Moreover as (P) (RR),, Wi) is a complete space [93, Theorem 6.18], the Picard fixed point theorem shows that there exists unique TH such that for vk 2 0, R.R m This probability law æř, called the invariant law of the Markov Chain.
Approximation of the invariant laws by finite time laws
We proved that N! and 7 are well defined, we can now tackle the problem of quantifying the distance between these two distributions in Vy-norm. By the triangle inequality, for i E N and
m
(50)
we have
|| |
1l,,, S || - 5e R. ll,, + 1 R.M 82 Rly lly, + R|5 =
(51)
We need control two type of term in the previous equation, the contractiveness in Vg- norm for the first and the third terms and the shift between the two law at time ky for the second term.
Contractiveness in V -n-morm
We study the contractiveness of the Markov kernel in Vo-norm. By Lemma 19 and [23, Corollary 21, there exist Pp E (0, 1) and Ep 2 0 such that Vx, y E Rd and Vi E {1,2), we have
|| 8 R. 5 (6 (V,)) + 8, R (V²2) 1 8 - Ep R., + S, R (1 (V2)) 1/2 2 (1+ + ||
=1)
(52)
42

---

By [59, Lemma 16] and [59, Lemma 17], under Assumption 1, for any m E N and V2m =
1 1+1 | 2m there exists Mm 2 such that Ak E I and Vi {1,2), we have
R 22,22 S M2m V2m (r) Thus, given that V2 s 2V2p and oz (V,3) (z), we have Vx E Rd
(53)
8 Rg v2 s 2M2 (2)
(54)
By injecting equation (54) into equation (52); using that Va bbs S va + Vb for a, b 2 0 and that VVp S pp, we get that for all x E Rd
16 - 5y Sy S V2E, V Man (2 + (er(u) (1 || 1 y|l) -
V2E V M2p (Vz(2) vy(u)) (1 |||||| -lvll)
Using the inequality v 1++110 | + |vl| - 1+ + |vl| - + | s 2" 2 (1+1|=1))+
2' $ (1 ||>l < (V) + Vy(u)), we get
| R by illv, I Dpp (v2
(55)
with Dr = 4/ Mzp This inequality generalizes [59, Proposition 5] that was demonstrated only for V1-
By integrating equation (55) for x ~ i1 and ~ v and the triangle inequality of the V-norm, we get for any probability measures p. v
| - RR,,,llv 3 Dppp (u(V)) + =VV)))
(56)
This proves in particular that with v = n.. which satisfies т., Rh = Tyj. the Markov Chain X is geometrically ergodic, i.c. the empirical measure of the Markov Chain at time k 2 0 of one realization converges in Vy-norm geometrically to the invariant law of the process.
|| - 8 ll, ||0, nēllv, S D2(=))p (
(57)
x2 thanks (V (z))). This is control for the first and the third terms of equation (51)
with (x(x)) Dp
Control of the shift of the two laws at time ky
The distribution 6, 6, is the distribution at time t = Ioy of the discrete-time Markov Chain X starting at x. The term 11og 8g R. llv, quantifies the deformation at time kry between the laws of the two processes starting at the same point run with two different drifts.
By the triangle inequality, we get
k-1
18 R - 85 R. =
1
Sr
Ryy
Rij 85 R, Ry.2
(k- 1)m 1(i+1)m I|v,
0=0
R ( mm Ri
5 R
1i0-j-1mmm 1)m 1)m
R,,2
||5 (k- 1mm Rat Rim 85 R 1)m R. Ri
R.
(58)
For o: Rd + R such that ||인|| S Vp and due to π². E. we get
(6.AA1/it) 11)m R.,, Bin 8, (b- 1)m R. R
(5,.R! 1k-kk-j---m R 8, R (k-j 1)m RT,2) ())(())
(5 R 8, R
[k-j pm RmT
( n,7(0))
(59)
43

---

By equation (56) applied with μ = 82, V u.y i = 2 and k = jm, thanks to (2(2)) 2 1, we have
|6 |6 mll,,, S V2
with B D,(1+
By the definition of the Vy-distance (43), we have
( (τ) I Bpg V? (2)).
Using that 82 R2 = =2,, (z) and that V22 S 2V22. we deduce that
(f)) - (1) pBpp'
S V2)(
(60)
Going back equation (59), thanks equation (60), get (6 R 1 Roy,1 Re
8z Ry,1
(
R2
(1)
8 (1----1)m 1)m Ry,1 o₂
R,,1
R,,1
1 1)m
12
(1))
Re72 (6) - m
< 2BBp jmy 1
Rot 8y R// (1
2Bpmm
s 2Bp R (K- RT 8 R. ( F.7,2llVe
jmy
Taking the supremum on f in the last inequality, get
| | (k-3 1-11 1)mn RT,, Ry 8x 12 (2 1-1 Ro R2 2ll,,
< 2B 110 R (k-j-1)m Re,,1 dn R (k- R. Ver
(61)
By injecting the previous inequality into equation (58), we get
k-1
|6 R 6g 1,, < 2B
Σ
jmy J. (kk (-l--j-1m 1)m Ro 5g R (k-5--100p 1)m R
(62)
j=0
Application of the Girsanov Theorem to get control at bounded time my
The previous inequality shows that we can bound || R.yn 8 RAp || - n 2 lly This last quantity has temporal duration of my E (1 71-7,11 due 1 which allows to apply Girsanov's 's theory to bound it by the drift difference. To do so, we need to introduce a continuous version of the Markov Chain:
12222l llv, with quantities of the form
dxt; (()) + V2dwf.
(63)
with (wi))20 a Wiener process and by, ((=))uett-..)))) 1) ((((41)) with & defined in equa- tion (47). Here the drift bú, is non-homogeneous, i.e. depends on the time t, and it path- dependent. This process is continuous counterpart of the Markov Chain (47). In fact, by integrating equation (63) for t E [ky,, (k + 1)y). we get
(1+1)7
1 (k+1)T
f (k+1))
drt = Jm
6' 60 dt + v2
dwf
J
kr
ebyy = 72b0 (zb,) + v Z
with ZETI N/O, Ia) because J (k+1)) dwf (Ta). Therefore, of, initialized with the probability law u has the same law than X defined in equation (47) initialized with the law p.
44

---

Under Assumption 1, the drift is Lipschitz with respect to the infinite norm, ie. for 0, E C(O,, (100,)].*))
-11 (000) 0' (
||0, ((o(u)) 6) ((((u)))E() 10
| - Ello
s 5 -
By [63, Theorem 5.2.2], equation (63) has unique strong solution of and
B(16,(((<))) ((=))u)tt-n))) t)l +00.
So assumptions of Lemma 20 are verified, and we get that for T > 0
$
1| - uPPllv, S (VP) +uP)(1))++)((33))) (L' (10 (o), di
(64)
with Vi, =1 Pi for i E {1 the Markov semi-group group at time (define in equation (39)) of the process following equation (63) and (x:))20 the stochastic process following equation (63) with the initial law z μ. For my, we have that pi R so
R
my
1/4
S (1RR,, (V + R (V
TE (1
(65)
Now, we can apply inequality (65) with μ 8z 1 (k---11)m get
0 12 12 11ik-j-1jp 1)m R 8r 1 n j- 1)m Re 1lv
8g R (K- (k----1) 1mm
RM, (V22) + 6r R ( (k-j-1)mm 13m R, (V
;
B (1bb (obs 1) - b² (z t) 11 dt
(66)
with x/, the process starting with the law 6, R fik--- at time t = and verifying equation (63).
Using equation (53) we have R R(k-5-1)m R (V2p) S M2p V2p. Recalling that 6 (V,))
(x)
and V22 < 2V2p. we obtain a uniform bound
8n R R (V22)) S 2M (x).
We also have that (V,)) < 2M Vap so, using again (53), we get
8 (k- 1-1 1)m R (V22) S 2M ( 10mm- S 2MM, (zp
Then we obtain
(, (5. 1mm
RM (V22) + 8z 1 10-jj-1mm RM (Vz)) s (2.4 + 2 (x)
By injecting the previous moment bounds in equation (66), we get
R R (-)m- pmm 5. ( R. Vi2
< (x) (L/me
E (1|b (al,5, t) b² (x) t)( dt
m-1
= Ax((x)
?
Σ
E (xtr))))) 6² (st
1
45

---

with (1) = (2 (ap(2) + 2MM (ap( a constant independent of j and Moreover, 2|ا
has the same law that X (k-J-1)m47
Hence we get that
1 1 (R- 100---1mmm 1)m
( 1)m R. VV
m-1
$ A1xx
- --
(67)
1=0
From bounded time my any finite time bn with ergodicity
We will massively use in this paragraph the ergodicity of the discrete-time Markov Chain to deduce from the control at time my in equation (67) control for any time k on [ - 6g R2
We define Ys the Markov Chain following equation (47) and starting with the invariant law n. at time h: = 0. Then the law of the Markov Chain Yg is m. at each time k 2 0. Next, by Assumption 1, b" and 6² are L-Lipschitz and we have
(()))b((x))) < (116) (z)]l + (z))))) & (O)1 +| (162 + L 1=]l)
s 2 (116* (0)1I + [(((()))) ( 21 ||
2 max (116 (0)1 + (1)( 2 L²) (1+1|=133.
(1)b'00)1
Thus, we have that
Φ(x) = (b) (x))
S V2(x) 1 ||
Φ
with Φn 2 max
(116+(0)]++ .L2).
By definition of the V2-norm (equation (43)), we
get that
(k-(-())))) B(o(Y.) || [[ 1 1)m-1 - m2llv=-
The previous equation can be reformulate into
IE (1
62 62 (mx - (XW)))))
I 8o116,_11 (k 12 1-1)m+ - -
(68)
However by Lemma 19, we have that
|8, R,1 By injecting in the previous equation the moment bound in equation (53), get
(kh-d-1)m+ </llvG V 8a P 1lm + TV2 (R 2.
||0 ( - T/1lV= (2M2 (k- - 1
(69)
By [23, Corollary 2). under Assumption 1, there exist A2(x) 2 0 and E 1) such that wk: 2
0.
Vi [1,2)
18 - FilloV S A2(x))p
Then, by combining the previous equation with equation (68) and equation (69), get
E
- -
< E (lbb (Ya) - + do (M (1--)1))+01
(70)
46

---

By summing the previous inequality for / E [0, m 1]. we get
E
|b (X
b²(X (k-ks 12(X 11---l1
pomtt MBBy~x (l1b(() 12(11113)
dov / 22222 A2
$ Az --سس mBy y (Ibb (V) b3 (Y)
constant independent of h and j. By injecting the previous equation in equation (67) and given that ym I thanks to m definition in equation (50), we get
with As(x) Φu / 22 (2 1-67
||6_R| 11mm Roy. 6g - 1jm R,722llss
R
A1((2)) (As(r)7p (n-i-tim
ymByy ( &
< A 2 (6 Derr
A1x))
(BY~az (V) 83
-1) (Y311))
We now combine the previous inequality with equation (62) to obtain
88 R
8g Sg
&m llv,
< 2BA (x) Σ jmy
(A)
+ (BYwaz (1)+(() - 62 (((3))))))))
5=0
< (2AA (x))
(k-1)my
p
Pp x
mcy (EY (11'(()) ((()))))((())))))
+ (B)
me 1 Pp
where, at the cost of slightly increasing G. we assume that
# 1. Denoting Aa(x)
2BA (1)
m
and As(x) = 2BAi (x) -
p we get
RIg 8, R ll, Ax(x)p + As(x)) (Ey (0(())--(())113)) (71)
Putting all together and asymptotic computations
We combine equation (51), equation (57) and equation (71) to obtain
|| | n nll,,, S As(x)p kmy
+ As(x)) (Ex (16'
+ +p(x))pmm kmyy
By taking l: + +00, we get
|| - x x,ll,; S As(x) (Erway (16((r)bb(x))))
with As(x) 2BA (x) T- -, with my 2 1 - 7 2 - 70, since we defined m 1 in
[
relation (50) and we supposed that (0. in the theorem's assumptions. Note that E Rd is free. We choose I = 0, then = (1+ (V22) which defined after equation (59) and A₁ (0) =
(2.Map + 2M1,)) $ which is defined before equation (67). By taking A + too in equation (54),
47

---

get that vz= E RR, (V,) & (2))).. In particular for = O, we get (V)) S 2M2p, thus
B 3 1p + 2.
This proves Theorem in p- p--asserstein distance with the constant
Gp
Dp + 2M2p) (2M4p + 2M2,))
Pp
where the constants Dp and Pp defined by the geometric convergence in equation (55), Mp by the moment bound in (53), yo = 22 with m, defined in Assumption and Vp = 1+ -|...... [
F.4 Proof Theorem
In this part, we prove Theorem 1. First, we recall its statement.
Theorem 6. Let b' and b² satisfy Assumption 1. X and X2 are two geometrically ergodic Markov m Chains with invariant laws may Th. Then for To = I and E No there exist Cp, C 2 0 such that Vy E (0, 7o). we have
W p m Cpllb's b (())))))))
|| TillTV S &01|b' - bllle2(m4))
Theorem is demonstrated for the W, and TV metrics. In [29, 68], the authors analyse the con- vergence of the Langevin dynamics using the Kullback-Leibler divergence. However, because our approach depends heavily on the triangle inequality property of the metric, it does not readily extend the Kullback-Leibler divergence, which does satisfy this inequality.
Proof. By Theorem 5, under Assumption we have that X and X are geometrically ergodic, with invariant laws n.. m.g Moreover, with % = I for E N there exists G, 2 0 such that Wyy E Yo). we have
Tēllı; Gp EY (16-(1)- -1(()))))))))
m
with V,, 1 +||++ -1--
However, by definition of the V-norm in equation (43), we have
|, - 1rr I || ll,,, < G (y (
which proves the first part of the Theorem relative to the -idistance. Next, by Lemma 18, we have for E N
Wp { 2 S -- +|1-1 29l
<2 GB (Erwzy (11b( (100(1))6)00033)))) *
which proves the second part for the Wp distance.
F.5
On the constant Cp, C' of Theorem
Note that C' C1, so we only need to study C, for p E N. The constant C, of Theorem is defined
by
Dp 2M2p) (2M4p 2M,, 2M2 1
Cp = 21-
2 1-70
(72)
1 Pp
where the constants D, and Pp are defined by the geometric convergence in equation (55), M, by the moment bound in (53), 7o 23 with m, defined in Assumption I and V, 1 ||
48

---

Cp is independent of the step-size and of the drifts b²,
The authors of [23] proved that the constant Pp is independent of the dimension d and that Dp is polynomial in the dimension. Therefore, Cp has polynomial dependence in the dimension d with dependence the moment of the target law.
The dependency on p is unclear as depends highly on the evolution the moment bounds Map with p. Therefore, the dependence of Cp in N is unknown in general.
The constant Dp dependent of the non-convexity radius by factor of V for R s 1 according to [23, Corollary 2]. Pp is independent R. Therefore the constant Cp explode when R + 0 with a dependency of R
*n Based on [23, equation (10)), we have that the dependency exponential
in R when It - +oo with Cp = ( LR2
F.6 Quantification of the discretization Error Proof of Theorem 2
Based on the proof of Theorem I we can recover the discretization error for discrete Unadjusted Langevin Algorithm (ULA). For that purpose, we introduce the ULA Markov Chain
X = Xx - ~VV())) + Zx
(73)
with Z a normalized Gaussian random variable, as well as the continuous Langevin Markov Process
dzt - -VV V2dw,,
(74)
with dw a Wiener process. Under Assumption 1, Theorem shows that X has an invariant law and is geometrically ergodic. Moreover, if VV verifies Assumption [23, Corollary 22] proves that 2f has π x e- as an invariant law and is geometrically ergodic.
Theorem 7. If t'ehe function VV verifies Assumption and & e Then, for for E N there exist Cp. Dp, Ö 2 such that by E (0, the Markov Chain is geometrically ergodic with an invariant law Ty and the discretization error is bounded by
W, (Ty, T) S OpT
|| æ||rV S On
|, x xllv, S Dp
with π -V and V = 1 11.1.PP.
Proof. This proof is based on the same reasoning that the proof of Theorem 5 with continuous Langevin processes instead of discrete-time Markov Chain. The key point is to write the discrete- time ULA Markov Chain continuous Langevin process in equation (75). Then, we verify that the step the reasoning of the proof of Theorem are still true this continuous context.
We define the ULA continuized continuous process by
d -b, (127)EE)) :)de+ V2dw?"
(75)
V((a Following the same rea- soning as the one given after equation (63), the process 2² is continuous counterpart of the Markov Chain (73). More precisely, 2², initialized with the probability law dx, has the same law than Xx. the ULA Markov Chain defined equation (73).
with b(((()))eRt,,) E ((r,,
We denote by P: the semi-group (see definition in equation (39)) of the stochastic equation (74) and R., the Markov kernel (see definition in equation (42)) of the Markov Chain defined equation (73).
We follow a similar sketch of the proof of Theorem 5. We first demonstrate a relation similar to equation (56), by replacing [23, Corollary 2] with [23, Corollary 2] for the process x/. We thus obtain that for e d and p E NN, there exist Ap and Pp (0, 1) such that, for μ probability
49

---

distribution on R we have
ay - p.R llv, I {,))) bmy
1 PPmm ollv, I (p/ )ppm
(76)
For Id and & E N. 121. by the triangle inequality and equation (76) applied for μ ox. have
| TTy T|l,,
$ 11 8y R.
Vl, |6 R 6g Pkmy Ilv, || 6 Pkmmy I7|,,
$ 2Ap 222 (p
kmy
+ 16 16, 8n RoPkmallv..
< 2 (1) km
16 1 1)m Rey Pjmz 8z 1 1-1---11m Pmny PmyPimnlly
1=0
Similarly to the reasoning that led us to equation (61), we get
| 16__R(k---1 R. Pjmy 5 R (a.l(---11)m)) P.nc Pamrl Vl,,
mm By combining the two previous equations, obtain
< PAp 115 1 P 1-1k- R. 82 R. R 1)m Pmay Vay
|| n.y T/|,,
k-1 Σ iii
22 km kmy 2A
Re Rek 1)m neT
Pmnyll Vaal
(77)
==
Then, by Lemma 20 and the fact that the drift of x VV and the drift of x² is by, we get
| 16 12 j- 1) 127h 8 6, 1i 1) P. Pmnyl 1 1l
8g R ( 1)m (V22)) + 8 R R (ark---1)mn 1)m (V22))
( my
E ((IVV( - by, (V..)) 1)]( dt
with b. defined in equation (75) and yr.j the continuous process starting with the law 5, RR ( 1)m and following equation (74).
Using the moment bound given by [59, Lemma 17], we get that there exists Fz(x) 0 such that vk e j to....,k- 111
(R. 1- (V2) + 8e R. 1)m 3-
Fy(x).
Combining previous equations thus gives
| 110
( j- 11m R.t 8r Reth (k- j-11-mm1mmmm PmyllVas
(78)
Fx(x)) (1,T) myy
(IIV(())))) - by (VVi,)EE ((V.)))ER...00)19 di 1
(79)
Since VV and by are L-Lipschitz from Assumption 1, we get, with m L that
E ((IVV()).)) by ((V,)))RR, 1)]1?) dt
m-1
(k+1))
L
E Bllve. 11 dt
(80)
Joy
k=
50

---

Because, Yt,j is following equation (74), we have ye.j Dey.j = J VV (yv,3)d v2 dw,. Combined with the Itô isometry, the fact that || (V))) S (IV((0) inequality, the moment bound in equation (53) and the fact that t ky S 7, we gel
L L|| the Cauchy-Schwarz
(y(oo,))du v2 [ dwill?)
E (1 yky (13)
EE
(81)
(V(uy,)ddul + 4E (11
S 2E
dw 11
koy
(1IIVV(0)1 + Son (lsmnslldte))
S 2B
+ 4yd
< 4y (12 + + ((,, (lomsssldd )) 4nd
< (0)) + 4L
E (11aa)11 du 4nd
Aoy
- 47 (0))) + 2 4yd
- (0) 41.2 MoV
(82)
Combining equations (82), (80) and (79), with BB = 4 V 4 and the fact that my 1, obtain
[| 160. R. 6, R (k- 1)m P myllvv, S ( (Bem)) (
(Ba)
since m = | so that my I 1. By injecting the previous inequality into the equation (77), we get
k-1
|T, - Fly,, 22A,V?(T) kmy + +A Σ
jmn ( (L)())
1=0
1
- V2) kmn + 2A 1- Pp
(LBB) 1/2
Taking h + in the previous inequality, get the desired result in Vy-norm. We get the result in Wp and TV norms following the same reasoning as the proof of Theorem in section F.4. O
G Proofs for PSGLA
In this part, we provide proofs for the analysis of the PSGLA algorithm defined in equation (3). First, we demonstrate regularity results on the drift 67 defined in equation (11), then based on our IULA Markov Chain (definition in equation (2)) analysis of section 2, we derive the convergence theory for the PSGLA algorithm.
G.1 The drift of PSGLA is verifying Assumption 1
Lemma 21. Under Assumptions 2-3, for all y E (0, (th bbm. by verifies
(i) 67 is L-smooth on Rd, with L = 2L + 2Lg
(ii) Vz, y IRd such that ||x vll 4Rg have
(b(x) b(y), x 1\ 2 11 o y/1
4
with the constants T,y, Legs P. n, Ro and p. defined in Assumptions 2-3.
Then, for y (i, 1 22, :/- 71 b verifies Assumption with L. 2T, 2T. R = 4.o and
4.
51

---

Note that the constant that appears in Lemma 21 are independent of 7,
Proof. We will demonstrate each point separately for the drift ba (x)
(Vg +
Vg)
defined in equation (11). We need that I 1 for the Moreau envelope g of to be well defined. P
(i) Under Assumption 3(), Lemma 15 of Appendix D.7 gives that for y S 2L." Vg" is n
Lipschitz. Combined with Assumption 2(0), we get, for x, y E gd
(x) - (v))
10/[=~>Vg'[]) -VV(==>Vo><<))) -1 Vo
<T 7 + 21,11==111 1 vll
< Ly [| vl) 21,11 - y/l
$ (2L, + 2Lg) || yll.
which proves point (i) of Lemma 21.
(ii) We want to have a lower bound of the quantity (67(z)- -b) - v). for 2, E IR when | - yll is sufficiently large.
For <> Σे. and v;, y E IRd, have
(x) 87 (v), x v) 2 2T y/
(v), (V) y)
where we used that fz(z V if 2 thanks to the computation of point (i).
We suppose that ||= vll R then there is at most one point between and y that belongs the
ball B(0, Ro).
We distinguish three cases.
[z, v] B(0, Ro) O. From Assumption 3(ii,, if 71, V2gg 2 nIg on Rd B(0, Ro)-
Then we immediately have
(b) - 17 (y), x v) 2 (μ 2 |
y||²
I E B(0, Ro), then ||y|| = 1y- 2 11y 1 |||||| 2 RR. We take E [x, v). such
that ||=||| = Ro, then |z, u] C Rdd B(0, Ro). We define to E [0, 1]. such that : = x x to (y
x). It holds that ||=- S 2R, and | =1 ||l x -r- =ll Ill x1| -|x- =|| 2Ro
and tg |- 2
--=0||
Under Assumption 3(i), by Lemma 15 of Appendix D.7, g is 2L, smooth, we get
Vg"))) x) x)= / (V'g (I t(y x) x), y z)dt
1/ (1'g(x+1(y--- x)) 2).1 x)dt
+ (V'g (1y - -))))))))))) y - x)de
to
2 - 20gtolly - x|12+ + to) to) x1?
2 - - - + -ly- =|1?,
and we deduce that
(x) - (y), x
v) 2
1 2
2L, Lg) 11 - 2012.
v. y & B(0, Ro), we look at the affine segment / E [0, 1] ~ x + byy - x)). this segment does not intersect with ((0, Ro), then we are in the first case. Thus suppose that the
52

---

segment crosses the ball B(0, Ro). We look at the norm of the vectors u(a) defined, for a E IR, along the affine line that passes through points and y, as
u(a) = ||z + a(y =) = | + 20(22, y x) + aly - =|1².
Notice that u is quadratic in a. We assumed that u(0), u(1 > RR and there exists e|o, 1[ such that u(() < Rh then there necessarily exist 0 40 < 41 1, such that u(lo) = u((1) = Ry. As consequence, 11 E (10,4), u(l) Ri and 1I E [0, (1).
ul)) Ry. We denote
20 x + to x)
21 = x (1 - x).
By definition 20; 21 E B(0, Ro), therefore =
=11l S 2ng Then
41 - 40 = |
2u x||
| - 201
2Rg
yy x lv =|| lly - x| S 11y x:
(83)
2
because |yy x|| 2 4Rg. We can now estimate the quantity of interest
<Vg (v) (x) /
(V t(y - x))(y - x),y - x)
(v'g"(x + 2))(1 - 2). z)dt
+ ( -ly- x))(v x), y z)
+
(V (x + t(y 2))(y - z). y - z)
11
2 (1 + to - f1) - z|1² - 2(11 - to) Lglly - x:
(1 + to f1)llly z11² Lnlly x212
" 1 |I 1= - T.g xrl??
where we used equation (83) in the last relation. So, we get
(v) 676 (z), x) トー 2bg - Lg)lly xx1?.
To conclude, in the three cases, for |1 - x|| 2 4 Rg and by Assumption 3(ii) 8L, + 4L, S 1s, we get
(b(y) - b(x),))))))))) 2) 2 _
2 2L, L,)1ly x1
2 4 Ily x x11
which proves the point (ii) of Lemma 21.
G.2 Proof of Theoreem
First, we recall the statement of Theorem 3.
Theorem 8. Under Assumptions 2-3, there exist r E (0, C2 R4 such that V7 E (0, 7).
with 7 min 1 2L, 32(L/ 1 72) where Lg, Ly, Lys,, P. n are defined in Assumptions 2-3, and vk E N, we have
Wp My) S kr + "27
(84)
with Pv, the distribution of Yn and Hl x 1--9"
Moreover there exist Cs, C4 E R4 such that Vy E (0, 7) and Vk E N. we have Wplpx,, S Oyr + 2 with px, the distribution of Xx and vy x Proxyo -1
(85)
53

---

Proof. Thanks to Lemma 21, under Assumptions 2-3, the drift of the Markov Chain Y₁ 8 verifies Assumption 1 with constants independent of y. Therefore, using Theorem 5, we deduce that this Markov Chain Y& is geometrically ergodic, so there exist C₁ 2 0, E (0, 1) and an invariant law Pco such that
Wi(Py, Poo) S C2rhy,
(86)
with Py, the distribution of Ys.
Next we introduce the Markov Chain E2 such that Yo = Yo and
Yk+1 Yo + (bo() + / 27/2+11
with bo -Vg" ff and Zx+1 (O( Following the same proof than Lemma 21, we deduce that bn verifies Assumption for y S min (t. - with the same parameters than b7, I, = 2I, + g. R = 4 Rg and 4. Note that L, R and m are independent of 7. The parameters T,y, l.g. Ro, p. 71. P are defined in Assumptions 2-3. Theorem gives that for " + and
7 E 70]. Yx geometrically converges to its invariant law p. and there exists C2 2 0 such that
Wp(Pee, p.) S C2 (Ex~px (1](X)) (x))) *
We define 7 = min (b- 1
24," m. 32(L, ,211,
Then, using the definition of in equation (11) and b0. Assumption Assumption 2()), Assump- tion 3(), the fact that g = Vg(Pro (x)) (see Lemma 12 of Appendix D.6) and Lemma 11 of Appendix D.5, we get
W Wp(pso, pT) < C2 (Ex-p (IVS(X- ~V)((x) - {)(x))3) $
s C2 (Rx-p= (IVg)(X)113) #
s C21ii (Rx-px ( (x) (12) #
s C2 (21,Ex-p= (1oro (x) Proxy9 (0) 11-) + 2|opoo (x) (13) +े
#
s CaLfn+ (
213
(1-) Ex-po (1|X11) + Proxg (0) 112
By equation (53), we know that for 7 5, Xx (IIx is bounded by constant independent
of y. Then, for 7 S 7 S 2p" we have I->p $ 2. Moreover Prox.y (0) 0 when 7 0. So there exists a constant C3 2 0, independent 7, such that, for y (0, +]
WI(Poo p.) & CsyR.
(87)
Note that by = V (g" + +f), so by Theorem 2, there exists C4 2 0 such that Vyy E (0, we have
Wplpy, My) S C
(88)
with My x 5-
Combining equations (86), (87) and (88) and the triangle inequality, we get
W (p Mx) I Ci + Csy + Cay
I kr + #
with C33 C3 + CC, This proves the first part of Theorem 3.
54

---

Due to Xx Prox (Y&), the distribution pxt of X is Px, P PY with Pv; the distribution of Y and "# the push forward operator defined for measurable set A C R by Px, (A) = py; (Prox (A)). With vy = Prox.g # ply, we get
Wp WPxxx M4) = min
1 x2 d211
3EA XR
with A the of all possible transport plans B between Px2 and V4. By the forward definition and Lemma 11 of Appendix D.5, we obtain
W pPXxx By) min SEA Rd
||Prxx9 (x1) - Proxxg (x2) (id((,,))))
$
min BEA
1121 12 x2|ld3(01,
(1 2p)
2p
W (p).
(1
7p)
The last equation demonstrates the second part of Theorem
G.3 On the exact law approximation with PSGLA
In this section, we provide a proof for Proposition 1. First, we recall this proposition
Proposition With æ x e My x e- and Vy = Proxyg#Hry Pyy we have, for V Rd
[1, +00) and p
lim |1 - x xllv = 0 7-00
(89)
lim
W Wp((yy TT = 0
(90)
lim W ( =0
=0
(91)
200
Moreover, if g'g L-Lipschitz, there exists Ep E R such that Vy E [0, 1
1 x s (T
(92)
W T) S Ep(L?
(93)
Wp +) +) S (T, + Lyy
(94)
Proof. This proof is generalization of the strategy proposed in the proof of [28, Proposition 3.1]. By the definition of the V-norm in equation (43), we have
sup / o(x) (M)(2) x(x)) dz, 10l5V
My T/|v
Rd
with (x)x = e- (-))) and x(x) a -()0)))0)))
JeT Then
||4 = sup 16(x)) I (x) [xx)
lølgv JRd
v(x) ((r) (m) 15--9 5-- dr
|1 1- (()))(())))))) - dx + / ((())(x)eelt))00)))
f E t-g
((z)<(z)
1--1-97 dx.
Rd
However, we know that Vor E Rd (x) S g(x), get
Il,, - =|lv
< / ((x)T(z) (co(o)- 11) dx + / (( (1 (1- -et- [e-
(1-
dx. (95)
Rd
55

---

For x E R., lu
(z) g
g(x) and the function - (2) is decreasing. So by the monotone
convergence theorem, we have
lim Ma - T/lV = 0. y-3
Lemma 18 proves that si W (M T) 0. This concludes the first part of Proposition 1.
Next, by the triangle inequality, Lemma 11 of Appendix D.5 and taking the particular coupling (Ia, Proxgg) # between π and Prox,a #T, we get
W wp(k,,m 1T) I w, (P Huy Proxyg #*) Wp (Prox H,,
W Wp( r)) + inf / |0s x2 x211"d((21, 222)
1 7p
W Wplny 1) (ʃ (fl1-11-1-00 | (2)) (
7P By the definition of the Moreau envelope, we have g(Prox (z)) + 2, || Prox (x) S sx(), so we get
Wp Wplm, R)) + /2 (f (l(( g(Prox (z)) dz((z)
W Wp(n, T) 1 7p
However, by Lemma 2 of Appendix D.2, we have that 19(x) - ((Prox (x)) has monotone con- vergence to O. By the monotone convergence theorem, we obtain
lim W Wp(nys T) = O. 7-0
If g is L-Lipschitz, then, for æ E Rd, we have
1
1 sup g(x) g(y)
g(x) - (x) = g(x)
inf yER*
||
y/12
9(w)
1| y/1
27
VER"
27
1
L
s sup || اار
||
= y/
7
yE
27
2
Since (xx) 2 (x) for all x Rd, we get و1g 10 equation (95), we get
r 2
By injecting this inequality into
|R, T/vv
< f ((x)((1) ( dx + / V(a)x(z)e (1-
-e-5- de.
Jzd
[e-1-07
Thanks to forr
2 20 we get
| T|lv S xV) (014-1) (V)) 12 (000))1(1---11 (1-0-14)
2V)
For [0, e 1 2u, so for S 3. we have
|1 1 T|V S (T)22
Using Lemma 18 of Appendix F.2, we obtain
W Wp(my, $2 (T(
which concludes for the inequality in W, distance between Hy and ग. with E, (v))
Using Lemma 12, the fact that V lox < L if is I--Lipschitz, the previous bound on W Wp((y, T)) and the particular coupling (Ia, Prox # between (by and My, we get
W 7y(y, S W Wplm,, m4) + W (1y, m) S (/ / (s))) -W
S + +
This demonstrates Proposition I with E, (V)))
56

---

G.4 Proof of Theorem 4
The Inexact PSGLA defined with S, an inexact approximation of Proxyg by
Xx+1 = Sy 18x->V((X; + /
with Ze+1 NN, Ia) i.idd We can write this algorithm as a two points algorithm
Yot1 = Xx (VV((K) + 22
Rx+1 = Sr (8a+1)
By introducing G, = = (Id - ST), we have that
Yx+1 = Sn kx) /V,S (vx)) 2
= Y% (Y,)(t)) - -VVS(2 -Vn)( + 27
8v-- 78b'()) -22
with the drift (1 Vf G,(())++ (v)
We recall Theorem 4. Theorem 9. Under Assumption 2-3, if verifies Assumption 1, there exist y > 0 and Cs, Co O7 R+ such that Vy (0,5), Yx of equation (14) has an invariant law j.y and Vk E N, have
O7 || Proxng (((r))"
W Wp(px, My) Osr + Cay $
7
Theorem is generalization of [33, Theorem 3.14] as it holds for non-convex potentials. Moreover, in our study, we do not assume priori that the inexactness of the proximal operator is bounded.
Proof. We assume that iz verifies Assumption 1, Yn is geometrically ergodic with invariant law Boy and there exist Bo 2 0 and r E (0, 1), such that
Wp(Pg, (r) S Bar*
(96)
with pv, the distribution of Y2
We define the sequence Yx+1 = Y4 (b² + 22 with (y) = V (v)" +
Vgg defined in equation (11). Thanks to Theorem 3, under Assumption 2-3, 67 verifies Assump- tion I and Y has Poo as its invariant law. By Theorem 1, we get that there exist 72 > 0 and B₁ 2 0
such that V/ 72]
W Wp Poc) S B1 (BY~A, (1b -Y()))))))))))) 2
Vg -VG < 2 B1 (By~i,, (Y)
< 2 Bi (00-:///110111000//------------0
#
137001121 V)) +
< 2 (1 + 1.7 12/72)== + (Ey~a, (1l> (Prox, (Y) - S₂ (V)()))
< 2 (1 + 13772) 3 |Prox S.y Sy)l)x((0))))
(97)
By combining equation (87), equation (88), equation (96) and equation (97) and the triangle inequal- ity, we get that
W Wolpge my) < Bor + 2 Bi (1 1372) 7 1/2 Proxn9 S C2y + Cay 30
$ Barky + + Bi + 12) 2ي ||Prox S + C3 $ / + +
< Bo + BBy i|Proxx, Sy SylEe(p.)) + #,
57

---

with 132 = 2 (1+ 13)r) io and B3 0372 + C4.
Now, we prove that for y small enough, G.y is Lipschitz. By Assumption 1()) by is L-Lipschitz and by Assumption 2(0) V is Ly-Lisschitz, for 7 (0, 72| and x, R4, we have
[z)(xx) - (v)) - L| y/ Vf(y - -G, S L yl
[G,(()) - V - -Vff -Vfy - -,,, _ L|| yll
(3)xx) -b, (1 s L||= yll
(1 (1- - C,(,) _ (L + L - v/l-
1 For 7 2L," get
(G) s 2 + [ vll-
(98)
So G. is LG 2( Lg Lippshitz We denote 73 min 72. s
We have that Px, = S. #r, and S, Ia -G,, is (1 + 73 LG) Lipschitz. Hence we obtain
wP(p = min DEA /d
[15,(z1) - (x,)) (22
$ (1 + Lc)
min BEE Rdx3d
| x2 x211"dd(
(1+ +
W (Ppg Mr))
with A the set distribution on Rd x Rd with marginals py, and μry This proves the desired result
with ý = 73. C = (1 + Bo. Co = (1 +1+ (3LG)) Bg and Co (1 + 13LL))
58

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our abstract and introduction explained our main theoretical results (Theo- and Theorem 3) and our experiment study (see Section 5). For instance, the assump- tion of strong convexity at infinity of the potential is clearly stated.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
fine to include aspirational goals motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
In the limitations section (Section 7), we clearly state the limitations of the paper.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "L.mmittions" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
59

---

Answer: [Yes]
Justification:
Assumptions are clearly stated in our theoretical results and detailed proofs of all our theoretical results be found in the Appendix. Sketch of the proof is given for the main results, Theorem and Theorem 3. A link to the proof of each result is given just after its statement in the main paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proof's provided appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data provided not)?
Answer: [Yes]
Justification: In Appendix C, all the parameters setting and exact algorithm implementation are given. Moreover, our code provided in supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model ge.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurlPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
60

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code is provided in supplemental material with detailed instruction for users. All the models weights and the data are open access.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
Sttees//ooeuuumissttte conPolicyy olicy) for more details. public/guide Baalcc/ggges///ee
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: // //nips..
wwtpc//gggiesseeeeeee Codee//dddeeebmeeeic sssisssionn asionPolicy" for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: In Appendix C, we provide all the parameters setting for the implemented algorithms. Moreover, the full code given in supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should presented in the core the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: In Appendix C, we provide the uncertainty of restoration for sampling algo- rithms, PnP-ULA and PnP-PSGLA.
Guidelines:
The answer NA means that the paper does not include experiments.
61

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g,, Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of eπrоrs is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: In Appendix C, we provide the type computer and the time of execution for our experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: htttps///errpps.cppppppcc///e/ee wttpe/hhhiiiiieeeeeeeeeeeeeeeeee
Answer: [Yes]
Justification:
The Code of Ethics have been respected in the paper.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The societal impacts of the paper is discussed in Scction 7.
62

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper is theoretical study of algorithms and only use open source data and models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Each data or models that have been use is reference in the paper. In supple- mental material, reference with the code all piece of the code that comes from other research papers.
Guidelines:
The answer NA means that the paper does not use existing assets.
"The authors should cite the original paper that produced the code package dataset.
63

---

The authors should state which version of the asset is used and, if possible, include URL.
The name the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswi wwwceheeeee... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooell as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and sereenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to NeurlPS Code Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing research with human subjects.
Guidelines:
64

---

The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy (https: htttp::/neeurpp.... / for what should or should not be described.
65


Reviews:
[{"review_id": "8fRHkgJX8k", "reviewer": "Reviewer_GF73", "summary": "The paper studies the stability of unadjusted Langevin algorithm with drift approximations, under the assumption that the potential is strongly convex at infinity. This assumption allows for nonconvex potentials. The resulting bound of the distance between (two biased) invariant distributions involve only the drift approximation error and no additional discretization error as seen in previous bounds. The distance between the biased invariant distribution and the target distribution is also provided. These bounds are in both $W_p$ and TV. The paper then applies these bounds to a specific algorithm with an approximate drift, namely, the proximal stochastic gradient Langevin algorithm (PSGLA). The convergence and bias bounds of PSGLA are provided. Numerical experiments compare several methods in posterior sampling, including PSGLA and its variants, and show competitive performance.", "questions": "Questions:\n- The key contraction results are referenced from previous works. I am curious whether they are based on reflection coupling since it is a common technique in nonconvex settings. Also, how good are those referenced bounds?\n- Regarding the tightness of the bounds in terms of nonconvexity, I am wondering whether the dependence on $R$ is hidden in the constants in the proofs. For example, in the proof of Theorem 5, page 41 eq (52), Corollary 2 in reference [22] is referred, but as I see in that paper, it should be $(1 + \\|x-y\\|/R)^{\\frac12}$. Maybe exposing $R$ dependence could be helpful to see the behavior of the bounds in nonconvex cases.\n- In the proof of Theorem 5, how important is it to choose $m \\gamma \\sim 1$? Do other choices of $m$ give similar bounds?\n- page 49 eq(80)-(81): for $\\mathbb{E}\\|\\nabla V(y_{u,j})\\|^2$, I understand that $y_{u,j}$ is not at equilibrium. It is known that $\\mathbb{E}_\\pi\\|\\nabla V\\|^2 \\leq Ld$ if $\\nabla^2 V \\preceq L I_d$, and I am wondering whether utilizing this fact could improve the bound a bit.\n\n\nTypos/minor questions:\n- page 3 line 81: \"In particular, the $L$-Lipschitzness involves that the drift is $L$-weakly convex\". Also page 16 line 623-624, \"Assumption (i) is equivalent to $-LI_d \\preceq \\nabla^2 b \\preceq L I_d$. I don't understand this claim. Since the Lipschitz constant is essentially a first-order information, how could it imply the second order derivatives of $b$?\n- page 8 Figure 1 caption: prior distributions in green -> they are in blue. The samples are green.\n- page 16 line 620: \"Assumption 2(i)\" -> Assumption 1(i).\n- page 38 Lemma 17, for TV, $V = 1$ and the current statement will be off by a factor of 2 (since TV is used as in line 1151 on page 39).\n- page 39 the equation after line 1156: there should be an expectation sign for the integral part.\n- page 41 line 1218, \"$R \\pi = \\pi$\" -> the LHS should be left multiplied by the $\\pi$.\n- page 45 line 1295: the inequalities after line 1295 and line 1297 have some inconsistent notations: eg. C_2 vs A_2 and W_4.\n- The statement in Proposition 1 and its restatement as Proposition 4 on page 52 are not consistent: Proposition 4 has $L^2$ in eqs (92) and (93) but they are $L$ in Proposition 1.\n- page 47 line 1339, \"$\\rho_p$ is independent of $d$\" -- does $\\rho_p$ depend on $\\gamma$?\n- page 57 the equation after line 1524 misses $1/p$ powers on the right.", "limitations": "There are some discussions of limitations in Section 7, but limitations in terms of the theoretical analysis are not discussed.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper is extremely well-written. The related works are clearly covered. The organization of the paper is thoughtful: Section 2 provides stability results of ULA which could be helpful for future research; and Section 3 provides intuitions and properties of proximal samplers, and then applies theories in Section 2 to the proximal sampler. This organization separates two theoretically heavy parts: stability results and proximal sampler properties, into two sections, which help readers to follow the paper. Within each theoretical part, the authors clearly state the main theorems and provide discussions of these results, without confusing readers with technical details. The appendix is also well-written. It has great background information. For example, it summarizes properties of the Moreau envelope, which is very friendly for people first knowing this important concept for proximal samplers. The proofs of the theorems have clear frameworks and I find them easy to follow. The authors show care for many writing details. Overall, the authors did a great job of presenting the results which could otherwise be very dense.\n2. The question of convergence and bias of proximal samplers in non-log-concave sampling is interesting.\n3. The stability results of unadjusted Langevin algorithm involve only the difference of the drifts, and bounds in both $W_p$ and TV metrics are provided. I think the results are interesting and can be useful for future research.\n4. Besides the theoretical contributions, the paper also has abundant numerical experiments on posterior sampling, comparing variants of PSGLA with other image restoration algorithms. The authors draw clear connections between the theoretical setup and the application scenario.\n\nWeaknesses:\n1. I am not sure how good/tight these bounds are, especially since most constants are not explicit (although I understand that the dependence could be complicated). I see discussions in Appendix F.5 on constants in Theorem 1. Currently, there are no discussions on the tightness of these bounds, for example, on the dimension $d$, nonconvexity (the radius $R$), and constants $m$ and $L$. In simple cases such as the Gaussian mixture, are the bounds good enough (especially when the nonconvexity is severe)? \n2. There is no theoretical explanation about the phenomenon that PnP-PSGLA with DnCNN outperforms PnP-ULA and the latter is slower in the numerical experiments. In the Gaussian mixture example, page 8 line 265, the authors mention the intuition that \"PnP-PSGLA rigidly project the iterates on the 'clean data' manifold\". I am curious whether the advantage of PnP-PSGLA over PnP-ULA can be understood within the framework of Section 2. (Although Section 2 is about distance between invariant distributions, the proof involves convergence rates along iterations.)", "was_revised": true, "final_justification": "The authors have provided detailed and clear response to all my questions, and I think this is a solid paper to publish in NeurIPS.", "rebuttal": "Thank you for your positive feedback and careful reading of our paper. We thank the reviewer for sharing some typos, especially in the Appendix. The typos that are not mentioned in our response will be corrected following the reviewer suggestions. Please see below our detailed responses.\n\n- I am not sure how good/tight these bounds are, especially since most constants are not explicit (although I understand that the dependence could be complicated). I see discussions in Appendix F.5 on constants in Theorem 1. Currently, there are no discussions on the tightness of these bounds, for example, on the dimension $d$, nonconvexity (the radius $R$), and constants $m$ and $L$. In simple cases such as the Gaussian mixture, are the bounds good enough (especially when the nonconvexity is severe)?\n\nWe thank the reviewer for raising questions regarding the tightness of the derived bounds. We acknowledge that this problem is mostly untractable. Indeed, in order to evaluate the tightness of the bound, we need for two drift $b^1$ and $b^2$ to be able to compute the associated invariant laws $\\pi_{\\gamma}^1$ and $\\pi_{\\gamma}^2$. Even if the drifts $b^1, b^2$ derive from Gaussian Mixture potentials, the invariant laws $\\pi_{\\gamma}^1, \\pi_{\\gamma}^2$ do not seem to be explicit. We find that if the drift $b^1, b^2$ derive from isotropic Gaussian potentials, the invariant distributions $\\pi_{\\gamma}^1, \\pi_{\\gamma}^2$ can be computed explicitly and the constant of Theorem 1 does not depend of the dimension. However this simple case does not capture the non-convex phenomena that we aim to address in this work. In order to highlight this limitation of our work, we propose to add at line 309 : \"From a theoretical point of view, we identify two main limitations of this work that might motivate future research. The first one is to obtain theoretical insights, such as accelerated convergence rate, of the superiority of PSGLA over ULA. The second one is to analyse the tightness of the constants involved in Theorem 1-2 that are partially implicit in the current work.\"\n\n- There is no theoretical explanation about the phenomenon that PnP-PSGLA with DnCNN outperforms PnP-ULA and the latter is slower in the numerical experiments. In the Gaussian mixture example, page 8 line 265, the authors mention the intuition that \"PnP-PSGLA rigidly project the iterates on the 'clean data' manifold\". I am curious whether the advantage of PnP-PSGLA over PnP-ULA can be understood within the framework of Section 2. (Although Section 2 is about distance between invariant distributions, the proof involves convergence rates along iterations.)\n\nThe superiority of PnP-PSGLA over PnP-ULA is only supported by empirical evidence in this paper. We highlight it to motivate the interest for more theoretical insights on PSGLA. In fact, the mixing time of PnP-ULA is its main drawback and PnP-PSGLA seems to be a good practical candidate to sample with a more reasonable mixing time. In this paper, we give the first proof of convergence for PSGLA in a non-convex setting. \nBoth PSGLA and ULA geometrically converge in our setting, studying the convergence rates of each method might be a way to compare theoretically these two algorithms. A fine analysis of the rates provided by [22] should be a first step for this analysis. We leave that work for future work.\nWe propose to add in the conclusion the following sentence at line 309: \"From a theoretical point of view, we identify two main limitations of this work that might motivate future research. The first one is to obtain theoretical insights, such as accelerated convergence rate, of the superiority of PSGLA over ULA. The second one is to analyse the tightness of the constants involve in Theorem 1-2 that are partially implicit in the current work.\"\n\n- The key contraction results are referenced from previous works. I am curious whether they are based on reflection coupling since it is a common technique in nonconvex settings. Also, how good are those referenced bounds?\n\nIndeed the main contraction rates we exploit are proved in  [22], where the authors based their analysis on a projected version of the discrete reflection coupling. To our knowledge, these bounds are state-of-the-art in the context of Langevin sampling for non-convex potential. Moreover, the rate proved in [22] (see equation (10)-(11) in [22]) is closed to the optimal convergence rate (from a small factor $(1-e^{2mR^2})^{-1}$) in the small step-size limit, i.e, those rates match the continuous-time limite rates obtained in [A Eberle, A Guillin, R Zimmer, Couplings and quantitative contraction rates for Langevin dynamics] which are optimal.\n\n- Regarding the tightness of the bounds in terms of nonconvexity, I am wondering whether the dependence on $R$ is hidden in the constants in the proofs. For example, in the proof of Theorem 5, page 41 eq (52), Corollary 2 in reference [22] is referred, but as I see in that paper, it should be $(1+|x-y|/R)^{\\frac{1}{2}}$. Maybe exposing $R$ dependence could be helpful to see the behavior of the bounds in nonconvex cases.\n\nAs the reviewer noticed, $C_p$ indeed explodes when $R \\to 0$. This dependency is hidden in the constants $E_p$ and $A_2(x)$ in the paper. We obtain $C_p \\sim \\left(\\frac{1}{R}\\right)^{\\frac{1}{2p}}$ when $R \\to 0$. However, in the case of $R = 0$, the potential is strongly convex and other tools could be used. The challenging and albeit more interesting case is when $R \\to + \\infty$. We obtain that the dependency is exponential in $R$ with $C_p = \\mathcal{O}(e^{\\frac{LR^2}{4}})$ when $R \\to +\\infty$.\nWe propose to make these dependencies explicit and detail them in Section F.5.\n\n- In the proof of Theorem 5, how important is it to choose $m \\gamma \\approx 1$ ? Do other choices of $m$ give similar bounds?\n\nThe choice of $m \\gamma \\approx 1$ is arbitrary in the proof and can be changed. The important point for the proof to hold is to choose $m \\gamma$ close to a fixed quantity. If we chose a different quantity for $m \\gamma$, the proof can be derived in the same way and, at the end, the constant will be multiplied by a factor $\\frac{\\sqrt{m \\gamma}}{1 - \\rho_p^{m \\gamma}}$. In theory, the factor $m \\gamma$ could be optimized.  However, to our knowledge there is no closed-form formula to find the minimum of $m \\gamma \\mapsto \\frac{\\sqrt{m \\gamma}}{1 - \\rho_p^{m \\gamma}}$. Therefore, we choose to keep $m \\gamma \\approx 1$ for simplicity.\n\n- page 49 eq(80)-(81): for $\\mathbb{E}|\\nabla V(y_{u,j})|^2$, I understand that $y_{u,j}$ is not at equilibrium. It is known that $\\mathbb{E}|\\nabla V|^2 \\le L d$ if $\\nabla^2 V \\preceq L I_d$, and I am wondering whether utilizing this fact could improve the bound a bit.\n\nWe thank the reviewer for this suggestion to improve the proof. Please correct us if we do not understand your suggestion. If $V(x) = \\|x\\|^2$ for $x \\in \\mathbb{R}^d$, then $\\nabla V(x) = 2x$ and $\\nabla^2 V = 2 I_d$, so, for $L = 2$, $\\nabla^2 V \\preceq L I_d$ but $\\mathbb{E}|\\nabla V(y_{u,j})|^2 = 4 \\mathbb{E}|y_{u,j}|^2$ could be larger than $L d$ if $y_{u,j}$ has a large variance. This seems to be a counter-example to this suggestion.\n\n- page 3 line 81: \"In particular, the $L$-Lipschitzness involves that the drift is $L$-weakly convex\". Also page 16 line 623-624, \"Assumption 1(i) is equivalent to $-L I_d \\preceq \\nabla^2 b \\preceq L I_d$. I don't understand this claim. Since the Lipschitz constant is essentially a first-order information, how could it imply the second order derivatives of $b$?\n\nWe thank the reviewer to point us this typo, it should be $\\nabla b$ instead of $\\nabla^2 b$. In fact the Lipschitness is linked to a first order information. We propose to reformulate page 3 line 81 into : \"In particular if $b = \\nabla V$, the $L$-Lipschitzness of $b$ implies that the potential $V$ is $L$-weakly convex\". And to reformulate page 16 line 623-624 into \"Moreover, if $b = \\nabla V$, the potential $V$ is $L$-weakly convex. Assumption 1(i) is equivalent to $-L I_d \\preceq \\nabla b \\preceq L I_d$.\".\n\n- There are some discussions of limitations in Section 7, but limitations in terms of the theoretical analysis are not discussed.\n\nWe propose to add in line 309 the following theoretical limitations : \"From a theoretical point of view, we identify two main limitations of this work that might motivate future research. The first one is to obtain theoretical insights, such as accelerated convergence rate, of the superiority of PSGLA over ULA. The second one is to analysis the tightness of the constants involve in Theorem 1-2 that are partially implicit in the current work.\".\n\n- page 47 line 1339, \"$\\rho_p$ is independent of $d$\" -- does $\\rho_p$ depend on $\\gamma$ ? \n\nThe constant $\\rho_p$ is independent of $\\gamma$ for $\\gamma \\in (0, \\gamma_0]$, This is detailed in Appendix F.5 line 1338. We highlight here that the main dependence of $\\rho_p$ is with respect to the radius of non-convexity $R$.\n\n- page 38 Lemma 17, for TV, $V = 1$ and the current statement will be off by a factor of 2 (since TV is used as in line 1151 on page 39).\n\nWe thank the reviewer for stressing this imprecision. The correct formula is $|\\mu - \\nu|= 2 \\inf_{\\beta \\in \\Pi} E_{(X, Y) \\sim \\beta}{1_{X \\neq Y}}$, with$|\\cdot|$ the total-variation norm, (see for instance Theorem 5.2 in [Torgny Lindvall. Lectures on the coupling method, 2002]).\nWe will correct the error in line 1151, lemma 19 and the constant in the proof (it only changes the constant $D_p$ to be $D_p = 4 \\sqrt{2} E_p \\sqrt{M_{2p}}$ in line 1236)."}, {"review_id": "kl3Lbu9EOc", "reviewer": "Reviewer_zNf2", "summary": "This is a theoretical paper addressing the problem of sampling distributions with non-convex potentials. The authors focus on analyzing the Unadjusted Langevin Algorithm (ULA) and its proximal variant, the Proximal Stochastic Gradient Langevin Algorithm (PSGLA). They contribute to proving the stability guarantee and discretization error of inexact ULA, as well as the convergence of PSGLA. Finally, an application to posterior sampling is included to show the superiority of PSGLA over ULA.", "questions": "I don't have further questions but I will continue to refer to the opinions of other reviewers.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The theoretical part of this paper is well-organized with clear statements. Several contributions are made for theoretical guarantee of non-log-concave sampling. \n- Detailed proofs as well as comprehensive discussions about the made assumptions are included. \n\nWeaknesses:\n- The link between the theoretical and experiment parts is not very tight. While the theoretical part mainly focuses on proving the stability results of ULA and the convergence of PSGLA, the experiment part focuses on showing the superiority of PSGLA over ULA. \n\nI am familiar with diffusion models but not particularly familiar with this specific field. I will continue to refer to the opinions of other reviewers for a more comprehensive evaluation.", "was_revised": true, "final_justification": "I thank the authors for the response. After reading the other valuable reviews, I believe that the quality and potential impact of this paper are worthy of further recognition. I am willing to increase my rating.", "rebuttal": "Thank you for your positive feedback and careful reading of our paper. If the reviewer has any more concerns regarding our paper, we are ready to answer them.\n\n- The link between the theoretical and experiment parts is not very tight. While the theoretical part mainly focuses on proving the stability results of ULA and the convergence of PSGLA, the experiment part focuses on showing the superiority of PSGLA over ULA.\n\nThe theoretical part focuses on proving a refined stability result on Langevin algorithms and use it to derive the first proof of convergence of the PSGLA in non-convex setting. In the experimental part, we showcase the PSGLA convergence and performance in different non-convex settings including GMM sampling and image restoration (see Figure 1 right row for convergence for GMM). Those theoretical results motivate our empirical study. In practice, we found that PSGLA converges faster than ULA to acceptable solutions."}, {"review_id": "0Eh3fi1oft", "reviewer": "Reviewer_op2G", "summary": "The paper is interested in discretizations of the Langevin dynamics whose stationary measure has density is $\\pi \\propto e^{-V}$ where $V = f + g$ i.e., a composite potential. More specifically, the paper is focused on settings of $f$, $g$ which are both not necessarily convex and differentiable. The first contribution of the paper is to understand the effect of an inexact discretization of the Langevin dynamics, and give sharper results for the stability results of the discretizations in the Wasserstein and TV metrics. Somewhat orthogonal to this result, the authors then consider the proximal SGLA which mimics the forward-backward method in optimization but for sampling and provide guarantees for the method under what appear to be newer assumptions on $f$ and $g$ compared to prior work. Finally, they instantiate an approximate version of this method for a couple of empirical tasks where they demonstrate the efficacy of this method.", "questions": "1. Invariant law: $X_{\\infty}$ instead of $X_{k}$?\n2. What does data-fidelity mean? Is it another term for the negative log-likelihood of the data under some model?\n3. Are there settings where the regularizer $g$ is chosen to the non-convex (which corresponds to a non-log-concave prior)?\n4. Theorem 2 is a characterization of the bias limit of the unadjusted Langevin algorithm, for which there are analyses for when the distribution $\\pi$ satisfies a log-Sobolev inequality which implies results of the form in Theorem 2 (for $p = 1, 2$ and TV). For drift $b = \\nabla V$ that satisfies Assumption 1, can it be said that $pi$ satisfies a log-Sobolev inequality, and how would the bounds on $W_{p}(\\pi_{\\gamma}, \\pi)$ compare in that case?\n5. Why is there a dependence on the smoothness of $f$ in the properties assumed about the Moreau envelope of $g$? Is this in some sense necessary, or does it make the analysis easier?\n6. The second part of theorem 3 is interesting, why is the push forward of the Moreau-corrected version of $\\pi$ by the proximal operator an interesting distribution to have results for?\n7. How does Proposition 1 compare to the composition of results from theorem 3 and Proposition 1 in https://arxiv.org/pdf/2405.15379? The setting in the latter proposition is constrained, so it might not be possible to directly use their result, in which case apologies.\n8. How does this compare this to the work of https://arxiv.org/abs/2101.06369 generally?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper is decently written, although I feel like the paper could be written better -- there are redundancies in various parts of the text. For example:\n- beginning of Section 3 (described previously in Lines 36-37),\n- contributions (1) (described previously in Line 34).\n\nAs noted in the summary, the contents of Section 2 seem somewhat disconnected from the rest of the paper as framed, and it is not immediately clear how this is relevant to the rest of the work (although the results from Section 3 use a result from this section) and it would be useful to highlight the relevance apriori (or rearrange the sections appropriately). I still think that the results of that section are interesting, although it would be instructive to the reader to help clarify what were the (new, if any) elements in comparison to the previous analyses that led to the stronger guarantees in this work (I understand that there's a proof sketch, but I feel like this would be more valuable). In Section 3, the first two properties stated of the Moreau envelope are rather well known (see for instance the monograph by [Parikh and Boyd](https://dl.acm.org/doi/10.1561/2400000003)). The discussion about PSGLA is also mostly derivative of prior discussion in [81] and could be condensed. With regard to Assumption 3, it would be helpful to give some examples of potentials $g$ satisfy this together (since properties of $g^{\\gamma}$ are generally harder to interpret.\n\nOther miscellaneous remarks:\n\n1. The notion of coupling in the definition of $W_{p}$ is a bit tedious, can be simply stated as collection of joint distributions whose marginals are $\\mu$ and $\\nu$.\n2. Analogously, the pushforward can be simply stated as $\\phi_{\\\\#}\\mu(f) = \\mu(\\phi(f))$.\n3. The notion of weakly convex is actually more commonly referred to as semi-convexity (see for instance: https://arxiv.org/tml/2502.03458v1).\n4. Would recommend moving definitions about invariant law, geometric ergodicity into Sec 1.1.\n5. Technically, only if $b$ is the gradient of a function is assumption 1(ii) a weaker version of $m$-strong convexity at infinity. This is just a growth condition that compliments the Lipschitz continuity assumption in 1(i) (Lipschitz continuity is not defined).\n6. Line 64: A function twice-differentiable --> A twice-differentiable function\n7. Line 103: following the same strategy than --> following the same strategy as", "was_revised": true, "final_justification": "I think this is an interesting paper, and would suggest the authors to make the recommended changes.", "rebuttal": "Thank you for your positive feedback and careful reading of our paper. We thank in particular the reviewer for pointing us some typos. The typos that are not mentioned in our response will be corrected following the reviewer suggestions. Please see below our detailed responses.\n\n- I feel like the paper could be written better -- there are redundancies in various parts of the text.\n\nWe thank the reviewer for spotting these redundancies. For the clarity of the paper, we choose to highlight our contributions in a separate paragraph and to explain our reasoning in the beginning of the sections. This choice can lead to some redundancies. We propose to reformulate line 34 into : \"With a new proof strategy, we overcome this limitation in Theorem 1 in Section 2.\" We would also be happy to include other feedback regarding the writing of the paper. \n\n- As noted in the summary, the contents of Section 2 seem somewhat disconnected from the rest of the paper [...] this would be more valuable).\n\nWe thank the reviewer for the feedback about the Section 2/3 articulation. Section 2 shows new general facts about Langevin stability in non-convex setting. Section 3 focuses on the convergence analysis of PSGLA, a specific proximal Langevin algorithm. The stability and discretization results proved in Section 2 are key for the PSGLA convergence analysis. Our structure is going from the more general results to the more particular ones. To make it clearer for the reader, we propose to add in line 71 the following sentence : \"The sampling stability result (Theorem 1) and the discretization error bound (Theorem 2) demonstrated in the section will be the key ingredients for the PSGLA convergence analysis in Section 3.\"\n\n- In Section 3, the first two properties stated of the Moreau envelope are rather well known (see for instance the monograph by Parikh and Boyd).\n\nIn fact the first three properties of Lemma 1 are well known for convex functions (as detailed in the monograph by Parikh and Boyd). In this paper, we generalize the properties for weakly convex functions. All the proofs and references for each property are given in Appendix D. The last property of Lemma 1 is totally new. We state these properties in the main paper because their are useful in Section 3.\n\n- The discussion about PSGLA is also mostly derivative of prior discussion in [81] and could be condensed.\n\nPSGLA have been introduced in [28] and studied in [81]. As advised by the reviewer, we checked [81] again. The interpretation of PSGLA as a different discretization of continuous Langevin dynamics than ULA is nevertheless not mentioned in [81] and the reformulation of PSGLA as a two-point algorithm to study the shadow sequence is not present in [81].\n\n- With regard to Assumption 3, it would be helpful to give some examples of potentials $g$ satisfy this together (since properties of $g^\\gamma$ are generally harder to interpret).\n\nLemma 16 in Appendix E gives an example of $g$ that satisfies Assumption 3. It shows that if $g$ is strongly convex at infinity and globally smooth, then Assumption 3 is verified. Prior with GMM potential are strongly convex at infinity and globally smooth. \nPlease note that Assumption 3(ii) could be removed by slightly modifying PSGLA as detailed in Appendix B on the discussion about Assumption 3(ii). \nTo make it more explicit in our comment, we propose to reformulate line 178-179 with : \"Lemma 16 in Appendix E shows that if g is strongly convex at infinity and globally smooth, such as Gaussian mixture models, then Assumption 3(ii) is verified.\".\n\n# Miscellaneous remarks:\n1- We thank the reviewer for his suggestion and we propose to modify line 62-63 into \"with $\\Pi$ the set of probability law $\\beta$ on $\\mathbb{R}^d \\times \\mathbb{R}^d$ whose marginals are $\\mu$ and $\\nu$.\".\n\n2- In our paper, we need (for Theorem 3 and Proposition 1 in particular) to introduce the pushforward measure and not only the pushforward measure applied to a function $f$.\n\n3- In the literature, both terminology are used : semiconvex in [Crandall, Michael G and Ishii, Hitoshi and Lions, Pierre-Louis, User’s guide to viscosity solutions of second order partial differential equations]; and weakly convex in [20, 39, 44, 47, 82]. We choose to use weakly-convex as it seems to be  common in the machine learning community. We propose to add in line 64, the sentence. \"This notion is also called semi-convexity [Crandall, Michael G and Ishii, Hitoshi and Lions, Pierre-Louis, User’s guide to viscosity solutions of second order partial differential equations][The Performance Of The Unadjusted Langevin Algorithm Without Smoothness Assumptions, Tim Johnston, Iosif Lytras, Nikolaos Makras, and Sotirios Sabanis].\"\n\n4- We thank the reviewer for this recommendation and we propose to follow it.\n\n5- We thank the reviewer for noticing this imprecision. We propose to reformulate line 78 as \"$b$ is $L$-Lipschitz, i.e. $\\forall x, y \\in \\mathbb{R}^d$, $\\|b(x) - b(y)\\| \\le L \\|x-y\\|$\". We propose to precise our comment in line 81-82 by \"If $b = \\nabla V$, Assumption 1(ii) is a relaxation of the strong convexity assumption on $V$, as it only holds for couple of points sufficiently far away\".\n\n# Questions\n1- Please correct us if we do not understand your suggestion. In the paper $p_{X_k}$ is the law of the iterate $X_k$ and $\\mu$, $\\nu$ and $\\pi$ are used for invariant laws. Thus there is no conflict of notations.\n\n2- In the image restoration community, the log-likelihood of the data is commonly called data-fidelity, see for instance [Plug-and-Play Methods for Integrating Physical and Learned Models in Computational Imaging, Kamilov, Bouman, Buzzard, Wohlberg 2022]. To avoid confusion, we propose to reformulate \"data-fidelity\" in line 36, line 128 and line 633 by \"negative log-likelihood\".\n\n3- Yes, for GMM prior or modern image priors induced by deep neural networks, the regularizer $g$ is non-convex, this is the case in all our experiments.\n\n4- From a first analysis, the connection between our Assumption 1 (strong convexity outside of a ball with certain radius) and a logarithmic Sobolev inequality does not seem to be immediate. Indeed, to the best of our knowledge the logarithmic Sobolev inequality is implied by a very strong version of the Foster-Lyapunov condition, see for instance [A link between the log-Sobolev inequality and Lyapunov condition, Lyapunov conditions for logarithmic Sobolev and Super Poincaré inequality]. However, while the target distribution might not satisfy a logarithmic Sobolev inequality it does satisfy a Poincar\\'e inequality, since Poincar\\'e inequalities are satisfied under a weaker Lyapunov condition [A simple proof of the Poincaré inequality for a large class of probability measures]. We then believe that using results from [Rapid Convergence of the Unadjusted Langevin Algorithm:\nIsoperimetry Suffices], we could derive the convergence of the ULA with respect to the R\\'enyi divergence. It is unclear if those results would be comparable to the ones we obtained in Wasserstein distance. Overall, we believe that using functional analysis tools like the logarithmic Sobolev or the Poincar\\'e inequality would constitute a complementary and interesting work avenue\n\n5- The constant of strong convexity of $g^\\gamma$ that appears in Assumption 3(ii) has to be larger than $8 L_f + 4 L_g$ in order to ensure that the drift defined in equation (11) that depends on $\\nabla f$ and $\\nabla g^\\gamma$ is increasing enough at infinity, i.e. verifies Assumption 1(ii). Roughly, the strong convexity of $g^\\gamma$ at infinity needs to compensate the weak convexity of $f$. This hard-to-verify Assumption 3(ii) could be remove by adding a projection mechanism in the PSGLA algorithm, see Appendix B for details.\n\n6- The distribution $\\nu_\\gamma$ proportional to $Prox_{\\gamma g}$ \\# $e^{-f - g^\\gamma}$ is not the target distribution, which is $\\pi \\propto e^{-f-g}$. We were not able to prove the convergence of PSGLA to $\\pi$ without additional assumption, but only to the shifted distribution $\\nu_{\\gamma}$, which arises naturally in the proof. However, Proposition 1 shows that $\\nu_{\\gamma}$ is close to $\\pi$ when $\\gamma \\to 0$ and quantifies the difference between these two distribution if $g$ is Lipschitz.\nFrom a practical point of view in image restoration, finishing by the application of the proximal operator \"projects\" the iterates on the clean-image manifold and improves the samples' quality.\n\n7- We thank the reviewer for pointing us these results. They are derived in a more restrictive setting but they require less assumptions. On the one hand this paper is lore restrictive because $g$ is supposed to be the characteristic function of some convex set. Proposition 1 of this paper then proposes a result that is dependent of the dimension of the problem ($p$ in their notation). On the other hand, they do not assume the Lipschitzness of $g$ but some geometrical properties on the convex set and the projection to this set. Therefore, these results could not be applied directly in our setting.\n\n8- First, the paper that you mention focuses on ULA and does not analyse proximal Langevin algorithm such as PSGLA. Secondly, this paper focuses on the ULA convergence whereas we study in our paper the ULA stability to drift shifts. Finally, we derive our bound in total-variation and Wasserstein distances but not in Kullback-Leibler (KL) divergence, which is included in this paper. As mentioned in Appendix F.4 after Theorem 6, line 1321-1324, our proof strategy does not generalize easily to KL because it relies massively on the triangle inequality that is not verified by KL. Based on the mentioned paper, we could try to derive a bound in KL. Thanks for sharing with us this paper, we propose to include this reference in line 1321."}, {"review_id": "5OiP9n7FQ5", "reviewer": "Reviewer_693y", "summary": "This work studies the stability of the Unadjusted Langevin Algorithm to perturbations in the drift. These stability bounds allow them to prove a convergence result for an inexact proximal stochastic gradient Langevin algorithm in non-log-concave settings. Such a proximal algorithm can be used in cases where the potential is separable into a smooth part and a weakly convex part. The authors demonstrate an application of the proposed ideas in Bayesian denoising.", "questions": "- The paper is well-written and clear. However, I feel that it could be better structured to emphasize what the main idea and takeaway is. There are four theorems that say different things and each take parsing. It may be better to structure Theorems 3/4 as the main theorems, since they tie to the main practical application considered, and use Theorems 1/2 as supporting theory for these two. This would help the flow of the paper and allow for easier reading.\n- It would be nice to see a setting where the proposed method is practically much better than existing methods. It is hard to see more than a marginal improvement in the existing experiments.\n- Currently I am having a hard time of seeing how this is an analysis of a stochastic gradient Langevin algorithm. Where in the theory are you really using stochastic gradients? Under further assumptions on the stochastic gradients, can other techniques like variance reduction be used to result in faster convergence?\n- Is there a possibility of applying this framework to study underdamped Proximal Stochastic Gradient Langevin? See \n\tGurbuzbalaban, M., Hu, Y., & Zhu, L. (2024). Penalized Overdamped and Underdamped Langevin Monte Carlo Algorithms for Constrained Sampling. Journal of Machine Learning Research, 25(263), 1-67.", "limitations": "Yes, they comment on the lack of efficiency, but it is hard to see if the proposed routes towards increased efficiency will actually work.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The authors develop useful theory on the stability of the inexact unadjusted Langevin algorithm.\n- The theoretical developments allow them to prove a convergence bound for the inexact proximal stochastic gradient Langevin algorithm, which has applications in real scenarios where one uses plug-and-play estimators for proximal operators.\n- The proof sketches, while short, are reasonably informative.\n\nWeaknesses:\n- The Gaussian mixture experiment is hard to read and not very informative.\n- The denoising experiment exhibits a marginal improvement in denoising with increased cost over DiffPIR. \n- In general, the framework does not seem to be computationall efficient compared to alternatives.", "was_revised": true, "final_justification": "The authors have adequately answered my questions and I maintain that this is worthy to be accepted to neurips.", "rebuttal": "Thank you for your positive feedback and careful reading of our paper. Please see below our detailed responses.\n\n- The Gaussian mixture experiment is hard to read and not very informative.\n\nIn this experiment, we set a GMM prior in 2D and solve a denoising problem, this leads to a distribution to sample that is represented in black on Figure 1. PnP-ULA and PnP-PSGLA sampling outputs are plotted in green. We observe that both algorithms approximate the target distribution but PnP-PSGLA explores in few steps the distribution and the different modes. In order to show a quantitative metric, we plot the Wasserstein distance (on the right column) between the target distribution and the sampled distribution with respect to the number of iterations. We observe that both algorithms decrease this quantity and than PnP-PSGLA converges faster than PnP-ULA. \nWe propose to reformulate the last sentence of the caption of Figure 1 with : \"Note that PnP-PSGLA succeeds to sample the posterior distribution even if there are various modes and the convergence is faster than PnP-ULA\".\n\n- The denoising experiment exhibits a marginal improvement in denoising with increased cost over DiffPIR.\n\nPnP-PSGLA and PnP-ULA sample the posterior distribution. DiffPIR, RED and PnP only estimate the maximum of the posterior distribution (MAP). Sampling provides a richer information with, for example, uncertainty information (see Figure 5 or Figure 6). Uncertainty quantification via sampling-based strategy is essential in decision-making processes that rely on restored images, notably in medical imaging applications. Therefore, it is natural than sampling methods such as PnP-ULA or PnP-PSGLA are slower than MAP methods as DiffPIR, RED and PnP. On Table 2, we show the capability of PnP-PSGLA to achieve state-of-the-art restoration quality, i.e. equivalent to DiffPIR, within sampling the posterior distribution and being significantly faster than PnP-ULA. This represents a clear step forward in empirical performance.\n\n- In general, the framework does not seem to be computational efficient compared to alternatives.\n\nAs mentioned in the previous answer, sampling methods indeed have an increased computational cost compared to \nMAP methods such as DiffPIR, RED or PnP. However, PnP-PSGLA is significantly faster than PnP-ULA, the concurrent (state-of-the-art) method for sampling in real-world applications.\n\n\n- The paper is well-written and clear. However, I feel that it could be better structured to emphasize what the main idea and takeaway is. There are four theorems that say different things and each take parsing. It may be better to structure Theorems 3/4 as the main theorems, since they tie to the main practical application considered, and use Theorems 1/2 as supporting theory for these two. This would help the flow of the paper and allow for easier reading.\n\nWe thank the reviewer for this suggestion. We choose to organize the paper in this way because we believe than Section 2 (Theorem 1/2) is  general and can be used for future works outside the context of proximal Langevin algorithms. Then we go deeper in our application on PSGLA in Section 3 (Theorem 3/4) based on the general results of Section 2 on Langevin algorithms. Finally, we apply PSGLA for posterior sampling. Our structure is going from the more general results to the more particular ones.\n\n- It would be nice to see a setting where the proposed method is practically much better than existing methods. It is hard to see more than a marginal improvement in the existing experiments.\n\nThe proposed method PnP-PSGLA is significantly faster than the PnP-ULA method which is the state-of-the-art real-world sampling method. DiffPIR, RED and PnP do not sample the posterior distribution and in particular they do not compute uncertainty information.\n\n- Currently I am having a hard time of seeing how this is an analysis of a stochastic gradient Langevin algorithm. Where in the theory are you really using stochastic gradients ? Under further assumptions on the stochastic gradients, can other techniques like variance reduction be used to result in faster convergence ?\n\nIn this paper, we choose to keep the original algorithm named \"PSGLA\" introduced in [80] which means Proximal Stochastic Gradient Langevin Algorithm. Unfortunately, we concede that this name can be confusing. In fact, the goal of PSGLA is to sample a target distribution and capture the variability of the distribution, e.g. its multi-modality. Therefore, PSGLA has not the same goal than stochastic gradient algorithms where the stochasticity is only used to optimize faster. Thus variance reduction methods are not appropriate in this context of sampling.\n\n- Is there a possibility of applying this framework to study underdamped Proximal Stochastic Gradient Langevin ? See Gurbuzbalaban, M., Hu, Y., \\& Zhu, L. (2024). Penalized Overdamped and Underdamped Langevin Monte Carlo Algorithms for Constrained Sampling. Journal of Machine Learning Research, 25(263), 1-67.\n\nThank for sharing with us this paper, we propose to include its reference in our related works in Appendix A. Our framework can be used to solve constraint sampling. If $g$ is the characteristic function of a convex set, PSGLA turns into a projected Langevin algorithm and our theory holds. Our theory about Langevin stability (Theorem 1) applies to  Penalized underdamped Langevin Monte Carlo (PULMC) as it is a Langevin type algorithm. On the other hand, the convergence result on PSGLA does not apply immediately to penalized underdamped Langevin Monte Carlo (PULMC) algorithm as PULMC is not a specific case of PSGLA. In this paper, the authors do not study a proximal Langevin algorithm as your question suggests. By any chance, would you have another reference in mind ?"}]

Author rebuttal:

Meta-review: This work established the convergence of proximal, stochastic gradient MCMC algorithms under inexact gradients in the non-log concave setting. This is primarily achieved by studying the stability of unadjusted langevin algorithm to perturbations in the drift function (i.e, inexactness). These algorithms are widely used in practice and this work provides important theoretical justifications for their use in the relevant inexact, stochastic, non-log-concave settings. The reviewers agree that the contributions are important and the paper is technically sound. I recommend acceptance.
Decision: Accept (poster)