A Proximal Algorithm for Sampling
Authors: Jiaming Liang
Yongxin Chen
Venue: Accepted by TMLR ()

Abstract: We study sampling problems associated with potentials that lack smoothness. The potentials can be either convex or non-convex. Departing from the standard smooth setting, the potentials are only assumed to be weakly smooth or non-smooth, or the summation of multiple such functions. We develop a sampling algorithm that resembles proximal algorithms in optimization for this challenging sampling task. Our algorithm is based on a special case of Gibbs sampling known as the alternating sampling framework (ASF). The key contribution of this work is a practical realization of the ASF based on rejection sampling for both non-convex and convex potentials that are not necessarily smooth. In almost all the cases of sampling considered in this work, our proximal sampling algorithm achieves a better
complexity than all existing methods.

Published in Transactions on Machine Learning Research (06/2023)
A Proximal Algorithm for Sampling
Jiaming Liang
Staming.lingggSa0 edu
Deportment of Computer Science, Yale University, New Hoven, CT 06511.
Yongxin Chen School of Aerospace Engineering, Georyia Institute of Technology, Atlanta, GA 30332.
yongchen @gotech. yongchen@gatech.coo
edu
Reviewed on OpenReview: https: // opw.reveeeer......... net/ pet//oorm? id- CkXOwlhf27
Abstract
We study sampling problems associated with potentials that may lack smoothness or con- vexity. Departing from the standard smooth setting, the potentials are only assumed to be weakly smooth or non-smooth, or the summation of multiple such functions. We develop a sampling algorithm that resembles proximal algorithms optimization for this challenging sampling task. Our algorithm is based on a special case of Gibbs sampling known as the alternating sampling framework (ASF). The key contribution of this work is practical ro- alization of the ASF based on rejection sampling for both non-convex and convex potentials that are not necessarily smooth. In almost all the cases of sampling considered in this work, our proximal sampling algorithm achieves a better complexity than all existing methods.
1 Introduction
The problem of drawing samples from an unnormalized probability distribution plays an essential role in data science and scientific computing DDurmus et al. 2018 Clarage et al., 1995 Maximova et al. 2016).
It has been widely used in many areas such as Bayesian inference, Bayesian neural networks, probabilistic graphical models, biology, and machine learning (Gelman et al. 2013
Kononenko 1989 Koller & Friedman 2009 Krauth 2006; SSites Jr & Marshall] 2003 Durmus et al. 2018]. Compared with optimization oriented methods, sampling has the advantage of being able to quantify the uncertainty and confidence level of the solution, and often provides more reliable solutions to engineering problems. This advantage comes at the cost of higher computational cost. It is thus important to develop more efficient sampling algorithms.
In the classical setting of sampling, the potential function f of an unnormalized target distribution exp(-f((x)) is assumed to be smooth and (strongly) convex. Over the past decades, many sam- pling algorithms have been developed, including Langevin Monte Carlo (LMC), kinetic Langevin Monte Carlo (KLMC). Hamiltonian Monte Carlo (HMC), Motropolis-adjusted Langevin algorithm (MALA), etc
(Dalalyan 2017 Grenander & Miller 1994 Parisi 1981 Roberts & Tweedie 1996. Dalalyan & Riou- DuranD
2020 Bou-Rabee & Hairer 2013
Roberts & Stramer 2002 Roberts & Tweedie 1996 Neal 2011). Many
of these algorithrs are based on some type of discretization of the Langevin diffusion or the underdamped Langevin diffusion. They resemble the gradient- based algorithms in optimization. These algorithms work well for (strongly) convex and smooth potentials; many non-asymptotic complexity bounds have been proven. However, the cases where cither the convexity or the smoothness is lacking are much less understood (Chewi
et al. 2021 Chen al.) 2022 Chatterji et al. 2020
Erdogdu & Hosseinzadeli 2021 Liang & Chen 2022
Dalalyan et al. 2022
Balasubramanian et al.) 2022 Mou et al. 2022a).
In this paper, we consider the challenging task of sampling from potentials that are not smooth and even not convex. Many sampling problems in real applications fall into this setting. For instance, Bayesian neural networks are highly non-convex models corresponding to probability densities with multi-modality (Izmailov ct al. 2021). The lack of smoothness due to the use of activation functions such as ReLU. The goal of this work is to develop an efficient algorithm with provable guarantees for a class of potentials that are not smooth. In particular, we consider potential functions that are semi-smooth, defined by 1..

---

Published in Transactions on Machine Learning Research (06/2023)
Inspired by the recent line of research that lies in the interface of sampling and optimization, examine this sampling task from optimization perspective. We build on the intuition of proximal algorithms for non-smooth optimization problems and develop a proximal algorithm to sample from non-convex and semi-smooth potentials. Our algorithm is based on the alternating sampling framework (ASF) (Lee ct all 2021 developed recently to sample from strongly convex potentials. In a nutshell, the ASF is Gibbs sampler over a carcfully designed augmented distribution of the target and one can thus sample from the target distribution by sampling from the augmented distribution. The convergence results of ASF have been recently improved (Chen et al. 2022) to cover inequalities such as the Logarithmic Sobolev inequality (T.ST) and the Poincaré inequality (PI).
distributions that satisfy functional
The ASF is an idealized algorithm that is not directly implementable. In each iteration, it needs to query the so-called restricted Gaussian oracle (RGO), which itself a sampling task from a quadratically regularized distribution exp(-f(x)) _ || y (2) for some given r) > and y E R.d. The RGO can be viewed as a sampling counterpart of the proximal map in optimization. The total complexity of ASF thus depends on that of the RGO. Except for few special cases where I has certain struct ures, the RGO is usually challenging task. One key contribution of this work is practical and efficient algorithm for RGO for potentials that are neither smooth nor convex. This algorithm extends the recent work Liang & Chen non-smooth potentials. Combining the ASF and our algorithm for RGO, we establish a proximal algorithm for sampling from (convex or non-convex) semi-smooth potentials. Note that the techniques used in Liang & Chen (2022) are no longer applicable to these non-convex semi-smooth settings. In this work, we developed a new algorithm and associated proof techniques for efficient RGO implementation.
(0022) for convex and
Our contributions are summarized as follows. i) We develop efficient sampling scheme of RGO for semi- smooth potentials which can be either convex non-convex and bound its complexity with a novel technique. ii) We combine our RGO scheme and the ASF to develop a sampling algorithm that can sample from both convex and non-convex semi-smooth potentials. Our algorithm has better non-asymptotic complexity than almost all existing methods in the same setting. iii) We further extend our algorithms for potentials that are the summation of multiple semi-smooth functions.
Table 1: Complexity bounds for sampling from non-convex potentials. Assumption
Source
Complexity
Metric
Chewi et al. 2021
Cpt
weakly smooth PI, a > 0 semi-smooth PI
Rényi
g//a
δ CpiLa 2pr12/11+ 2/(1+a) de
this paper (Thm. 3.5
Rényi
maax/1/ac]
Nguyen et al.
δ C
cl-max[1/as}
mmx 14 3d
a; > 0, composite semi-smooth, LSI
KL
(2021)
δ CLSI Ei= Lioi 21(ait1)
this paper (Thm.
composite
KL
4.4
semi-smooth, LSI
this paper (Thm. 4.5
① Cpt (CPi
Σn Cr
22 2/(0.-1)
composite semi-smooth, PI
Rényi
Related works: MCMC sampling from non-convex potentials has been investigated in Raginsky et al.
[2017g: Vempala & Wibisono (2019);
Wibisono (2019): ; Chewi et al. (2021): Erdogdu & Hosseinzadehi (2021):
Mou et al. (2022b); Luu et al. (2021 There have also been some works on sampling without smoothness
Lehec (2021)
Durmus et al. (2019):
Chatterji et al. 22020) : Chewi et al. 2021); Mou et al. (002a)) Shen
ct al.
2020): Durmus et al. 2018):
Freund et al. (2022): : Sallm & Richtárik (0200 Bernton (018)): Nguyen
el al.
2021 Liang & Chen (2022). The literature for the case where the potential function lacks both
convexity and smoothness is rather scarce. In Nguyen et al. (2021); Erdogdu & Hosseinzadehi (2021). the
authors analyze the convergence of LMC for weakly smooth potentials that satisfy a dissipativity condition.
The target distribution is assumed to satisfy some functional inequality. EEdogdu & Hosseinzadeh (2021)
also assumes an additional tail growth condition. The dissipativity condition is removed in Chewi et al.
2

---

Published in Transactions on Machine Learning Research (06/2023)
2021p. p. The results in Nguyen et al. (2021 are applicable to potentials that the summation of multiple weakly smooth functions, while those in Chewi et al. (2021); Erdogdu & Hosseinzadeh (2021) are not. To compare our results with them, we make the simplification that the initial distance, either in KL or Rényi divergence, to the target distribution is ((d). The results in cases with non-convex potentials are presented in Table I It can be seen that our complexities have better dependence on all the parameters: LSI constant CLSI, PI constant Cr₁, weakly smooth coefficients La, and dimension Morcover, our complexity bounds depend polylogarithmically on the accuracy (thus does not appear in the Ô notation) while all the other results have polynomial dependence on 1/E.
2 Problem formulation and Background
We are interested in sampling from distributions with potentials that are not necessarily smooth. More specifically, we consider the sampling task with the target distribution y exp(-f(x)) where the potential f satisfies
-
- f())ll Σ Lou Iu o110 Vu, E Rd
(1)
for some 0, E [0,1] and Lo, > 0, iiisis n. Here I' denotes a subgradient of f in the Frechet subdifferential (see Definition A.1. When n = 1 and 01 = 1, it is well-known that f is a smooth function. When n = 1 and
0 0<a1= < 1, f satisfying [T) is known as a weakly smooth function. When n = and α₁ = 0, f satisfying [1] is a non-smooth function. Thus, the cases we consider cover all three cases: smooth, weakly-smooth, and non-smooth. For ease of reference, we termed a function satisfying the condition (1) a semi-smooth function. The target distribution is assumed to satisfy LSI Pl, but f can be non-convex. The class of distributions consider have been studied in (Chatterji et al.] 2020 Chewi et al. 2021 2021) for MCMC sampling. One example of such distribution is exp(- (A10 for some full rank matricos A1, A2, vector b, and some activation (e.g., ReI.U) function a. This is a Bayesian regression problem.
Nguyen et al.
b
|
|>|
In this work, we aim to develop a proximal algorithm for sampling from non-convex potentials that satisfy Our method is built on the alternating sampling framework (ASF) introduced in Lee al.) (2021). Unlike most existing sampling algorithms that require the potential to be smooth, ASF is applicable to semi-smooth problems. Initialized at Tp p ASF with target distribution x xx (x( exp(-f(x)) and stepsize performs the two alternating steps follows.
Algorithm Alternating Sampling Framework (Lee et al., 2021
1. Sample ye n x (y) wx) expl- 2n |
y|l
2. Sample F n XIY (ar yk) xx expl- f(x)) 2n 1 1kl1
The ASF is a special instance of the Gibbs sampling (Geman Geman 1984 from
π y) x exp - f(())
||x - y/13)
(2)
2m
In Algorithm I sampling Ue given 2y in step 1 is easy since π X (v) xx) N n/) is an isotropic Gaussian distribution. Sampling I++1 given ye in step 2 is however highly noutrivial task; it corresponds to the restricted Gaussian oracle for ff (Lee et al.) 2021p. defined as follows.
Definition 2.1 Given a point y Rd and slepsize 1) > 0, the restricted Gaussion oracle (RGO) for f d + R is sampling oracle that returns a random sample from distribution proportional to exp(-f(.) || (l2)))((2nn
The RGO can be viewed as the sampling counterpart of the proximal map in optimization that is widely used in proximal algorithms for optimization (Parikh & Boyd 2014). The ASF is an idealized algorithm:
3

---

Published in Transactions on Machine Learning Research (06/2023)
efficient implementation of the RGO is crucial to use this framework in practice. For some special cases of f. the RGO admits computationally efficient realization (Mou et al. 2022a Shen et al. 2020 Liang & Chen 2022). For general f, especially semi-smooth ones considered in this work, it was not clear how to realize the RGO efficiently.
Under the assumption that the RGO in the ASF can be efficiently realized, the ASF exhibits surprising convergence properties. It was firstly established in Lee et al. (2021) that, when is strongly convex, Algorithm | converges linearly. This result is further improved recently in Chen et al. (2022) under various weaker assumptions on the target distribution xx exp(-f). We summarize below several convergence results established in Chen et al. (2022) that will be used.
Throughout the paper, we abuse notation by identifying a probability measure with its densily w.r.t. Lebesgue measure. To this end, for two probability distributions p < v, we denote by
Ho(0) :
= plogg L. /
==10)==-
- (g 9-1
1
p
log D4-1
the KL divergence, the Chi-squared divergence, and the Rényí divergence, respectively. Note that R2
log(1 x2),, R1,-= = Hr, and R2 S By .v for any 1 q S of < oo (Rényi 1961 Vempala & Wibisono 2019 We denote by W2 the Wasserstein-2 distance (Villani) 2021) ). Recall probability distribution v satisfies LSI with constant CLSI
(1/CLsI-LST) if for every p, Hv(p)
2 Jp),,, where the Fisher information
(p) is defined (p) = E log =11²]. A probability distribution satisfies PI with constant Op1 > 0 (1/Cpr-PI) if for any smooth bounded function & Rd + R, we have Eyl(v- - [b())) & Cp]Ee|||Veb)..
Theorem 2.2 (CChen et al., 2022 Theorem 3)) Assumee that x & exp(-f) satisfies X-LSI. For any inilial distribulion po the k-lh ilerale o of Algorithm 1 with step size >> salisfies
< HaS (p
Hz (pk)
(1 An) 2h
Moreover, for all 2 1,
R (px) S R (pt)) (1+ An) 2k/9
Theorem 2.3 (Chhen et al., 2022, Theorem 4)) Assume x exp(-f) satisfies X-PI. For any initial distribution p the k-th iterate PK of Algorithm with step size 17 > 0 satisfies
x (p
x (pt) <
(1 Ar) 24
Moreover, for all q 2,
R (pt)) lolog1++M))
9 if l S 2log(1+Am) (R (pt') - -1), (R x (pt) 1)]-
x (pt)) <
11((1 + >n) 2n) 2(k-
kk z kn = 9
Theorem 2.4 (Chen et al., 2022 Theorem 2)) Assume that x x exp(-f) is log- log-concave. For ony initial distribution ph the kith sterate of of Algorithm i with step size n > satisfies
H (xx) W2(P', x*)
km
To use the ASF for sampling problems, we need to realize the RGO with efficient implementations.. In the rest of this paper, we develop an efficient algorithm for RGO associated with a potential satisfying (I). and then combine with the ASF to establish a proximal algorithm for sampling. The complexity of the proximal algorithm can be obtained by combining the above convergence results for ASF and the complexity results we establish for RGO. The rest. of the paper is organized follows. In Section we consider a special
4

---

Published in Transactions on Machine Learning Research (06/2023)
case of ① with complexity results for sampling from distributions with non-convex and semi-smooth potentials. Tn Section 4 we extend the aforementioned complexity results to the general cases ( In Section 5 we specialize ( to the case where f is convex. In Section G we present preliminary computational results to demonstrate the efficacy of the proximal sampling algorithm. In Section 7 we present some concluding remarks. Finally, Appendices
develop efficient implementation for RGO via rejection sampling, and establish
we present technical results and proofs omitted in the paper and provide a self-contained
discussion on solving a subproblem in the proximal sampling algorithm.
3 Proximal sampling for non-convex and semi-smooth potentials
Our main objective in this section is to establish complexity results for sampling from distributions with non-convex and semi-smooth potent ials satislying
[ with n = 1, i.e,
(f(w)- & Lallu- v1 Vu,UE ER.
(3)
We refer to such a function an s.-aassmm-smmoth function.
The bottleneck of Algorithm 1 for sampling from general distribution exp(-f) is efficient realization of the RGO, i.c., step of Algorithm [ To address this issue, develop an efficient algorithm for the corresponding RGO based on rejection sampling. We show that, with carefully designed proposal and sufficiently small 7), the expected number of rejection sampling steps to obtain one effective sample in RGO turns out to be bounded above by a dimension-free constant. The core to achioving such a constant bound on the expected rejection steps novel construction proposal distribution that does not rely on the convexity of f and a refined analysis that captures the nature of semi-smooth functions. We utilize a useful property of semi-smooth functions that they can be approximated by smooth functions to arbitrary accuracy, at the cost of increasing their smoothness parameters. This is formalized in the following lemma, of which the proof is postponed to Appendix B Relevant ideas have been explored in Devolder et al. (0014)
Nesterov 2015 to design universal methods for convex semi-smooth optimization problems.
Lemma 3.1 Assume f is an Laa-a-semi-smooth function, then for 8 > O and every u, u E Rdd
M ||u
1112 (1 - a)o
If(u) f(v) (f'()), -- w\1
(4)
2
where
L
M
(5)
[(a + 1)8
Our algorithm is inspired by Liang & Chen of rejection sampling used in Liang & Chen (2022) is Gaussian distribution centered at an (approxinate)
2022),
which also uses rejection sampling for RGO. The proposal
minimizer of the regularized potential function. We thus consider the regularized optimization problem
prox, (rox,,())= = argmiin seRd [](() = f(x + 2n | v1
(6)
where y E IRd is given. Departing from the convex setting studied in Liang & Chen (202)). when f non- convex and semi-smooth, G6 may not be a convex optimization regardless of the value of n. Nevertheless, strongly convex and smooth function up to some approximation
thanks to Lemma 3.1 fy close
error, and O can still be solved efficiently using convex smooth optimization algorithms such as Nesterov's acceleration. We describe variant of the method in Algorithm in Appendix D The following proposition presents a complexity result of Algorithm for finding an approximate stationary point of fy with a small 7). Its proof is postponed to Appendix
Proposition 3.2 Assume n S Md. and let w E Bdd be an approzimate stationary point of f7, i.e.,
1
I Md, == (w) + 1 ( y)-
(7)
where M is in 51. Then, the complein to fend w with Algorithm 3 is Ô(1)
5

---

Published in Transactions on Machine Learning Research (06/2023)
With this approximate stationary point, obtain the following key ingredients of our rejection sampling- based RGO.
Lemma 3.3 Let w² Rd be stationary point of fg. i.e,
f'(w)) (w* y) = 0,
(8)
and be approrimate stationary point in Define
M
1
(1 11-ay
[1-a)8
(=) = f(w) (f (f' w)
1 w|l
+
|| y/
(9)
2
2n
2
(1 a)
(x) f(w") (f" w²) +
|| - 111
+
1|00
y11
+
(10)
2
21j
2
Then, we have for every r E Idd
1r S (1(x) S (2 (x))
(11)
Proof: Inequalities in directly follow from and the definitions of hi and hg in respectively.
9 and
10
We are now ready to present the rejection sampling algorithm (Algorithm 2 for RGO.
Algorithm RGO Rejection Sampling
1. Compute approximate solution w satisfying 7
with Algorithm
2. Generate sample X ~ exp(-h",,, (z))
3. Generate sample U ~ 10
4. If
U (x(())
exp( -4, (X))
then accept/return X; otherwise, reject X and go to step 2.
By construction, the proposal x exp(-14,,,x) is close to the target XIX (xc y) xx exp(-17(x)) when т is sufficiently small, and hence the expected number of rejection steps is small. The following proposition rigorously justifies this intuition.
Proposition 3.4 Assume f Lna-a-semi-smooth and let fy be as in 2 follows the distribution π x (x y) exp (-f7 Moreover, if
6 Then X generated by Algorithm
[(a 1)0 51İ
1 S Md
(12)
L
2 is at most exp ((1-a)6 + 3)
then the expected namber of rejection steps in Algorithm
Proof: It. is well-known in rejection sampling X XIY (xll)) By definition, the probability that X is
accepted is
P US exp(-ff(X)) exp( (.p(-
-
exp(-f7(xx) exp(-hi,, (x))
dx f exx((-
exp(_ (x)) expl -h (z) J Texp( expp_-hr, (r)))dx (r)

---

Published in Transactions on Machine Learning Research (06/2023)
Using the above identity,
11
and Lemma A.4 we have
U S exp( (3(())
exp( (x)))
P
exp(
hr. (X))
exp( (xxp(-1,,,(00))) (x))dd
1 - nM
d/2
exp
wu" 112 - f(w0) ) + (f"(ww) w²) - 1v1 - 1 2 X1ーn5 ||s|2 f(w) + (1,, w) b 11/l11 + 120)
27
1 nM
exp
21 ||wl|2
1 nM
d/2
((1 a)d
2(1 - n)M) |s|1
"1
exp
1 + T,
1
1
x exp
I 112
|w|l f(w''(''))))))")) f(w) + (f w²)
(w, y w)
(13)
217
21
It follows from
4
with (u, v) = (w,w") that
M
w w²1 + (1 a8)
- f(w) + f(w") + (f'(w)), w w²) 5
2
2
which together with 8 implics that
|| w
1|
|w - ff(w") + f(w) + (f'(w)), w,
(w, y - -w)
2n
2m
1
1
||
|0011
|2l2 - -f(w") + f(w) + (f'(w"), ),
(, (70" +
+w== === - -w)
2m
2n
1
1
||0
w=11
f(w") + f(w) + (f (w") w w)
2n)
1
M
(1- - a16 (1 - a88
||00 w²1 1|
2 w/ w0
21
2
2
where the last inequality is due to
12 Plugging the above inequality into we oblain
p p(US xxp(-f7(X))
N
1
7M
d/2
exp
3(1 -a)5
77
||s|
1 M
2(1 M)
Hence, using the above bound, rejection iterations
12
and
7 we arrive at the following bound on the expected number of
+ 7
d/2
exp
3(1 a)
+
11
MM) ||s112
P
exp( (X)) U
1 - nM
2
2(1
expl 1. (x))
M 1
d/2
3(1 a)d
3(1 - a)5
||s|12
n||>|13
S (1 4n d/2 exp
exp
TM
Md
d/2
3(1
a)d
/3(1-o0 - a)d +3
+1 exp
exp
Note that is a tunable paramcter. Choosing a large 8 makes M small and n large in view of (5) and 12 respectively. Such a choice results in better complexity of ASF but a larger nunber of expected rejection steps in RGO. Combining Proposition (3.4) and the convergence results of ASF we obtain the following non- asymptotic complexity bound to sample from non-convex semi-smooth potentials. This complexity bound is better than all existing results when E [0, 1), see Table I for comparison.
Theorem 3.5 Assume f is La --semi-smooth and x x exp(- satisfies PI with constant OpI- With initial distribution pe and slepsize n 1/(T.a =d),
d), Algorithm using Algorithm as an RGO has the

---

Published in Transactions on Machine Learning Research (06/2023)
ttemeeion.complerity bound
δ (Cmitat dlog Xxx (1
(14)
to achieve e error to the target π x in terms of Chi-squared divergence, and
δ CPLLa* ने. qdR, (o²)). q 222
(15)
to achieve e error in Rényi divergence Rx Each iteration queries Õ(1) subgradients of f.
Proof:
The result is a direct consequence of Theorem 2.3 Proposition 3.2 and Proposition
3.4 with the
choice of stepsize r x 1/(a TT d).
Remark: When the coordinate scaled by 7 as x 7 YE, by definition, the semi-smoothness coefficient becomes g La and the PI constant becomes CPI/n2. By Proposition 3.4 attain ( complexity for
1-e
[a++1)6]++ o+1 [a+1)6 a+1
the RGO, the stepsize should be I
Thus, applying Theorem 2.3 the total
(7a (y" 3,
complexity remains the same as that without coordinate scaling.
4 Proximal sampling for non-convex composite potentials
This section is devoted the sampling from distributions with non-convex composite potential f satisfying Results presented in this section generalize those in Section 3 which are for the setting with = 1. Although Section 3 is developed for the simple case where = 1 in (1), the proof techniques apply to the Hence, to avoid duplication, we present the following results analogous to those in
1].
general case of
Section without giving proofs.
3
The following lemuna direct generalization Lemma 3.1
which shows that functions satislying be approximated by smooth functions up some controllable approximation errors.
| can
Lemma 4.1 Assume f satisfies 1 then for any 8 > O, we have
Mn 1 w
(1 -1- (1-a)6
1s(1) - - w> 5
Vu, u E Rdd
(16)
2
2
1=1
where
Los
M,
(17)
[(a + 1)6 क,
The next proposition is counterpart of Proposition 3.2 and gives the complexity of solving optimization problem ( in the context of (1]
Proposition 4.2 Assume 7 S 1/(Mad), and let w, E Rdd be an approcimate stationary point of rn such that (w,) + + (w,, - - S VM,dd Then, the iteration-compleattii to find w, with Algorithm is O(1).
Again, the core to the proximal algorithm (Algorithm 1 is an efficient implementation RGO. We use Algorithm with slight modification as a realization RGO in the context of (1). First, in step 1 of we use Algorithm 3 to compute wn as in Proposition 4.2 instead of w. Second, steps 2 and of Algorithm instead of using hi,,, in (9) define hy, follows,
Algorithm 2
MY f(w) + (f'Ww, w) Mn |1 wll2 +
1 2n
a5)
1 v11
2
where Mn is in 17 The next proposition is generalization of Proposition
3.4
8

---

Published in Transactions on Machine Learning Research (06/2023)
Proposition 4.3 Assume f satisfies and let fy be as in 6 Then X gencrated by Algorithm with
modification follows the distribution æ (x y) & exp (-)
1 Moreover, if r S Mad then the expected
3 3 (1-a,)
number of rejection steps in Algorithm is at most exp
In the rest of this section, we present two results on the complexity of sampling for non-convex composite potentials where the target distribution satisfies either LSI or PI. Our complexity bounds are better than all existing results when mina; [0, 1), see Table [ for comparison.
Theorem 4.4 Assume f satisfies ① and x & exp(-f) satisfies LSI with constant CLSI- With initial
distribulion p and slepsize x 1/ Di=1 Laitz d) Algorithm using the modified Algorithm as an RGO has the Deration-compleezii bound
72
Ô CLSI
Log
(18)
achieve error to π in KL divergence. Each iteration queries ((1) subgradients of f and generates O(1) samples in expectation from Gaussian distribution.. Moreover, for all 9 1, the deeratinnccompleasii bound to achieve error to xx in Rényi divergence Rg is
6(CLst
CLSI Σ 1=1
Lai m dg
Proof: This theorem is direct consequence of Theorem 2.2 and Propositions 4.2
Theorem 4.5 Assume f satisfies and x & exp(-f) satisfies PI with constont Cri.
With initial
distribution p and stepsize 1/ 1 Lai d)
क.
Algorithm I using the modified Algorithm 2
RGO has the iteration ccmiiieriit bound
CpI
Σ
? Laitt d log Xax (pt')
(19)
to achieve e error to the target x in terms of Chi-squared divergence, and
ō Cri Σ Lai qd (08)): 9 922
(20)
to achieve e ervor in Rényi divergence Rg Each iteration queries Õ(1) subgradients of f and generates O(1) samples in expectation from Gaussian distribution.
Proof: This theorem immediately follows from Theorem 2.3 and Propositions 4.2 4.3
5 Proximal sampling for convex composite potentials
For completeness, in this section present complexity result for sampling from distributions with convex potential f satisfying [ We only consider the weakly convex setting here strongly log-concave distri- butions satisfy LSI and are thus covered by Theorem 4.4 The result is a consequence of Theorem 2.4 for log-concave densities combined with our RGO implementat ion. In particular, Lemuna 4.1 and Propositions 4.3 4.3 apply to this setting. Hence, using Theorem 2.4 and Propositions [.2 4.3) we directly obtain the following complexity result. Note our result is applicable to composite potentials with any number of com- ponents while most existing results are only applicable composite potentials with most two components. We also present alternative result via regularization approach in Appendix

---

Published in Transactions on Machine Learning Research (06/2023)
Theorem 5.1 Assume f satisfies and x exp(-f) is log-concave. With initial distribution pa and stepsize = 1/ (Ei=1 Lai mi+T
d).
Algorithm using Algorithm 2 as an RGO has the itention-compleeityy
bound
(2 x , > La:
achieve e ervor the target x in terms of KL divergence. Each iteration queries Õ(1) subgradients of J and generales (1) samples in expectation from slandard Gaussian distribulion.
Proof: This thcorem is a diroct consequence of Theorem 2.4 and Propositions 4.3
6 Computational results
In this section, present a numerical example to illustrate result. Gaussian-Laplace mixture
We consider sampling from
v(x) 0.5(2m) d/2
det /
1xx 1)/2) + 0.5((2)
where Q = USUT -d S diag( 14, 15, 16, 18), and U is an arbitrary orthogonal matrix.
We run 500, 000 iterations (with 100, 000 burn-in iterations) for both the proximal sampling algorithm and LMC with == 1/(Md) where
as in (5) with (a, L.) = (1, and =. Histograms and trace plots (of the 3-rd coordinate) of the samples generated by both methods are presented in Figures and 2 The average numbers of optimization iterations and rejection sampling iterations in Algorithm are 500, 000 iterations (with 500, 000 burn-in iterations) for LMC with 1/(MM)). Figure 3 presents the histogram and trace plot for this LMC. The red curves in histograms are the scaled target density v(z). Figures 4 and 5 show the results for MALA in the same settings as those of Figures 2 and 3 respectively. In these experiments, we observe that our algorithm achioves better accuracy under the same computational budget constraints.
and
1.5 and 1.3, respectively. In addition, also
Histogram
Trace Plot
terstiin
Figure 1: Gaussian- Lasso mixture using the proximal sampling algorithm
10

---

Published in Transactions on Machine Learning Research (06/2023)
Histogram
Trace Plot
neeratio
Figure 2: Caussian-Lasso mixture using LMC
Hilsoggra
Trace Plot
tteaatio
Figure 3: Gaussian- mixture using LMC with small n
Histogram
itoratio
Figure 4: Gaussian-Lasso mixture using MALA
Histogram
Trace Piot
Iteation
Figure 5: Gaussian- Caassian-Lassoo mixture using MALA with small 7
11

---

Published in Transactions on Machine Learning Research (06/2023)
7 Conclusions
In this paper, we develop novel proximal sampling algorithm for distributions with semi-smooth potentials and establish complexity-bound results for the proposed method under the assumplion that distributions are log-concave or satisfy LSI or PI. Our proximal algorithm is based on the ASF, which resembles the proximal point method in optimization. Each iteration of the ASF generates a sample from a rogularized larget distribution by querying the RGO, which is itself' a challenging algorithmic task due to the lack of smoothness and possibly convexity. The core to our approach is an efficient realization of the RGO based on rejection sampling. We develop a novel technique to bound the expected number of rejection steps in the RGO, which leads to competitive complexity results to sample from semi-smooth and possibly non-convex potentials.
References
Krishna Balasubramanian, Sinho Chewi, Murat A Erdogdu, Adil Salim, and Shunshi Zhang. Towards a theory of con-log-concant sampling: first-order stationarity guarantoes for langevin monte carlo. In Conference on Learning Theory, pp. 2896 2923. PMLR, 2022.
Espen Bernton. Langevin Monte Carlo and JKO splitting. In Conference On Learning Theory, pp. 1777- 1798. PMLR, 2018.
Nawaf Bou-Rabee and Martin Hairer. Nonasymptotic mixing of the MALA algorithm. IMA Journal of Numerical Analysis, 3311)880-110, 2013.
Niladri Chatterji, Jelena. Diakonikolas, Michael I Jordan, and Peter Bartlett. Langevin Monte Carlo without smoothness. In International Conference on Artificial Intelligence and Statistics, pp. 1716 1726. PMLR, 2020.
Yongxin Chen, Sinho Chewi, Adil Salim, and Andre Wibisono. Improved analysis for proximal algorithm for sampling. In Conference on Learning Theory, pp. 2984-3014. PMLR, 2022.
Sinho Chewi, Murat A Erdogdu, Mufan Bill Li, Ruoqi Shen, and Malthew Zhang. Analysis of Langevin Monte Carlo from Poincaré to Log-Sobolev. arXiv preprint arXiv:211 22..1..2.22 12662, 2021.
James B Clarage, Tod Romo, B Kim Andrews, Montgomery Pettitt, and George N Phillips. A sampling problem in molccular dynamics simulations of macromolecules. Proceedings of the National Academy of Sciences, (2(8):3288 3292, 1995.
Arnak S Dalalyan. Theoretical guarantees for approximate sampling from smooth and log- log-concave densities. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 79(3):651-676 2017.
Arnak S Dalalyan and Lionel Riou-Durand. On sampling from log-concave density using kinetic Langevin diffusions. Bernoulli, 26(3):1956-110) 2020.
Arnak Dalalyan, Avelik Karagulyan, and Lionel Riou-Durand. Bounding the error of discretized langevin algorithms for non-strongly log-concave targets. Journal of Machine Learning Research, 23(235):1-3 2022.
Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146(1):37-75, 2014.
Alain Durmus, Eric Moulines, and Marcelo Pereyra. Efficient. Bayesian computation by proximal Markov Chain Monte Carlo: when Langevin moets Morcan. SIAM Journal on Imaging Sciences, 11(1):473-506 2018.
Alain Durmus, Szymon Majewski, and Blažej Miasojedow. Analysis of Langevin Monte Carlo via convex optimization. The Journal of Machine Learning Research, 20(1):2666-277 2211, 2019.
12

---

Published in Transactions on Machine Learning Research (06/2023)
Murat A Erdogdu and Rasa Hosseinzadeh. On the convergence of Langevin Monte Carlo: the interplay between tail growth and smoothness. In Conference on Learning Theory, pp. 1776-1822. PMTR, 2021.
Yoav Freund, Yi-An Ma, and Tong Zhang. When is the convergence time of langevin algorithms dimension independent? a composite optimization viewpoint. Journal of Machine Learning Research, 23(214):1-33 2022.
Andrew Gelman, John Carlin, Hal S Stern, David Dunson, Aki Vehtari, and Donald Rubin. Bayesion Data Analysis. CRC press, 2013.
Stuart Geman and Donald Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration images. IEEE Trunsactions on pattern analysis and machine intelligence, (6):721 741, 1984.
Ulf Grenander and Michael Miller. Representations of knowledge in complex systems. Journal of the Royal Slalistical Sociely: Series B (Metholologioau), 56(4):549 581, 1994.
Pavel Izmailov, Sharad Vikram, Matthew D Hoffman, and Andrew Gordon Gordon Wilson What are bayesian neural network posteriors really like? In International Conference on Machine Learning, pp. PMLR, 2021.
Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
Igor Kononenko. Bayesian neural networks. Biological Cybernetics, 61(5):361-370, 1989.
Werner Krauth. Statistical mechanics: algorithmss and compulations, volume 13. OUP Oxford, 2006.
Yin Tat Leo, Ruoqi Shen, and Kevin Tian. Structured logconcave sampling with restricted Gaussian oracle. In Conference on Learning Theory, pp. 2993 3050. PMLR, 2021.
Joseph Lehec. The langevin monte carlo algorithm in the non-smooth log-concave case. Available on arXiv:2101.10695, 2021.
Jiaming Liang and Yongxin Chen. A proximal algorithm for sampling from non-smooth potentials. In 2022 Winter Simulation Conference (WSC), pp. 3229-33 -2400, 2022.
Tung Duy Luu, Jalal Fadili, and Christophe Chesneau. Sampling from non-smooth distributions through Langevin diffusion. Methodology and Computing in Applied Probubility, 2377)11173- 2021.
Tatiana Maximova, Ryan Moffatt, Buyong Ma, Ruth Nussinov, and Amarda Shehu. Principles and overview of sampling methods for modeling macromolecular structure and dynamics. PLoS computational biology, 12(4)=e1044119 2016.
Wenlong Mou, Nicolas Flammarion, Martin Wainwright, and Poter L Bartlett. An efficient sampling algorithm for non-smooth composite potentials. Journal of Machine Learving Research, 23(233): 50, 2022a.
Wenlong Mou, Nicolas Flammarion, Martin Wainwright, and Peter Bartlett. Improved bounds for discretization of langevin diffusions: Near-optimal rates without convexity. Bernoulli, (87)):1577-161 2022b.
Radford M Neal. MCMC using hamiltonian dynamics. Handbook of Markov Chain Monte Carlo, 2(11):2, 2011.
Yu Nesterov. Universal gradient methods for convex optimization problems. Mathematical Programming, 152(1):381-444 404, 2015.
Dao Nguyen, Xin Dang, and Yixin Chen. Unadjusted Langevin algorithm for non-convex weakly smooth potentials. arXiv preprint orXiv:2101.0633 063669 2021.
Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends in optimázation, 1(3):127-239, 2014.
13

---

Published in Transactions on Machine Learning Research (06/2023)
Giorgio Parisi. Correlation functions and computer simulations. Nucleor Physics B, 180(3):378 384-384, 1981.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. In Conference on Learning Theory, pp. 1674-1703 PMLR,
2017.
Alfréd Rényi. On measures of entropy and information. In Proceedings of the fourth Berkeley symposium on mathematical statistics and probability, volume 1, Berkeley, California, USA, 1961.
Gareth O Roberts and Osnat Stramer. Langevin diffusions and Metropolis-Hastigge algorithms. Methodology and Computing in Applied Probability, 4(4):337 357, 2002.
Gareth O Roberts and Richard Tweedie. Exponential convergence of Langevin distributions and their discrete approximations. Bernoulli, pp. 341-363, 1996.
Adil Salim and Peter Richtárik. Primal dual interpretation of the proximal stochastic gradient Langevin algorithm. Advances Newrul Information Processing Systems, 33:3786 3796, 2020.
Ruoqi Shen, Kevin Tian, and Yin Tat Lec. Composite logconcave sampling with Restricted Gaussian
Oracle. Available on arXiv:2006.0599 2020.
Jack W Sites Jr and Jonathon C Marshall. Delimiting species: renaissance issue in systematic biology.
Trends in Ecology & Evolution, 18(9):462-41) 470, 2003.
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperime- try suffices. Advances in neural information processing systems, 32, 2019.
Cédric Villani. Topics in optimal transportation, volume 58. American Mathematical Soc., 2021.
Andre Wibisono. Sampling as optimization in the space of measures: The langevin dynamics as composite optimization problem. In Conference on Learning Theory, pp. 2093 3027. PMLR, 2018.
Andre Wibisono. Proximal langevin algorithm: Rapid convergence under isoperimetry. ar preprint arXww:1911.01460, 2019.
14

---

Published in Transactions on Machine Learning Research (06/2023)
Contents
Introduction
1
2
Problem formulation and Background
3
3
Proximal sampling for non-convex and semi-smooth potentials
5
Proximal sampling for non-convex composite potentials
8
Proximal sampling for convex composite potentials
9
6 Computational results
10
Conclusions
12
Technical results
16
B Missing proofs
18
B. Proof of Lemma 3.1
18
B.2 Proof of Proposition 3.2
19
C Sampling from regularized convex semi-smooth potentials
19
D Solving the optimization problem
21
E Approximate implementations of ASF
24
15

---

Published in Transactions on Machine Learning Research (06/2023)
A Technical results
This section collects the definition of Frechet subdifferential and few technical results that are useful for the analysis of RGO in Section 3
Definition A.1 (Frechet subdifferential) Let f R" + R U foot be proper closed function, then the Frechet subdifferential is defined as
0f(x) { U R" lim inf f(v) f(x) (u, xx) 2 0
4 11 x
The first result is the well-known Gaussian integral.
Lemma A.2 A useful Gaussion inlegral: for any v) > 0,
J exp
1 dr (2mT) d/2
||=1|]
2m
The following lemma shows that fy as in 6 is close to strongly convex and smooth function when is small. This result is used in Proposition
3.2
Lemma A.3 Let 13 = f + 21 y and (fz) = f' + 1/( n), then we have for every u, E Rd
f
1 M1 I|u 2112 - (1-a)8
S f (u) ((F)))((()())))
1
1|u 1 0112 2 (1 a)d
$ 2
+ +M)
Proof: Using the definitions of 13 and (f3Y, we have
f2(4) ())) - (u), v)
1
=f(u) f(v) (f'()) -
|| y/1
|10
y/1
(v y, v) 17
2m
2n
=f(u) - -(v))(((v)) u v) + 2n
| v1l2.
The lemma now follows from above identity and
The next lomma gives equivalent formulas of f exp( nY, (x)) and J (exp(-hy; (x))()) (x)) that are usefuul in Proposition 3.4
Lemma A.4 Recall w and wn are defined in Proposition 3.2 and Lemma
3.9
respectively. Let hy, and hy
as in 9 and 110,, respectively. Then, we have the following integrals
2nT
4/2
exp( (1T
exp (H1 (w)),
(21)
1-
1-
nM
d/2
/
2nT
expl expl-hhy (z)) =
exp (Hz(")),
(22)
+ n/1l
where
(w(w)
1
||/|| +
2(1 - M) ||>|12 - -f(w) +
17
_
1
(ur, y - w.
||
+
1
5,
(23)
27
17
27
2
Hz(w*)= = 2n
1
||=2 1|2 - f(w") )+ + (f'("")) w²)
1
||
- a 5.
(24)
2n
2
16

---

Published in Transactions on Machine Learning Research (06/2023)
Proof: We first rewrite hyy and by as follows
M
(1 (1-
a)
(1) + (w' x w.)
=1110- -2 w|12
|| y|1
2n
2
1 - n
x
nM
w - 1
y/ +
77
('w))
2nj
1 7M
1 7M
21/(1 17M wmMM
μ 7 (w)(
+ f(w) - (f'(w.. w)
M
|121 +
1
|1 1
- a
8,
(25)
2
2n
2
and
M
(1
(1-a)8
(x) =f(w-) + (1'(w"), ), w²) +
|| w1112=
||
y/1
2
20
2
1 1/-
7M
2
1.
1 + nM w³
y/ +
8 (((x))
2n
1 nM
+ n
Indw' + =nff(w"))
21/(1 + v)M
+ f(ww)( - (f' (w" w²) + M 1|=51 +
1
1- a
|1//12 +
(26)
2
2n
2
It follows from
25 and Lemma
A.2 that
/ (,,
2
d/2
exp(fi (w)),
(27)
1 n
/ (1)
2
d/2
exp(Hz(("))
(28)
1 1 1+HM)
where
Al (w)
[n y - (f'
21/(1 7/M)
M
1
11/12 1-a 8,
||m||2
2
27
2
Hz(w")
|| w00 + y - nf (w (w0))1 f(w")((w))))))))))) (f(("",,w" w²)
21/(1 + m//rr
M
1-a a 8. |y/|
||
2
2n
2
It suffices to show that A (w) (w) and Az(w=*) H2(w") to complete the proof.
17

---

Published in Transactions on Machine Learning Research (06/2023)
We first verify that H1 (w)) H1(w). Using the definition of Hw( above and the definition of in we have
Hu(
1n - w + w - y nf (w) f(w) + (f (w), w)
21y(1 - 17
M
1
11y112 + 1-a8 8
woll
21)
1
11(2M1
- 1) + 1/s1? f(w) + (f(w),
21y(1 nM)
M
1
1-a 8
|
|1y11
+
21)
1
7
||21
+
M
1|=l1 - (w, + 2(1 v)
77
|| - [(w)) + (f(ww,,
2n
2
1 - a 2
|1yl1
+
8
21
|| +
2(1 v. ||||12 f(w) + (w. w)
17
1
|0l1 +
a
27
21)
2
In view of 13 we verify that (w) = H1 (w) and hence 21 is proved.
We next verify that H2(w=)) = H2 Using the definition of Hz(w") and
8 we have
1
fl2(w")
ImMMw + w w" + - (w= f(w") + (f'(w),, w
2n(1 + vM)
M
1
-
|1/1|2 21
1
1- a 2
8
2
1
M
11 + +1)w0*1
Iw |00 - f(w=) + (f'(w",, w²)
2ny1
+
2
1
1 1-a 8
|1/1
27
2
1
100 112
f((w') + (f (w") w²)
1
|1yl1 - 5.
27
21
In view of 24 we verify that Hz(w")) = H2( and hence
22 is proved.
B Missing proofs
B.1 Proof of Lemma 3.1
Tt. follows from the assumption that f is Laa-semismmoohh that for every u,u Rd.
If(u) - f(v) - (f'(), u w> Tea I|u - ullat1
(29)
a+1
Using the Young's ' inequality ab S <00/ /pp + b2 with
2
2
- | 11 b= -
a
p= a ++1 q =
(a + 1)8
1-a'
we obtain
La -|u- ull
L .+
1u r/
a+1
2a + 1)8
a+l
2
Plugging the above inequality into 29 we have
L
(1 - a)
ff() ff()- f()) - (f) u 0>15
1u
2 2 +
2[(a + 1)0 -
2
18

---

Published in Transactions on Machine Learning Research (06/2023)
This inequality and the definition of M in (5 imply
B.2 Proof of Proposition 3.2
Tt. follows from Lemma A.3 that fy satisfies
38 with
M, (1 a)
1
M,
L
(30)
2
Since 7, S 1/(Md), it is easy to verify that the assumption p (i.e., VMd in case) in Proposition D.4 is satisfied. Hence, it follows from Proposition D.4 and (30) that the proposition holds.
C Sampling from regularized convex semi-smooth potentials
This section presents an alternative approach via regularization for sampling in the same setting as in Soc-
tion 3 i.e., f is convex and satisfies ( More specifically, the alternative complexity result obtained by first applying Theorem 2.2 on a regularized convex semi-smooth potential and then specifying the regularization
parameter.
We consider the following regularized potential with some 0,
1() = 1() -
(31)
which clearly p-strongly convex by construction. Hence, exp(-f) satisfies y-LSI and Theorem 2.2 is applicable. Since is p-strongly convex, improved versions of results in Section 4 can be obtained. We omit the proofs since they can be casily obtained by following similar ideas the proofs given in Section
Lemma C.1 Assume f is a convex function and satisfies
① then for 8 > 0 and every u, v Rd we have
Mn
||u u1 + Σ (1-a:)8
f(w)-((v) (f(()), 1)
2
2
( (f'( n) 2 0112
where f and M,, are as in 31 and 17
respectively.
Proposition C.2 Assume S M.d. and let w E Rd be an approzimate stationary point of
[m](0) = f(x))) 1 =Ix - y/1²
min WERd
(32)
2n
i.e.,
|| S Mnd, f') + ( 4), 1J
(33)
where Mn is as in 17 Then, the clemution-ompleeityy to find w by using Algorithm is Ō().
Lemma C.3 Let w' E Rdd be stationary point of fgg i.e.,
f'(w") + - (w- - y) = 0.
Define
(x) = f(ww) + (f)) x w) +
" 111 w/12 + 2n
1 y112.
Mr + 11
(1 - a:)
hy (x) = f(ww)) + (w") ) w²)
| 1 w" 2 +
|| w11
Σ
2
2n
==1
19

---

Published in Transactions on Machine Learning Research (06/2023)
where is in 33 Then, have for every R
by, (x) S (x) S h
Proposition C.4 Assume f is convez and satisfies and let fg be as in 132 Then X generated by
(with 7 f.J and (1,y(x) replaced by (33 fg. and hī,(a)) respectively) follows the distribution x XIY (xr v) exp
Algorithe
(ff Moreover, i/ S M.d. then the expected number of rejection steps in Algorithm
i== (1-a.)5 +1). 2 is at most exp
Proposition C.5 Assume f is convex and satisfies 11, and let f be as in 31 With initial distribution pà and slepsize y x 1/
[Ei=l Lai meti d). Algorithm using Algorithm 2 as an RGO achieves e error in lerms
of KL divergence with respect lo exp(-f) in
Ei= Lo:
(34)
iteration, and each iteration queries O(1) subgradient oracle of f and (() Gaussian distribution sampling oracle.
Proof: By construction, f is p-strongly convex and exp(-f) satisfies J-LSI. Using Theorem 2.2 starting
from initial distribution Po it takes
H (pt)
log
(35)
2pmn
6
iterations for Algorithm
to achieve e error to exp(-f) with respect to KI. divergence.
By Propositions C.2 and C.4 Algorithm queries Õ(1) subgradient oracle of f and O(1) Gaussian distri-
bution sampling oracle. Complexity (34 then follows by plugging 1) into 35
Building upon Proposition C.5 for sampling from exp(-f(x)) exp(- u||=- x 122/2,, we establish a complexity result, in the following theorem, to sample from the original target distribution x exp(-f) by choosing proper regularization constant Jr.
Thcorem C.6 Let x exp(-f(x)) be the target distribution where f is convex and satisfies 20 E Rdd and 0 be given and set
Let
1 =
(36)
(V + 1|:00 Fmin 12)
where M4 Jgg || Fmin dm ( (x) and Fmin E Argmin (f(x) E RdJ. Wilh inilial distribution pg and stepsize 17 x 1/
Algorithm using Algorithm as an RGO for step 1, applied to x exp(-f) exp(p1 HA|l 01 2 has the steration-complecity bound
Lui Σm=
El La: d d(MM4 + 1|000 Fenin 1?2)
(37)
8
achieve e error x in terms of total variation.
Let Xx denote the distribution of the samples generated by Algorithm Jusing Algorithm as an RGO. Following the proof of Corollary 4.1 of Chatterji et al. (2020), we obtain
Proof:
||
xxx || < x u/|TV + 1/v
TTV
20

---

Published in Transactions on Machine Learning Research (06/2023)
and
(Le -f(x)- - f(x))3dm (r)
1
1/2
(1ee
1
1/2
| - u/rrv S
dr d (x)
2
Rd
2
Rd
2
(1e
1/2
1/4
14
(1|x Iminll 112 + || - x0113)² do dotx (x)
2
gd
1/2
11
(2|1x - Tmiall [oaall++0 +21|2min - xx01(t) dh x (x))
2
Rd
22u
2 (Ma ||aimin - =0911)) 1/2 22
(M 1 2min 12) E
2
where the last identity is due to the definition of in (36) Hence, it suffices to derive the iteration- complexity bound for Algorithm [ to achieve ll - 1/// I E/2, which is (37 in view of Proposition C.5 with as in
36p. Note that even though the complexity result in Proposition C.5 is with respect to KL divergence, one can get the same order complexity with respect to total variation using Pinsker inequality.
Solving the optimization problem
In this section, we use Nesterov's acceleration establish the ceeration-cmplees for solving general optimization problem that is nearly strongly convex and nearly smooth. This general result is then applied in Section to find approximate stationary point of fy (see Proposition 3.2
We consider the optimization problem min(g(2) Rd), where g satisfies
P 1|u u112 - 0 s g(u) - g(v) - (0/ (0), u) < 2
L ア 1 + +
Vu
(38)
for some given 0 0, l 2 0, and L 2 We use Nesterov's accelerated gradient method find a & approximate stationary point w such that (w)( S p. We also establish the tteration-oomplexity obtain p-approximate stationary point.
A Algorithm 3 Accelerated Gradient Method
0. Let an initial point zo, parameters L, > 0 be given, and set yo Zo: Ao = 0, To 1, and A: O:
1. Compute
Th V 2
T5 AT
ax
A
As + ap.
(39)
2L
Auile + ag.K.
Tk+1 Th + OKH,,
3b
(40)
Ax+1
2. Compute
M641 := argmin wERd
(u(4)= + - ||u 2x1l $.
(41)
2
Ik41 == argmin (ax7((u) wERd
Th " -1ue xx 11]
(42)
2
where
(x( = g( + (g'( -bx) + 1 | 12
(43)
3. Set k - k + 1 and go to step 1.
Lemma D.1 For every k and u Rdd we have
9 < g(()= - (u) =
2 Iu xx 2 + A.
11
(44)
21

---

Published in Transactions on Machine Learning Research (06/2023)
Proof: This lemma directly follows from 38 and the definition of y in
43
Lemma D.2 For every & 2 0, the following statements hold:
a) ARt1 = Lat/Ta
6) Aut1 2 I
V
2vL
6) Ei=o A1+1
0xp(((k-110-11011 where B = 1 + yB
[(B--1)
2/L"
Proof: a) This statement directly follows from (3
b) It easy to see from Ag and Tu that A1 1/L. Using the definitions of A₃ and T in 39
and 40 respectively, and the facts that Ag 0 and TD 1, we easily derive that
= To + Akp = + Axp.
(45)
It follows from
39 that
+
K 4T LA
A + TK
(VAx+
V
A&+1 A as A&
+
2L
2L
VL
2
The above inequality and 45 imply
Th
VI+ Ant
(1 vP VΛk
A 2
A
/A+
2
2
2VL
This statement now follows from the above relation and the fact that A 1/L.
c) Noting from b) that Ac+1 2 32h /L, which together with the fact exp((x x)) for x 2: 1, implics
that
62h g2(k+1) -1 L(32-10
exp(2(k + 1)(B - -
A
L
L(B2
0
Lemma D.3 For every & 2 0, define
tu(u)= = A4 [g(xx) - g(u)] + Th 1|u - -x
(46)
then for every Rdd, we have
f
A - -xxll S (u) (x+1(u) + 2A
(47)
2
Proof: Using the fact 7h is convex and the definition of Fx in 40 we have
(yn) + auT)(u)
|
xx
Aubkk + ag4
Th-AP
Akyl + ag
A4+177
Ak+1
2
Ast1
=A++1
%
ARNI + apu
+
L
An
a&u
Au+1
AR+1
2A++1 min (Ta(u)=
-
I
I|u
11
2
I
-Aet1
(a(06+1)
11192-1
F
112
22

---

Published in Transactions on Machine Learning Research (06/2023)
where the first identity is due to 339 and the second identity is due to the definition of yk+1 in follows from the second inequality of 44 with u = yk+11 and the above inequality that
41 It
Ak+1 g(8++1)
0+ + M
|1 - =x
L
< Au+1 Th (1(++1)
=1111-11 - +x211?
2
I (y))(())) + a677 (2*+()) Th | 2*k 1|
S (un) + (u) + Tk ||u - xul1 Th+11 1 xx+111 1|2
where the last inequality is due to 42) and the fact that aRTR Txll Rearranging the terms in the above inequality, obtain
1//11//2 /2 is Te41-strongl convex.
1 マ/ As+1 1 #xll?
<A4T((U)) + (u)) ||u 2x11 Tk+1 ||u - 0k+1|l AR+1 (g( 0)
=As (g(lk) g(w]l Tk ||u u- x=11112-- Ak+1 (g( g[()]] Tk+1 ||u
xk+11l
+ As IY (Bx) - [(vk]] + ax (Tx(2) - gu)] + As+10
Stu(u) tk+1 (u) 1
where the identity is due to the fact that A&t1 = A₁ + aak, and the last inequality is due to 46 and the first inequality of 44
Proposition D.4 1f 2 2/2( + L)VO//T, then the number of iterations ko to obtain a p-approzimate stationary point of g is at most
2VL + vP
(n L)
2
+1)
hp
log
(48)
2/F4
p²
2/H
Proof: It follows from the optimality condition
41 that
g'(āx) (1x + (5x Vk+1))
Using the above relation and summing 47 with u = x² from = to h - 1, we have
P
A Ilg (2
Mi+1 - -6,11 2,112
2n + L)
k-1
di
k-1
I to(o=") + 2
Σ
A =
+
Σ
A4+10,
2
i=0
1=0
where the last identity follows from the facts that Ag assumption on imply that
0 and
=
The above inequality and the
(μ T.)2
dg
(n+ L)2
df
1²
min 0sick-1
(2x))
40
S
Σ A,1
P
Σ i=0
A
2
In order to show minosisk- (+)) s p, it suffices to show
(μ L)2
di
0²
(49)
Σ -
A
2
Using Lemma D.2
(c) and the fact that 2> Ko where Ko is as in
48) we have
k k-1
- 1112)(3-1)/8)-))
2( + L)
A41 2
2
1
pp2
1=0
and hence 49 is proved.
23

---

Published in Transactions on Machine Learning Research (06/2023)
E Approximate implementations of ASF
The implementation of RGO in Algorithm 2 is exact, hence the samples of both RGO and ASF are unbiased. In contrast, it is shown in Theorem 1 of Wibisono 2019) (resp., Theorem of Vempala & Wibisono (2019) that the proximal Langevin algorithm (PLA) (resp., LMC) is biased. From the perspective of proximal sampling, we give an explanation of this fact by showing that PLA and its equivalent method, namely, proximal Langevin Monte Carlo (PLMC) of [eenttnn (2018), can be viewed as an instance of ASF whose implementation of RGO is inexact.
Assume the potential function f is convex and smooth. Recall that PLMC itcratively generates samples as follows: given yh E R4, then the next sample yk++ takes the form of yh++1 = prox,f (Ms) + /2nz where 2 (), It is easy to verify that the following algorithm gives an equivalent form PLMC.
A Algorithm Proximal Langevin Monte Carlo (Bernton 2018)
1. Sample Ih ~ expl 2n | ,rox,, (yx) (yx) )|
2. Sample 1k+1 π XIX (yl IR) expl- 2 ly xx|l²]
Next, we show that PLMC is an approximate implementation of ASF. Similar to ASF, PLMC also alternates between steps and 2. More specifically, step of PLMC plays the same role as step of ASF, and step of PLMC can be viewed as sampling from the proposal density
[x)] without rejection, where 2/ || prox,, (1k s f (z). Since (x) is the potential function of the RGO in step 2 of ASF. Hence, step 1 of PLMC is an approximate implementation of the RGO. As result, both PLMC and PLA are approximate implementations of ASF, and thus they are biased.
h1 (z) == fg. (prox,,((k))
Following a similar argument, we show that LMC can be viewed as an instance of ASF whose implementation of RGO is inexact. Assume f in the target distribution x x exp(-f) is convex and smooth and recall that the iterative step in LMC can be described as
Mk+1 = Uk VVVA) + 212 2 (),
(50)
We claim that the following algorithm gives an equivalent form of LMC 50 from the proximal sampling perspective.
Algorithm 5 Langevin Monte Carlo
1. Sample yk nT xTXX(yy (y) σK) expl 2n | =|
2. Sample Ik+1 ~ expl- Mn 2 ye V (2xx)
Indeed, steps 1 and 2 can be equivalently written as
Fb+1 1/: f((u) + Vizu. zk ((, 1),
Mk++ = 0b+1 + Vn 2 N(0,1),
where yett is the sample from step in the next iteration. Combining the above identities, we have
Uk+1 Uk- f(Vv) + VT((a + x d yk VVf(v) 22zz, (0.
Moreover, LMC and ASF share the same step 1, and step 2 of LMC equivalently generates Te+1 from (x) where
1
hx(z) = f(x) + (V)()),, yn) + ||x 1.ll2.
(51)
2m
Using the definition of h in and the convexity of f, we have
1
(z) E f(x) +
| vall = $3. (z).
2n
24

---

Published in Transactions on Machine Learning Research (06/2023)
Note that f (x) is the potential function of the RGO in step 2 of ASF. Hence, step 2 of LMC can be interpreted as an RGO implementation with the proposal density (x)[-h((x) but without rejection. As a result, LMC is an approximate implementation of ASF and thus LMC is biased.
It is worth noting that many other sampling algorithms, for example, symmetric Langevin algorithm of Wibisono (2188) and Metropolis-adjusted proximal gradient Langevin dynamics of Mou al. (2022a), can also be shown to be approximate implementations of ASF in an analogous way.
25


Reviews:
[{"review_id": "NV1I8LFf2m", "reviewer": "Reviewer_u2Fa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n#### Strengths  \n\n* The class of semi-smooth functions is much larger than the one of the smooth functions. \n* The application Nesterov's accelerated algorithm implemented to find the majorizing density.\n* The paper extends the setting by Liang & Chen. \n#### Weaknesses\n\n-   The nonconvexity arising from (1) does not cover the entire class of nonconvex functions. In particular, (1) implies a quadratic lower bound on the function $f$. This means that by adding a square norm with a sufficiently large multiplier, a convex function can be obtained.\n-   The coefficients $L_i$ and $\\alpha_i$ for the example of a semismooth potential displayed on page 3 are not specified.\n-   In the general case, it is unclear how to find or approximate the constants $L_i$ and $\\alpha_i$.\n-   None of the theorems are proven in the paper. Even the theorems with seemingly \"obvious\" proofs should be properly written and explained.\n-   The quality of writing in the paper is insufficient, lacking necessary mathematical details.\n\n##### Experiments\n\n-   The chosen step size for LMC in the experiments is significantly smaller (depends on the dimension) than the theoretical step size, which  is of order ($\\approx 1/L$) and does not depend on the dimension.\n-   The target distribution used in the experiments is overly simplistic, and the dimension of the space is very small ($d=5$).\n\n#### Question\n\n-   Regarding the RGO discussed in the paper, which has a broad form allowing for almost any potential function, am I correct in understanding that the proposed method solves the exact sampling problem through a finite number of rejection-acceptance steps? If that is the case, it is possible that there is a hidden dependence on the dimension, either in the multiple parameter conditions or potentially missing in the proof.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper examines the Alternating Sampling Framework (ASF) for sampling from a target distribution proportional to $\\exp(-f)$, where $f$ is a semismooth (as defined in the paper) and nonconvex function. The ASF framework consists of two steps performed at each iteration. The first step involves Gaussian sampling, while the second step requires sampling from a proximal version of $\\exp(-f)$, referred to as RGO.\n\nTo implement the RGO step, the authors propose a Rejection/Acceptance sampling mechanism by bounding the potential function with a quadratic function. They determine this new function by finding a loose stationary point using Nesterov's accelerated algorithm. The paper provides guarantees that the number of rounds required for each iteration is bounded.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Requested Changes\n\n- add the reference Balasubramanian et al. 2022 (LMC in the non-convex setting), Dalalyan et al. 2019 (LMC and KLMC in non-strongly log-concave setting).\n- page 2: `one and` -> `and one`\n- the hyperlinks (references, equations. etc.) do not work\n- page 3: Use `citep` for the last reference.\n- To avoid possible confusion, it is worth mentioning that the distributions and their densities are considered to be equivalent in the paper.\n- Rewrite Algorithm 4 in terms of the function $f_y^{\\eta}$. In the appendix, the parameters are different and do not translate well to the sampling setting.\n- page 7: `Combing` -> `Combining`\n- In the last line of (12) $\\times$ operator could be added to increase the clarity of the formula.\n- Page 7: the equation after `which together with (7) implies that`. The term $\\frac{1}{\\eta} ||w||^2$ is missing on the third line.\n- Use the LaTeX environment `{align}` to align  the equations. \n- Page 7: `Note $\\delta$ is a tunable parameter.` ->  `Note that $\\delta$ is a tunable parameter.`\n- Add more complicated experiments that confirm the results of the theorem. It would be useful to see that the expected number of rejections indeed has the upper-bound mentioned in the theorems for . ", "broader_impact_concerns": "Theoretical work. No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3ydo86yXjU", "reviewer": "Reviewer_n7Lu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n- The paper is well written \n- th algorithm works in a semi-smooth non convex setting extending previous works that work for with semi-smooth and convex or smooths and non-convex settings \n- proposed algorithm seems to be competitive by looking at Table 1.\n\nWeaknesses:\n- in view Liang and Chen 2022 this work seems incremental. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The key contribution is the development and analysis of sampling from distributions with possibly non-covex and semi-smooth potencial. \nThe algorithm is heavily based on: a) alternating sampling framework ASF that has been dveloped for semi-smooths (but convex) case in Lee et al. 2021 and extended to distrbutions satisfying logarithmic sobilve inequlitiy LSI or Poincare inequlity PI functional inequlities by Chen at. al.; b) ideas from Liang and Chen 2022 that treats the same setting as the current paper but with convex potencial. In particular, Liang and Chen 2022 develop practical algorithm for sampling from restricted gaussian oracle which is critical for efficient implementation of ASF.    \n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- a detailed discussion comparing current work and Liang and Chen 2022 should be inlcuded. \n- In Lemma A.3.  is f' a derivative of subdifferential? I though f is not differentiable ", "broader_impact_concerns": "methdological work; no ethical considerations. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ym5mlqme00", "reviewer": "Reviewer_wgsP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n- The implementation of the RGO is important in practice. First, because the outer loop (ASF) is going to be important in the future, given the recent results on this sampler. Second, because we do not have many closed form formula for the RGO but we do have **exact** subroutines (as the one presented in the paper). So, investigating these exact subroutines is of practical interest.\n\n- The result in this paper on the RGO (the inner loop) can be combined with known results on the ASF (the outer loop) which enables to provide an end-to-end guarantee in terms of number of gradient calls to achieve epsilon accuracy.\n\n**Weaknesses:**\n\n- The paper is not well written. The topic of the paper is implementing the RGO. Each section should be related to this topic. The content of each section should be dedicated to the topic of the section. \n\n-  The introduction is too confusing for such a simple situation: there is an outer loop (ASF) that is well understood but requires implementation of the RGO (inner loop). The inner loop has been studied when f is convex nonsmooth, this paper is about the inner loop when f is semi smooth, under various other assumptions: LSI, PI, log concave. The authors could simplify and shorten the introduction.\n- Semi-smoothness should be motivated. I know that TMLR is mainly about correctness of the paper, but why is semi-smoothness relevant in practice? Besides, is it easy to learn the semi-smoothness parameters? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The Alternating Sampling Framework (ASF) is a sampling algorithm to sample $\\exp(-f)$ that achieves theoretical superiority, but relies on the implementation of the so called RGO at each iteration, a sampling subproblem that needs to be solved at each iteration. The RGO can be seen as the sampling analogue of the proximity operator in optimization, therefore its implementation is of practical interest. \n\nThis paper deals with the implementation of the RGO when $f$ is a semi-smooth function. They establish SOTA complexity results in the number of (sub)gradient calls to achieve epsilon accuracy in the semi-smooth setting.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- \"Departing from the standard smooth setting, the potentials are only assumed to be weakly smooth or non-smooth\" and \"When n = 1 and α1 = 0, f satisfying (1) is a non-smooth function. Thus, the cases we consider cover all three cases: smooth, weakly-smooth, and non-smooth.\" The paper does not cover arbitrary non-smoothness, right?\n\n- \"The target distribution ν is assumed to satisfy LSI or PI, but f can be non-convex in general.\" The paper does not cover arbitrary non convexity, right? Since at least PI is assumed.\n\n- \"[We] develop a proximal algorithm to sample from non-convex and semi-smooth potentials.\" The outer loop is not among your contributions.\n \n- I don't understand the first sentence of the proof of Prop 3.4 (bottom of page 6). Could you explain more please?\n\n- Please add more context at the beginning sentence of Section C, about the goal of this section, and the difference with the approach in the main paper.\n\n- Regarding my comment on the quality of writing, I give some examples here:\n\n\" This type of distribution has been studied in (Chatterji et al., 2020; Chewi et al., 2021; Nguyen et al., 2021) for MCMC sampling.\" Don't need to sell PI or LSI here.\n\n\"We set δ = 1 in all our experiments.\" Write this sentence in the exp section rather than the theory section.\n\nSection 6 does not help the paper (which is about implementing the RGO) and is already known (I believe). Maybe, merge section 6 with section E in the appendix.\n\n\n--------------------------------------------------------------------------------------------------------------\nIn summary, I don't have any concerns about the results in this paper (except bottom of Page 6), but I do have concerns about the clarity of the paper, for a non expert reader.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Vk9vB9e3e9", "reviewer": "Reviewer_Dv6M", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper gives state-of-the-art results (at least, at the time it was written) for semi-smooth sampling, making it a valuable contribution to the field. The implementation of the restricted Gaussian oracle (RGO) and the derived complexity guarantees are novel and insightful.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper investigates the use of the proximal sampler for sampling from semi-smooth potentials. While the convergence of the proximal sampler has been previously studied, this paper's novelty lies in describing implementations of the restricted Gaussian oracle (RGO) in the semi-smooth case and deriving complexity guarantees. The paper provides state-of-the-art results for semi-smooth sampling.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Add a remark discussing the scale invariance of the results.\n- In theorem statements, clarify that the number of queries is in expectation.\n- In Thm. 4.4, provide guarantees in the Rényi divergence.\n- The experimental comparison with the LMC algorithm is not fair, as LMC is a low-accuracy algorithm. Include a comparison with the Metropolis-Adjusted Langevin Algorithm (MALA) instead.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The author study a certain subroutine (RGO) of the Alternating Sampling Framework (ASF). ASF is a sampling algorithm with favorable theoretical properties relying on the call of a restricted Gaussian oracle (RGO) in each iteration. RGO is a sampling subproblem that can be seen as an  analogue of the proximity operator in optimization. 

In particular, this paper deals with the implementation of the RGO in the semi-smooth regime. The authors establish new SOTA complexity results (in the number of subgradient calls to achieve epsilon accuracy) in this regime.

- The paper studies an important problem: how to implement RGO in practice. 
- The extension to semi-smoothness is interesting since the class of semi-smooth functions is much larger than the class of smooth functions.
- The paper is contains interesting theoretical results that appear to be correct.
- The results are of a somewhat incremental nature, but still interesting (this is an extension of the results of Liang & Chen).
- The implementation of the RGO is important in practice. 
- The writing quality was criticized by several reviewers (e.g., intro is more confusing than it has to bel; semi-smoothness can be motivated in a better way). 

More pros and cons were mentioned in the reviews.

In summary, this is a good paper (after the revision), and I recommend for it to be accepted.

Action Editor
Decision: Accept (poster)