A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers
Authors: Ye He
Alireza Mousavi-Hosseini
Krishna Balasubramanian
Murat A Erdogdu
Venue: NeurIPS 2024 poster (2024)
Keywords: Proximal samplers
Complexity of heavy-tailed sampling
Restricted Gaussian oracle
Restricted Stable oracle
Primary area: learning_theory
TL;DR: Gaussian-based proximal samplers face accuracy limits sampling heavy-tailed targets. Stable-based samplers offer high-accuracy guarantees, surpassing this constraint.

Abstract: We study the complexity of heavy-tailed sampling and present a separation result in terms of obtaining high-accuracy versus low-accuracy guarantees i.e., samplers that require only $\mathcal{O}(\log(1/\varepsilon))$ versus $\Omega(\text{poly}(1/\varepsilon))$ iterations to output a sample which is $\varepsilon$-close to the target in $\chi^2$-divergence. Our results are presented for proximal samplers that are based on Gaussian versus stable oracles. We show that proximal samplers based on the Gaussian oracle have a fundamental barrier in that they necessarily achieve only low-accuracy guarantees when sampling from a class of heavy-tailed targets. In contrast, proximal samplers based on the stable oracle exhibit high-accuracy guarantees, thereby overcoming the aforementioned limitation. We also prove lower bounds for samplers under the stable oracle and show that our upper bounds cannot be fundamentally improved.

A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers
Ye He Georgia Institute of Technology yhe367@gatech. edu
Alireza Mousavi-Hosseini University of Toronto, and Vector Institute mousaviecs. toronto.co.m...o edu
Krishnakumar Balasubramanian University of California, Davis
Murat A. Erdogdu University of Toronto, and Vector Institute erdogduêcs toronto.ec edu
abala@ucdavis.ee.
Abstract
We study the complexity of htavy-tailed sampling and present a separation result in terms of obtaining high-accuracy versus low-accuracy guarantees i.e., samplers that require only ([log(1/E)) versus ((poly(1/EE) iterations to output a sample which is s-close the target in >-=divergence. Our results presented for proximal samplers that are based on Gaussian versus stable oracles. We show that proximal samplers based the Gaussian oracle have fundamental barrier in that they necessarily achieve only low-accuracy guarantees when sampling from a class of heavy-tailed targets. In contrast, proximal samplers based the stable oracle exhibit high-accuracy guarantees, thereby overcoming the aforementioned limitation. We also prove lower bounds for samplers under the stable oracle and show that our upper bounds cannot be fundamentally improved.
Introduction
The task of sampling from heavy-tailed targets arises in various domains such Bayesian statis- ties [GJPS08, GLM18), machine learning [CDV09, BZ17, N$R19, SZTG20, DKTZ20), robust statisties [KN04, JR07, Kam18, YLR22], multiple comparison procedures [GBH04, GB09], and study of geophysical systems [SP15, QM16, PBEM23). This problem is particularly challenging when using gradient-based Markov Chain Monte Carlo (MCMC) algorithms due diminishing gradients, which occurs when the tails of the target density decay at a slow (e.g. polynomial) rate. Indeed, canonical algorithms like Langevin Monte Carlo (LMC) have been empirically observed to perform poorly [LWME199, HMW21, HFBE24] when sampling from such heavy-tailed targets.
Several approaches have been proposed in the literature overcome these limitations of LMC and related algorithms. The predominant ones include (i) transformation- based approaches, where a diffeomorphic (invertible) transformation used to first map the heavy-tailed density a light-tailed one so that a light-tailed sampling algorithm can be used [JG12, Yt.222, HBE24), (ii) discretizing general Itô diffusions with non-standard Brownian motion that have heavy-tailed densities their cquilibrium density [EMS18, LWME19, HFBE24], and (iii) discretizing stable-driven stochastic differential equations [ZZ23]. However, the few theoretical results available on the analysis of algorithms based on approaches (i) and (ii) provide only low-accuracy heavy-tailed samplers; such algorithms require (oly(1/E) iterations to obtain sample that E-close the target reasonable metric of choice. Furthermore, quantitative complexity guarantees for the sampling approach used in (iii) are not yet available; thus, existing comparisons are mainly based on empirical studies.
In stark contrast, when the target density is light-tailed it is well-known that algorithms like proximal samplers based Gaussian oracles and the Metropolis Adjusted Langevin Algorithm (MALA) have high-accuracy guarantees; these algorithms require only polylog(1/8 iterations to obtain a sample which is e-close the target in some metrie. See, for example, the works by (DCWY19, LST21b,
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

v 2 1
1/ E (0, 1)
Oracle
Gaussian (Alg. 1)
Stable (Alg. 2 & 3)
Gaussian (Alg. 1)
Stable (Alg. 2 & 3)
Complexity ((E=²) 3) (Cor. 2)
(llg(E=-)) (Cor. 5)
()(==t) (Cor. 2)
O ((== (Cor. 5)
Table I: Separation for Proximal Samplers: Gaussian vs. practical Stable oracles (a 1): Upper and lower iteration complexity bounds to generate an e-accurate sample in x²= <<iieeeree from the gemeralized Cauchy target densities with degrees of freedom v, i.c. my (1 + ( Here, 2 Ô hide constants depending on V/ and polylog(d (d. 1/E), For the proximal sampler with a general a-Stable oracle (Algorithm 2), the upper bound for v E (0, 1) is (llo((1/E) when a = v. The lower bounds are from Corollary 2 via 2TV <x'.
WSC22a, CCSW22, CG23]. Specifically, [LST2Ib] analyzed the proximal sampling algorithm to sample from class of strongly log-concave densities and obtained high-accuracy guarantees. [CCSW22] established similar high-accuracy guarantees for the proximal sampler to sample from target densities that satisfy certain functional inequality, covering a range of light-tailed densities with exponentially fast tail decay (e.g. log-Sobolev and Poincaré inequalities). However, it is not clear if the proximal sampler achieves the same desirable performance when the target not light-tailed.
In light of existing results, in this work, we first consider the following question:
Q1. What are the fundamental limits of proximal samplers under the Gaussian oracle when sampling from heavy-tailed targets?
To answer this question, we construct lower bounds showing that Gaussian-based samplers necessarily require poly(1/e) /e) iterations to sample from class of heavy-tailed targets. These results complement the lower bounds on the complexity of sampling from heavy-tailed densities using the LMC algorithm established in [MHFH*2]] 23]. With this lower bound in hand, we next consider the following question:
Q2. Is it possible to design high-accurayy samplers for heavy-tailed targets?
We answer this in the affirmative by constructing proximal samplers that are based on stable oracles (see Definition I and Algorithm 2) by leveraging the fractional heat-flow corresponding a class of stable-driven SDEs. We analyze the complexity of this algorithm when sampling from heavy-tailed densities that satisfy a fractional Poincaré inequality, and establish that they require only log(1/a iterations. Together, our answers to Q1 and Q2 provide a clear separation between samplers based on Gaussian and stable oracles. Our contributions can be summarized as follows.
Lower bounds for the Gaussian oracle: In Section 2, we focus on Q1 and establish Theorems 1 and 2 respectively that the Langevin diffusion and the proximal sampler based on the Gaussian oracle necessarily have a fundamental barrier when sampling from heavy-tailed densities. Our proof technique builds on [Hail0], and provides a novel perspective for obtaining algorithm- dependent lower bounds for sampling, which may be of independent interest.
A proximal sampler based on the stable oracle: In Section 3, we introduce a proximal sampler based on the a-stable oracle, which fundamentally relies on the exact implementations of the fractional heat flow that correspond to sable-driven SDE. Here, the parameter a determines the allowed class of heavy-tailed targets which could be sampled with high-accuracy In Theorem and Proposition 1, we provide upper bounds on the iteration complexity that are of smaller order than the corresponding lower bounds established for the Gaussian oracle. We provide a rejection- sampling based implementation of the a-stable oracle for the case 1 and prove complexity upper bounds in Corollary 3. Finally, in Theorem 4, considering a sub-class of Cauchy-type targets, we prove lower bounds showing that our upper bounds cannot be fundamentally improved.
An illustration of our results for Cauchy target densities, nV X (1 + |xd)))(d++)// degrees of freedom, is provided in Table 1. We specifically consider the practical version of the stable proximal sampler with a= 1 (i.e.. Algorithm 2 with the stable oracle implemented by Algorithm 3), and show that it always outperforms the Gaussian proximal sampler (Algorithm 1). Indeed, when v 2 1, the separation between these algorithms is obvious. In the case v E (0, 1), Algorithm 2 & 3 has poly(1/a /) complexity, nevertheless, still improves the complexity of the Gaussian proximal sampler by factor of e. We also show via lower bounds (in Section 3.4) that the poly(1/=) complexity for Algorithm & 3. when E (0, 1). can only be improved up to certain factors. We remark that for the ideal proximal sampler (Algorithm 2). the upper bound when v E (0. 1) is also (log( //))). These results demonstrate clear separation between Gaussian and stable proximal samplers.
/2 where v is the
Related works. We first discuss works analyzing the complexity of heavy-tailed sampling as charac- terized by a functional inequality assumption. [CDV09] analyzed the connection between sampling

---

algorithms for a class of s- s-concave densities satisfying a certain isoperimetry condition related to weighted Poincaré inequalities. [HFBE24] undertook a mean srean-square analysis of discretization of specific Itô diffusion that characterizes a class of heavy-tailed densities satisfying weighted Poincaré inequality. [ALPW22] and [3L)W233 analyzed the complexity of aseudo-marging MCMC algorithms and the random- -wak Metropolis algorithm respectively, under weak Poincaré inequalities. As mentioned before. [MHFH + 23] showed lower bounds for the LMC algorithm when the target density satisfies a weak Poincaré inequality. [HBE24] and [YLR22] analyzed a transformation based approach for heavy-tailed sampling under conditions closely related to the same functional inequality. This transformation methodology is also used to demonstrate asymptotic exponential ergodicity for other sampling algorithms like the bouncy particle sampler and the zig-zag sampler, in the heavy- tailed settings [DBCD19, DGM20, BRZ19]. These works provide only low-accuracy guarantees for heavy-tailed sampling and do not consider the use of weak Fractional Poincaré inequalities.
Recent years have witnessed significant focus on (strongly) log-concave sampling, leading to an extensive body of work that is challenging to encapsulate succinetly. In the context of (strongly) log- concave or light-tailed distributions, plethora of non-asymptotic investigations have been conducted on LMC variations, including advanced integrators [SL19, LWME19, HBE20), underdamped LMC [CCBJ18, EGZI9, CLW23, DRD20J, and MALA (DCWY 19,, LST20, CLA+ 21, WSC22b). Outside the realm of log.concavity, the dissipativity assumption, which regulates the growth of the potential, has been used in numerous studies to derive convergence guarantees [DM17, RRT17, EMS18, EH21, MFWB22, EHZ22, BCE+22].
While research on upper bounds of sampling algorithms' complexity has advanced considerably, the exploration of lower bounds is still nascent. [CGL,+22] explored the query complexity of sampling from strongly log-concave distributions in one-dimensional settings. [L.TT22] established lower bounds for LMC in sampling from strongly log-concave distributions. [CBL22] presented lower bounds for sampling from strongly log-concave distributions with noisy gradients. [GLL20] focused on lower bounds for estimating normalizing constants of log-concave densities. Contributions by [LST21a] and [WSC22b] provide lower bounds in the metropolized algorithm category, including Langevin and Hamiltonian Monte Carlo, in strongly log-concave contexts. Finally, [CGLL22] contributed to lower bounds in Fisher information for non-log-concave sampling.
2 Lower Bounds for Sampling with the Gaussian Oracle
In this section, we focus on Q1 for both the Langevin diffusion (in continuous time) and the proximal sampler (in discrete time), where both procedures have the target density as their invariant measures. Our results below illustrate the limitation of the Gaussian oracle' for heavy-tailed sampling in both continuous and discrete time, showing that the phenomenon is not because of the discretization effect, but is inherently related to the use of Gaussian oracles.
Langevin diffusion. We first start with the overdamped Langevin diffusion (LD):
dx,- (X,,) v2dB,
(LD)
LD achieves high-accuracy "sampling" in continuous time, i.c. polylog(1/E) convergence rate in the light-tailed setting. We make the following dissipatiivity-ypee assumption.
Assumption 1. The target density is given by xx xxxx) x exp(-V(x)). where V R IR satisfies
(d (1+=))= 1+ |x|2
(d 12)lx|2 for some 1/2 2 $ 2 0.
Vx E TRdd
S (c. VV(x)) S 1 |z|
Remark 1. The upper bound on (at, (c))) ensures that V grows at most logarithmically in [x]. Consequently, x is heuvy-tailed and in fact does not satisfy a Poincaré inequality. The lower bound on (x. VV (x)) is only needed for deriving the dimension dependency in our guarantees. If is only interested in the e dependency, this condition can be replaced with 0 < (x. Vx))).
classical example of a density satisfying the above assumption is the generalized Cauchy density with degrees of freedom 1/2 I/2 > O, where the potential is given by
+ V In(1 + 12
V. (x(
(1)
2
The following result, proved in Appendix A, provides lower bound on the performance of LD.
Herr, for the sake of unified presentation, we refer the of Brownian motion in (LD) Gaussian oracle.
3

---

Algorithm/ 1 Gaussian Proximal Sampler [LST2Ib]
Input:
Sample 2o, and step rj > 0. for k = 1, ,N
|/ Gibbs sampler |/ Heat flow
Sample yı ~ x x (+ = (22,, nla)
Sample Fx+1 Wi ~ π XIX (-1vs) & x cxp exp (-I--wl")
// Calls to RGO
return N
Theorem
Suppose xx x cXp satisfies Assumption 1. Let X, be the solution of the Langevin diffusion, and Mr == (Xi). Then, for any 5 > 0,
TV(T* pi) 2 Cr == (1+5) (Cs(uo) + kst)
mx(1+))
where Kig == 1V 2n V 12(1+5)
(d+v2]d' Co(po) 2t02
TI( /30l) with y nos v2) and
2tvy
Cryang a constant depending only on 1n and 1/2
If we assume [Xol S (Vvd) for simplicity, then by choosing 8
2lu
(P2 (22-Ps)lnd we obtain v2 Int
In
TV( (u4) 2 S2
12
Thus, LD requires at least P2y, (d (d -ー (1/2)2/02) to reach & error in total variation. While this bound may be small in high dimensions when 1/2 V1, for the canonical model of Cauchy-type potentials with V/2 = 111 = 1s, it will be independent of dimension, as stated by the following result. Note that Assumption I can also cover general scaling by replacing |x]] with c|x/ for some constant e, which would introduce a multiplicative factor of 1/c² for the lower bound on T. This is expected as e.g.. mixing to the Gibbs potential e² [a|= can be faster than mixing to |x|] by factor of 1/c².
Corollary 1. Consider the generalized Cauchy density TH x exp(-Va) where Vy, is as in (1). Let X, be the solution of the Langevin diffusion, and pt = Law(X.). For simplicity, assume the initialization satisfies [Xol S O(vd). Then, achieving (V : S requires T2 (ty(s=
The above lower bound implies that LD is a low-accuracy "sampler" for this target density in the sense that it depends polynomially on 1/e; this dependence gets worse with smaller v as the tails get heavier. It is worth highlighting the gap between the upper bound of [MHFH* 23, Corollary 8), which is (11/4//), and the lower bound in Corollary 1.
Gaussian proximal sampler. In the remainder of this section, we prove that the Gaussian proximal sampler, described in Algorithm 1, also suffers from poly(1/e) rate when the target density is heavy-tailed. each iteration of Algorithm 1, the first step involves sampling a standard Gaussian random variable y centered at the current iterate I& with variance n/; this is one-step isotropic Brownian random walk. Alternatively, since the Fokker- Planck equation of the standard Brownian motion is the classical heat equation, this step could also be interpreted as an exact simulation of the heat flow; see, for example, [CG03] and [Wib18]. Specifically, the density of yu is the solution to the heat flow at time 1) with the initial condition being the density of 2g. The second step is called the restricted Gaussian oracle (RGO) as coined by [LST21b]; under which (Ix, yk) is a reversible Markov chain whose stationary density has z-marginal x
Assumption 2. For some 1/2 2 112 2 0, the target x (z) x
with V : Rd + IR satisfies
(d + 2
(d+ 12)aal
(d + v2)²
VX E Rdd
1 |+/2| S (c. VV()))
[VV()) < + |||
AV S
1 + |
The first condition above also appears in Assumption 1 and the second condition implies the upper bound of Assumption 1; thus, the above assumption stronger. Note that the generalized Cauchy measure (1) satisfies this assumption with 1/2 = v. Under Assumption 2, we state the following lower bound on the Gaussian proximal sampler and defer its proof to Appendix A.
Theorem 2. Suppose x exp(-V) satisfies Assumption 2. Let DR denote the 1 iterate of the Gaussian proximal sampler (Algorithm 1) with step n and let pi == =Lww(x Then, for any > O,
TV( x .Px xx 2 Cn.ed " (1+6) (Co(po) + koTk)
v2(1+8) 2
where Kg. (p()) and Cm,m are defined in Theorem 1.

---

Above, assuming [ool S ((vd) with the same choice of á as in Theorem I yields TV( pk 2 Pei zd (ke)) - ). Note that in order for the RGO step to be efficiently implementable, we need to have sufficiently small r7. The state-of-the thrtt-rrttttttee implementation of RGO requires a step size of order 17 (L/ (2) when V has L-Lipschitz gradients [FYC23]. With this choice of step size, the above lower bound requires least N Pun ,vz (Ld' (adl/2(M1-aaal))) (1//)) (1/)) iterations. The assumptions in Theorem 2 once again cover the canonical examples of generalized Cauchy densities, where we have L ==dd d p, which simplifies the lower bound as follows.
Corollary 2. Consider the generalized Cauchy density मे exp(-Vo) where V2, is as in (I). Let vy denote the hthh iterate of the Gaussian proximal sampler, and define p == Law(ar) and choose the step size ( ( (L. we assume (Xo S (((v)) simplicity, then achieving TV(Tİ, .xX)= S requires N 2 Zh (ddd (d) iterations.
We emphasize that the above lower bound is of order poly(1/E) as advertised. Thus, the RGO-based proximal sampler can only yield a low-accuracy guarantee in this setting.
3 Stable Proximal Sampler and the Restricted o-Stable Oracle
Having characterized the limitations of Gaussian oracles for heavy-tailed sampling, thereby answering Q1, in what follows, we will focus on Q2 and construct proximal samplers based on the a-stable oracle, and prove that they achieve high-accuracy guarantees when sampling from heavy-tailed targets. First, we provide a basic overview of c-stable processes and fractional heat flows.
Isotropic a-stable process. For / 2 0, let x(()) be the isotropic stable Lévy process in Rdd starting from x E Rd, with the index of stability E (0, 2]. defined uniquely via its characteristic function
(l -x) = e -=((s"" When a = 2, x is a scaled Brownian motion, and when 0 < a < 2,
t becomes pure Lévy jump process in Rd. The transition density of x(a) then given by
/ cxp((dlef))) i(6.)) (2) gd
(ta) = p. (y
with
(0) (v) - (2
where the second equation above is the inverse Fourier transform of the characteristic function, thus returns the density. The transition kernel and the density in (2) have closed-form expressions for the special cases = 2. In particular, when a 1, p, reduces
Cauchy density with degrees of freedom V/ = 1, i.e. Pi (1) (v) x (lvl2 + - We finally note that the isotropic stable Lévy process X!" displays self-similarity like the Brownian motion; the processes x and a x(() have the same distribution. This property is crucial in the development of the stable proximal sampler.
Fractional heat flow. The equation 0,u(t, - (- x) with the condition u(0, x) wo(x) is an extension of the classical heat flow, and is referred to as the fractional heat flow. Here, (-A))/2 is the fractional Laplacian operator with (0,2), 2]. which is the infinitesimal generator of the isotropic stable process. For a = 2, it reduces to the standard Laplacian operator A.
Stable proximal sampler. Let (2. y) be a joint density such that ((r,)) x T (x)pp") (17; x. y). where x is the target and pla) xr y) the transition density of the o-stable process, introduced in (2). It is easy to verify that (i) the X X-marginal of is π (ii) the conditional density of Y given X is
(a) vIx (-Iz) = (m)) (17 -).. (iii) the Y --marginal is x² 7 Py i.c. x is obtained by evolving xx along the a-fractional heat flow for time 7, and (iv) the conditional density of X given Y is x XIX (:19) x π ())p(o (7: v). Based on these, we introduce the following stable oracle.
Definition 1 (Restricted atStaale Oracle). Given y E Rd, an oracle that outputs random vector distributed according to X (-1y), is called the Restricted a-Stable Oracle (RaSO).
Note that when a 2, the RaSO reduces to the RGO of [LST21b]. The Stable Proximal Sampler (Algorithm 2) with parameter a is initialized at a point To Rdd and performs Gibbs sampling on the joint density л. In each iteration, the first step involves sampling an isotropic a-stable random vector ys centered at the current iterate Vg, which a one-step isotropic u-stable random walk. This could also be interpreted as an exact simulation of the fractional heat flow. Indeed, due to the relation between the fractional heat flow and the isotropic stable process, the density of yk is exactly the solution to the a- fractiional heat flow at time 7) with the initial condition being the density of æk-
5

---

Algorithm 2 Stable Proximal Sampler with parameter a
Input: Sample 20, step 7j and a (0,
for k = 0, 1, ... ,
// Gibbs sampler // Fractional heat flow
Sample yı x > (xx) =
Sample Z8+1 M/ xx1Y (-1yx) x (.)pla) (m
// Calls to Raso
return N
When a = 2, the first step reduces to an isotropic Brownian random walk and simulation of the classical heat flow. The second step calls the RaSO at the point yk-
3.1 Convergence guarantees
We next provide convergence guarantees for the stable proximal sampler in x >²-divergence assuming access the RaSO. Similar results for practical implementation are presented in Section 3.2. To proceed, we introduce the fractional Poincaré inequality, first introduced in [WW15] to characterize class of heavy-tailed densities including the canonical Cauchy class.
Definition 2 (Fractional Poincaré Inequality). For & (0, 2), probability density μs satisfies I-fractional Poincaré inequality (FPI) if there exists a positive constant Crei()) such that for any
function o : F > R the domain of Ey we have
Var S CFPRCO) ((0) (6). (o).
(FPI)
where e is a non-local Dirichlet form associated with μ defined as
(6)) = cd.6 []
(Ø(x) o(u))² (d40) dxu(w)dy
('T((d+0)/2) with ca.a 7//2[[(-0/2)
(att)
Remark 2. FPI is weaker condition than Assumption 2. In fact, any density satisfying the first conditions in Assumption 2 satisfies 9-FPI for all < v2 [WW15, Theorem 1.1]. In Proposition we show that as 0 + 2 FPI becomes equivalent to the standard Poincaré inequality.
X.Y Y is the joint law of In the sequel, P denotes the law of Tı, PV denotes the law of yk. and Pk (Irk yk). We provide the following convergence guarantee under an FPI, proved in Appendix B.2. Theorem 3. Assume that xx satisfies the a-FPI with parameter Crpu,)) for E (0, For any step size rj > 0 and initial density p. the th iterate of Algorithm 2, with parameter a, satisfies
( x |ス*) S exp (-kn) (Crri(a) + +n) +1)= x² ).*)
As a consequence of Remark and Proposition 2, we recover the result in [CCSW22, Theorem 4], by letting + 2 While results in Theorem 3 are based on Algorithm 2 which requires exact calls to RaSO, the next result, proved Appendix B.3, shows that even with an inexact implementation of RaSO, the error accumulation is at most linear, and Algorithm 2 still converges quickly.
Proposition 1. Suppose the RaSO in Algorithm 2 is implemented inexactly, i.e. there exists a positive constant ETV such that TV(2 X (-lv). Px XY (-ly) ETV for all y Rd and k 1, where Pk is the density of the inexact RoSO sample conditioned on y. Let PX be the density of the output of the wtth step of Algorithm 2 with the inexact RaSO and pk be the density of the output of 1hhh step Algorithm 2 with the exact RaSO. Then, for all 2 O.
=X1Y (-ly)
TV P S TV :P KETV.
Further, if Pb po any K > Ko. we get TV xx) iferv SE/2K, where the constant Ko (1 CIP((o)) log (xN I )/²?) with Cre((a) being the a-FPI parameter of x
3.2 A practical implementation of RaSO In the sequel, we introduce practical implementation of RaSO when = 1. For this, we consider the case when the target density π x e satisfies the 1-FPI with parameter Cyr(1). more thorough implementation of RaSO for other values of a will be investigated in future work.
Assumption 3. There exist constants B, L > 0 such that for any minimizer x" E arg min V (μ)
and for all gd, V satisfies V(x) V (x*) ) < L2 x 13

---

Algorithm 3 RaSO Implementation for a = 1 via Rejection Sampling
Input: V. xx E arg V, 1) > 0. y ER.
while TRUE Generate (Z), Z2, u) ~ (V( @ (00, U[001 x y + +
|/ Rejection sampling
|/ Cauchy random vector
return x: if u S
// Accept-reject step
Algorithm 3 provides an exact implementation of RaSO for a = 1 via rejection sampling. Inputs to this algorithm are the intermediate points yı in the stable proximal sampler (Algorithm 2). Note that Algorithm requires a global minimizer of V, which is always assumed to exist, which guarantees that the acceptance probability is non-trivial. It generates proposals with density p (77; ..y and utilizes that p is a Cauchy density and Cauchy random vectors can be generated via ratios between Gaussian random vector and square-root of a x² random variable. Finally, the accept-reject step ensures that the output z has density π> (-ly) x e <-VY(()( " 8). This makes Algorithm 3 zeroth-order algorithm requiring only access to function evaluations of V. Under Assumption 3, by choosing small step-size, we can control the expected number of rejections in Algorithm 3. We now state the iteration complexity of our stable proximal sampler with this RaSO implementation in the following result, whose proof is provided in Appendix B.3.
Corollary 3. Assume V satiiffies Assumption 3. If we choose the step-size n O then Algorithm 3 implements the RoSO with a = 1, with the expected number of zeroth-order calls to V of order Fleep((.)) [lyx (). Further assume x satisfies 1-FPI with parameter CFeU1). Suppose we run Algorithm 2 with RoSO implemented for with a = 1 by Algorithm 3. Then, to return sample which is E-close in x" -divergence to the target, the expected number of iterations required by Algorithm 2 is
((FFp L log(x²(p)) \/x))
Note that the above result provides a high-accuracy guarantee for the implementable version of the stable proximal sampler (Algorithm 3) for class of heavy-tailed targets, overcoming the fundamental barrier established in Theorem 2 for the Gaussian proximal sampler (i.e., Algorithm 1). A numerical illustration of this improvement is provided in Appendix D by sampling from student-t distributions.
Remark 3. (1) Finding global minimizer of the potential V can be hard, which could be avoided if lower bound on the potential V is available; see Appendix B.3. (2) A trivial bound for Ejexp( }] exp(LMM for M =E,x [[X + x2p x ) |X [20] 1. Since our main focus is high vs low accuracy samplers, deriving sharper bound is beyond the scope of the current paper.
3.3 Illustrative examples
To illustrate our results, we now apply the proximal algorithms to sample from Cauchy densities and discuss the complexity of both the ideal sampler (Algorithm 2) in which we can choose any a E (0. 2) and the implementable version with a = 1 (Algorithm 3). For the ideal sampler, we can choose S V for any degrees of freedom v > O, and apply Theorem 3 since nr satisfies a a-FPI [WW15] 15..
Corollary 4. For any v > O, consider the generalized Cauchy target T. α exp(-V,) with V,, defined in (1). For the stable proximal sampler with parameter E (0, 2) and a S (i.e., Algorithm 2). suppose we set the step-size E (0, 1) and draw the initial sample from the standard Gaussian density. Then, the number of iterations required by Algorithm 2 to produce an e-accurate sample in <i-divergence is ((CFPI(a))) log(d/s) where CFPI(a) is the a-FPI parameter of Nv.
For the implementable sampler, since the parameter is fixed to be 1, whether suitable FPI is satisfied or not depends on the degrees of freedom v. Specifically, when v 2 1, 1-FPI is satisfied and Corollary 5 applies. When v E (0, 1), the other hand, 1-FPI is not satisfied. To tackle this issue, we prove convergence guarantees for the proximal sampler under a weak fractional Poincaré inequality; the next corollary, proved in Appendix B.4, summarizes these results.
Corollary 5. For the Cauchy target Ty & exp(-V.) where Vy is defined in (1), we consider Algorithm 2 with = 1, a standard Gaussian initialization, and RoSO implemented by Algorithm 3.
(1) When v 2 1, if we set the step-size O(d (d + +))a), the expected number iterations required by Algorithm 2 to oulput sample which is s-close in -diieergee to the target is of order O dCF (d + v)y log log(d/=)), where OFPIC)) is the 1-FPI parameter of nv.
7

---

(2) When E (0,1), if we set the step-size = = () the expected number of iterations required by Algorithm 2, to output sample which is E-close in x² X2-divergence to the larget is of order O( max {e² dddd -od--t--b+t where e is the positive constant given in (16). Here, O hides the polylog factors on d and 1/E.
The stable proximal sampler (Algorithm 2) is high accuracy sampler for the class of generalized Cauchy targets, long as a S P, meaning that achieves log(L/e) iteration complexity. The improvement from poly(1/e) /e) to log(1/E) separates the stable proximal sampler and the Gaussian proximal sampler in the task of heavy-tailed sampling. When we use the rejection-sampee mentation with parameter a = 1 (Algorithm 3), iteration complexity goes through a phase transition as the tails get heavier. When the generalized Cauchy density has a finite mean (v > 1), we achieve a high-accuracy sampler with log(1/e) iteration complexity. However, without finite mean (i.e., E (0, 1)), the algorithm becomes a low-accuracy sampler with poly(1/2) complexity. Even this low-accuracy regime, the implementable stable proximal sampler outperforms the Gaussian one, as originally highlighted in Table 1. Last, we claim that the poly(1/E) complexity of Algorithms 2 and is not due to a loose analysis, we show voly(1/)) lower bounds in the following section.
imple-
3.4 Lower bounds for the stable proximal sampler
We now study lower bounds on the stable proximal sampler to sample from the class of target densities satisfying Assumption 2, which includes the generalized Cauchy target. Recall that Assumption implies the FPI used in Theorem 3. The result below, proved in Appendix C, complements Theorem 3, showing the impossibility of achieving log(1/E) rates for sufficiently large a.
Theorem 4. Suppose π x exp(-V) with V satisfying Assumption 2 and "2(d+rs) <a s.52. 2. Ler d+v:
In denote the ht iterate of Algorithm 2 with parameter and step size 1T, and let p = Law(xx).
Then for any E
(12(dt))) ..), and g(d, v1, v1, T) = v22 (T(d + v1) 12(d + v2)}. we have rdd+ )al.u,
d+t1
(B[(1 + 2= ml I +2))))))))))))))) - (ddwa))(ddd.....)))
TV ) 2 Curipaad
2
where Cripaa is a constant depending only on v1, 12, and m (0) is the 7th absolute moment of the a-stable random variable with density (a) defined in (2).
Remark 4. The parameter in Theorem 4 can be chosen arbitrarily close to a. Specifically, if we assume |Xol= I O(Vd), then with the choice of = [logllodd] d' log
log loglog(n we have
login 1)
TV(T* Px 2 Du where Ωt hides polylog(de (d/n) factors.
2
(d mla
(a) k +2,)) ((dtt))gddd
The 7hh absolute moment of the a-stable random variable depends on the choice of a and the dimension d. It is hard to find an explicit formula of m² in general. An explicit formula is only available in some special cases, such as a = 1, Specializing Theorem 4 for the generalized Cauchy potential (i.e.,
12) we obtain the following explicit result.
Corollary 6. Let a (0, 2]. Suppose nu x exp(-V.) where Vx(x) as in for some u E (0. or). Let (rx) be the output of Algorithm 2 with parameter a and step-size 1j > O, and p = Law (x6) for all l 2 Then for any T E (V,a),
TV nT) 2 Cr-rd (E[(1 _o13)²] + m(a)
VT
(0)
k2 T 2 n1a)
(o) is the Thhh absolute moment of the a-stable random variable with density pla) as in (2). where my
For the rejection sampling implementation in Algorithm 3, a = 1 and m = edd') ) for all 7 < 1 (see Appendix B.I). Notice that to implement the RaSO in the Stable proximal sampler efficiently, we need a sufficiently small step-size 17. When the target potential satisfies Assumption 3, i.c. V is 3-Hölder continuous with parameter L, we require " O(d 3 -ー ensure RoSO can be implemented with O(1) queries. Therefore, if we choose 1) = O 1 --- the minimum number of iterations need to get an E-error in TV is
2(T-v) (2+T) d2+7 ((2+T)
2r
2y
8

---

For the generalized Cauchy potential with E (0. we have 3 = v/4 and L = (d+ which leads to the following corollary.
Corollary 7. Suppose म x exp(-Vv) is the generalized Cauchy density with v E (0. 1). Let Is denote the k-th iterate of the stable proximal sampler with a = (Algorithm 3), and Pkc
x = Law (I*).
we choose the step size 1j O(L= - 1) where L d+v is the v/ 4-Höölerr constant Vf and as- T4ST/2
v
sume, for simplicity, |zo| S O(V)), then, TV , S E requires 2 Dur 21v E ((24)) for any (v, Further, by choosing max(v, 1 lu<(log(d/=)))
obtain
log(d/=)
P+8
2(1- 3v
N 2 B2 d 3v
in order for TV & PN SE.
The above result shows that when implementing the RaSO in Algorithm 2 with Algorithm 3, to sample from generalized Cauchy targets with v E (0, 1), we can at best have an iteration complexity of order (oly(1/E), matching the upper bounds in Corollary 5 up to certain factors.
4 Overview of Proof Techniques
Lower bounds. We build on the techniques developed in [Hail0], Let fe denotes the law of LD
along its trajectory. To proceed, we need some G RR R for which we can upper bound μ (G) =
I Gdju, and some f: Rd IR that satisfies x xxxG 2 y) 2 (2) for all E R4. After finding the candidates G and f. Lemma 1 in Appendix A guarantees TV(T* (Me) 2 SuPyER, f(v) - (G))//
This technique relies on choosing G such that has heavy tails under π x leading to a large fly). while having light tails along the trajectory, thus small H₂(G), By picking G = exp(xV) with x 2 1, one can immediately observe that x (G) = oo, thus indeed has heavy tails under x
To control fee (G) along the trajectory, one can use the generator of LD to bound (. Recall the generator of LD, (-D(-) ( (VV, V.). Therefore, with choice of G exp(x<V), controlling Oetue (G) requires bounding the first and second derivatives of V. To avoid making extra assumptions for V in the analysis of LD, we instead construct G based on a surrogate potential (xx) d+-22 In(1 + [ar which is an upper bound to the potential V. We then estimate based on 2
this surrogate potential in Lemma 2, and control the growth of (c(G) in Lemma 3. Combined with Lemma 1, this leads the proof of Theorem I, with the details provided in Appendix A.
For the Gaussian proximal sampler, bounding P (G) requires controlling the expectation of G along the forward and backward heat flow. For the particular choice of G = cxp(xVV), we show in Lemma 4 that the growth of Px (G) can be controlled only by considering a forward heat flow with the corresponding generator LHE = 1 A. Therefore, given additional estimates on the second derivatives of V, we bound the growth of p (G) in Lemma 5. Once this bound is achieved, we can invoke Lemma to finish the proof of Theorem 2.
Upper bounds. Our upper bound analysis builds on that by [CCSW22] in the specific ways discussed next. We consider the change in x² divergence when we apply the two operations to the law pk to the iterates and the target π (i) evolving the two densities along the ce-fractional heat flow for time 7 and (ii) applying the RaSO to the resulting densities. For the step (i), it is required to show that the solution along the fractional heat flow of the stable proximal sampler at any time, satisfies FPI. To show this, (a) the convolution property of the FPI is proved in Lemma 6, and (6) the FPI parameter for the stable process follows from [Cha04, Theorem 23]. In Proposition 3, it is then shown that the x2 divergence decays exponentially fast along the fractional heat flow under the assumption of FPI. The aforementioned results enable to prove the exponential decay of x² divergence along the fractional heat flow under FPI in Proposition 3. To deal with the step (ii) above, we use the data processing inequality; see Proposition 3. These two steps together, enable us derive the stated upper bounds for the stable proximal sampler.
Discussion
We showed the limitations of Gaussian proximal samplers for high-accurccy heavy-tailed sampling, and proposed and analyzed stable proximal samplers, establishing that they are indeed high-accuracy algorithms. We now list few important limitations and problems for future research: (i) It is important to develop efficiently implementable versions of the stable proximal sampler for all values of E (0,2) and characterize their complexity in terms of problem parameters, (ii) Gaussian

---

proximal samplers can be interpreted as a proximal point method for approximating the entropic regularized Wasserstein gradient flow of the KL objective [CCSW22]. This leads to the question. can we provide variational intepreration of the stable proximal sampler? A potential approach is to leverage the results by [Erb14] on gradient flow interpretation of jump processes corresponding to the fractional heat equation, (iii) It is possible to use non-standard Itó process in the proximal sampler (in place of the a-stable diffusion); see, for example, [EMS18, 18, LWME11, HFBE244. With this modification, it is interesting to examine the rates under weighted Poincaré inequalities that also characterize beavy-tailed densities. There are two difficulties to overcome here: (a) How to generate an exact non-standard Itô process? (b) How to implement the corresponding Restricted non-standard Gaussian Oracle, which requires the zeroth order information of the transition density of the Itô process? In certain cases, non standard Itô diffusion can be interpreted Brownian motion an emhedded sub-manifold; thus, the approach in (GIL.*23) might be useful.
Acknowledgements
KB was supported in part by NSF grants DMS DMS-2053918 and DMS-20 MMN-2241426.
References
[ALPW22]
Christophe Andrieu, Anthony Lee, Sam Power, and Andi Q Wang, Comparison of Markov chains via weak Poincaré inequalities with application to mseudo-marginal MCMC, The Annals of Statistics 50 (2022), no. 6, 3592-3618.
[ALPW23]
Weak Poincaré Inequalities for Markov chains: Theory and Applications, arviv preprint arXiv:2312.1 11666992.11699 (2023).
[App09]
David Applebaum, Lévy processes and stochastic calculus, Cambridge university press, 2009.
[BCE+22] Krishnakumar Balasubramanian, Sinho Chewi, Murat A Erdogdu, Adil Salim, and Shunshi Zhang, Towards a theory of non-log-concave sampling: First-order station- arity guarantees for Langevin Monte Carlo, Conference on Learning Theory, PMLR, 2022, pp. 2896-2923.
[BHJ08]
Krzysztof Bogdan, Wolfhard Hansen, and Tomasz Jakubowski, Time-dependent Schrödinger perturbations of transition densities, Studia Mathematica 189 (2008), no. 3, 235-254.
[BRZ19]
Joris Bierkens, Gareth O Roberts, and Pierre-André Zitt, Ergodicity of the zigzag process, The Annals of Applied Probability 29 (2019), no. 4, 2366-2301.
[BZ17]
Maria-Florina F Balcan and Hongyang Zhang, Sample and computationally efficient learning algorithms under s-concave distributions, Advances in Neural Information Processing Systems 30 (2017).
[CBL22] Niladri S Chatterji, Peter L Bartlett, and Philip M Long, Oracle lower bounds for stochastic gradient sampling algorithms, Bernoulli 28 (2022), no. 1074-1092.
(CCBJ18) Xiang Cheng, Niladri Chatterji, Peter L Bartlett, and Michael Jordan, Underdamped Langevin MCMC: A non-asymplotic analysis, Conference on learning theory, PMLR, 2018. pp. 300-323.
[CCSW22] Yongxin Chen, Sinho Chewi, Adil Salim, and Andre Wibisono, Improved analysis for a proximal algorithm for sampling, Conference on Learning Theory, PMLR, 2022, pp. 2984-3014.
[CDV09]
Karthekeyan Chandrasckaran, Amit Deshpande, and Santosh Vempala, Sampling s-concave functions: The limit of convexity based isoperimetry, International Work- shop Approximation Algorithms for Combinatorial Optimization, Springer, 2009, pp. 420-433.
[CG03]
Eric A Carlen and Wilfrid Gangbo, Constrained steepest descent in the 2- Wasserstein metric, Annals of mathematics (2003), 807-846.
10

---

[CG23] Yuansi Chen and Khashayar Gatmiry, A Simple Proof of the Mixing of Metropolis- Adjusted Langevin Algoritim under Smoothness and Isoperimetry, arXiv preprint arXiv:2304.04095 (2023).
[CGL+22] Sinho Chewi, Patrik R Gerber, Chen Lu, Thibaut Le Gouic, and Philippe Rigollet, The query complexity of sampling from strongly log-concave distributions in one dimension, Proceedings of Thirty Fifth Conference Learning Theory, vol. 178, PMLR, 2022,
pp. 2041-2059.
[CGLL22] Sinho Chewi, Patrik Gerber, Holden Lee, and Chen Lu, Fisher information lower bounds for sampling, arXiv preprint arXiv:2210.02482 (2022).
[Cha04] Djalil Chafai, Entropies, convexity, and functional inequalities, on P-entropies and (--obolev inqqualities, Journal of Mathematics of Kyoto University 44 (2004), no. 225-363.
[CLA*21] Sinho Chewi, Chen Lu, Kwangjun Ahn, Xiang Cheng, Thibaut Le Gouic, and Philippe Rigollet, Optimal dimension dependence of the Metropolis-Adde Adijssted Langevin Algo- rithm, Conference Learning Theory, PMLR, 2021, pp. 1260-1300
[CLW23]
Yu Cao, Jianfeng Lu, and Lihan Wang, On explicit Læ-convergence rate estimate for underdamped Langevin dynamics, Archive for Rational Mechanics and Analysis 247 (2023), no. 5, 90.
[DBCD19] George Deligiannidis, Alexandre Bouchard-Cöre and Arnaud Doucet, Exponential ergodicity of the Bouncy Particle Sampler, Annals of Statistics 47 (2019),
[DCWY19] Raaz Dwivedi, Yuansi Chen, Martin Wainwright, and Bin Yu, Log-concave sampling: Metropolis-Hlastine algorithms are fast, Journal of Machine Learning Research 20 (2019), no. 183, 1-42.
[DGM20]
Alain Durmus, Arnaud Guillin, and Pierre Monmarché, Geometric ergodicity of the Bouncy Particle Sampler, Annals of applied probability 30 (2020), no. 5, 2069-2098.
[DKT220]
Tlaas Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis, Learning halfspaces with Massart noise under structured distributions, Conference Learning Theory, PMLR, 2020, pp. 1486-1513.
[DM17)
Alain Durmus and Éric Moulines, Nonasymptotic convergence analysis for the adjusted Langevin algorithm, The Annals of Applied Probability 27 (2017), no. 3, 1551-1587 (en).
[DRD20] Arnak Dalalyan and Lionel Riou-Durand, On sampling from a log-concave density using kinetic Langevin diffusions, Bernoulli 26 (2020), no. 3, 1956-1988.
[EGZ19] Andreas Eberle, Arnaud Guillin, and Raphael Zimmer, Couplings and quantitative contraction rates for Langevin dynamics, The Annals of Probability 47 (2019), no. 4, 1982-2010.
[EH21]
Murat A Erdogdu and Rasa Hosseinzadeh, On the convergence of Langevin Monte Carlo: The interplay between tail growth and smoothness, Conference on Learning Theory, PMLR, 2021, pp. 1776-1822.
[EHZ22]
Murat A Erdogdu, Rasa Hosseinzadeh, and Shunshi Zhang, Convergence of Langevin Monte Carlo in chi-squared and Rényí divergence, International Conference on Artifi- cial Intelligence and Statistics, PMLR, 2022, pp. 8151-8175.
[EMS18]
Murat A Erdogdu, Lester Mackey, and Ohad Shamir, Global non-convex optimization with discretized diffusions, Advances in Neural Information Processing Systems 31 (2018).
[Erb14]
Matthias Erbar, Gradient flows of the entropy for jump processes, Annales de I'IHP Probabilités et statistiques, vol. 50, 2014, pp. 920-945.

---

[FYC23]
Jiaojiao Fan, Bo Yuan, and Yongxin Chen, Improved dimension dependence of proximal algorithm for sampling, arXiv preprint arXiv:2302.10081 (2023).
[GB09]
Alan Genz and Frank Bretz, Computation of multivariate normal and t-probabilities, vol. 195, Springer Science & Business Media, 2009.
[GBH04]
Alan Genz, Frank Bretz, and Yosef Hochberg, Approximations to multivariate inte- grals with application to multiple comparison procedures, Recent Developments in Multiple Comparison Procedures, Institute of Mathematical Statistics, 2004, pp. 24-32.
[GJPS08]
Andrew Gelman, Aleks Jakulin, Maria Grazia Pittau, and Yu-Sung Su, A weakly informative default prior distribution for logistic and other regression models, The annals of applied statistics (2008), no. 4, 1360-1383.
[GLL220]
Rong Ge, Holden Lee, and Jianfeng Lu, Estimating normalizing constants for log- concave distributions: Algorithms and lower bounds, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020, pp. 579-586.
[GLL+*33] Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, and Kevin Tian, Algorithmic aspects of the Log-Lap transform and non-Euclidean proximal sampler, arXiv preprint arXiv:2302.06085 (2023).
[GLM18] Joyee Ghosh, Yingbo Li, and Robin Mitra, On the use of Cauchy prior distributions for Bayesian logistic regression, Bayesian Analysis 13 (2018), no. 2, 359-383.
[Hai10]
Martin Hairer, Convergence of Markov processes, Lecture notes (2010).
[HBE20]
Ye He, Krishnakumar Balasubramanian, and Murat A Erdogdu, On the ergodicity, bias and asymptotic normality of randomized midpoint sampling method, Advances in Neural Information Processing Systems 33 (2020), 7366-7376.
[HBE24]
An analysis Transformed Unadjusted Langevin Algorithm for Heavy-tailed Sampling, IEEE Transactions on Information Theory (2024).
[HFBE24]
Ye He, Tyler Farghly, Krishnakumar Balasubramanian, and Murat A Erdogdu, Mean- square analysis of discretized Itô diffusions for heavy-tailed sampling, Journal of Machine Learning Research (to appear) (2024).
[HMW21]
Lu-Jing Huang, Mateusz B Majka, and Jian Wang, Approximation of heavy-tailed distributions via stable-driven SDEs, Bernoulli 27 (2021), no. 3, 2040-2068.
[JG12]
Leif T Johnson and Charles J Geyer, Variable transformation to obtain geometric ergodicity the Random-Wand Walk Metropolis algorithm, The Annals of Statistics 40 (2012), no. 6, 3050-3076.
[JR07]
Søren Jarner and Gareth Roberts, Convergence of heavy-tailed Monte Carlo Markov Chain algorithms, Scandinavian Journal of Statistics 34 (2007), no. 4, 781-815.
[Kam18]
Kengo Kamatani, Efficient strategy for the Markov chain Monte Carlo in high- dimension with heavy-tailed target probability distribution, Bernoulli 24 (2018), no. 4B, 3711-3750.
[KN04]
Samuel Kotz and Saralees Nadarajah, Multivariate t-distributions and their applica- tions, Cambridge University Press, 2004.
[Kwa17]
Mateusz Kwašnicki, Ten equivalent definitions of the fractional Laplace operator, Fractional Calculus and Applied Analysis 20 (2017), no. 7-51.
[LST20]
Yin Tat Lee, Ruoqi Shen, and Kevin Tian, Logsmooth gradient concentration and tighter runtimes for Metropolized Hamiltonian Monte Carlo, Conference on learning theory, PMLR, 2020, pp. 2565-2597.
[ISTT21a]
Lower bounds on Metropolized sampling methods for well-conditioned distri- butions, Advances in Neural Information Processing Systems 34 (2021), 18812-18824.
12

---

[LST2Ib]
Structured logconcave sampling with a Restricted Gaussian Oracle, Confer- ence on Learning Theory, PMLR, 2021, pp. 2993-3050.
[LWME19]
Xuechen Li, Yi Wu, Lester Mackey, and Murat Erdogdu, Stochastic Runge-King Kutta accelerates Langevin Monte Carlo and beyond, Advances in neural information pro- cessing systems 32 (2019).
[LZT22] Ruilin Li, Hongyuan Zha, and Molei Tao, Sqri(d) Dimension Dependence of Langevin Monte Carlo, The International Conference on Learning Representations, 2022.
[MFWB22]
Wenlong Mou, Nicolas Flammarion, Martin J Wainwright, and Peter L Bartlett, Im- proved bounds for discretization of Langevin diffusions: Near-optimal rates without convexity, Bernoulli 28 (2022), no. 3, 1577-1601.
[MHFH + 23] Alireza Mousavi-Hosseini Tyler K. Farghly, Ye He, Krishna Balasubramanian, and Murat A. Erdogdu, Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincaré Inequality, Proceedings of Thirty Sixth Conference Learning Theory, vol. 195, 2023, pp. 1-35.
[No120]
John P Nolan, Univariate stable distributions, Springer, 2020.
[N$R19]
Than Huy Nguyen, Umut Şimşekli, and Gaël Richard, Non-asymptotic analysis of Frac- tional Langevin Monte Carlo for non-convex optimization, International Conference Machine Learning, 2019, pp. 48 4810-4819.
[PBEM23]
Mathicu Le Provost, Ricardo Baptista, Jeff D Eldredge, and Youssef Marzouk, An adaptive ensemble filter for heavy-tailed distributions: Tuning-free inflation and local- ization, arXiv preprint arXiv:2310.08741 (2023).
[QM16]
Di Qi and Andrew J Majda, Predicting fat-tailed intermittent probability distributions in passive scalar turbulence with imperfect models through empirical information theory, Communications in Mathematical Sciences 14 (2016), no. 6, 1687-1722.
[RRT17]
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky, Non-convex learning via stochastic gradient Langevin dynamics: A nonasymptotic analysis, Conference on Learning Theory, PMLR, 2017, pp. 1674-1703.
[SL19]
Ruoqi Shen and Yin Tat Lee, The randomized midpoint method for log-concave sampling, Advances in Neural Information Processing Systems 32 (2019).
[SP15]
Prashant D Sardeshmukh and Cécile Penland, Understanding the distinctively skewed and heavy tailed character of atmospheric and oceanic probability distributions, Chaos: An Interdisciplinary Journal of Nonlinear Science 25 (2015), no. 3.
I$ZTG20)
Umut Şimşekli, Lingjiong Zhu, Yee Whye Teh, and Mert Gurbuzbalaban, Fractional underdamped Langevin dynamics: Retargeting SGD with momentum under heavy- tailed gradient noise, International Conference on Machine Learning, 2020, pp. 8970- 8980.
[Wib18] Andre Wibisono, Sampling as optimization in the space of measures: The Langevin dynamics as composite optimization problem, Conference Learning Theory, PMLR, 2018, pp. 2093-3027.
[WSC22a] Keru Wu. Scott Schmidler, and Yuansi Chen, Minimax mixing time of the Metropolis- adjusted Langevin algorithu for log-concave sampling, The Journal of Machine Learning Research 23 (2022), no. 1, 12348-12410.
[WSC22b)
Minimax Mixing Time of the Metropolis-Adjustel Langevin Algorithm for Cog-Concave Sampling, Journal of Machine learning Research 23 (2022), no. 270, 1-63.
[WW15]
Feng-Ye Yu Wang and Jian Wang, Functional inequalities for stable-like Dirichlet forms, Journal of Theoretical Probability 28 (2015), no. 2, 423-448.
13

---

[YLR22]
Jun Yang, Krzysztof Latuszyúski, and Gareth Roberts, Stereographic Markov Chain Monte Carlo, arXiv preprint arXiv:2205.12112 (2022).
[ZZ23]
Xiaolong Zhang and Xicheng Zhang, Ergodicity of supercritical SDEs driven by o-stable processes and heavy-tailed sampling, Bernoulli 29 (2023), no. 3, 1933-1958.
14

---

A Lower Bound Proofs for the Langevin Diffusion and the Gaussian Proximal Sampler
While research upper bounds of sampling algorithmss' complexity has advanced considerably, the exploration of lower bounds is still nascent. [2] explored the query complexity of sampling from strongly log-concave distributions in one-dimensional settings. [LZT222] established lower bounds for LMC in sampling from strongly log-concaye distributions. [CBL22] presented lower bounds for sampling from strongly log log-concave distributions with noisy gradients. [GLL20] focused on lower bounds for estimating normalizing constants of log-concave densities. Contributions by [LST21a] and [WSC22b] provide lower bounds in the metropolized algorithm category, including Langevin and Hamiltonian Monte Carlo, in strongly log-concave contexts. Finally, [CGLL22] contributed lower bounds in Fisher information for non-log-concave sampling. In what follows, we take a different approach and rely on the arguments developed in [Hail0].
We begin by stating the following result which drives our lower bound strategy.
Lemma ([Hail0 10, Theorem 5.1]). Suppose y and are probability measures R. Consider some G: Rd + R2 and f: IR+ + R4 satisfying p(G Z y) 2 fly) for all E R4. Then,
TV(,,)) 2 sup f(y) f Gdv yER+
y
In particular, suppose Id f R4 y uf(y) E RR is a bijection, then
TV(, 2 { f)r (2m))
for any m 2 Gdv.
Proof. By the definition of total variation and Markov's inequality, for any y >
TV v) 2 (G 2 y) v(G 2 v) 2 f(y) [ Gdv
2/
When Id f is invertible, choosing y result.
(Id f) (2m) implies yf(y) 2m and yields the desired
To apply Lemma when the target density satisfies Assumption we need establish tail lower bounds for this density, which we do so via the following lemma. In the following, let wa = denote the volume of the unit d-ball.
4//2
F([d+2]/2]
Lemma 2. Suppose x (xx) x exp(-V(x)) satisfies Assumption 1. Then, for all 0.
2de vi/d
(10) 2 R)
(d (2v (222)r//211 R R-2) (d+tg)/2 2 2
When focusing on dependence on and d, we obtain,
(10) 2 R) 2 Cv, d (2 1 + R (ddt)(d2)))/22
where Cr 21 21--1/2 ((pr))))))2))
Proof. Without loss of generality assume V(0)= = O. Via Assumption 1, we have the estimates for V.
V(x)= f' 1
d 222 In + |x(3)
(a, (V(x))) s (d+ v)
11=0 1 1 tt/
and similarly
V(x) d+ 11
In + |x(1))
15

---

Consequently, using the spherical coordinates,
x (|z)
R
1 2
(1+ [x|2) [=+)))))((dt)>>)1)
Z s12R
duid
(1 2d-
JrZR
dwid 1 + R
3) (
r p-2 dr
Z
r2
dwall + -R 2) -
R
Zd
Next, using the lower bound established on V and spherical coordinates, we obtain,
/ (1 (dtt))
Z
JRd
dwd ( (1 (d)ttt)))) dr dr
1 _
(o 00
111/2-1(1 2 -u)a/² u)d/2-11d du
2
ddudB(vr/2 /22/)
2
dwal /21/2
2T v1) v1)/2)
where B denotes the beta function. Plugging back into our tail lower bound, we obtain,
([d + /2)
(|a) 2 R)
(1 R R-2) - (d+tva/2 R= 12.
(dd2/2)I(d/2)
Moreover, by [MHFH*23, 23, Lemma 32] we have
['(d + 11)/2)
I((d+ + 2)/2)
2de w1/d d+v (d/2)ur/2
T(d/2)
d+h I((d+2)
which completes the proof.
Another element of Lemma is controlling the growth of (X)) throughout the process. The following lemma achieves such control under the Langevin diffusion.
Lemma Suppose (Xt)r20 is the solution to the Langevin diffusion starting at Xo with the corresponding potential ((x) satisfying Assumption 1. Let G(z) = exp(x((x)) where V(x) d+ In(1 + 2x) and k 2 dtvs V 1. Then,
2
x(d+v2)
GG))),) s (E(G(X.) R + 4k(d + v2)()
Proof. Recall the generator of the Langevin diffusion 2(.) -VVVV, V.). Then, dE(G(X.)] B[CG(X.))
dt
KI [H/VV AF (VV, (V) G
s RE [N/VV| AF) 6
(Assumption 1)
G(X,)
< 2d² "
1+ |2
2k + 2R
(((.)) k(d+2))
< 2x v2) E()(()))
x(d+22)
(Jensen's Inequality).
Integrating the above inequality completes the proof.
16

---

With the above lemmas in hand, we are ready to present the proof of Theorem 1.
Proof of Theorem 1. To apply Lemma we choose G(z) exp(xx((x)) where ((x) - In(1
lx())) with K 2 1
2 By Lemma 2 we have
2to2"
x (G 2 (1x) 2 yrlatra)) 2 Cnddr (1+ y -(dtua)/2
on
ynlatos)
Moreover, define
aldtt22
g(t) (9(0))atie) अकंंर + An(d + p2)t)
with g(0) = E[G(X.)]. Then by Lemma 3 we have B[G(())) S g((( and we can invoke Lemma 1 to obtain
Cr,d1/2 (1 (1+ yoteiizs) -ddt2))/2
g(t)
TV(T* vb) 2 sup WER+
y yn
y
(-
(d ([dd
u2)y (2)ymui
g ((VV))
2 sup Cv, 121 cxp exp yER+
y ynterez
2
where we used the fact that 1 + + S et for all a E R and g(() is non-decreasing Choose
y' = =C C2 g(t V()
d21/2
for a sufficiently large constant C2 2 1. For simplicity, let
g(t) = g(t V 1) ()
4x(d + v2)
and notice that Using the fact that
((dev)) a(d402)-11 x(d402)-02 (4x(1 + /2/d)g(t)
5ー = Ch mn
(3)
2 x(d) nld v2)
V² 2 (41s)
Neldtugl-12 v- d
x(d+r2)-
we have
(-
1 1//2/d d ) ee 12 mattonn
g(t (
TV( pe) 2 C₁ exp
8K
y²
1(tV
2 12 m(a
11"
where Ey.oo Cuger 1trg/d
By plugging in the value of y from (3), we obtain,
TV(x* (e)
(Cmin Cerin mediia) Ch
{a"" " (2x(1 v2/d)(()) T (((+tg)--
Thus for sufficiently large Dg there exists Ch such that
TV 14:) 2 Ch (d (4x(1 + v/d) 1+ uid+
Choosing according to the statement of the theorem completes the proof.
In order to prove similar theorem for the Gaussian proximal sampler, we control the growth of [[G((x)) for the iterates of the proximal sampler via the following lemmas.
17

---

Lemma 4. Suppose (ax, Mk)s are the iterates of the Gaussian proximal sampler with step size vj and target density x x exp(-V) for some V : RRd - TR. Lea G(x) = =ex(x=V(x)) with & 2 1. Then, for every k 0,
B[G(Z*+1) G + 2222)l
where N(0, Ia) is sampled independently from zs.
|=- Therefore, Proof. Recall that x XIX (xly) x exp (- (zz) 2nj
exp ((1s - 1))(()) (w- yu
E[G((++11 yxk =yy Cyu
2n
dx.
(2
Ccn B[G + (1121111111 13
where ~ No0, Ia). Furthermore,
Cya = (2Th)a/2 / exp ( -V(x)
1x yx 1
dx
20j
-V(G(yk -xTzz) yx)-
Therefore,
[[G((++1) Vkll
E[G(uk v1211 2-11/ 1/r Vkl
E[G(yk + /1121) ykl
G[ vTjzz) yul "xl'"//=E(G(u/ + vTzz)) 1vd
(Jensen's Inequality)
= G + /nza) yk].
Recall yk 5& M22 where 22 N(0, Ta) is independent from zy. By the towering property of conditional expectation,
B[G(#++1) - B[G( + T v2222
= =E[G(r++ + v 2n=
where ('0 La) is independent from ZR. which completes the proof.
In order to provide a more refined control over [[G(=))], we need additional assumptions on V. In particular, when considering the generalized Cauchy density, arrive the following lemma.
Lemma 5. Suppose (It, Ms are the iterates of the Gaussian proximal sampler with step size n and target density x exp(-V) satisfies
(d + v2)l
and (v < (d + +222
VV(=)
1 1+ 1z|2
|x|2
for all x E Rd. Let G(æ))= exp(xV (x)) with K 2 1 1
2tt9 Then, for every k 2 0,
B[G((++1) ( B(G(z Rator + 4xnk(d + U2).
Proof. From Lemma 4, we have
[[G(+))) & E(G( + 22n=)),
where (N Ia) is independent from øg. Consider the Brownian motion starting at Øg. denoted
by Z, B, 2y where (B,) is standard Brownian motion in gd Notice that the generator for the
18

---

process dZ; = dB, is L = A. Therefore,
dE|G
(ZCG(Z))
(x)G V (1 AV)]
11 1 ((2,) (d 22)²
2
s 2x + v2) (E(()
x(d+ts)
$ 2x 2x (E) x(d+v2)
(Jensen's 's Inequality).
Integrating the above inequality yields
E[G(Z,) नकाي & [[) a(dios) + 2nc(d + 12)t.
The proof is complete by noticing that Zo J. and Z: + 22jz for t 2n.
Proof Theorem 2. Notice that the statements of Lemmas and 5 virtually the same by changing t to 2km.. Using this fact, the rest of the proof follows exactly the same as the proof of Theorem L
B Proofs for the Stable Proximal Sampler
B.1 Preliminaries
In this section, we introduce additional preliminaries on the isotropic a-stable process, the fractional Poincaré-type inequalities, the fractional Laplacian and the fractional heat flow.
The Lévy process is stochastic process that is stochastically continuous with independent and stationary increments. Due to the stochastic continuity, the Lévy processes have cådlàg trajectories, which allows jumps in the paths. A Lévy process Y, is uniquely determined by triple (b, A, v) through the following
formula: for all 2 0 and & E Rd.
E B[e [E..)) = exp (1i(()))) AT
/ /udiso
(e
1 i(S, v) 1 (MIs (w)) ) (4)
where b Rd is drift vector. A Rddd is the covariance matrix of the Brownian motion in the Lévy-Itô Itô decomposition Thereom 2.4.16] and v is the Lévy measure related to the jump parts in the Lévy-Itô decomposition.
The rotationally invariant(ssorropcc) stable process is a special case for the Levy process when A 0 and y is the measure given by
(dy) = Ca,a lyl (d+a),
Cd =
(5)
Based on the Lévy-Khhnchee formula (4), if we initialize the process at Rd its characteristic function is given by
E -(( x, E Rd, t 0.
(6)
The index of stability a E (0, 2] determines the tail- tail-heaviness of the densities: the smaller is a, the heavier the tail. The parameter t (6) measures the spread of X, around the center. When a the stable process pertains to the Brownian motion running with a time clock twice as fast as the standard one and hence it has continuous paths. When (0,2) the stable process paths contain discontinuities, which are often referred as jumps. At each fixed time, unlike the Brownian motion, the atabael process density only has finite -d -ommen for p < a, i.e.
+ 00
E to0) (0,2),
E Pl
m(()
+00
a (0,2).
19

---

When d = 1, the fractional absolute moment formula for mp can be derived explicitly, see [No120, Chapter 3.7]. When d > the explicit formula for my is only known some special cases. For example, when process is the self-similarity. By examining the characteristic functions, it is easy to verify that the isotropic a-stable process is self-similar with the Hurst index 1/a, i.c. ((a) and a'/"xx"" have the same distribution. Or equivalently, p. (x) =t (/ "p (t 2)) for all x E IR and t > 0.
(a)
1, mp (1)
(add+tp/aaj((ppp/p2))) for all 1. Another good property of c-stable [1d/2)
The fractional Laplacian operator in Id of order a is denoted by ((-A)o/2 for (0,2). It was introduced as non-local generalization of the Laplacian operator model various physical phenomenons, In [Kwal7], ten equivalent definitions of the fractional Laplacian operator are introduced. Here we recall two of them:
(a) Distributional definition: For all Schwartz functions e defined on R2, we have
(w))))y = | f(x) (-(-2) dr.
(b) Singular integral definition: For limit in the space L (PR)), ), p E [1, 00), we have
f(x + 2) f(x)
((-A)a/3(()) lim r-0+ ग x4/2 D1 RA,
dz.
|2|
where B, is the unit ball with radius r centered at the origin.
The fractional Laplacian can be understood as the infinitesimal generator of the stable Levy process.
More explicitly. the semigroup defined by the transition probability p(() in (2) has the infinitesimal generator -( (--A) (-A)a/2 )o/2, i.e. the density function pr. (a) satisfies the following equation in the sense of distribution, [BHJ08]:
0.p. (x)= (x).
(7) is usually referred as the a-fractional heat flow. When a = 2, 2. is the Laplacian operator and (7) becomes the heat flow.
Proposition 2 (From FPI to PI). When 2 + 2-, the 0-FPI reduces to the classical Poincaré inequality with Dirichlet form (y( = (Vox)) for any smooth bounded Φ : RR Rd.
Proof. It suffices to prove that 0 (6) converges to Ep( as 1 + 2- for any smooth function ø.
Recall the definition of e(()) (Ø):
el = Cd.il // (0(x) o(u))²
(x y (d+t) drp(r)dy with ca.9 n T/22[((0/2)
where C = O - 1) as 1 + 2 Now we rewrite the inside integral in E (Ø) and split the integral region into centered unit ball, denoted B1, and its complement:
/ (ő(x)) o(y))2
2040 1ot y|((+0) dx / (Ølv + +) -())) dz
J240
(x)(++0)
(0ly + 2) o(y))²
(Ólu + 2) -b(v)²
dz +
dz.
| (d+0)
|2| (d+
I1
12
For Iz, we have
4
11b0 dr #
lo
( dr
4 ||bb|1 dr
12 S 4 11
dz
R20B 1 2ed+0
T( 1)
UT 1
As result, the term in e(()) (6) that is induced by To satisfies
ca.9 { f Taply)dy S ca.9
4 11 d
0 as + 2
( +1)
20

---

For I1, we have when & > 1,
- S R.. 1z|at0
((iily); 2)12 dz
(0(y + 2) -)( - (Vo(v): 2) (Ø(v +2 o(u) + (Vo(u), 2)) dz
12|0+0
B1
/ 121- d2 de
S | 11 ((
B1
di 2
l I (R
0-- dr
r(
0
dx 2
|o (
(0 ()r 1)
where (| == supzer (x)) for 1, 2. As a result, the term in (6) that is induced by In satisfies
ca.9 |pc (12 (12-
2)) |2|0+0
b |1 (1d)) du
dz) dz)n(y)d S ca.0
0 as 0 + 2
11 + +1)
Therefore we have (0)
(0) + ca.0 SA SB.
(Vo()) 1z lad ply)dzdy as + 2 Last, we prove the
limit is equivalent to 28, (6). For i o j. we have
/ R,
0,0(y) (1)
where 2g. for all & * and 2j Zz. Therefore, JB. 0,0 (,0(1)0,)())
0. As result,
(Vo(y), 2)12 d+u
Σ Σi (0,00)))
dz
12|a+0
d
/
= Σ (0ro(1))
B1 |2|0+0 dz
1=1
12)
(2- 0)T +1)
and the proof follows from ca.0 (2- (2-0)((++1) - as + 2
B.2
x convergence under FPI
In this section, study the decaying property of x -dvverggee from p to x where pk is the law of Zg. In the following analysis, we denote Pk = Pk X.Y as the law of (Ik Us), P the law of yk. We will analyze the two steps in the stable proximal sampler separately.
Step 1. In the following proposition, we study the decay of x2 -divergeenc in step 1.
Proposition Assume that x satisfies the a-FPI with parameter CiP((a), then for each 2 0,
x2 xxx V < exp (-n (Crpi()) + n) =)) x² (px (
Proof of Proposition 3. For the simplicity of notations, will write pla) and ((()) p and pa respectively in this proof. Since x ~ pxx and y ~ p(n: x, we have
p (v) f g p(mzz v, v) (x)dx=
pe (x) z)dr ox pp))))
3d
21

---

Therefore, we can view P as Pk xx evolving along the following factional heat flow
e.p: = - Pc. That is if Ao Pk then Pa = Pk Similarly, since π xx Py. 1f A0 xxx then P. = For any E [0, n), define TH. = pr and p. pk Pt- The derivative of ø-divergence from P. to X Tt can be calculated as
d
me dx
dt
x
Rd
x 0'
ph
dTT
(Ospi
O.m
m5 A)
dx
A) TT - (-1) pp
dx
JRc
$ 0' )
(-A)
(- Φ5
me dr,
m
where in the second identity we used the distributional definition of the fractional Laplacian. Next according to the singular integral definition of fractional Laplacian, we have
f(x + 2) f(x)
(11 f(z) = Ca.o
lim m-5 BA
dz,
(8)
2 2/
where B. = (x BOCER::aa |2| s r) and Cd.a is given in (5). With (8), we have
dt 1 o1
d
Pi
x
xxx
la+e] (x+z)
(2))
e (m+s) o' (a++))
(x)
26 (2 (a+s)
lim { ca, m Jz JRAB
of (otz) (mts)
me (x)
mt (o+t))
da (x)da.
1z/d=a
When 6(r) (r 1)2. Sas ol fof mm de x² (px lor.") ) and we have
(ote) (a+s)
(w))
d (pt (T cáa lim Jea S di
r001 JRn.B.
dam
X dx = Exx
According to [Cha04, Theorem 23], p. satisfies a-FPI with parameter / for all (0, n]. Since xx also satisfies the a-FPI with parameter CPPic)), Lemma implics that x/"" = xx * satisfies the a-FPI with parameter Crn(a) for all t (0, n). Therefore we have
20 E dt
d
(xxxx x (Cren()) + +n) xp: 1m
Last, according to Gronwall's inequality we have
< 22 | exp (- (Crricc) + +m) x2 1=x)
Step 2. In this step, we study the decay of >i-diveree in step 2. building on the work by [CCSW22). According to the RaSO, we have p (x) = Ser π X (xlv)ek (v)dy. Also notice that xx (x) = Fea x (#lv)<> (v)dy. According to the data processing inequalities, x² divergence won't 't increase after step 2, i.e. x (pi
S (xX
Combining our results in Step 1 and Step 2, we prove Theorem 3.
Lemma Let #1 P2 be two probability densities satisfying the O-FPI with parameters C1, C2 respectively. Then μi #2 satisfies the 0-FPI with parameter C1 + Cz.
Proof of Lemma 6. Let X, be two independent random variables such that X ~ μr and Y ulz- Then X + ~ #1 P2. According to variance decomposition, we have for any function Φ.
Var us (Ø) = Var (ø(X + Y)) E Var (ø(X- + Y)J + Var (E [x(X + Y)
22

---

Since X ~ μi and μu satisfies the 9-FPI with parameter C1, we have
(Ø(x + Y + o(x + Y))
Var (+(X+ S Cicda
(2|(d+0) dzyu (z)da,
(2#0)
therefore we have
E [Var (6(X + [)[I
<CEca |||
(Ø(x + y + 2) ((x + y))²
(9)
d=ap (2) (x)d
(2|(d+0)
12#0}
Since Y ~ 22 and #2 satisfies the Ø-FPI with parameter C2, we have
Var (E (X
M[
(1 (1o(x + t)) =))1 o( + y) (z)dr)
S C2ndda
dzp2(1)dy
(2](2+0)
(6(x 10 + olx n))²
S Credd
in (x)drdppaw(y)
(10)
2 (d
where the last inequality follows from Jensen's 's inequality. Combining (9) and (10), we have
Var uuz (0) S Cicdaa II| (1x0)
(ő(x + y + 2) o(x + y))² (ed
12| (2((+)))
(x(x + y - + 8/)* ii (w)drrdzpaw)dd
+ C2aama
2 21(6+0)
(0(x + V 2) p(x v))² dayp (r))deuz(yddy
(C1 C2
|/| (=((++))
(x#0)
(Ø(u + 2) x(u))² (2)(0+0)
(C1 C2) Cdl.r
(=20)
dapi pa(u)du
= (C1 + C2) (p))))))))))
where the second inequality follows from Fatou's lemma.
B.3 Implementation of the Stable Proximal Sampler
In this section we discuss the implementation of the RaSO step our stable proximal sampler. We introduce an exact implementation of the RoSO step without optimizing the target potential and the proofs for Corollary 3 and Proposition 1.
Rejection sampling without optimization. Suppose uniform lower bound of the target potential known, i.c. there a constant CLow such that inf V(z) 2 CLow > -oo, RaSO at each step
can be implemented exactly via rejection sampler with proposals ēx+1 following pn the acceptance probability exp(- (x CLow). Then the expected number of rejections, N, satisfies
(ax) (. yke and
( c e-We)))tCmmmll p( (.F:,,,,)))) dxr and log N = -Law - log (f gdi
N
(n.
Without loss of generality, we assume xt = 0, which always hold if we translate the potential V by (00). Then we have
log N < CLow + { (V(x) v(0)) (a) ud)d
< - Crow + S( x + yk p/a (x))xx
T( d+1 r 1-8 L
< -CLow LEx [| + L LE x [1X29111
1)
r
d+1
23

---

where the second inequality follows from Assumption 3 and the last inequality follows from the proof of Corollary 3. With the above estimation, we can pick " @(G d 1- and the expected number of rejections satisfies log N OCCLow + LMM with M = [xx[|X|]] + x2 )xxx
Proof of Corollary 3. The expected number of iterations conditioned on yk in the rejection sampling
N= (1 e e-Voo))V x,;
and log -V(x*) - log
e (1
s / (V(x) - V(x*)) 1)p")) (a) (11, x., y))
12d
= [ (V(x + yk) - V(x ((=')),, (m) (z)dz.
Jac
WLOG, assume x² = 0. Since V satisfies Assumption 3, we have
log N < I
/
+
yk
(a) Py (x))dx
LT
(T(4+1) d+1
241
2
17
x + yx vel" (2(x=1 + =,12)- " dx
Rdd
π
R2
LT d+1
S Llyak 18
7
(|=]]
n?²)
dx
S L/val 8
LI
(1/
+ +11²)
d1l dx
JR
T( 2
(
1-8 L
1
d+1-1
Therefore, when 7 = ( 4), the expected number rejections N is order E[exp(L)pp yu 1s). Since x satisfies 1-FPI with parameter CFPIc)). according to [Cha04], Pt satisfies the 1-FPI with parameter for any E (0, Last it follows from Theorem 9 that for any v) O, to achieve E-accuracy x² divergence, we need to perform the stable proximal sampler K steps with
x2 (pp 1 1T²)
(2(0r )T))))
K > (Crpicyy" + log
O(FPpin) 1 log
Proof of Proposition I. For all l: 2 O, we have
TV I ( XX = /
(v)dy, / $ TV XXL (v)dy, / P (-1x) (y)dy) TV( XIX (-1))X (w)dv, / XXY (-18) TV $ E, (V (t. (.)) PxL
X Pkti (+1v)p (y)dy)
| ( (1w)) (v)dy)
<TV + TV x
where the last two inequalities follow from the data processing inequality. Therefore, TV ) KETV + TV vxx for all & > 1.
24

---

Next, the iteration complexity of Algorithm with an inexact RaSO can be obtained from Proposition Since P pb. according Pinsker's inequality, we have
TV ) S TV Pk + TVV x x*) - TV PE + (P 1/2
< kETv + (xxp(=kn(Crrmg + 1x2 (
For any ε > and any K satisfies
K2 (CpPl(a))) +1 1n (2x2 100
the RoSO can be implemented inexactly with erv S 2 the density of the K"hh iterate of Algorithm 2 is e-close to the target in the total variation distance, i.c. TV >
Se. G
B.4 Convergence under Weak Fractional Poincaré Inequality
Our main result for Algorithm in Theorem 3 is proved under the assumption the target satisfying a-FPI. Furthermore, for the eejection-sampiinn the parameter a is one has to check the a-FPI is satisfied or not, which depends on the degrees of freedom parameter of the generalized Cauchy desity. Specifically, when 2 1, 1-FPI is satisfied and hence have Corollary 5, part (i) based on Theorem 3. When v/ E (0, 1), 1-FPI is not satisfied and hence Theorem no longer applies.
based implementation of the RaSO in Algorithm 3, be In order to Theorem for the case of generalized Cauchy targets,
To tackle this issue, we now introduce a generalization of Theorem 3 to the case when the target satisfies a weak version of Fractioanl Poincaré inequality (wFPI) and provide convergence guarantees for the stable proximal sampler in 2 -2-iieereence.
Definition (weak Fractional Poincaré Inequality). For (0, a probability density μ satisfies 0-weak fractional Poincaré inequality if there exists decreasing function (wFer(0) R + R+
such that for any Φ IRd IR in the domain of E with p(ò) = 0, we have
plo²) Owrr (r) ) 1 Vr
(wFPI)
where c(d) is non-local Dirichlet form associated with μ defined
(o(z) 2(v))2 (6) : cd.0 /f (m)t)) xx y (d+0) dx
with
ca.0 n 7//2[[(-0/2)
The wFPI is satisfied by any probability density that is locally bounded, and is hence extremely general. Setting the parameter r 0, wFPI reduces to FPI with CFPI(O) = (WFF)(O)(
Theorem 5. Assume that x satisfies the a-wFPI with parameter BWFPI(a) (r) for some E (0, 2). oc, the kth iterate of
Then for any step size r > and initial condition pă such that Roc (pd | X) the stable proximal sampler with parameter (Algorithm 2) satisfies
x2 xx S exp - (Bwrrtt (r) + 1)) kn)>> | xxx)
+ Ar exp (SwFPr (r) + +n) (k: + 1)m) exp (2 |x ))x
The proof of Theorem 5 follows the same two-step analysis as it is introduced in the beginning of
Section B.2. The convergence property corresponding to Step 1 is stated in the following Proposition.
Proposition 4. Assume that x satisfies the a-wFPI with parameter BwErl(a) for some a E (0, 2),
for each l 2 0, 0,
x2X ( S exp ( (Swrri(a) (r) + m1) -) xn) (T=
(11)
+ 4r - 11--exp exp ( (BwrPIta) (r) + 17) -1n) exp (2 | (Tx
Proof of Proposition 4. In the stable proximal sampler with parameter a, we have P.z pk p.
(a) and xx = xxx_ pn Therefore view pxx and Y as x and x evolving along the fractional
25

---

heat flow by time yy respectively. For any / E [0, n)], define प.. = x xp(() and vZ = - xpp (a) We have
dt x (pt m
E
E 1).
According [Cha04, Theorem 231, Pi to Lemma 7, mz satisfies the a-wFPI with BwErI(a) (r) + 7, Therefore we get
(a) satisfies a-FPI with parameter 7j for all & (0, According
d dt x2 (pt m ) < (SwrrI(a) + 1)) -1 x (0t mt + (BIIP) (r) +r) 1 x 11.30
s (#WFPl(a) + "")="'""" x2 (pF
m
) + 4r 4r (SWFPI(a)) (r) n) exp (2 (pk Fz )))
where the last inequality follows from the definition of Renyi-divergence and the data processing inequality. Last, (11) follows from Gronwall's inequality.
Proof of Theorem 5. According to Proposition 4, the x² decaying property in step of the algorithm as follows,
( (T)) S exp (- (3wrrt(a) (r) + 11) x) I
+ 4r (1 exp ( (- (Bwrriça) (r) + 11) n) exp (2 (ok (TT)))
In step 2, we have pk+1 pk x and xx xx x Therefore according the data processing inequality, we get
x² ( S x² (xx )
s exp ( - (BWFPr(O) + 1)) 11) )
+ 4r exp (SWTPI (r) 17) 77)-'m) "n) exp (2 (pk (T))T²)))
S exp ((BWIr((a) 17) n) 1)) + ++4r(1 - cxp (- (SWFFi(a) (r) + n) '(k + 1)n) exp (2 (p)) (p="1 1)x));
(p (
where the last inequality follows from the data processing inequality. Last, apply the above iterative relation l times and we prove (11).
Lemma 7.
Let μr be a probability density on Hd satisfying the O-wFPI with parameter Bwrr( (r). Let μn be a probability density on Rdd satisfying the 9-FPI with parameter Crewoy Then μn μ12 satisfies 9-wFPI with parameter Swrru (T) + Creug)
Proof of Lemma 7. Let X, Y be two independent random variables such that X ~ #2 and Y ~ ui. According to variance decomposition, we have for any function & such that #1 * #2( O.
Var (Ø) = Var (ø(X + Y)) = E Var (ø(X- + +)JE)}+ Var (E [ø(X + Y)
Since X u2 and μ2 satisfies the 9-FPI with parameter OFP((O), have
B|Var (Ø(X + Y)[Y)]
(12)
(ò(z + y 2) +2+ 6(x + y))²
(13)
[2]
(=/0)
Since ~ ai and in satisfies the 9-wFPI with parameter (wErr()) following the proof of Lemma we have
Var [Ø(X + Y)DT)
(Ólx [6 + y 2) 6(x y))*
[2|(+0)
tr|l/ olxr (((t+)))aaa)))) -)aa(a)ddd
// ((o+t))((()ddrxi())))
(14)
SAnwooaras MM
I
(6fz + y 2) o( v))
(a(r)dadd + 1
[z](+0))
26

---

where the last inequality follows from the fact that (2( = 0 and the convexity |+|l and (14), have
Combining (12)
Var wng (6)
[/] (*#0)
(0(x + 4 + p(x v))²
Ca.a
dz (v)dy
(2)(2+0)
/| (x70]
(Ø(I+ + y +2) o(r y))² (a())drdaps + I
(w (r)ca,a
(2)(d+0)
(Bwnntt (r) + Crer())) Ca.a /f
(Ølu -(u))
[=|(dt0) day4 p2(u)du + ||
(Swrntt)) (r) + Cwr()) EuI-ua (0) + +roldl Lemma is hence proved.
B.5 Proofs for the Generalized Cauchy Examples
In this section, we provide proofs for the two corollaries in Section 3.2.
Proof of Corollary 4. According [WW15, Corollary 1.2], Ty satisfies a-FPI with parameter Crri(a) for any I min(2, Therefore it follows from Theorem 3 that
(p (x) I exp (-kn (CFPI(a)) + n) -1 x (TT).
(15)
According to [MHFH Corollary 22], when Po (O, Ia) and d 2 2, Roo (p (xp) In(2"/T(p//2) + In( d+z) which implies (p) (TT)) ((d). Therefore Corollary follows from (15) and 7 E (0, 1).
S
Proof of Corollary 5. We prove the two part the Corollary separately:
(i) When 2 according [WW15, Corollary 1.2] Ty satisfies the 1-FPI with parameter CpPi())- Corollary 3 applies with L 4(d v) and 8 1/4 and the iteration complexity of Algorithm is of order O (Crrqayyd (d 2)4 In (pt me)/s)).
(ii) When (0, 1), according [WW15, Corollary 1.2], there exists positive constant such that ny satisfies the 1-wFPI with parameter
(wtPIn(()) = c(1 + +r (1-1w)/
(16)
Theorem implies that
kn 1) 4) c(1 + r- (1-w xx² 2p0 (mc)
x2 ( (x)) S exp (-
(k: + 1)7
+ +r(1 - -exp
+ c(1 r (1-1>/1) )) exp (Ad
<expl
17 + c(1 r- (1-11))ju) (p) mm)
kn
(k + 1)yr
11 + c(1 r- (1-))/u) exp (2 (pt. | 1).
exp (-20 (08) (sw))
For any > 0 and k 2 1, pick r
we have x2 (px (ov)) ) < E if
(k+1)"m
2(1 R)o (To) ) In 1// 2x (px [mu)
k 1 +
2 -1 exp
Corollary applies with L (d + v)/v and 9 v/4. Therefore, by choosing 1/ = O(d 1/2 (dl w) 3 the
itcration complexity Algorithm 2 order
of max f d 3/2 od 0 1-v exp
2(1 v (pt (mw) }} Ind 22 2x [,u)
27

---

C Proofs for the Lower Bounds on the Stable Proximal Sampler
In this section we introduce the proofs for the lower bounds for the stable proximal sampler with parameter a when the target is the generalized Cauchy density with degrees of freedom strictly smaller than a. The lower bound is proved following the idea introduced in Section 2.
Lemma 8. Suppose (I yk)k are the iterates of the stable proximal sampler with parameter a, step size 1j and larget density xx exp(-V) for some V Rd R. k E 1), Then, for every 2 O,
Let G(æ)) exp(nV (x)) with
B[G(+++1) S B 2 na =x)),
where 2k. with density Pi (a) is sampled independently from v.k
Proof of Lemma 8. Recall that X (xly) n X (t)pla) We have
B[G(xx-1) B
Bl G(z)** (x)p, yx)dx)
G uv + n 2x 7T (yk + [b)a]]]
where Zye = (x) (x y = Eix (wke 7 2x) yu and 25 is the a-stable random
vector with density p( which independent yku Fg. Let T 12 R be T(r) r- Since
(0, 1), T is convex and rT(r) is concave. According to the fact that G(x) T(=*)
and Jensen's 's inequality, we have
E T( )) 11- 2x))
B[G(I++)]]
=
E [ (yk + 17a zx) 1k]]
R ( (uk- + n7 + zx)))(l1))]
Since T' is convex, apply Jensen's 's inequality again and we get
E[G((++1)] s BJG(() + 1 2x) = E [E[G + v/ 2/2 + 17 [x)]
EIG + 2 2 [=T]]
where z/. is the o-stable random vector with density (0), which is independent to Ta zu and the last identity follows from the self- self-similarity of a-stable process with Σn p(()) which is independent to Tk-
Lemma 9. Suppose (Ix: size n and target density x² x exp(-V) satisfies
(Ix,Vb) Wb0k are the iterates of the stable proximal sampler with parameter a, step
(d + v2)lar
and AV & (d + v2)
VV(a))
1+ |x|
1 1x]
for some v2 (0, a) and for all x E Rd.. Let G(xx = exp(xV(xV)) with
( + 1 + 12)
Then, for every 1s and
0.
E[G(x++1)) (1 +
k(d+22)
E[G(xx) s(d4w)) x(d+v2)
" +
e(dtor))
m ald+te))
(a)
(17)
(a) where m x(d++r)) = E||zz| (idtuaa) with zu being an a-stable random vector with density Pi Moreover, for every N O.
(a)
E[G(#N)] S [[G())) m (a)
m N a(dtos)
+1 w((tta))
(18)
where S is hiding uniform positive constant factor.
28

---

Proof of Lemma 9. Without loss of generality assume (()) = 0. Then, we have that,
V(x) = =(+)= S (z. (t((t)) - (d + v2) L. t|z|
d 12
In(1 + |z//)).
+ ||0p2
2
Therefore G(x) exp(x=((2) (2:) S + |x 12 ) pdd+t))/ Since E (u2(d v2) ald + u2)-
G(x) = ((o] when |x| > 1 and G + n 2x) Lemma 8 is finite. We have [x + 2 17 ]
< + Ia + 22 17 2k 12) m(dia
<TB((1 + (1 (a) 2 4- 17
+ r ))(b P)
$(1 +) i2)
[xx((x)) + me! and
(1+r")
2k [dd+)
5(1+r) ((d
E[G(=>)] + add) m(dtug)
11+ midhin)
m
midd+v2)
where the first inequality follows from the Young's 's inequality and m ((d+t))
(a)
| [n(dtes) with
24 being an a-stable random vector with density pi (17) follows from Lemma 8. Furthermore, by induction we have
E[G(xn)] $ (1 11
(1 + [1+r)((tts))0))
v(d=w)) x(dtw2)
(1 +l
s(d+v)) (a) m x(d+v2))
(1 + (1+r)clttm)//
Pick #(d+ug)N and (18) is proved.
Proof of Theorem 4. To apply Lemma 1, we choose G(z) cxp(xV(x))) with x E (vg(d
122 add + 1) !) C (0, 1). Without loss of generality assume V(0) = 0. Via Assumption 1, we
have the estimates for V.
V(x) = L (z. (Lx.))) 2 (d+ u) S/'
4al
+ V1 2
v(+)=/(
dl
In(1 + (00
1 tt
By Lemma 2 we have
t <>((() 2 v) 2 [x| y u(
2 Cu, (1+
y ((441))
We then invoke Lemma and Lemma 9 to obtain TV(pN, xxx
E[G(zo)] + m (a) a(d)o2))
+1 ((ddw2)
di
xxd+to)) N
2 sup CupCr d²t (1 y matios 921
y (dd
v1) The fact that & E (u2(d + 11)= ald + 122 ensures that the supremum on the right side is always positive. In particular, picking y such that
RaI θ Contd 7 (B[G(z))] + m (a)
mi(+ee)) N
aldton) t1m aldte2)
obtain that
TV
ald Jug Aug C aod (
(a) (a) (E(G(xo)) +
x(d+v2) N v(de
+1 ((dttt))
where is hiding uniform positive constant factor. Therefore, for any a ( a-d d+v2 (a diro) and get that
(2((+)2) dtes ,2] and
5 E (0, d+m ), we can choose
x
2 Con ss.d Hil (oae (E(G(z))] m (a)
( N - +1 )
(o (dd
Theorem 4 then follows by taking - 8.
29

---

20
9.5-
Proximel Sempler Stable Proximal Sampler
17.
Average Position
13
033
13.0
-0-
Gaussian Proximal Sampler
Stable Proximal Sampler
0.23
12.
100-
Geussian Proximal Sempler
Stable Proximal Sampler
0.15
0.10
50-
ont-
20
80
00
100
0.00
25
25
25
30
0.0
60
300
Figure 1: Comparison between Gaussian and Stable Proximal Sampler: target is chosen to be one-
dimensional student-t with center 0 and 4 degrees of freedom; initialization is chosen z0 20.
C.1 Further Discussions on Lower bounds of the stable proximal sampler
To derive a lower bound for the stable proximal sampler with parameter o, it is worth mentioning that there is an extra difficulty applying our method when 2 a. Recall that when v E (0, a), T
has heavier tail than xxx does. Therefore, when we apply
TV mo) (T pk (G v)
(19)
to study the lower bound, it suffices to derive a lower bound on TT 2 y), and an upper bound on p (G 2 y) which is smaller than the lower bound on T. 2 y). Deriving these bounds is not too hard: the lower bound can be obtained by looking at explicit integral against directly and the upper bound is derived based on the fractional absolute moment accumulation of the isotropic a-stable random variables along the stable proximal sampler.
However, when v 2 a, we expect that Pi has heavier tail than T.. Therefore, to apply (19), we need to find an upper bound on T 2 y). and a lower bound on p (G 2 y) which smaller than the upper bound on (G y). Notice that p (G y) quantity varying along the trajectory of the stable proximal sampler. Deriving lower bound along the trajectory is essentially more challenging than deriving an upper bound.
In order to derive a satisfying lower bound in this case, it hence remains to characterize the stable proximal sampler as approximation of appropriate gradient flow, just as that the Brownian- driven proximal sampler can be interpret as the entropy-regularized JKO scheme in [CCSW22]; also Section 5. To understand this kind of gradient flow approximations itself is an interesting future work as it may help us to understand and characterize the class of MCMC samplers that utilize heavy-tail samples to approximate lighter-tail target densities, which is non-standard compared to commonly used MCMC samplers such as ULA, MALA, etc.
D Numerical Illusraaions
In this section, we present numerical results that illustrate the improved performance of the proximal sampler with stable oracles (a = 1) compared to that with Gaussian oracles. We first sample from the one-dimensional student-t distribution with center zero and degrees of freedom by running the proximal samplers with different oracles in parallel for 100 times. Each individual chain is run for 100 iterations with step-size y = 0.1. Figures 1,2,3 present the convergence results for different initializations zg = 20, 5, -5 respectively. In each figure, the first column shows the means and variances of the iterates along the trajectories; the center column shows the histograms of the last iterates and the target density (red curve); the last column shows the convergence of Wasserstein-2 distance along the trajectories. We also sample from the two-dimensional student-t distribution with center at the origin and 4 degrees of freedom by running the proximal samplers with different oracles in parallel for 30 times. Each individual chain is run for 20 iterations with step-size 17 = 0.1 with the initialization at Tо = [5, 1]. In Figure 4, we present the convergence results, the first column showing the means and variances of the first-coordinates along the trajectories, the center column showing the histograms of first-coordinate in the last iterates and the first-coordinate marginal density of the target distribution (red curve), and the last column showing the convergence of Wasserstein-2 distance along the trajectories.
30

---

Gaussian Proximal Sampler
Goutsion Proximal Sampler
Goussian Proximal Sampler Stable Proximal Sampler
Stable Proximal Sampler
Stable Proximal Sampler
Sescccrtton Dictorne
Average
Gpens
Prithinn
Orens
Figure 2: Comparison between Gaussian and Stable Proximal Sampler: target is chosen to be one- dimensional student-t with center 0 and 4 degrees freedom; initialization is chosen 2g
Gaussian Proximal Sampler
Proximal Sampler Stable Proximal Sampler
Warserstin Dietance
Prosimal Stable Provimal Samp
Average Postion
Stable Proximal Sampler
04
20
60
100
0:0
-5
-2
00
300
Figure 3: Comparison between Gaussian and Stable Proximal Sampler: target is chosen to be one-
dimensional student-t with center 0 and 4 degrees of freedom; initialization is chosen zn 55
10
10
Gaussian Proximal Sampler Sampler
Goursian Proximal Sampler
Wasserstain Dictance
Gaussian Proximal Samoler Sampler
Avetegee Position
Sampler
0.2
Posalion
Figure 4: Comparison between Gaussian and Stable Proximal Sampler: target is chosen to be two- dimensional student-t with center (0, 0) and degrees of freedom; initialization is chosen = [5, 1].
31

---

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: The main claim in the abstract and introduction is the separation result between Gaussian and Proximal Sampler. The rest of the sections are exactly stating (and proving) the aforementioned separation result.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Please Section 5.
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 "Limitations" 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 authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it 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 address problems of privacy and faimess.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers penalize honesty concerning limitations.
will be specifically instructed
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
32

---

Answer: [Yes]
Justification: The assumptions are listed in the respective theorem. The (correct) proofs are provided in the appendix.
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 the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or 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 ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: Our work is primarily theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 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, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make 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 to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make 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 new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce 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 authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
33

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
Our work is primarily theoretical.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https: :tapps://niie /ttp///nii.p... cc/
pub i guides/ Codeeuumm ss onPol (yycy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a 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. cc/ wwtpc///pppggpp...c..o.oooooooet
Cooeeeeeeeeeeee ProdeSubmii iesionoolicnne for more details. The authors should provide instructions on 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 subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our work is primarily theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our work is primarily theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
34

---

The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our work is primarily theoretical.
Guidelines:
The answer means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ttp:://////iss..eeeee cttppp//cccttttcccc....l.....
Answer: [Yes]
Justification: The authors have read the Ethics Guideline and followed it in the paper preperation.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is primarily theoretical.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
35

---

The conference expects that many papers will be foundational research and not tied to 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 mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
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: Our work is primarily theoretical.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses 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: [NA]
Justification: Our work is primarily theoretical.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papers rawl aw! thcode com da set. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
36

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our work is primarily theoretical.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an 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 paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work is primarily theoretical.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, 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 to 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:
Our work is primarily theoretical.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS 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.
37


Reviews:
[{"review_id": "9OSFu4H7g1", "reviewer": "Reviewer_nmvc", "summary": "This paper studies the complexity of sampling heavy-tailed distributions. It provides lower bounds on the complexity of Gaussian-based samplers for a class of heavy-tailed targets. Then, the paper constructs proximal samplers based on stable oracles, which improve the sampling complexity.", "questions": "* Is there any intuition that a Gaussian-based sampler has lower accuracy for heavy-tailed targets than for non-heavy-tailed targets?\n* How would a Gaussian-based sampler compare with a stable oracle for not heavy-tailed targets?", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* This paper is well-written. The background of sampling and the research problems regarding sampling complexity are clearly introduced. The contributions of the lower bound on Gaussian-based samplers for heavy-tailed targets and the improved complexity using stable oracles are clearly presented.\n* The paper is technically sound. The definitions and assumptions are discussed clearly, and the theoretical results are supported by proof sketches.", "weaknesses": "The contribution of the paper could be improved with empirical experiments to evaluate the sampling algorithms and their complexity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their valuable advice and comments and greatly appreciate the positive evaluation.\n\n>The contribution of the paper could be improved with empirical experiments to evaluate the sampling algorithms and their complexity.\n\nFollowing the reviewer's suggestion, we have added numerical experiments that compare the Gaussian proximal sampler and the stable proximal sampler with $\\alpha=1$; see the uploaded pdf file as part of the rebuttal. In the first three experiments (corresponding to rows), we choose the target distribution to be the one-dimensional student-t distribution with 4 degrees of freedom and zero mean, and run the algorithms in parallel for 100 steps with step-size 0.1, to get 100 chains. We adopt different initializations, $x_0=20,5,-5$, and visualize the convergence via the average trajectories (with standard deviations), histogram of the last-step samples and the Wasserstein-2 distance decay, respectively. In the last experiment, we choose a 2-dimensional student-t distribution with 4 degrees of freedom and zero mean, and run the algorithms in parallel for 20 steps with step-size 0.1, to get 30 chains. We adopt the initialization, $x_0=[5,1]$, and use the same visualizations for the first-coordinate (marginals). The stable proximal sampler outperforms the Gaussian proximal sampler in all cases. \n\nIn the revised version of our paper, we will include a section containing extensive detailed numerical studies demonstrating the performance of the algorithms.\n\n>Is there any intuition that a Gaussian-based sampler has lower accuracy for heavy-tailed targets than for non-heavy-tailed targets?\n\nFor the Gaussian-based sampler, the repeated sampling steps $y_k\\sim \\pi^{Y|X}(\\cdot|x_k)=\\mathcal{N}(x_k,\\eta I_d)$ are crucial to ensure rapid convergence. These are essentially heat flow simulations, that take advantage of the geometric properties of the logconcave (non-heavy-tailed) target distributions, providing an exponential decay in KL-divergence. \n\nWhen the target distribution is heavy-tailed, the standard heat flow mixes slowly. Intuitively, if our initial condition is a light-tailed random variable, it would take many steps for the Gaussian proximal sampler to match the moments of the heavy-tailed target, because in every iteration we only add Gaussian noise with a small variance.  \n\n>How would a Gaussian-based sampler compare with a stable oracle for not heavy-tailed targets?\n\nGaussian proximal sampler performs well when the target satisfies a Poincare or alog-Sobolev inequality [1]. When the RGO step is implemented exactly, the algorithm converges exponentially fast. Since these light-tailed distributions also satisfy the Fractional Poincare inequality (FPI), our Theorem 3 suggests the stable proximal sampler also converges exponentially fast. The difference lies in the rates of exponential convergence. Intuitively, stable proximal sampler may have a smaller convergence rate compared to Gaussian proximal sampler. For example, if the target is a Gaussian which has a concentrated region that most samples would lie in, since the stable proximal sampler adds heavy-tail randomnesses in each iteration, it may move a sample out of the concentrated region more easily. Therefore, it takes longer for the stable proximal sampler to move most of the particles inside the concentrated region. Analytically, the convergence rates depend on the Poincare constant and the FPI constant in the Gaussian and stable case, respectively \n\n[1] Chen, Yongxin, et al. \"Improved analysis for a proximal algorithm for sampling.\" Conference on Learning Theory. PMLR, 2022.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "uc6KPPkdL0", "reviewer": "Reviewer_MHrz", "summary": "The authors provide a lower bound for sampling from heavy tailed distributions under the Gaussian oracle of order $O(\\textup{poly}(1/\\varepsilon))$. They then propose an alternative proximal sampling algorithm using the $\\alpha$-stable oracle that achieves a convergence rate of $O(\\log(1/\\varepsilon))$ for heavy-tailed distributions satisfying a fractional Poincare inequality. They then provide a practical implementation of the stable proximal sampler, and lower bounds on its convergence rate.", "questions": "I have no clarifications to request.", "limitations": "The authors provide an adequate discussion of the limitations of their methods in the final section, and I foresee no additional negative impacts of their work.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This work presents a very nice combination of results showing a separation in the performance of stable and Gaussian proximal samplers. The combination of lower and upper bounds separating the two methods makes the work a particularly interesting contribution.\n\n- The addition of a practical implementation of the stable proximal sampler is nice to have, demonstrating that it is viable in practice.\n\n- The work is generally clearly presented and the authors are clear about their contributions.\n\n- Overall, I consider this to be a very sound piece of theoretical work.", "weaknesses": "I have no major concerns about this paper. The presentation is somewhat dense in places, though this is mostly just a consequence of it being a very technical paper and not a flaw as such. If the authors want to make the claim that practicioners should use the stable proximal sampler in applied settings, then they may want to provide empirical evidence of its performance compared to the Gaussian proximal sampler. However, I understand that this is not the main purpose of this theoretical paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their valuable advice and comments and greatly appreciate the positive evaluation.\n\n>I have no major concerns about this paper. The presentation is somewhat dense in places, though this is mostly just a consequence of it being a very technical paper and not a flaw as such. If the authors want to make the claim that practicioners should use the stable proximal sampler in applied settings, then they may want to provide empirical evidence of its performance compared to the Gaussian proximal sampler. However, I understand that this is not the main purpose of this theoretical paper.\n\nFollowing the reviewer's suggestion, we have added numerical experiments that compare the Gaussian proximal sampler and the stable proximal sampler with $\\alpha=1$; see the uploaded pdf file as part of the rebuttal. In the first three experiments (corresponding to rows), we choose the target distribution to be the one-dimensional student-t distribution with 4 degrees of freedom and zero mean, and run the algorithms in parallel for 100 steps with step-size 0.1, to get 100 chains. We adopt different initializations, $x_0=20,5,-5$, and visualize the convergence via the average trajectories (with standard deviations), histogram of the last-step samples and the Wasserstein-2 distance decay, respectively. In the last experiment, we choose a 2-dimensional student-t distribution with 4 degrees of freedom and zero mean, and run the algorithms in parallel for 20 steps with step-size 0.1, to get 30 chains. We adopt the initialization, $x_0=[5,1]$, and use the same visualizations for the first-coordinate (marginals). The stable proximal sampler outperforms the Gaussian proximal sampler in all cases. \n\nIn the revised version of our paper, we will include a section containing extensive detailed numerical studies demonstrating the performance of the algorithms.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "5Ofh7FZ5zb", "reviewer": "Reviewer_vTyM", "summary": "The paper focus on studying the complexity of heavy-tailed sampling and present a separation result in terms of obtaining high-accuracy versus low-accuracy guarantees. Their results are presented for proximal samplers that are based on Gaussian versus stable oracles. Authors show that proximal samplers based on the Gaussian oracle have a fundamental barrier in that they necessarily achieve only low-accuracy guarantees when sampling from a class of heavy-tailed targets. In contrast, proximal samplers based on the stable oracle exhibit high-accuracy guarantees, thereby overcoming the aforementioned limitation. They also prove lower bounds for samplers under the stable oracle and show that our upper bounds cannot be fundamentally improved.", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "Although I am not an expert in this field, I find this work quite interesting. The authors provide new material and support their statements with proofs.", "weaknesses": "The paper is not tested in any way on a numerical experiment. I am convinced that a paper presented at this type of conference should be both motivated by a real-world application and tested numerically, e.g., on a near-real-world formulation of the problem.\n\n**After a rebuttal process**, the authors agreed with this weakness and promised to add the experiments to the final version of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their valuable advice and comments and greatly appreciate the positive evaluation.\n\n>The paper is not tested in any way on a numerical experiment. I am convinced that a paper presented at this type of conference should be both motivated by a real-world application and tested numerically, e.g., on a near-real-world formulation of the problem.\n\nFollowing the reviewer's suggestion, we have added numerical experiments that compare the Gaussian proximal sampler and the stable proximal sampler with $\\alpha=1$; see the uploaded pdf file as part of the rebuttal. In the first three experiments (corresponding to rows), we choose the target distribution to be the one-dimensional student-t distribution with 4 degrees of freedom and zero mean, and run the algorithms in parallel for 100 steps with step-size 0.1, to get 100 chains. We adopt different initializations, $x_0=20,5,-5$, and visualize the convergence via the average trajectories (with standard deviations), histogram of the last-step samples and the Wasserstein-2 distance decay, respectively. In the last experiment, we choose a 2-dimensional student-t distribution with 4 degrees of freedom and zero mean, and run the algorithms in parallel for 20 steps with step-size 0.1, to get 30 chains. We adopt the initialization, $x_0=[5,1]$, and use the same visualizations for the first-coordinate (marginals). The stable proximal sampler outperforms the Gaussian proximal sampler in all cases. \n\nIn the revised version of our paper, we will include a section containing extensive detailed numerical studies demonstrating the performance of the algorithms.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "K2UBZSWIwI", "reviewer": "Reviewer_YAjf", "summary": "This paper studies the problem of heavy-tailed sampling. First, the paper shows that while the gaussian proximal samplers are efficient for light-tailed targets, they are not accurate for heavy-tailed ones; the paper develops a lower bounds for the Gaussian proximal samplers, which reveals a fundamental challenge in heavy-tailed settings.\n\nThen, the paper proceeds to develop a novel samplers based on restricted alpha-stable oracle; the insight is to replace the standard heat equation in gaussian oracle with a fractional heat flow. The paper proves that under suitable conditions the proposed sampler is efficient for heavy-tailed targets. Additionally, the paper proposes a practical implementation for a particular case of alpha=1.", "questions": "- I wonder if the efficiency rejection sampling efficiency in Alg.3 has been taken into account of the sampler's theoretical complexity and practical complexity?\n\n- Maybe I am missing this -- what is the impact of alpha?", "limitations": "Most of the limitations have been touched upon in sec 5. Otherwise see the weakness comments.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Novel theoretical analysis for the gaussian oracle sampler, which provides a new insight to developing sampling algorithms\n\n- A novel methodology for heavy-tailed sampling", "weaknesses": "- The paper is purely theoretical and lacks experimental evaluation; it would be nice to at least have a toy illustration for the implementable algorithm 2+3 in the alpha=1 case.\n\n- As the authors discussed in Sec5, the current paper does not present implementable algorithms for general alpha values in (0,2).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their valuable advice and comments and greatly appreciate the positive evaluation.\n\n>The paper is purely theoretical and lacks experimental evaluation; it would be nice to at least have a toy illustration for the implementable algorithm 2+3 in the $\\alpha=1$ case.\n\nFollowing the reviewer's suggestion, we have added numerical experiments that compare the Gaussian proximal sampler and the stable proximal sampler with $\\alpha=1$; see the uploaded pdf file as part of the rebuttal. In the first three experiments (corresponding to rows), we choose the target distribution to be the one-dimensional student-t distribution with 4 degrees of freedom and zero mean, and run the algorithms in parallel for 100 steps with step-size 0.1, to get 100 chains. We adopt different initializations, $x_0=20,5,-5$, and visualize the convergence via the average trajectories (with standard deviations), histogram of the last-step samples and the Wasserstein-2 distance decay, respectively. In the last experiment, we choose a 2-dimensional student-t distribution with 4 degrees of freedom and zero mean, and run the algorithms in parallel for 20 steps with step-size 0.1, to get 30 chains. We adopt the initialization, $x_0=[5,1]$, and use the same visualizations for the first-coordinate (marginals). The stable proximal sampler outperforms the Gaussian proximal sampler in all cases. \n\nIn the revised version of our paper, we will include a section containing extensive detailed numerical studies demonstrating the performance of the algorithms. \n\n>As the authors discussed in Sec5, the current paper does not present implementable algorithms for general alpha values in (0,2).\n\nThere is currently a difficulty to implement the R$\\alpha$SO exactly for general $\\alpha\\in (0,2)$ due to the fact that there is no explicit representation for the $\\alpha$-stable density for general $\\alpha$. It is an interesting to investigate an exact/inexact implementation of the R$\\alpha$SO for general $\\alpha\\in (0,2)$.\n\n>I wonder if the efficiency rejection sampling efficiency in Alg.3 has been taken into account of the sampler's theoretical complexity and practical complexity?\n\nSimilar to the discussion of the Gaussian proximal sampler in [1], the iteration complexity results in our paper assumes the R$\\alpha$SO, and the efficiency of Algorithm 3 is not included. In section 3, we provide Algorithm 3 as a practical implementation of R$\\alpha$SO and its efficiency is discussed in Remark 3.\n\n>Maybe I am missing this -- what is the impact of $\\alpha$?\n\n$\\alpha$ is a parameter that appears in the Fractional Poincare inequality (FPI) and the stable process. As shown in Theorem 3, if the target distribution satisfies $\\alpha$-FPI, the $\\alpha$-stable proximal sampler convergens exponentially fast. The $\\alpha$ in $\\alpha$-FPI characterizes the tail-heaviness of the target distribution. If the target is extreme heavy-tail, we need to apply the stable proximal sampler with a small value of $\\alpha\\in (0,2)$ so that the target satisfies the $\\alpha$-FPI. If we choose a large $\\alpha\\in (0,2)$ and the target doesn't satisfy $\\alpha$-FPI, then the $\\alpha$-stable proximal sampler only converges polynomially fast. Details are included in Section B.4 in the appendix.\n\n[1] Chen, Yongxin, et al. \"Improved analysis for a proximal algorithm for sampling.\" Conference on Learning Theory. PMLR, 2022", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "e2ERikvqJN", "reviewer": "Reviewer_kBax", "summary": "The paper investigates the complexity of sampling from heavy-tailed distributions and presents a distinction between obtaining high-accuracy and low-accuracy guarantees. It analyzes two types of proximal samplers: those based on Gaussian oracles and those based on stable oracles. The main findings are that Gaussian oracle-based samplers can only achieve low-accuracy guarantees when sampling from heavy-tailed distributions, while stable oracle-based samplers can achieve high-accuracy guarantees. Additionally, the paper establishes lower bounds for samplers using the stable oracle, indicating that the presented upper bounds are optimal and cannot be fundamentally improved.", "questions": "1. Can you give an example in the real-world to motivate your problem?\n2. Is it possible to run some experiments to verify your results?", "limitations": "There is no experiment.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The problem is well-motivated and interesting. \n2. Designed the algorithms and derived the upper bounds and lower bounds for different settings. \n3. The authors also provided insightful discussion.\n4. The authors provided solid theoretical proof for the results.", "weaknesses": "There is no experiment to verify the theoretical findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their valuable advice and comments and greatly appreciate the positive evaluation.\n\n>Weakness: There is no experiment to verify the theoretical findings.\n>Question 2: Is it possible to run some experiments to verify your results?\n\nFollowing the reviewer's suggestion, we have added numerical experiments that compare the Gaussian proximal sampler and the stable proximal sampler with $\\alpha=1$; see the uploaded pdf file as part of the rebuttal. In the first three experiments (corresponding to rows), we choose the target distribution to be the one-dimensional student-t distribution with 4 degrees of freedom and zero mean, and run the algorithms in parallel for 100 steps with step-size 0.1, to get 100 chains. We adopt different initializations, $x_0=20,5,-5$, and visualize the convergence via the average trajectories (with standard deviations), histogram of the last-step samples and the Wasserstein-2 distance decay, respectively. In the last experiment, we choose a 2-dimensional student-t distribution with 4 degrees of freedom and zero mean, and run the algorithms in parallel for 20 steps with step-size 0.1, to get 30 chains. We adopt the initialization, $x_0=[5,1]$, and use the same visualizations for the first-coordinate (marginals). The stable proximal sampler outperforms the Gaussian proximal sampler in all cases. \n\nIn the revised version of our paper, we will include a section containing extensive detailed numerical studies demonstrating the performance of the algorithms.\n\n>Question 1: Can you give an example in the real-world to motivate your problem?\n\nThere are several real-world applications of heavy-tailed sampling which arises in various domains such as Bayesian statistics [GJPS08, GLM18], machine learning [CDV09, BZ17, NSR19, SZTG20, DKTZ20], robust statistics [KN04, JR07, Kam18, YŁR22], multiple comparison procedures [GBH04, GB09], and study of geophysical systems [SP15, QM16, PBEM23].\n\nIn particular the papers by [SP15, QM16, PBEM23] discuss real-world data analysis problems which crucially hinge on heavy-tailed sampling. We will be happy to elaborate this problem in the revision, subjected to space constraints.\n\nFurthermore, there has been recent works on heavy-tailed diffusion models; see e.g., [YPKL24],\tarXiv:2407.18609 and [PSVM24]. We anticipate that our results in this work have implications for heavy-tailed diffusion models as well.\n\nFinally, please refer to the recent workshops at Neurips 2023 (titled \"Heavy Tails in ML: Structure, Stability, Dynamics\") and Issac Newton institute (titled \"Heavy tails in machine learning\") for further emerging applications of heavy-tailed sampling in real-world data science. \n\n[YPKL24]- Yoon, E. B., Park, K., Kim, S., & Lim, S. (2023). Score-based generative models with Lévy processes. Advances in Neural Information Processing Systems, 36, 40694-40707.\n\n[PSVM24] - Paquet, E., Soleymani, F., Viktor, H. L., & Michalowski, W. (2024). Annealed fractional Lévy–Itō diffusion models for protein generation. Computational and Structural Biotechnology Journal, 23, 1641-1653.", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank the reviewer for their valuable advice and comments and greatly appreciate the positive evaluation. Results from the added experiments are included in the pdf file.

Meta-review: The paper presents a separation between Gaussian and stable-based proximal samplers in terms of low vs. high-accuracy guarantees. All reviewers recommended acceptance after discussion. The main concern was lack of experiments, which the authors presented during discussion. I recommend acceptance and remind the authors to add the experiments to the paper.
Decision: Accept (poster)