In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies
Authors: Yunbum Kook
Santosh Vempala
Matthew Shunshi Zhang
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Sampling
convex bodies
MCMC
uniform sampling
Primary area: probabilistic_methods
TL;DR: We propose a sampler for the uniform distribution on a convex body, based on forward and backward heat flows.

Abstract: We present a new random walk for uniformly sampling high-dimensional convex bodies. It achieves state-of-the-art runtime complexity with stronger guarantees on the output than previously known, namely in Rényi divergence (which implies TV, $\mathcal{W}_2$, KL, $\chi^2$). The proof departs from known approaches for polytime algorithms for the problem - we utilize a stochastic diffusion perspective to show contraction to the target distribution with the rate of convergence determined by functional isoperimetric constants of the stationary density.

In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies
Yunbum Kook
Santosh Vempala
School of Computer Science Georgia Institute of Technology yb. kook@gatech. edu
School of Computer Science Georgia Institute of Technology
vempala@gatech.c edu
Matthew S. Zhang
Department of Computer Science,
University of Toronto, matthew natthew.zhangdmal utoronto.com ca
Abstract
We present a new random walk for uniformly sampling high-dimensional convex bodies. It achieves state-of-the-art runtime complexity with stronger guarantees on the output than previously known, namely in Rényi divergence (which implies TV, W2, KL, 2²). The proof departs from known approaches for polytime algorithms for the problem - we utilize a stochastic diffusion perspective to show contraction the target distribution with the rate of convergence determined by functional isoperimetric constants of the stationary density.
Introduction
Generating random samples from a high-dimensional convex body is a basic algorithmic problem with myriad connections and applications. The core of the celebrated result of [1]. giving randomized polynomial-time algorithm for computing the volume of convex body, was the first polynomial-tine algorithm for uniformly sampling convex bodies. In the decades since, the study of sampling has led to long series of improvements in its algorithmic complexity [2. 3, 4, 5, 6]. often based on uncovering new mathematical/geomme ggcomerre structure, establishing connections to other fields (c.g., functional analysis, matrix concentration) and developing tools for proving isoperimetric inequalities and analyzing Markov chains. With the proliferation data and the increasing importance of machine learning, sampling has also become essential algorithmic tool, with applications needing samplers in very high dimension, e.g., scientific computing [7, 8, 9], systems biology [10, 11], differential privacy [12, 13] and machine learning [14, 15].
Samplers for convex bodies are based on Markov chains (see $5 for summary). Their analysis based on bounding the conductance of the associated Markov chain, which in turn bounds the mixing rate. Analyzing the conductance requires combining delicate geometric arguments with (Cheeger) isoperimetric incqualities for convex bodies. An archetypal example of the latter is the following: for any measurable partition S₁, S2, S3 of a convex body K Rdd, we have
vol(Ss) d(S).S:)
min(vol(S)), vol(S2))
Cx
where d(.,.) is the (minimum) Euclidean distance, and Cx is an isoperimetric constant the uniform distribution over XC. (The KLS conjecture posits that Cx ((1) for any convex body X. in isotropic position, i.e., under the normalization that a random point from IC has identity covariance). The coefficient CR is bounded by the Poincaré constant of the uniform distribution over I. (and they
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

in fact asymptotically equal). The classical proof of conductance uses geometric properties of the random walk hand to reduce the analysis to suitable isoperimetric inequality (see e.g., [3, 16]). The end result is guarantee on the number of steps after which the total variation distance (TV distance) between the current distribution and the target bounded by a desired error parameter. This framework has been widely used and effective in analyzing an array of candidate samplers, e.g.. Ball walk [4], Hit-and-Run [17, 5], Riemannian Hamiltonian Monte Carlo [18] etc.
One successful approach, studied intensively over the past decade, is based on diffusion. The basic idea first analyze a continuous- time diffusion process, typically modeled by a stochastic differential equation (SDE), and then show that suitable time-dicrettzztton of the process, sometimes together with a Metropolis filter, converges the desired distribution efficiently. A major success along this line is the Unadjusted Langevin Algorithm and its variants, studied first in [19]. These algorithms have strong guarantees for sampling "nice" distributions [20, 21, 22, 23], such as ones that are strongly log-concave, or more generally distributions satisfying isoperimetric inequalities, while also obeying some smoothness conditions. The analysis of these algorithms markedly different from the conductance approach, and typically yields guarantees in stronger metrics such as the KL-divergence.
Our starting point is the following question:
Can diffusion- based approaches be used for the problem of sampling convex bodies?
Despite remarkable progress, thus far, constrained sampling problems have evaded the diffusion approach, except as high-level analogy (e.g., the Ball walk can be viewed as discretization of Brownian motion, but this alone does not suggest a route for analysis) or with significantly worse convergence rates (e.g., (24, 25)).
Contributions. Our main finding is a simple diffusion- algorithm that can be mapped to stochastic process (and, importantly, to pair of forward and backward processes), such that the rate of convergence is bounded directly by an appropriate functional inequality for the target distribution. As consequence, for the first time, we obtain clean end-to-end guarantees in the Rényi divergence (which implics guarantees in other well known quantities such as W2, TV, KL, x² etc.), while giving state-of-the-att runtime complexity for sampling convex bodies (e.g.. Ball walk or Speedy walk [3, 4J). Besides being a stronger guarantee on the output, Rényi divergence of particular interest for differential privacy [13]. Perhaps most interesting that our proof approach is completely different from prior work on convex body sampling. In summary,
The guarantees hold for the qéRéyi divergences while matching the rates of previous work (prior work only had guarantees in the TV distance).
The analysis is simple, modular, and easily extendable to several other settings.
Organization. In $2, we provide some relevant notions for understanding our results. We then proceed to outline our algorithm in $3. The algorithmic guarantees are provided in $4, in which we also outline our proof and compare with the analysis of Ball walk, Speedy walk. Lastly, we provide a detailed survey of the relevant literature in $5 before concluding.
2 Preliminaries
Unless otherwise specified, we will use for the 2-norm Rdd We write = O(b). S b to mean that a I cb for some universal constant c > 0. Similarly, a 2 b, a = (bbb) for a 2 cb. while a = O()) means S b, b S simultancously. We will also use a = (()) to denote a Obb polylog(bb)) (b)). Lastly, we will use measure and density interchangeably when there is no confusion.
To quantify the convergence rate, we introduce some common divergences between distributions. Definition 1 (Distance and divergence). For two measures μ., v/ Rdd the total variation distance between them is defined by
|| p||TV == sup (B) v(B),, BEF
where F is the collection of all measurable subsets of ıd_ The 2- Wasserstein distance is given by
W (H, = inf LE Exx,y> ||| - Y [ "ET(),))

---

(raject)
K2
Ball walk
Speedy walk
In-and-Out
Figure 1: Description of uniform samplers: (i) Ball walk: proposes uniform random point from (x))), but & K. so it stays at 21 22. (ii) Speedy walk: moves to I2 drawn uniformly at random from K. n (x(z)). ). (iii) In-and-Out: first moves y/2 obtained by taking a Gaussian step from ø1. and then to 22 obtained by sampling the truncated Gaussian N (12, hla)kx.
where T is the set of all couplings between Jr, u. Next, define the f-divergence of μ towards with & y (i.e./ is absolutely continuous with respect to v) as, for some convex function, f IR+ - IR with f(1) 0 and f'(o)) oc.
Dj(a [1) = f {(())
de
de.
The KL-divergence arises when taking fxx x log x, the -diverggee when taking f(x) x. and the q-Rényi divergence is given by
Rg l| v) == - log log [1)
We say that probability measure on Rd satisfies Poincaré inequality (PI) with parameter CpI(v) if for all smooth functions f Rd + R.
Definition 2.
Var.f S CPi(P) E
(PI)
where Var. = [
The Poincaré inequality is implied by the log-Sobolev inequality.
Definition 3. We say that probability measure v on Rd satisfies log-Sobolev inequality (LSI) with parameter CLsi(v) if for all smooth functions IRd I.
Ent, - 20 (V) (((
(LSI-l)
where (f²) = Exlf2 f log 1 - E, [f 2 log (f)) Equivalently, for any probability measure over Rdd with < U,
KL( v) S Cisilv) FlG v),
(LSI-II)
where FI(H v) = E log
| is the Fisher information of μ with respect to v.
de
3 Diffusion for uniform sampling
We propose the following In-and-Out' sampler for uniformly sampling from K. Each iteration consists of two steps, one that might leave the body and the second accepted only if is (back) in AC.
It might be illuminating for the reader to compare this algorithm the well-studied Ball walk (Algorithm 2); each proposed step a uniform random point in a fixed-radius ball around the current point, and is accepted only if the proposed point is in the body A.. In contrast, each iteration of In-and-Out is two-step process, where the first step (Line 2) ignores the boundary of the body, and
'This name reflects the "geometry" of how the iterates are moving. As elaborate in Remark 1, the name "proximal sampler' may be more familiar those from optimization background.

---

Algorithm 1 In-and-Out
Input: initial point Do ~ Nu, convex body K C R iterations T, threshold N, and h > Output: 2T++-
1: for i ....., T'd do
2: Sample yi+1 (a hla).
3: Repeat: Sample T++1 (1 until 2441 E or #attempts; 2 N (declare Failure).
4: end for
the second step (Line 3) is accepted only if a proposal x141 is feasible point in IC. We will presently elaborate on the benefits of this variation.
Each successful iteration of the algorithm, i.e., one that is not declared "Failure", can be called a proper step. We will see that the number of proper steps is directly bounded by isoperimetric constants (such as Poincaré and log-Sobolev) of the target distribution. In fact, this holds quite generally without assuming the convexity of K. The implementation of an iteration is based on rejection sampling (Line 3), and our analysis of the efficiency of this step relies crucially convexity of I.. This is reminiscent of the Speedy walk in the literature on convex body sampling (Algorithm 3), which is used as tool to analyze proper steps of the Ball walk. We refer the reader to Appendix C for a brief survey on these and related walks.
the
This simple algorithm can be interpreted view will allow us to use tools from stochastic analysis. In particular, we shall demonstrate how to interpret the two steps of one iteration of In-and-Out alternating forward and backward heat flows. We begin by defining an augmented probability measure on Rd x Rd by
composition of "flows" in the space of measures. This
(x, y) X exp मे x vl(? 1x(x).
We denote by xx xt XIX ( the marginal distribution of its first component (resp. conditional distribution given the second component), and similarly denote by x² x (+|z) for the second component. In particular, the marginal in the first component x is the uniform distribution over K. Sampling from such joint distribution to obtain the marginal on X (say), can be more efficient than directly working only with xx This idea was utilized in Gaussian Cooling [6] and later as the restricted Gaussian Oracle (RGO) [26, 27].
Under this notation, Algorithm I corresponds to a Gibbs sampling scheme from the two marginals of T(r, y). To be precise, Line 2 and Line correspond sampling from
Vi+1 x XIX (-1x;) = (Z,,, hTa)
and
Ti+1 ~ π XIY (-186+1) = N (yeet,hTaale:
We implement the latter step through rejection sampling; if the number of trials in Line 3 hits the threshold N, then we halt and declare failure of the algorithm.
well known that such a Gibbs sampling procedure will ensure the desired stationarity of π ( y). Note that, conditioned on the event that the algorithm does not fail, the resulting iterate will be an unbiased sample from the correct distribution.
Stochastic perspective: forward and backward heat flows. Our algorithm can be viewed through the lens of stochastic analysis, due an improved analysis for the proximal sampling [27]. This view provides an interpolation in continuous-time, which is simple and powerful. To make this concrete, we borrow an exposition from [28. $8.3]. We denote the successive laws of x; and y by uxx and yu respectively. Recall that the first step of sampling from X (-1xr) (Line 2) yields "Y = Jm" riX== duę (æ:). This is the result of evolving probability measure under (forward) heat flow of p. for some time h, given by the following stochastic differential equation: for Zo ~ nx²
dz.- dB.
(FH)
where B, is the standard Brownian process. We write law 1u," P.. In particular, Zn, +6 uxx (O, (ala) potz for < ~ (O, When pax" x the first step of Algorithm gives
T (v) = [ A( (x)) vol((C) (2mh)d/3 / exp( 2h
1 lly - x x|| dx.
(3.1)
4

---

Table 1: The Fokker-Planck equations for the forward and backward heat flow describe how the laws of Z and zt in (FH) and (BH) evolve over time. See Appendix B.2 for details.
Forward flow
Backward flow
SDE
dZ = dB,
dZz = V Vog((1 X Pa-+) (Z( dt + dB,
Bokker-Plancke
0ep4 2pp
dep4 div(u) V Vlog(1 ( X Ph-t)) + 2045
The second step of sampling from π x (-1y+++) can be represented by | = - x duy du (v) (Line 3). The continuous- time process corresponding to this step might not be obvious. However, let us consider (FH) with Zo xx Then, Zn n², so the joint distribution of (Zn, Zp.) is simply This implies that (Zol Z4, y) x x Imagine there is an SDE reversing the forward heat flow in a sense that if we are initialized deterministically at Zμ ~ 8y at time O, then the law of the SDE at time h would be law( Zo Z2, = y) = x x Then, this SDE would serve as a continuous-time interpolation of the second step.
Such a time reversal SDE is indeed possible! The following SDE on )eejo. initialized at Zo ~ nT xx Pn ensures Zn- ~ law (2t) = x Ph-ti
dzz Vlog(T Ph- dl ddB for E [0.
(BH)
Although this designed to reverse (FH) initialized by Zu- ~ π X (so Zn Zi n ), its construc- tion also ensures that if 2 .g. a point mass, then 2í ~ law ZZ y) = π x Thus, if we initialize (BH) with Z ~ p then the law of 2 corresponds to f x d (3) = = Remark 1. We note that In-and- Out is exactly the proximal sampling scheme [26, 27, 29,27.29 for uniform distributions. The proximal sampler with a target density proportional to exp(-V considers an augmented distribution π (T. y) x cxp(-V(x)
1 | y)l?) and then repeats the following 2h
two steps: (1) Vi+1 ~ π x||==,, = (xx,, hTa) and then (2) F++1 ~ n x| Naïvely, the proximal sampler is implemented by performing rejection sampling, with the Gaussian centered at the minimizer of log π [Y=++++ the proposal. Realizing this would require projection oracle (to AC), which is only known to be implementable with (dd) membership queries. In-and-Out completely avoids the need for projection oracle.
4 Results
Our computational model is the classical general model for convex bodies [30]. We assume vol(K.) > 0 throughout this paper. Below, B, (z) denotes the d-dimensional ball of radius r centered at
Definition 4 (Convex body oracle). A well-defined membership oracle for convex body K. C Rd is given by a point zo E K, a number D > O, with the guarantee that B (zo) S K. C (D and an oracle that correctly answers YES or NO to any query of the form "x KC?"
Definition 5 (Warmness). A distribution μ is M M-warm with respect to another distribution ı if for every x in the support of π, we have du(x)) < MM dr(xx)
We now summarize our main result, which is further elaborated in Appendix B.4 (Theorem 5). Below, T is the uniform distribution over K,, and Ry is the Rényi-divergence of order (see Definition 1). Theorem 1 (Informal version of Theorem 5). For any given n, E (0, 1). q 2 1, and any convex body K. given by a well-defined membership oracle, there exist choices of parameters h, N such that In-and-Out, starting from an M --ram distribution, with probability at least
7,, returns X ~ a such that Rr ><)===x < e. The number of proper steps is Ogdd A log² M and the expected total number of membership queries is ÖlgMd Aogg L where is the largest eigenvalue of the covariance of k
Remark 2. Despite our guarantee being in the much stronger "metric" of Rg compared to the TV guarantees of Ball walk, we do not have to incur any additional asymptotic complexity.
To obtain this result, one should choose the following values for the parameters: h-1 (dl log 9MA log log 2), N = - gMg A Algg log"(1/s) ). See Lemma 3 for more details.
7
5

---

Finally, while the assumption of warmness for the initialization may seem strong at the outset, for well-rounded convex bodies (Ex~= I CPd for some constant C),, it possible generate an (1) warm-start with complexity (dd)) See [6, 31] for details.
We note that for X xx [|Cov(* olop tr(Cov(**)) EII|X EX]] S D²
The above guarantee in the Rényi divergence immediately provides W2, TV, KL, and x² guarantees as special cases. For two distributions μ and æ,, we have
1. KL(uI|=) π) = li Rg & Rg (4
du |||| m) S R (u|1=) & Roo (H][ sug sup de < g 959 d'
2. 2 1| - Illiv= S KL(# || π) & log(x (1 || r) + 1) R2(μ1 || T).
3. (H, (T) (L x) (Talagrand's T Tz-inequality) and CLsI(T*) 2 D².
4. W (1,, π) & (CpI(T) x² T) [32] and (P)( & [Cov((*) llap log d.
The query complexity is better the convex body is (near- (near- )isorropic, i.e., the uniform distribution over the body has (near- didenttty covariance. This relies on recent estimates of the worst-case Poincaré constant for isotropic log-concave distributions [33, 34]. The condition that the convex body is isotropic can be achieved in practice through rounding procedure [35]. See $5 for more details,
Corollary 1. Assume that -K is near-isotropic, i.e. the operator norm of its covariance is O(1). Under the same setting above, In-and- fh-and-Out succeeds with probability 1 T,, returning X p such that RggH x²*)= S s. The number of proper steps is Ogdd log? M. ), and the expected total number 7e
of membership queries dl log 1
Our analysis will in fact show that the bound on the number of proper steps holds for general non- convex bodies and any feasible start in K. This is deduced under an M-warm start in Corollaries 2 and 3. We remark that such a bound for non-convex uniform sampling is not known for the Ball walk or the Speedy walk.
Theorem 2. For any given & E (0, and set K. C (0) with vol(K) > O, In-and-Out with after the following number
variance and M M-warm initial distribution achieves Ry (mm 11=xxx of iterations:
CPI(TT*) m m-min min [O(gh=>CI((TT) log M) )
for 2, for 1.
(O(gh - ))lg log M
We have two different convergence results above under (LSI-I) and (PI). Under (LSI-l) we have logarthlogrit dependence on the warmness parameter M. On the other hand, using (PI), which is weaker than (LSI-l) (in general, Cpi < CLsi), the dependence on M is logarithmic. We discuss implications of our results further in $4.2.
4.1 Outline of analysis.
We first record two fundamental lemmas, which introduce the mathematical formalism for our analysis. The first is the existence of forward and backward heat flows (Lemma 12), which will interpolate each line in Algorithm 1. These flow equations describe how the laws of Z, and Z in (FH) and (BH) evolve respectively over time. All proofs are deferred to Appendix B. Lemma 1. The forward heat flow equation with initial distribution μu is given by
0,14 = 1 Apr.
and its backward heat flow equation is given by
d,p div (nt Vog((= 1og(=xXP--)) + DDpT with 15 p4
These admit (weak) solutions on [0, h] for any initial distribution pa with dag d
< M < co.
One successful iteration of In-and-Out exactly the same as the composition of running the forward heat flow and then backward heat flow, both for time h.

---

Lemma 2. Let fi be the law of the k-th iterate Dy of In-and-Out. If (FH) is initialized with law( Zo) = Pk
xx then law(Zn) = pltt If (BH) is initialized with law (55) -Mi then
law( (wx PR+1
We summarize our proof strategy below, which requires us to demonstrate two facts: (i) The current distribution should converge to the uniform distribution, (ii) within each iteration of the algorithm, the failure probability and the expected number of rejections should be small enough. In this section provide the main claims within each of these parts, and defer the remaining details to Appendix B.
While each individual component resembles pre-existing work in the literature, in their synthesis we will demonstrate how to interleave past developments in theoretical computer science, optimal transport, and functional analysis. The combination of these in this domain yields elegant and surprisingly simple proofs, as well as stronger results.
Part (i). Broadly speaking, we need to demonstrate that the corresponding Markov chain rapidly mixing. Here, we use the heat flow perspective to derive mixing rates under any suitable divergence measure (such as KL, x², or R2). This extends known results for the unconstrained setting [27]. To summarize the proof, by considering instead the solutions after small time t, we invoke known contraction results from [27] and then use a continuity argument to conclude the proof.
Theorem 3. Let y be the law of the k-th output of In-and- with initial distribution pă¹ Let CLSI be the (LSI-l) constant of the uniform distribution xx over K. Then, for any q 2
R (M) )
(1 + h/ CLsi (isi)2224 2k/9
For CpI the (PI) constant of nT
x2 (4 || (T < x2 )*)
+ h CCp)
Furthermore, for any g 2 2,
Ry (Mp |xx)= 24 log(lg((hhhcc (1 + -
if -
(R,, | )-1
Rg(M || n S
4
log(1 Fox(l+A/CCi //Oi))
cl 1 )-1)
if 2 ko = 2
The final result reduces the problem of obtaining a mixing guarantee to that of demonstrating functional inequality on the target distribution. For this, it not strictly necessary that I. be convex.
Part (ii). Convexity of IC is crucial this time unlike Part (i). We show in Appendix B.3 that the failure probability remains under control by taking a suitable variance h and threshold N, and that the expected number of trials per iteration is of order log N, not N. To do this, we apply detailed argument involving local conductance and the convexity of K., which relies on techniques from [36].
Lemma 3 (Per-iteration guarantees). Let K. be any convex body in Ed presented by a well-defined membership oracle, π the uniform distribution over K, and an M-warm initial distribution
log Z with respect to π For any given m E N and E (0, 1), set Z 9m (2 9), h = 2d log 7 and
N = Z log Z = Ō. Then, the failure probability of one iteration of In-and-Out is at most n/m, and the expected membership queries per iteration is O(M log* mM)
4.2 Discussion
No need to be lazy. Previous uniform samplers like Ball walk are made lazy (i.e., with probability 1/2, it does nothing), ensure convergence to the target stationary distribution. However, our algorithm does not need this, as our sampler is shown to directly contract towards the target.
Unified framework. We remark that Theorem 2 places the previously known mixing guarantees for Ball walk, Speedy walk a unified framework. Existing tight guarantees for Speedy walk are in TV distance and based on the log- log-Sebolev constant, assuming oracle for implementing each step [37].
7

---

The known convergence guarantees of Ball walk (see Appendix C for details), namely the mixing time of O of D2 log !) for TV distance, are for the composite algorithm [Speedy welk-reeection sampling]. Here Speedy walk records only the accepted steps of Ball walk, so its stationary distri- bution differs slightly from the uniform distribution (and can be corrected with a post-processing step). On the other hand, In-and-Out actually converges to x¹ without any adjustments and achieves stronger Rényi divergence bounds in the same asymptotic complexity. Our analysis shows that the mixing guarantee is determined by isoperimetric constants of the target (Poincaré or -og--obolev).
Effective step size. The Ball walk's largest possible step size is of order 1/vd (see Appendix C) to keep the rejection probability bounded by constant. This bound could also be viewed as an "effective" step size of In-and-Out, since the 2--norm of the Gaussian (0, hI) concentrated around Vhd and we will set the variance h of In-and-Out to (11/d),, so we have Vhd = 1/vd.
What has really changed? In-and-Out has clear similarities to both Ball walk and Speedy walk. What then are the changes that allow us to use continuous time interpolation? One step of Ball walk [random step (y E Bs(z) + Metropolii-filke filter (accept if y E X.)]. This filtering is an abrupt discrete step, and it is unclear how to control contraction. It could be replaced by step of Speedy walk (ar ~ Unif( (v) n K.). Then, each iteration of In-and-Out can be viewed as Gaussian version of a Ball walk's proposal + Speedy walk algorithm.
How can we compare In-and-Out with Speedy walk? Iterating speedy steps leads to a biased distribu- tion. As clarified in Remark 3, one step of (a Gaussian version of) Speedy walk can be understood as a step of backward heat flow. Therefore, if one can control the isoperimetric constants of the biased distribution along the trajectory of the backward flow, then contraction of Speedy walk toward the biased distribution will follow from the simultaneous backward analysis.
5
Related work
Sampling from constrained log- log-concave distributions is a fundamental task arising in many fields. Uniform sampling with convex constraints is its simplest manifestation, which was first studied as a core subroutine for randomized volume-compptation algorithm [1]. Since then, this fundamental problem has been studied for over three decades [2, 3, 4, 38, 5, 25, 24). We review these algorithms, grouping them under three categories geometric random walks, structured samplers, and diffusion- type samplers. Below, K is convex.
Geometric random walk. We discuss two geometric random walks Ball walk [3, 4] and Hit-and-Run [39, 17]. Ball walk is a simple metropolized random walk; it draws y uniformly at random from ball of radius ó centered at a current point x, and moves to if y E K. and stays x otherwise. In the literature, Ball walk actually refers composite algorithm consisting of [Speedy walk+ rejection sampling), where Speedy walk records only the accepted steps of Ball walk (see Appendix C for details). The step size ó should be set to (d-1/22 to avoid stepping outside of K. [4] showed that Ball walk needs (M Da log {) membership queries to be E-close to x² in TV, where D is the diameter of K,, and the warmness parameter M measures the closeness of the initial distribution to the target uniform distribution =
Hit-and- art-ann-Run-a is another zeroth- order algorithm that needs no step size; it picks a uniform random line l passing a current point, and move to uniform random point on En K. [5] shows that, if we define the second moment as R² ;= E xx~=x x [||- E. ]. then Hit-and-Run requires (d R² log M) queries. Notably, this algorithm has a poly-togarithmic dependence on M as opposed to Ball walk.
Both algorithm are affected by skewed shape of K. (i.e., large D or R), so these samplers combined with pre-processing step called rounding. This procedure finds a linear transformation that makes the geometry of I. less skewed and so more amenable to sampling. In literature, there exists a randomized algorithm [35] that rounds XC and generates a good warm start (i.e., M- = O(1), with Ball walk used as core subroutine. This algorithm takes up (c535) queries in total, and in such position with the good warm start, Ball walk only needs (dd log }) queries to sample from K
Structured samplers. The aforementioned samplers hased on geometric random walks require only access to the membership oracle of the convex body without any additional structural assumptions.
8

---

The alternate paradigm of geometry-aware sampling attempts to exploit the structure of convex constraints, with the aim of expediting the convergence of the resultant sampling schemes. One common assumption is to make available self-concorlart barrier function & which has regularity on its high-order derivatives and blows up when approaching the boundary aK. The Hessian of ø encodes the local geometry of the constraint, and the samplers often work directly with V²
The first canonical example of such a zeroth-order sampler is Dikin walk used when K. is given by m linear constraints [40]; it draws a uniform sample from an ellipsoid (characterized by V² of fixed radius around a current point, and is often combined with a Metropolis adjustment. [40] shows that Dikin walk mixes in O (md log M) - steps, although each iteration is slightly more expensive than one
membership query. This algorithi requires no rounding, but still needs a good warm-stat which can be achieved by an annealing-tyy algorithm using (mdd) iterations of Dikin walk [41].
Riemannian Hamiltonian Monte Carlo is structured sampler that exploits the first-order information of the potential (i.e., [log(1/z) [42]; its proposal is given as the solution to the Hamilton's ODE equation, followed by the Metropolis- filter. In the linear-constraint setting above, it requires O log Mr many iterations to achieve e-close distance to xx [18]. This sampler is further analyzed for practical ODE solvers [43] and for more sophisticated self-concordant barriers [44].
Similarly, Mirror Langevin [45, 46, 47, 48] is a class of algorithms which converts the constrained problem into an unconstrained one obtained by considering the pushforward of the constrained space by VΦ. The algorithm can also be metropolized [49]. The best known rate for this algorithm is (d _) under some strong assumptions on /b.
Diffusion-type samplers. Samplers based on discretizations of Itô diffusions, stochastic processes which rapidly mix in continuous time, have long been used for sampling without constraints [19, 20, 21, 28]. While the underlying stochastic processes generalize easily to constrained settings, the discretization analysis relies crucially on the smoothness of the target distribution. This is clearly impossible to achieve in the constrained setting, so some techniques are required to circumvent this difficulty. These algorithms, however, generalize easily to the more general problem of sampling from distributions of the form H α ee '1,,, by incorporating first order information from f.
The first approach for adapting diffusion-based samplers [50, 25, 51] iterates two-step procedure. First, a random step is taken, with 14+1/2 ~ (xx,, 2hTa) for some appropriately chosen step h, and then project it to XC, i.e., +2+1 = projx (xx+1/2). The complexity is given in terms of queries to a projection oracle, each call to which can be implemented with polynomial number of membership oracle queries; total of ((d ((d")"/e*) /e*) queries are needed to be E-close in W2 to x Another approach, which uses an algorithmically designed "soft" penalty instead of a projection, was proposed in [52], and achieves a rate estimate (ddc2)).
A second approach, suggested by [24], considers a different proximal scheme, which performs a called
"soft projection" onto K, by taking steps like ((11 - hy 122 + (=)) Moreau- Yosida regularized Langevin, named after an analogous regularization scheme for constrained optimization. This scheme also relies on access to a projection oracle for K., and quantifies their query complexity accordingly. Their final rate estimate is Odd% to be e-close in TV distance to X
Observing the prior work integrating diffusion based sampling with convex constraints, the de- pendence on the key parameters d, e, while polynomial, are many orders worse than the rates for zeroth-order samplers such as Ball walk, Hit-and-Run. In contrast, our analysis not only recovers but in some sense surpasses the known rates for Ball walk, Hit-and-Run, while harmonizing well with the continuous-time perspective of diffusions.
Proximal schemes for sampling. The Gibbs sampling scheme used in this paper was inspired by the restricted Gaussian oracle introduced in [26] (in turn inspired by Gaussian Cooling [6]), which alternately iterates between a pure Gaussian step, and a "proximal" step (which we elaborate in our exposition). This scheme was given novel interpretations by [27], which showed that it interpolates the forward and backward heat flows, in the sense defined by [53]. The backward heat flow itself is intimately related to stochastic localization schemes, invented and popularized in [54, 55].
A gradient step can be added in the more general case, for sampling from x

---

This formulation proved surprisingly powerful, allowing many existing rates in unconstrained sam- pling to be recovered from a relatively simple analysis. This was further extended by [29] to achieve the current state-of-the-art rate in unconstrained sampling. Finally, [56] suggest that this could be applied to tackle some constrained problems. However, the assumptions in this final mentioned work are not compatible with the uniform sampling problem general convex bodies.
Conclusion
We propose In-and- Aut-Outtoa for uniform sampling on convex bodies, and show that obtains guarantees in Ry divergence from an M-warm start, substantially stronger than prior work, and without increasing the computational complexity. Notably, our proof technique quite different and provides direct reduction to isoperimetric constants of the targer distribution.
While the current work focuses uniform sampling of convex bodies, there number of natural extensions that may be considered. It may be possible to prove analogous results for general log- concave distributions, and on non-log-concave distributions satisfying isoperimetric inequalities, e.g., it is open to find a polytime algorithm for sampling a general distribution satisfying Poincaré inequality presented by a function oracle (with no smoothness assumptions).
Acknowledgements. We are deeply grateful Andre Wibisono and Sinho Chewi for helpful comments and pointers to the literature for Lemma 10. This work was supported in part by NSF award 2106444, NSERC through the CGS-D award, and Simons Investigator award.
References
[1] Martin Dyer, Alan Frieze, and Ravi Kannan. A random polynomial-time algorithm for approxi- mating the volume of convex bodies. Journal of the ACM (JACM), 38(1):1-17, 1991.
[2] László Lovász and Miklós Simonovits. The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume. In Foundations of Computer Science (FOCS), pages 346-354. IEEE, 1990.
[3] László Lovász and Miklós Simonovits. Random walks in a convex body and an improved volume algorithm. Random Structures & Algorithms (RS&A), 4(4):359-412, 1993.
[4] Ravi Kannan, László Lovász, and Miklós Simonovits. Random walks and (*())) volume algorithm for convex bodies. Random Structures & Algorithms (RS&A), 11(1):1-50, 1997.
[5] László Lovász and Santosh S Vempala. Hit-and-run from a corner. SIAM Journal on Computing (SICOMP), (5(44):85-1100) 2006.
[6] Ben Cousins and Santosh S Vempala. Gaussian Cooling and (*(1²) algorithms for volume and Gaussian volume. SIAM Journal on Computing (SICOMP). 47(3):1277-1275 2018.
[7] Ben Cousins and Santosh Vempala. A practical volume algorithm. Mathematical Programming Computation, 8(2):133-166) 2016.
[8] Hulda S Haraldsdóttir, Ben Cousins, Ines Thiele, Ronan MT Fleming, and Santosh S Vempala. CHRR: coordinate hit-and-rum with rounding for uniform sampling of constraint- models. Bioinformatics, 33(11):144111433 1017 2017.
[9] Yunbum Kook, Yin Tat Lee, Ruoqi Shen, and Santosh S Vempala. Sampling with Riemannian Hamiltonian Monte Carlo in constrained space. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pages 31684-31696, 2022.
[10] Nathan E Lewis, Harish Nagarajan, and Bernhard O Palsson. Constraining the metabolic genotype-phenotype relationship using phylogeny of in silico methods. Nature Reviews Microbiology, 10(4):291-305, 2012.
10

---

[11] Ines Thiele, Neil Swainston, Ronan MT Fleming, Andreas Hoppe, Swagatika Sahoo, Maike K Aurich, Hulda Haraldsdottir, Monica L Mo, Ottar Rolfsson, Miranda Stobbe, et al. community-driven global reconstruction of human metabolism. Nature Biotechnology, 31): 419-425, 2013.
[12] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Foundations of Computer Science (FOCS), pages 94-103. IEEE, 2007.
[13] Ilya Mironov. Rényi differential privacy. Computer Security Foundations Symposium (CSF), pages 263-275. IEEE, 2017.
[14] Eli Bingham, Jonathan P. Chen, Martin Jankowiak, Fritz Obermeyer, Neeraj Pradhan, Theofanis Karaletsos, Rohit Singh, Paul A. Szerlip, Paul Horsfall, and Noah D. Goodman. Pyro: Deep universal probabilistic programming. The Journal of Muchine Learning Reseurch (JMLR), 20: 28:1-28:66 2019.
[15] Stan Development Team, RStan: the R interface to Stan, 2020. URL http:hhtttttt...te sta...rg/..........o.ooo.o R package version 2.21.2.
[16] Santosh Vempala. Geometric random walks: survey, Combinatorial and Computational Geometry, 52(573-612):2, 2005.
[17] László Lovász. Hit-and-run mixes fast. Mathematical Programming, 86:443-4611 1999.
[18] Yin Tat Lee and Santosh S Vempala. Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation. In Symposiun on Theory of Computing (STOC), pages 1115 1121, 2018.
[19] Julian Besag, Peter Green, David Higdon, and Kerrie Mengersen. Bayesian computation and stochastic systems. Statistical Science, pages 3-41, 1995.
[20] Arnak S Dalalyan and Alexandre B Tsybakov. Sparse regression learning by aggregation and Langevin Monte-Carlo. Journal of Computer and System Sciences, (8(5):1423-144) 2012.
[21] Arnak Dalalyan. Further and stronger analogy between sampling and optimization: Langevin Monte Carlo and gradient descent. In Conference on Learning Theory (COLT), pages 678-689. PMLR, 2017.
[22] Alain Durmus, Szymon Majewski, and Blazej Miasojedow. Analysis of Langevin Monte Carlo via convex optimization. The Journal of Machine Learning Research (JMLR), 2061):266--2711, 2019.
[23] Santosh S Vempala and Andre Wibisono. Rapid convergence of the unadjusted Langevin algo- rithm: Isoperimetry suffices. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019.
[24] Nicolas Brosse, Alain Durmus, Éric Moulines, and Marcelo Pereyra. Sampling from a log- concave distribution with compact support with proximal Langevin Monte Carlo. In Conference on Learning Theory (COLT), volume 65, pages 319-342. PMLR, 2017.
[25] Sébastien Bubeck, Ronen Eldan, and Joseph Lehec. Sampling from log-concave distribution with projected Langevin Monte Carlo. Discrete & Computational Geometry (DCG), 59:757-783, 2018.
[26] Yin Tat Lee, Ruoqi Shen, and Kevin Tian. Structured logconcave sampling with restricted Gaussian oracle. In Conference on Learning Theory (COLT), pages 2993-3050, PMLR, 2021.
[27] Yongxin Chen, Sinho Chewi, Adil Salim, and Andre Wibisono. Improved analysis for proximal algorithm for sampling. In Conference on Learning Theory (COLTT), pages 2984-3014. PMLR, 2022.
[28] Sinho Chewi. Log-concave sampling. Book draft available at https://chewisinhoo wtwpiiiiiiiooiigttub.b... github. io, 2024.

---

[29] Jiaojiao Fan, Bo Yuan, and Yongxin Chen. Improved dimension dependence of a proximal algorithm for sampling, In Conference on Learning Theory (COLT), pages 1473-1521. PMLR, 2023.
[30] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algoritims and combina- torial optimization, volume 2. Springer, 1988.
[31] Yunbum Kook and Matthew Zhang. Rényi-infinity constrained sampling with de membership queries. In To appear in Symposium on Discrete Algorithms (SODA), 2025.
[32] Yuan Liu. The Poincaré inequality and quadratic transportation- variance inequalities. Electronic Journal of Probubility, 25(1):1-16, 2020.
[33] Ravi Kannan, László Lovász, and Miklós Simonovits. Isoperimetric problems for convex bodies and localization lemma. Discrete & Computational Geometry, 13(3):541-555 1995.
[34] Boáz Klartag. Logarithmic bounds for isoperimetry and slices of convex sets. Ars Inveniendi Analytica, 2023.
[35] He Jia, Aditi Laddha, Yin Tat Lee, and Santosh S Vempala. Reducing isotropy and volume to KLS: an O (n(2(p)) volume algorithm. In Symposium on Theory of Computing (STOC), pages 961-974, 2021.
[36] Mikhail Belkin, Hariharan Narayanan, and Partha Niyogi. Heat flow and a faster algorithm to compute the surface area of a convex body. In Foundations of Computer Science (FOCS), pages 47-56. IEEE, 2006.
[37] Yin Tat Lee and Santosh Srinivas Vempala. Eldan's stochastic localization and the KLS hyperplane conjecture: An improved lower bound for expansion. In Foundations of Computer Science (FOCS), pages 998-1007. IEEE, 2017.
[38] László Lovász and Santosh S Vempala. Hit-and-run is fast and fun. preprint, Microsoft Research, 2003.
[39] Robert I. Smith. Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions. Operations Research, 1266):1296-13000 1984.
[40] Ravindran Kannan and Hariharan Narayanan. Random walks on polytopes and an affine interior point method for linear programming. Mathematics of Operations Research, 37(1):1-20, 2012. 22.
[41] Yunbum Kook and Santosh S Vempala. Gaussian Cooling and Dikin walks: The Interior-Poin Method for logconcave sampling. arXiv preprint arXiv:2307.12943: 2023.
[42] Mark Girolami and Ben Calderhead, Riemann manifold Langevin and Hamiltonian Monte Carlo methods. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 73 (2):123-214, 2011.
[43] Yunbum Kook, Yin Tat Lee, Ruoqi Shen, and Santosh S Vempala. Condition- independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical in- tegrators. In Conference on Learning Theory (COLT), volume 195, pages 4569. PMLR, 2023.
[44] Khashayar Gatmiry, Jonathan Kelner, and Santosh S Vempala. Sampling with barriers: Faster mixing via Lewis weights. arXiv preprint urXiv:2303. 000800, 2023.
[45] Kelvin Shuangjian Zhang, Gabriel Peyré, Jalal Fadili, and Marcelo Pereyra. Wasserstein control of mirror Langevin Monte Carlo. In Conference on Learning Theory (COLT), pages 3814-3841. PMLR, 2020.
[46] Qijia Jiang. Mirror Langevin Monte Carlo: the case under isoperimetry. Advances Neural Information Processing Systems (NeurIPS), 34:715-725, 2021.
[47] K Kwangjun Ahn and Sinho Chewi. Efficient constrained sampling via the mirror-Langevin algorithm. Advances Neural Information Processing Systems (NeurIPS), 34:28405-28418, 2021.
12

---

[48] Ruilin Li, Molei Tao, Santosh S Vempala, and Andre Wibisono. The mirror Langevin algorithm converges with vanishing bias. In International Conference on Algorithmic Learning Theory (AI.7), pages 718-742. PMLR, 2022.
[49] Vishwak Srinivasan, Andre Wibisono, and Ashia Wilson. Fast sampling from constrained spaces using the Metropolis-adjusted mirror Langevin algorithm. arXiv preprint arXiv:2312.08823, 2023.
[50] Sebastien Bubeck, Ronen Eldan, and Joseph Lehec. Finite-time analysis of projected Langevin Monte Carlo. In Advances in Neural Information Processing Systems (NeurIPS), volume 28, 2015.
[51] Joseph Lehec. The Langevin Monte Carlo algorithm in the non-smooth log-concave case. The Annals of Applied Probability, 33(6A):4858 4874, 2023.
[52] Mert Gürbüzbalaban, Yuanhan Hu, and Lingjiong Zhu. Penalized Langevin and Hamiltonian Monte Carlo algorithms for constrained sampling. arXiv preprint arXiv:22/2.0055 2022.
[53] Boáz Klartag and Eli Putterman. Spectral monotonicity under Gaussian convolution. arXiv preprint 2tt.:..90099999 2021.
[54] Ronen Eldan. Thin shell implies spectral gap up polylog via stochastic localization scheme. Geometric and Functional Analysis (GAFA), 23(2):532-569, 2013.
[55] Yuansi Chen. An almost constant lower bound of the isoperimetric coefficient in the KLS conjecture. Geometric and Functional Analysis (GAFA). 31:34 61, 2021.
[56] Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, and Kevin Tian. Algorithmic aspects of the log-Laplace transform and a non- non-Euclidean proximal sampler. In Conference on Learning Theory (COLT), volume 195, pages 2399-2439, PMLR, 2023.
[57] Bo Yuan, Jiaojiao Fan, Jiaming Liang, Andre Wibisono, and Yongxin Chen. On a class of Gibbs sampling over networks. In Conference on Learning Theory (COLT), pages 5754-5780. PMLR, 2023.
(58) Djalil Chafai. Entropies, convexity, and functional inequalities, on phi-entropies and phi-soboley inequalities. Journal of Mathematics of Kyoto University, 44(2):325-3633 2004.
[59] Patrick Billingsley. Probability and measure. John Wiley Sons, 1995.
[60] Luigi Ambrosio, Nicola Fusco, and Diego Pallara. Functions of bounded variation and free discontinuity problems. Oxford University Press, 2000.
[61] Ravi Kannan, László Lovász, and Ravi Montenegro. Blocking conductance and mixing in random walks. Combinatorics, Probability and Computing. 15(4):541-570 2006.
[62] Jeff Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. Problems in analysis, 625(195- 1995:199):110 1970.
[63] Emanuel Milman. On the role of convexity in isoperimetry. spectral gap and concentration. Inventiones Mathematicae, 177(1): 2009.
[64] Michel Ledoux. A simple analytic proof of an inequality by P. Buser. Proceedings of the American Mathematical Society, 121(3):551-95) 1994.
[65] Boáz Klartag and Joseph Lehec. Bourgain's 's slicing problem and KLS isoperimetry up to polylog. Geometric and Functional Analysis (GAFA), 32(5): 134-1159, 2022.
[66] Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
[67] Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient flows: metric spaces and in the space of probability measures. Springer Science & Business Media, 2005.
13

---

A
Helpful lemmas
Before proceeding, we state two important lemmas which are needed for our proofs. The first the data-proesssing inequality for Rényi divergence and f-divergence, given below.
Lemma 4 (Data-processing inequality). For measures μ4, Markov kernel P. f-divergence Dj, and q 2
holds that
Dy(uP) vP) S Dy(m and Rg vP) - R2
Functional inequalities allow to show exponential contraction of various divergences, through the following helpful inequality.
Lemma 5 (Grönwall). Suppose that 9 : [0, T] + R are two continuous finctioon,, with being differentiable on [0. I' and satisfying
u' (t) S g() u(t)
for all [0, T].
Then,
u(t) S exp(S/ ((s) ((s) ds u()) for all [0.T].
B Analysis
Before proceeding, first give the proof of Lemma in the main text. A more general version of Lemma proved in the form Lemma 12.
Proof of Lemma 2. We explicitly show that the forward and backward heat flows indeed interpolate the two discrete steps given Algorithm 1. For the forward part, we have Zn = Zo + for ~ NO, hla), so
law (n) (Zw (N,,, = 1 * hl, = -K
Regarding the backward part, it is known from [27, Lemma 14] that the construction of the time- reversal SDE ensures that (Z₁ 4 and (Zo, Zn) have the same joint distribution, when Zo x² (and so Zn ).). Hence, law 2 1/5 y) law( Zo) y) π x\\==,, where the last equality follows from (Zo, Zn) w. Since initialize (BH) with Z y 1 have
/ law Z Z = 8) (dy) /
law (2
XIX (.19) (dy) Mk+1
where the last follows from the definition of Line 3.
B.1 Functional inequalities
The contraction of an outer loop of algorithm is controlled by isoperimetry of the uniform distribution x which is described precisely by a functional inequality. The most natural ones to consider in this setting are the Poincaré inequality (Pl) and log-Sobolev inequality (LSI-I). In Appendix D. we provide a more detailed discussion of how these are related to other important notions of isoperimetry, such as the Cheeger and Tog-Cheeger inequalities.
Below, we use μt, v to denote two arbitrary probability measures over R4, The relationship between a de into (PI).
Poincaré inequality and the x2 divveeegee derived by substituting f du
Lemma 6. Assume that satisfies (PI) with parameter Cpi(v). For any probability measure μ over Rd with & it holds that
Cpi(v)
du
22 P)
E.
dv
The Poincaré inequality implies functional inequalities for the Rényi divergence.
14

---

Lemma' 7 ((23, Lemma 91). Assume that v satisfies (PI) with parameter Cpi(v). For any g 2 2 and probability measure y over TR,, it holds that
exp( (1 u)) - q (pile) ( v),
where RFg (p]l := E,, ( V log de q of ja with respect
|1 E. 1( (d))) is the Rényi Fisher information of order
du
The log-Sobolev inequality paired with the KL-divergence (LSI-II) can be understood as special case of the following inequality paired with the q-Rényi divergence for q 1.
Lemma 8 ([23, Lemma 5)). Assume that satisfies (LSI-II) with parameter CLsI(V). For any q 2 1 and probability measure over R&, it holds that
Ra(u (1 Cisilv))
RF v).
2
Note that limg-11 R2 KL and RF, FI.
We have collected below the functional inequalities used to establish the mixing of our algorithm (see Appendix D for detailed presentation).
Lemma 9. Let K. C TRd be convex body with diameter D, and a be the uniform distribution over K.. Then, (T)( (T) $ ((Cov(z)llee llop log d and CLSI(T) X D2 If is isotropic, then CP((T) E log d and CLSI(T) x D.
B.2
Contraction and mixing
We start by analyzing how many outer iterations of In-and-Out are required to be 8-close to x the uniform distribution over K. The contraction of Algorithm I comes from analyzing Lines and through the perspective of heat flows (see $3). To exploit this view, we first revisit the previous contraction analysis [27], which is carried out for distributions with smooth densities. Although the uniform distribution is not even continuous, we prove a technical lemma (Lemma 12) that enables us extend previously known results the uniform distribution. Lastly, combining the previous results with our technical lemma, we obtain clean contraction results of Algorithm toward the uniform distribution x Theorem 3.
Part I: Contraction analysis for smooth distributions. In this part, review the contraction results for heat flow and its time-reversal [27]. which are intimately connected with our algorithm. We also provide key technical ingredients needed for its proof, such the computations for measures evolving under simultaneous forward/backwart heat flows. We refer interested readers to Appendix for additional details. Only in Part I, assume that v denotes probability measure with smooth density.
Forward heat flow. Fokker-Planck equation), which describes the evolution of the law of Ze under (FH),
We begin by introducing the "heat flow" equation (or also known as the
o, Apt: = div(14 log
(FP-FH)
well known that one can realize this equation in discrete time through a Gaussian transition density, in the sense that, for yn (the solution at time h > 0 to (FP-FH) with initial condition μo), and for any smooth function f IRd + R.
Eyn [(() = Ey (P)S(=)),
where (x)( = EN( By this we can formally identify n4 = PoPh. and also write μ4, for the law of Zn,, where (7h) J120 solves (FH).
p Such inequalities are often called Polyak-Lojasienn Lojasiewicz inequalities, which say for f R - R. and all y E Rd that fly) 5 a //V f(y)ll for some constant c, min f(x) 0.
"(P h22 is often called the heat semigroup.
15

---

Backward heat flow. Although there are many ways to define a "reversal" of Ph, we will use the notion of adjoint introduced by [53], which is the most immediately useful.
Given some initial measure v and some time horizon h, the adjoint corresponds to reversing (FH) for times in [0, hi when the initial distribution under consideration is Zo ~ V. For other measures, it must be interpreted more carefully, and is given by the following partial differential equation starting from some measure M (see (E.1) and its derivation):
1 + + A5 for E h0,
d.pt div V Vlog(uPa-.))
(FP-BH)
Write 14 Mo 0,ah where (Qt he([o.t] is family of transition densities. Write Pu,h for the joint distribution of the (Zo, Zp, m of (FH), when Zo and Poja for the conditional. Note that P Pajo(-[z) = (z, hla). It is also known that (FP-BH) gives time-reversal of the heat
equation at the SDE level, in the sense that we can interpret 6 2 = (o = x). Thus
MO 0% P (-IZa xx) MD (dx), and vPhQt uPr- for all ( E [0. h).
The ultimate purpose of this machinery to affirm our earlier description of the Gibbs sampling procedure as alternating forward and backward heat flows. Indeed, notice that, if μu is the law of the iterate at some iteration i, then μi: Pr. is precisely po+1 under our scheme, while (n, Pr)
is - assuming Q% .A is well defined for non- non-smooth measures πx Thus, while Algorithm is implemented via discrete steps, it can be exactly analyzed through arguments in continuous time. We shall see the benefits of this shortly.
Instead of considering the change in metrics along the evolution of uP, with respect to "fixed" will be useful to consider the simultaneous evolution of uPt, vP; (and similarly uQq. (vP))Q.). This type of computation was carried out for specific metrics in earlier work [23, 27]. The following a more generalized form of one appearing in [57, Lemma 2]. the lemma below, we consider an arbitrary diffusion equation with corresponding Fokker-Plann equation:
1
dX2- = (x.))) di + dB, and dept = - (bijae) + 2 Apr
(B.1)
where by Rdd Rd is smooth, X, Rd and μ4 Law(X,) if Xo ~ No-
Lemma 10 (Decay along forward/backwar heat flows). Let (Ht) (4)))2, (vi)120 denote the laws of the solutions to (B.1) starting at Ho, Vo respectively. Then, for any differentiable function g.
0.g(Ds(ue v.)) - (Dy(me v1) x Ey, (V(f'
log
Vt
Proof. The case where g id is application of the chain rule, it suffices take g = id and simply differentiate an f-divergence.
For brevity, we drop the variable of functions involved, and proceed as follows:
O.D |l m.) = /(1 Mt ) (f'
14 1i
("t)'u
V
dx
us
/ Onee (t) -f'o
-
14
+ (f'
Mt ) dx
v4.
V1
v4.
3 / (-V- (brvi) + 1 = (fo
- (f'
He Ht
dx
v1
(f' -|-- (bipe) + Ap) Mi dr, ui
where in (i) we substitute the F-P equation from (B.1). Integrating by parts (i.c., ʃ div(G) - -[( G) for a real-valued function ff and vector-valued function G), we have that
=
f1-V. (b
14) dx 21
(f'
Mt " Me dx.
(B.2)
On the other hand, we have that
- /1 (-va)(b
) dr
au--/1
(bive 14 (f" 14 + (f
14 |+))"" 14 dx.
us ve
vi
vs u1
16

---

The second term cancels with the RHS of (B.2). We have a similar cancellation for the 2/2 Av, term:
/ 2 (fo
Me dx
Vir
(f'
Mt V Mt 14
dx.
14
2
14
and - | Au (f' o M4 1 dx =
/ 1
Vul,
1t
(s
M
) + (f
a
1te
) 14t
dz.
Vi
2
V
vt
V Vi
Combining these, we are left with
-|- (bru)) [
(f H
- (f'
Ht ft
dx
Vt
Vt2
/bier (bilt
Vvi, V (f'
He H4 dr
2
14 14
/ (bapue 24 Vlog Ue, V (
)
dr.
V/
Finally, we note that
1 _ /1-V (brlte) + 2 un
(f' [ dx =
/ (Dite
Vuc vf''
1
[ dx
2
beite - 2 th log Hr, Vi' o 4) dr.
1
Putting it all together, noticing that the drift terms cancel, we left with
log 0(D | (1) -- / (u
Me ( da - 2 Bus bi
(s'
v
He log
( U4
)
which completes the proof.
To recover the decay result for the q-Rényi divergence, one can substitute g = 1 log x and q-1 fx) = For the xi-diverg,ece, instead substitute g(x) = x and f(x) x² 1. From this, we can obtain single step of decay for the Rényí and -divergences under different functional inequalities.
Before proceeding, we need a standard lemma on functional inequalities under (FH).
Lemma 11 (Functional inequalities under Gaussian convolutions, [58, Corollary 13]). The following inequality holds for any π with finite log- too-Sooolev and Poincaré constants,
Cp)( CPI(T) +t, and (L))(TPP)) S CisI(TT) t.
Combining the previous two lemmas, we can establish contraction between μPhQu and v after one forward/backwart iteration.
Theorem 4 ([27, Theorem and 4]). Assume v. a measure with smooth density, satisfies (LSI-I) with constant Cisi. For any q 2 1 and initial distribution μ with a smooth densiry, denoting again Qa = hu
Ru v)
Ru (1 h/Cisi)2/v
If y satisfies (PI) with constant Cpi, then it follows that
x² v)
X(uPhQulll)s
(1 h/Cp)
Moreover, for all q 2,
(u v)
2 log( + hh/mm))
(2 || () 2 1,
RnluPhQn 11
R2 (2)
if (H v) 1.
(1+h/Ca)77
17

---

Proof. Since the SDE in (B.1) captures the forward heat flow (FH), we set Ao and Pu in Lemma 10 to μ and v, respectively, obtaining contraction along the forward heat flow as follows: Substituting the q-Rényi into Lemma 10, we have, from the definition of the Rényi divergence as (1 v)
9-1
1 (= 1). with f(x)= = x² - 1 and g(x)
log( + 1),
EuP.
V
uPPt UP
Vlog uPt
(rR 1P))
9
2
(u
1) Eup,
u.P
91
9-2
EaP
PPP PPPt
(V
u.P PP
V log uP) pP
2
EuP.
P.Ps PP
E
Epp.
uPc
?
V
log
Pif vf:
1|2
9
1
RF (Fg(uP)
|| (PP),
(4)
2
Eup,
P.Pt vP
2
where in (i), we use again that ([s(( = V
( and (1i) uses that
+
V.
uPr v log uPt and the last equality recalls the definition of the Rényi Fisher information. PPt DP.
This yields
(uR, vP.) RF || PP)) < 1 (uP, vP:)
1 R (aP: vP:)
<
(2) q Cis((P:)) (18)
q
CLSI +
where we used Lemma 8 in (+) and Lemma 11 in (ii). Applying Grönwall's inequality (Lemma 5),
R2 || vPh) S exp (-1 CLsi+t
1 Rt)
Ry () v) (1) (1 +1+h/C h/+i/Cis))'V
Since the SDE (B.1) also captures the backward equation (BH), we set and vo in Lemma 10 to uPh and = vPr respectively, obtaining contraction along the backward heat flow:
arRr(uPhQi (Q.) RF
FF (uPh:t (Q:)
S Ru(uPh. 11 (Q.)
R2(PPh00 (Qi)
(is((Q())
(1)
C + h
where (i) follows from that FQ2 = vP vph- and Cis(((Q)) S h-t due to Lemma 11. Applying Lemma 5 again yields
Rg(uPh ()
Pu(P (1 h/CLsi)
Composing these two inequalities leads the decay rate claimed in the theorem.
The result in the -iveeeegee can be derived entirely analogously. For instance, the decay from the forward part can be shown as follows:
x2 uPP) CPI(vP,)
(² || vPt)
0,x² 0,x² (uPP - E.p.
vP..
Opi +t
where (i) follows from Lemma 6. Applying Grönwall's inequality then gives
(u wPA) S exp (-J, h
ct (- xt)x2 (1)) < 1+
The decay along the backward heat flow in x² is entirely analogous to the Rényi case. Then we combine two contraction results from the forward and backward flows, completing the proof.
The result in the R2 under (PI) can be shown in similar manner. Only difference is that in forward and backward computations, one should use the functional inequality in Lemma 7 and the following standard inequalities:
if [1) 21,
- exp(-RR(1 11 2 (M 1)
(R 1.
18

---

Part II: Extension to constrained distributions. We now prove a technical lemma that extends the contraction results to constrained distributions. This lemma guarantees the existence of weak solutions to two stochastic processes that describe the evolution of distributions involved in Line 2 and In-and-Out, in addition to lower-semicontinuity of f-divergence. We shall prove for any measure that is absolutely continuous with respect to x since this imposes no additional technical hurdles.
Lemma 12. Let v be a measure, absolutely continuous with respect to the uniform measure xx The forward and backward heat flow equations given by
Oepe = AAp. 2
d.p4 = div( Vlog(uPa--)) + - with P phh
admit solutions on (0, ft.. and the weak limit lime Hi 1hj exists for any initial measure μi with bounded support. Moreover, for any f-divergence with f lower semi-continuous,
Dy(mh [1) & lim D
A00
Proof. The existence of weak solutions for the forward equation is well-known, since 1o can be weakly approximated by measures with continuous density, for which the heat equation admits unique solution for all time. In particular, the weak solution is C for t > 0.
The reverse SDE is more subtle, since log vP: will in general cease be Lipschitz as 0. On the other hand, for any h > 0, we can write explicitly
1 Ma (x) (2th)a/2
|| y13 dpo(v).
exp(
2h
considers the system started at Au = the =up and solve the forward-backward Pokker-Plande equations on times [0, h - e), then fin- = pb = P/
Ao and
exp(
| y 2 2 6
1 -
dun(y).
Tepp(
2 3
(P.(z)
This follows from that if we consider system started at time e > 0, with initial distribution Jec, then we obtain the above through the Bayesian perspective on the forward and reverse heat semigroups, elaborated in Appendix E.
We now show that the following integral is indeed integrable, 2 is well-defined:
ih (x) /
exp(
| vll
((())
2h
du)(v)
exp
((22) de
2h
For fixed and h/2,
f exp(
||= - y/ (()) dz 2 exp( (lly Fo l1 + D)2 2(h
2(h e)
as the support of is constrained to K. c BD(xo). Since li has bounded support, mn(v) S exp( [el for some constant a > 0. Thus,
exp(
| 2(h-c)
(1)(v)
exp
|x-1|| 2(h-c)
(1)
f exp(
= =- vP (2) 2[h-e]
exp(
(1l -1y-=00 no D)
2(h-c)
(2(x - I0), 8) + 2DIly xoll
||yll
S exp
h
and the last bound is integrable in y.
19

---

We then show the pointwise convergence of p to 2 as - 0. Note that vPc - V, as v has bounded support. Also, the denominator independent of due to
(2 - c))aa/ /
=| y11 x -
2(h
Hence, for S d-1
exp
2(h-c)
h
4/2
exp
2h
S expp
| 111 (c) dz
h
feepp(
| 12-y/
(z(2)
2(h-r)
x
exp
2h
f exp(
1-->|1 [z(
dz
2h
As shown above, the last bound is integrable with respect to Hh, the dominated convergence theorem implies
|| exp(
exp(
x 1==vvl =-- )v(2) dz
lim c-0
2(h 2(h-c)
dun(y)
2h
dun(y),
[ /exp(=
vll 2(h-c) Pc
Sexp(
Thus, the pointwise convergence follows. Note that take vxxx) x* the distribution of the backwards step of our algorithm. particular, this corresponds to first sampling x ~ ph, then ~ Q% (-Iz), which is precisely the law of 14 given by (FP-BH).
val( then ii
1x(#)
As for the second statement, it follows from Scheffé's ' lemma [59, Theorem 16. 12] that the pointwise convergence of ph- + fij leads its TV-oonvergence, which in turn implies the weak convergence. It follows from lower semicontinuity of Dy [60, Theorem 2.34] that the weak convergence ensures (5(1t || v) < limæto D (1 -.)))
In the sequel, we will only consider = xx Since the Rényi divergence is a continuous func- tion of the x divergence (see Definition 1), which itself is f-divergence, it enjoys the same lower-semicontiniity properties. Using this lower-semicontiniity together with the decay results in Theorem 4, can easily derive the contraction results of In-and-Out in R, and x2 for any 1. We remark that this result does not require convexity of K.
Proof of Theorem 3. Let set μi0 jnd and me X Then, pa H6 and 14 = frr Th = xx For small > 0, as μ. = (p ) p *0, ela) is -mooth, we can now invoke the decay results with step size h-c )- respectively when t Rg and क- x²
Th -
in Theorem Thus, for contraction constants
C. (1 + Cisite)
h-c )-2/ and C. (1 Chete
o11 m.) s C. +(u me) C. $(Fo || mo),
where we used the data-procsssing inequality for the last inequality. By the second result of Lemma 12, sending - leads to
(N²
X || , (nn mn) < C T ll mo) C DZ m*)).
Repeating this argument times completes the proof.
B.3 Failure probability and wasted steps
We begin by defining a suitable version of local conductance [4]. Definition (Local conductance). The local conductance
12d is defined by
def JK exp(
24 | vll?)
Jxc exp( 24 ||
vl13) dy
((x)
Jg exp(
24 || u
dy
(2th)d/2
The local conductance at y quantifies the success probability of the proposal in Line 3. Then the expected number of trials until the first success of Line is 1/E(y). Revisiting (3.1), we can notice nt (v) /(v)/ v(y))vol(CC.
20

---

Naïve analysis for expected number of trials. Starting from π² when we just naïvely sample from π X (-1z) for all a without imposing any failure condition, the expected number of trials for one iteration that for the probability density Ps of (x, fild).
J. ElV) (a)))))
1
(dx) (dd))
n (dy)
E(y) dy JRc fly) vol(K)
aa E(y)
This suggests that one should consider the algorithm having "failed" if the number of trials exceeds some threshold.
Refined analysis under a failure condition. Going forward, we assume an M-warm start as in duu
previous work for uniform sampling algorithms. By induction we have di S M for all
Lemma 13 (Propagation of warm-start). From M M-warm start, have du. faz
M for all i.
Proof. Assume that x satisfies the M-warm start. Then, for any measurable S and the transition kernel Tr of Algorithm 1 at x7,
(S) = [ (x) M T,(S))a MMT
where the last equality follows from the stationarity of Hence, / S M.
We now establish lemma that comes in handy when analyzing the failure probability of the algorithm. In essence, this lemma bounds the probability that taking Gaussian step from x in Line gets 5-distance away from K. Let us denote the ô-blowup I by K&s == {o R2 d(x, XC) I 83.
Lemma 14. For a convex body K. C TRd containing unit ball B1 (0).
8²
nt (KC) S exp(- + 8d)
2h
Proof. For E ÖKg, we can take the supporting half-space H (z) at projx (v) containing K,, due to convexity of K. Then,
(K2) = vol(K) / / exp(- 2 11y x01²)
dr dy
(2xh)d/2
/ <wolle
exp( 2/ 11y x0|
de
vol(K)) 11())
(2mh1)//2
exp( 2²
26
d2 dy.
(B.3)
vol(K) Jkgg d(y.K)
22th
Let us denote the tail probability of the 1-dimensional Gaussian with variance by
T(s) == (N 1 1-11-(h-111 -1/2ss)
where t is the CDF of the standard Gaussian. By the co-area formula and integration by parts,
f
1 22 exp(
2A
dzdy
T(s) vol(OK..)
K3g d(v.K)
V2Th
T(s) vol() 2z
+
f
000
exp(
) //' vol(OKC.) dz
22
(B.4)
/2rhh
Recall that T(s) < 2 exp(- (h/-)/2)))) for 1/2 2 0 due to a standard tail bound on a Gaussian distribution. This tail bound, combined with
[ vol() de = vol(K.) - vol(K)) x vol((1 + 8) KC) - vol(K)) = ((1 +) - 1) vol(KC).
21

---

ensures that vanishes at 8 co. Hence, bounding the first term in (B.4) by 0 results in
Jos S exp(- 2²)
1
5² 2nd J. exp(-
dz dy S
(1 + 8) -1) vol(K)) ds
V2th
/2th
Sexp(ad)
vol(K)
2 exp(hd /2)
exp(
(s - hd) ()
ds
2h
(6
hd)²
vol(K) exp(hde 1/d22///// /2) e2)xxp(
2h
8² (x(()))pp(( + öd).
2h
where in (1) we used the tail bound for a Gaussian.
This core lemma suggests taking 8 = s/a and h = o/d² for some t, c >> 0, under which we have
t²
(KC)) S exp(
+t)
2c
Now we choose a suitable threshold for bounding the failure probability. Following (B.3) in the proof, one notice that for KG 0 (2(1/d), and h ()
exp(
24 =²²
((V) S
de = PZ-NiOO 20 s exp(-s((t)))
d(v.K)
V2Th
Thus, the expected number of trials from K2 for the rejection sampling in Line 3 is E(v)- > exp(S2(12)). Intuitively, one can ignore whatever happens in KGg. since K. takes up most of measure of Y As the number of trials from K3 is at least (xp()((t)) in expectation, the most straightforward way ignore algorithmic behaviors from Kţ is simply set the threshold to N ((exp(t)) Even though the threshold is N, the expected number of trials much lower.
Lemma 3 bounds the failure probability and expected number of trials per iteration.
Proof of Lemma 3. For pa = 4 NN, hla), the failure probability is Ey,, [(1 8) Since du/dx < . implies dpm//d (on//d(>>)))))))))))))))()))))) )). duc / M, it follows that
E M < M Exy [(1 - 1
Then,
1)2N dxy
/ A+
I JKonteeN- (og(m//
+ L -KAntEEN-T 1og//= (o
gg
K0g
[ 1 log(3mM/n))
S x (KC)) +
(xp(-eN)or do (
((y) dy
+
KonleeN 1ogl3mm/nn) vol(K)
t2
n log(3mM/n) vol(ACs)
S <exp(
+t)
2c
3mM
vol(KC
12
" e
3mM
< expp(
+ 1) +
log N
2c
3mM
"
where used vol(Ks) C vol((1 + 8)K) (1 8)at vol(K)) s et vol(K). Taking
log log 2 2
t = v8log log 7, and N = Z(log Z)4, we can bound the last line by " MM Therefore,
E [[1 -(-) < M L,,Y {())) " m
22

---

We now bound the expected number of trials per iteration. Let X be the minimum of the threshold N and the number of trials until the first success. Then the expected number of trials per step bounded by ME, r X since dpp/dr I M. Thus,
Jpc. 1E (N doy $ / 1 dr N (KC))
vol(Ks) vol(K) + No *
f² + +1) - (log 2) + 3(lg 2)* (log" mMM 2c
Se' N
Therefore, the expected number of trials per step is O(M log* mM) " ). and the claim follows since each trial uses one query to the membership oracle of K.
B.4 Putting it together
We can now show that In-and-Out subsumes previous results uniform sampling from convex bodies (such as Ball walk and Speedy walk), providing detailed versions of the main results in $4.
We first establish that the query complexity of In-and-Out matches that of the Ball walk under stronger divergences. Recall that 2/| ITv S KL S log(1 + +x²) Xx².
Theorem 5. For any given 1), e (0, 1). q 2 1, m E N defined below and any convex body K. given by a well-defined membership oracle, consider In-and-Out (Algorithm 1) with an M-warm initial distribution Po h = (2d2 log 9mM ) and N = O mM
((mM) ). For x the uniform distribution over K.
It achieves R. (1x x S e after = Ögd [Cov(T* alap log" M iterations. With probability
1 1n the algorithm iterates this many times without failure, using (dgMd||[Cov (x* Mlop log" me expected number of membership queries in total.
For isotropic xx, with probability 1 - 1/, the algorithm achieves Ry |l x²) S with m Ógdd log" 2 M) iterations, using Og log ) membership queries in expectation. Tp.
Proof. We just put together Lemma 3 and Theorem 3. For target accuracy >> O, we use the Ry-decay under (PI) for q 2 2 in Theorem 3. The M-warm start assumption guarantees R2 || | x $ log M.
Due to CpI( X) = OlI (lop log d) (Lemma 9), In-and-Out can achieve R2 (1 T ( S after m = by Lemma 3, the union bound ensures that the total failure probability is at most r) throughout m iterations. Lastly, each iteration requires O(M log" ) membership queries in expectation by
olop log" M) iterations. Since each iteration has n/ f//m-failure probability
Lemma 3. Therefore, In-and- Out uses Md min( (D², ||Cov(=**) (lpp) log +) expected number me
of membership queries over m iterations. Since Rg is non-decreasing in q. we can obtain the desired bound on R2 for q E 21.
For isotropic xx we have Cov(T*) Ia. so the claim immediately follows from Cpi( X) (log d) (see Lemma 9).
We now show that the number of proper steps is bounded as claimed for general non-convex bodies and any feasible start in K. We first establish this result under M-warm start (Theorem 2).
Proof of Theorem 2. By the Rényi-decay under (LSI-l) in Theorem 3, In-and-Out can achieve E-
distance to x after O(gh (lighh'CCsstee "Cssi(=*) ) log RnGn" [x= iterations for q 2 1.
For 2 2, we use the decay result under (PI). In this case, In-and-Out decays under two different ( (Ry || a x)) iterations until (. xхx) reaches 1. Then, In-and-Out additionally needs ((gh-'Cpi(T X log ?) iterations, and thus it needs Olgh - -'CpI(' (n6" xx) S log M, we complete the proof.
rates depending on the value of (- x² It first needs
xx + log 2)) iterations in total. By substituting
Next, we show that In-and- Out mixes from any start.
23

---

Corollary 2. For any given E (0, and set K C Bp(0), In-and- Out with variance h and any feasible start zu E I achieves Ry |l x²) S E after m = Ölgh D(ghh log d+ /h/ iterations.
CCss((**)))
Proof. We first bound the warmness of uº w.r.t. πx when 16 8 One can readily check that
(x) 1x(x)) /
exp(- 2 llv x |23 exp( 2x lly soll?)
dy
(2mh)a/2 JK exp( 2h lly -=1²) de
By Young's inequality, 11 - x=12 - (1l/l + D)² - |11y 3D for a E K. Hence,
exp
1 by - 12|| 20122) exp
2 lyy xo.l3) dy
25
JKC exp( 2h 1Iy
- 2i x/|3) dr
exp(2h D22
1
3 [1)l()) dy
exp
(1v ze|2 + 11 =ool2
vol(AC)
2h
exp(2h- )
1
exp
lly 2(x =o)1l + (1|==112 + |+Ol1 21|2 + z0l13)) dy
vol(K))
2h
exp(5h-1D")
1
lyy 2(x zx))1²) dy
exp
vol(K)
4h
exp(5h ) -D2)
vol(KC) (4th)d/2
Therefore, M = ess sup #x
< 24/2 exp(sh By Theorem under (LSI-I), In-and-Out needs
Ö(gh Lloh-'Cisitee *C) log d+D2/h iterations.
We then obtain following corollary for a convex body K. Corollary 3. For any given (0, 1) and convex body (D) In-and-Out with variance and an M-warm initial distribution achieves Rg (HTT || x I E after m = OOg DD )
iterations. If X is isotropic, then In-and-Out only needs - Doo d-d d- (h) iterations.
Proof. For convex K., it follows from Lemma 9 that CLsi(T*) O(D3) and CIs((T*) O(D) for isotropic K. The rest the proof can be completed a similar way.
For h O) In-and-Out requires (gd D²) iterations and in particular Ö(gdl D) iteration for isotropic uniform distributions. These results match those of Speedy walk [61, 37] (see Theorem 7).
C Ball walk and Speedy walk
We restate the previously known guarantees for uniform sampling by Ball walk and Speedy walk. Below, let B,(x)) denote the d-dimensional ball of radius r centered at x.
Algorithm 2 Ball walk
Input: initial distribution To, convex body C. Rd, iterations T. step size 0.
1: Sample 2o ~ To.
2: for 1,..., T do
3: Sample
Unif( (B5(
4: I E K. then क + y. Else, H; + 24-1-
5: end for
Ball walk is particularly simple; draw uniform random point from B, around the current point, and go there the drawn point inside K. and stay current point otherwise. Its stationary distribution can be casily seen to be и 1, the uniform distribution over K.
24

---

In the literature, there are two approaches to analyzing the convergence rate of this sampler: (i) direct analysis via the s-conductance of Ball walk and (ii) an indirect approach which first passes through Speedy walk.
Direct analysis. The following TV-guarantee is obtained by lower bounding the s-conductance of Ball walk, which requires a one-step coupling argument and the Cheeger inequality for x. We refer interested readers to [16, $5J.
Theorem 6 (Convergence of Ball walk). For any e E (0, 1) and convex body K. R presented well-defined membership oracle, lel TTs be the distribution after t steps of Ball walk with an M M-warm initial distribution To. Then, Ball walk with step size O vava) achieves || x||TV S E for
t 2 d2 D2 g log
M g" !f π is isotropic, then Ball walk needs Od g log log m iterations.
The mixing time of Ball walk under this approach has polynomial dependence on 1/e, rather than polylogarithmic dependence.
Indirect analysis through Speedy walk. [4] introduced Speedy walk, which could be viewed as a version of Ball walk and converges to a speedy distribution (see Proposition 1), which is slightly biased from π. Then, Speedy walk is used together with another algorithmic component (rejection sampling) [4, Algorithm 4. 15] that converts the speedy distribution to the uniform distribution. In the literature, Ball walk often refers 'Speedy walk combined with the conversion step', rather than direct implementation of Algorithm 2. Strictly speaking, a mixing guarantee of this combined provable guarantee of Ball walk.
algorithm should not be referred
Algorithm 3 Speedy walk
Input: initial distribution To. convex body IC C Rd iterations T, step size 5 >> 0.
1: Sample zo To.
2: for = 1, ,,....2 T do
3: Sample x; Unif(K Bs(x=-1)).
4: end for
As opposed to Ball walk, Speedy walk always takes some step at each iteration. However, the problem of sampling from z; Unif(K Ba(x;-1) in Line 3 is not straightforward. This step admits the following implementation based on rejection sampling, via a procedure denoted by (*):
Propose y ~ Unif(BB(E;-1)
Set 71+1 y if K. Otherwise, repeat the proposal.
Each actual step (indexed by i) in Speedy walk is called a proper step, and rejected steps during (*) called improper steps. For example, if 21 21, 22, T3, 43, 23, I4,... are the positions produced by Ball walk, then only proper steps I 222 43, .4.... are recorded by Speedy walk.
To describe the theoretical guarantees of Speedy walk, define the local conductance {(x) at x K. which measures the success probability of the rejection sampling scheme (*):
((x) = vol(K BB(x))
vol(B((x)
and define the average conductance:
E. vol(KC) / (x)
Proposition 1 ([4]). The stationary distribution v of Speedy walk has density
v(x) = f(x) 1x(x) Jx. {(x( dx
The speedy distribution v is indeed different from the uniform distribution n, and this discrepancy quantified in terms of the average conductance.
25

---

Proposition 2 ([4, Page 22]). || T||TV - 1-1 x
One can relate the step size 8 to the average conductance. Proposition 3 (Bound on average conductance, [4, Corollary 4.5]). X
5ya 2
The best known result for Speedy walk's mixing is due to [61] devising the blocking conductance and using the log- Cheeger inequality. When v is isotropic (i.e., it has covariance proportional to the identity matrix), [37] improves the mixing bound via the log- teeeheeeerr constant.
Theorem 7 (Mixing of Speedy walk). For any (0,1) and convex body K. C Hd presented by well-defined membership oracle, let Vi be the distribution after proper steps of Speedy walk started any feasible point To K. Then, Speedy walk with step size 8 = (dd-11/ achieves al (ive-vily -V|TVV S E for 2 (D2 + log DV (V))) d2 ? From an M -arrm start, the expected number of improper steps during iterations is (tM)) When v is isotropic. Speedy walk needs O D log ? log log D) proper steps to achieve E- TV distance v.
Then, [4] uses the following post-procenn post-processing step to obtain an approximately uniform distribution on K. with provable guarantee.
A: Call Speedy walk to obtain a sample X ~ v until
2d X. 2d X E IC. If so, return X
2d-1
2d-1
Proposition 4 ([4, Theorem 4.16]). Under the same setting above, assume ||V - vl[TV S E for step size 8 & (8d 4 and fixed t E N. For v = law given by A, it holds that || 7 TV S E, and the expected number of calls the conversion algorithm is at most 2.
Combining the previous two results, we conclude that the total expected number of membership
queries to obtain a sample E-close to π in TV is (MM D2 log 2) which now has a poly-logarithmit dependence on 1/e.
Remark 3 (Backward heat flow analysis of Speedy walk). Consider Gaussian version of Speedy walk, whose one-step corresponds to 2441 ~ N(;, higg] and this transition kernel ex- due the stationarity of under the transition kernel defined by the backward heat flow for time l that reverses xx (0, hTa) to x Hence, if we control the I.SI/PT constants of along the backward heat-flow's trajectory, then we could directly analyze Speedy walk by emulating computations in Lemma 4.
actly matches integrating (BH) for time h. Thus, =Q) xxxxxx
Speedy walk, where Q ,h
D Functional inequalities
We provide full details on functional incqualities omitted in Appendix B.I. We use f and JLC to denote probability measure and log-concave probability measure over Rd respectively.
Cheeger and PI constants. The Cheeger isoperimetric constant Cer(p) measures how large surface area measurable subset with larger volume has, defined by
(+())
inf Cen SCR" min(u((),,uS$))
where the infimum is taken all measurable subsets S, and n p+(S) is the Minkowski content of S under defined as, for S == (x E X d(x, S) < {),
(S)) = lim inf ((S²) - H(S)
8-0
[62] established CPI(R) S (w), and then [33] showed that for covariance matrix Σ,, E,I(- (-- ET,
Ccn(MLC) 2 EE p ||| E 1/2
(D.1)
(tr 1/c)
1/2
'The opposite direction Crr(pcc) > Ca (pic) ) also holds for log-concave distributions due to [63], while Cpi(H) 2 C / for general distributions due [64].
26

---

This immediately leads to CPi(T) X [ExI] - 12 & D2 for the uniform distribution π over convex body with diameter > 0.
Kannan et al. proposed the KIS conjecture in the same paper, which says that for the spectral norm || 1|2
CcH(H4)) 2
|| 1/2 12
While the original result in [33] ensures Cch 2 1/2 for an isotropic log-concave distribution
(due Σ Ta), this conjecture indeed claims Can 2 1 for such case. Following line of work
[37, 55, 65, 34], the current bound
(log d) d/2
Cc (ULL) 2
|| 1l2 1/2
which implies that CPI( S log d when π is isotropic for convex K.
Log-Ch Ch-egheege and LSI constants. Just the Cheeger and PI constants are related above, there known connections between LSI and log-Cheeger constants. The log- Cheeger constant ClogCh (1) of a distribution μ E P(RR)) is defined as
(S)
(Lg == inf
SCRI ps5) log ((S)
[64] established that CLsI(R) X (1) and [61] showed that any log-concave distributions
with support of diameter D satisfy Clogen (PLS) 2 D-1 Later in 2016, [37] improved this to GrogCn (ALs) D D-1/2 under isotropy. Therefore, for convex K,, follows that Cis((T) x D and
that CLSI(T)
D if æ is isotropic.
E The Wasserstein geometry
We present additional technical background on the Wasserstein geometry and Markov semigroup theory. Interested readers can refer to [66, 67, 28] for standard references Wasserstein spaces and applications to sampling.
Wasserstein gradient. Let P2. (12)) be the space of probability measures admitting densities Rd with finite second moment. Although there are many ways to metrize a2 (Rd),, the geometry induced by the Wasserstein-2 distance W2 is particularly useful structure for analysis.
Under the Wy-geometry, one can define "gradient" of functional defined over (2.ac(R.) Specifi- cally, for functional F P2 (Idd + R RU (co), the Wasserstein gradient of F at E a2. (12d) defined as F(u) = ((F) E (I))). where is the standard gradient and 5F is the first variation of F². Equipped with this W2-gradient one can define the Wasserstein gradient flow of F that describes the evolution of a measure {Mu J12. from some initial measure as follows:
0.44 = div (ii Vw,
More generally, we can identify the Wasserstein "velocity" for some measure μ4 as 0t if the time derivative of d4 can be written in the form
0q div(per))
Under this identification, the time derivative of a functional F on P2, (Rd)) with smooth Wasserstein gradient under these dynamics can be written
0,F(m) E,,, FWw,)(()),,
The opposite direction holds under dimension dimension-scaling scclonnnnncnnnnnnonnn due to [64]: CLsi(H) 2 C (n)/d. "The first variation can be defined, for any measures Vo, i/ E P2. (Ltd) as limago ter) (FF())) in vo). This definition is unique to an additive constant, which is irrelevant as we are only concereed with its gradient.
27

---

when E (v th E C (RR)) (1e)). This is the appropriate notion tangent space in this geometry.
(m)))
where {-}
(.P))
denotes the closure of set with respect to
For instance, when we take the functional to be the entropy of the measure, H(H) = ] log one can verify V H() = V log js. The heat flow equation can be written 0,/4, = A444
Sit(VPss) = 2 div( V log μ4), which indicates that the velocity of measures μ4 under the heat flow is U2 _ V log Pe. Hence, we can notice that Vw, H(4) -t and thus recover the heat flow as the Wasserstein gradient flow of the entropy of the measure.
Likker-Plancke equation and time-reversal of SDE. (X₂) given by
Consider stochastic differential equation
dX,; -a (Xx, + dB,
with Xo ~ po.
(E.1)
It is well known that measures (4 described by
1
defi: = div(140)) + Au4,
(E.2)
correspond to law(X.). In this context, (E.2) is referred to as the Fokker-Planck equation correspond- ing (E.1).
From this equation, one can deduce the Fokker-Planck equation of the time reversal Fht == pr-
1 - - div (ar-t + V log (T) 2 Auf
d.p. - div(u aT-1) -
In particular, this describes the evolution of law(X;) of the stochastic differential equation:
dX; = (X,) - V Wlog (x,) dt + dB, with X, ~ 16 = pr-
(E.3)
While the law of this process will give /T = at time T, is also true that it will give (o 3) one starts (E.3) Xo- = z. This is subtle fact, whose justification requires the introduction of a tool called Doob's 's hi-transform. The presentation of this subject is beyond the scope of this paper, and we refer interested readers to [53] reference to its application in this context.
28

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
integral part of your paper submission. They visible the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The checklist answers
The reviewers of your paper will be asked to use the checklist one of the factors in their evaluation.
While "[Yes] is generally preferable to "[No]" ", it perfectly acceptable to answer "[No] provided a proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). ) In general, answering "[No] " or "[NA] is not grounds for rejection. While the questions are phrased in binary way, acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification elaborate. All supporting evidence can appear either in the main paper the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
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 primary claim is that we are presenting a new algorithm for uniform sampling convex bodies, with guarantees in Rényi divergence. This is achieved by Algorithm through Theorem 5.
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 be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The primary limitations of this work are due to the assumptions. The assumptions are clearly given when presenting our main results, and some potential extensions or relaxations given in conclusion.
Guidelines:
29

---

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 a 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 on 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 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 or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't I acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
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?
Answer: [Yes]
The assumptions are provided for each theorem, and the full proofs can be found in Appendix B. A brief proof overview of the proofs are found in the main text, following the results.
Justification:
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided 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.
Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
The contribution of this paper is primarily theoretical, and the paper does contain any experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data are provided not.
30

---

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 novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how construct the dataset).
model (e.g., a large language model), then there should either
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-soures models, it may be that access to the model is limited in some way (e.g.. to registered users). but it should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification:
The paper does not contain experiments and therefore does not require data or code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (bttps://nips.cc/)
guides/ Cilees/CooSuubbissc wettuubmmsssiiiiii swwiisssissiponnooooooo for more details.
While encourage the release of code and data, understand that this might not be possible,
so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for
open-source benchmark).
The instructions should contain the exact command and environment needed the results. See the NeurIPS code and data submission guidelines (https: : http//iisscccpp/////////// public/ guides Staee/CooeSubbiiiic iss ssionPolicy) for more details.
reproduce
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 a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification: The paper does not contain experiments.
31

---

Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core of the paper to a 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: The paper does not contain experiments.
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, confidence intervals, statistical significance tests, least for the experiments that support the main claims 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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK report I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors 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 of range (e.g. negative error rates).
If error bars are reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [NA]
Justification: The paper does not contain experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurt cc/pubiccc/hthiicttullll........
Answer: [Yes]
Justification:
The paper conforms to the Code of Ethics and the guidelines prescribed therein.
Guidelines:
32

---

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 circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there a special consideration due laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
The impact of this paper is primarily theoretical, and it is therefore difficult to quantify societal impact directly. The discussion surrounding the main theorems contains the benefits and limitations of our analysis, which we would hope also captures their societal impact.
Justification:
Guidelines:
The answer NA means that there is societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to par- ticular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, is legitimate to point out that improvement in the quality of generative models could be used generate deepfakes for disinformation. On the other hand, 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 is being used intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g.. pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not release data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse 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 restrictions access the model 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 take this into account and make best faith effort.
12. Licenses for existing assets
Question: 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?
33

---

Answer: [NA]
Justification:
The paper does not use existing assets.
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 the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, terms of use in the package should be provided. For popular datasets, paperswi haperswithcone thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged. both the original license and the license the derived asset (if it has changed) should be provided.
If this information
available online, the authors are encouraged reach out the asset'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:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations,
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. Crowdsoureing and Research with Human Subjects
Question: For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper involves neither crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail possible should included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should 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 Sub- jects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
34

---

Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may he 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 applica- ble), such as the institution conducting the review.
35


Reviews:
[{"review_id": "YA78z7AWyn", "reviewer": "Reviewer_W5VJ", "summary": "This work presents a new algorithm, called In-and-Out, for sampling from the uniform distribution over a convex subset $K$ of $R^d$ that comes with stronger guarantees than previous algorithms. The proposed algorithm is an instantiation of the Proximal Sampler (PS), an abstract sampling algorithm which was recently shown to have very strong guarantees (Chen et al., 2022 [27]). The PS was previously considered for sampling from $\\propto e^{-f} dx$ given first-order oracle access to $f$, and was typically implemented using a form of rejection sampling; the guarantees in [27] are stated purely in terms of the Poincare Inequality (PI) or Log-Sobolev Inequality (LSI) constant of the target. In the setting of this work, the target is $\\propto 1_K$ the uniform distribution on a set $K$ for which we have membership oracle access, and the implementation also uses (another form of) rejection sampling. The guarantees presented in this work follow from the analysis from [27] (§B.2) and a regularity lemma (Lemma 12), from bounds on the PI and LSI constants of uniform distributions known from various recent works (Lemma 9 and §D), and from fine bounds on the failure probability in rejection sampling (§B.3).", "questions": "- Regarding the first point in \"Weaknesses\": what are some application cases in machine learning where your work applies?\n- Can the In-and-Out algorithm be extended to sampling from a target $\\propto e^{-f} 1_K$ where $f$ is smooth on $R^d$ given first-order access to $f$ and membership oracle access to $K$? Specifically the rejection sampling step and its failure probability analysis (since I expect the analysis of the abstract algorithm, PS, is unchanged)\n- On line 175, you mention a better query complexity if $K$ is near-isotropic, but Corollary 1 just below is about the exactly-isotropic case. What does line 175 refer to? (Is it Thm 5? if yes it should be mentioned in the main text)\n- Out of curiosity: are there ways to rescale a convex body to be near-isotropic, given membership oracle access? This could give a preprocessing step which could improve the query complexity you report.", "limitations": "The authors have adequately addressed the limitations.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "From the point of view of the problem of sampling convex bodies, the contributions of this paper are outstanding. The results appear much stronger than previously known guarantees (but I am not familiar with the literature on this problem, so I can only trust the authors's discussion of the related work.) It illustrates that the diffusion approach to sampling can yield strong results on a problem where geometric approaches are perhaps more natural.\n\nFrom the point of view of algorithmic diffusion, this paper is not \"just\" a piecing together of several known components, as the analysis of the failure probability of the rejection step is not at all obvious. I found the concise rewriting of the analysis of [27] (Part I of §B.2) quite appreciable as well.", "weaknesses": "- No application is presented or discussed. Usually for theoretical works such as this one, the value of the contribution lies in the analysis technique, with the hope that it will allow to eventually obtain guarantees for future applications. But the applications that naturally come to my mind are cases which the results of [27] already cover.\n\nSome minor suggestions:\n- The relation between Thms 1, 2, 3 is a little bit confusing, as only Thms 2, 3 talk about PI and LSI constants. Perhaps the presentation of the results could be made clearer by moving Lemma 9 to the end of §2, or at least making a reference to it there.\n- I would suggest mentioning already in the abstract or the introduction that In-and-Out is an instance of PS. This would be fairer w.r.t. prior work in my opnion.\n- The fact that Part I of §B.2 is a restatement of the analysis of [27] should be clarified (the terms \"revisit\" and \"review\" currently used on lines 563, 569 are not completely clear).\n- On lines 139-141, you mention that the time-reversal SDE has the property that it is also a reversal \"pointwise\", i.e, conditional on the endpoint. But I did not see where this fact is used, as in §B.2 only the reversal of the heat flow at the PDE level is used.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\textbf{Application}$\n\nOur work mainly aims to provide a new algorithmic/analytic framework for the uniform sampling problem under the membership oracle model. The applications of this problem are already widespread and well-known, therefore we do not feel the need to propose any new applications. Instead, we note that this problem is used in a number of fundamental settings: volume computation for convex bodies; as a core subroutine in general convex body sampling; metabolic flux sampling in systems biology; Bayesian inference in statistics; and other domains of scientific computing. Thus, new results for the core algorithmic problem would immediately imply theoretical improvements for all these settings. \n\n$\\textbf{Extension to potentials}$\n\nWe thank the reviewer for their insightful suggestion. While our framework could potentially accommodate it, the rates after incorporating a first-order oracle for sampling $e^{-f}1_K$ are not immediately clear from our analysis and would take some more effort. We leave this for future work.\n\n$\\textbf{Confusion around Line 175}$\n\nWe apologize for the confusion. Corollary 1 holds for the near-isotropic case as well, since the operator norm of the covariance is $\\mathcal{O}(1)$.\n\n$\\textbf{How to make it isotropic}$\n\nThe question of obtaining an isotropic position has been studied for more than two decades in theoretical computer science. For references, please consult [1, 2] for an idea of how this can be done. In summary, their approach is to draw a few samples from the body and then obtain a rough estimate of the covariance $T$. Then, applying a proper linear map $T^{-1/2}$ to the body will reduce the skewness. Repeating these steps $\\mathcal{O}(\\log d)$ many times (along with some type of annealing algorithm) ensures that a transformed body is nearly isotropic with high probability. Although we had mentioned this procedure in our related works, we will make a comment earlier in our paper for clarity. We thank the reviewer for their question.\n\n$\\textbf{Regarding Line 139-141 (time-reversal of SDE)}$\n\nThe final paragraph of Appendix E discusses why the pointwise reversal property is needed. In particular, it allows us to claim that given a starting point $z$, the reverse SDE from such a starting point has distribution $\\pi^{X|Y=y}$, a property used in the initial paragraphs of Appendix B. This will be clarified in our revision. \n\n***\n\n[1] Gaussian Cooling and $O^*(n^3)$ Algorithms for Volume and Gaussian Volume, Ben Cousins and Santosh S. Vempala.\n\n[2] Reducing Isotropy and Volume to KLS: An $O(n^3\\psi^2)$ Volume Algorithm, Jia et al.", "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": "x6AMbybH3S", "reviewer": "Reviewer_T79w", "summary": "The paper addresses the fundamental problem of uniformly sampling high-dimensional convex bodies. The main contribution is the proposal of the In-and-Out algorithm, analyzed within the framework of the proximal sampling scheme. Using existing analyses from the literature, the paper derives strong results. Additionally, the authors discuss classical methods for constrained sampling and diffusion-based or proximal methods for unconstrained sampling.", "questions": "- Is it possible to extend these results to the log-concave setting?\n- The membership oracle used is standard. What if we are given the polytope constraint explicitly?", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- Overall, I like this paper. It proposes a new method and offers valuable insights. Additionally, the paper achieves strong results with straightforward proofs.\n- The paper is well-written and easy to follow.", "weaknesses": "- The analysis techniques used in the paper already exist in the literature, which limits the technical contribution.\n-The paper does not provide a comparison of iteration/query complexity with existing works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\textbf{Techniques are already existing}$\n\nAs noted by Reviewer W5VJ, our paper is not “just” putting together known components. Previous work on proximal sampling works under a well-conditioned setting without hard constraints, where the number of trials for rejection sampling (for the backward step) is always $\\mathcal{O}(1)$ regardless of the forward step. However, in the presence of constraints, this type of analysis for the backward step is no longer possible. Analyzing proximal-type sampling for this setting has been a well-known open problem. Instead, we carried out the analysis for the backward step in a more careful way. As a result, there are a number of new ideas in the rejection analysis.\n\n$\\textbf{Extension to a general setting}$\n\nWe thank the reviewer for their insightful suggestion. While our framework could potentially accommodate it, the rates after incorporating a first-order oracle for sampling $e^{-f}1_K$ are not immediately clear from our analysis and would take some more effort. We leave this for future work.\n\n$\\textbf{Polytope constraint?}$\n\nThere are several ways of leveraging the explicit structure of the log-concave sampling problem. For instance, one can easily implement a projection oracle for polytope constraints (which is stronger than a membership one), so one may consider a projection-based algorithm. Another approach for exploiting the structure is to use barrier-related information. In general, a convex constraint admits a self-concordant barrier $\\phi$, and samplers with the local metric given by the Hessian $\\nabla^2 \\phi$ are provably fast and practical (due to condition-number independence, for instance).", "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": "m6QrHlv1N7", "reviewer": "Reviewer_V3VH", "summary": "The paper presents a novel random walk algorithm for uniform sampling of high-dimensional convex bodies that provides improved runtime complexity and guarantees on the result, especially with respect to Rényi divergence. \nSampling high-dimensional convex bodies, a fundamental problem in algorithm theory with numerous applications in scientific computing, systems biology, differential privacy, and (to a lesser extent) machine learning. All the samplers known so far rely on Markov chains and most of the time, convergence analysis depends on limiting the conductivity of the associated chain, which in turn controls the mixing rate.\n\nThe algorithm alternates in and out moves, which is a kind of modification of ball walk, avoiding MH step. The theoretical analysis shows that the method contracts the distribution towards the target distribution at a rate that is influenced by the isoperimetric properties of the convex body. \nThe results show the effectiveness of the new algorithm compared to traditional methods such as the ball-walk and hit-and-run algorithms. The \"in-and-out\" method shows superior performance, especially in high-dimensional environments, due to its direct reduction to isoperimetric constants.", "questions": "- Can you provide more details on the initialization process and parameter selection (e.g., h, N) for the algorithm?\n- Could you elaborate on how the functional isoperimetric constants influence the convergence rate of the algorithm for specific geometry (polytopes, ellipsoids, etc...) ?\n- How can the algorithm be extended to sample from general log-concave distributions restricted to convex bodies or other non-log-concave distributions satisfying isoperimetric inequalities? [is there a \"general\" idea that can be preserved? - replacing the \"hard\" Metropolis filter by and In-and-Out mechanism ?]\n-", "limitations": "yes", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Introduction of the \"in-and-out\" algorithm for uniform sampling that uses a heat flow approach.\n-  stronger guarantees  in terms of Rényi divergence, which includes other divergence measures such as total variation (TV), Wasserstein (W2), Kullback-Leibler (KL) and chi-squared (χ2).\n- analysis of mixing rates from a heat flow perspective, providing new insights and extending known results for the unconstrained domain.\nConvergence rate is shown to be determined by functional inequalities such as Poincaré (PI) and Log-Sobolev inequalities (LSI-I).\nIteration complexity: For isotropic distributions, the algorithm achieves convergence with a polynomial number of iterations depending on the dimension and the desired accuracy.", "weaknesses": "- I don't see any major weaknesses. The paper is easy to read, the main stages of the analysis are outlined in the text (I didn't have time to check the appendices) and are interesting. I regret the absence of a numerical section to compare the interest of the In-and-Out method on practical examples [comparing it to existing algorithms].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\textbf{Initialization process and parameter selection}$\n\n- Initialization process: We assume that the initial start is $M$-warm in this work. Obtaining this warm-start is non-trivial, and requires some type of annealing algorithm in general. Warm-start generation has been studied for more than two decades in theoretical computer science. See e.g. [1] for how this can be done.\n- Parameter selection: The details of $N, h, \\eta$ are given in the proof (see Lemma 3 and 14 for example). We will make this more clear in the initial Theorem statement as well. Note that we do not track the absolute constants hidden in big-O notation, but this can be obtained from a careful reading of the proof; our analysis was not optimal with respect to numerical constants, which can likely be sharpened with a more precise argument. \n\n$\\textbf{How FI parameters affect the convergence rate for specific geometry}$\n\nThe Poincare constant in general is on the same order as the maximum eigenvalue of the covariance, while the log-Sobolev constant is bounded by the squared diameter of the convex body (please refer to Appendix D).\nHowever, for a more structured body, it is not clear what the sharpest possible constant is for these functional inequalities. In general, we expect that it would be very difficult to estimate unless the body is something simple like an $\\ell_p$ ball.\nWe can also obtain the constants under a linear map $T: x \\mapsto Ax$ by multiplying the constants by $||A||^2$.\n\n$\\textbf{Extension to a general setting}$\n\nWe thank the reviewer for their insightful suggestion. While our framework could potentially accommodate it, the rates after incorporating a first-order oracle for sampling $e^{-f}1_K$ are not immediately clear from our analysis and would take some more effort. We leave this for future work.\n\n***\n\n[1] Gaussian Cooling and $O^*(n^3)$ Algorithms for Volume and Gaussian Volume, Ben Cousins and Santosh S. Vempala.", "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": "PDgUiWfwbl", "reviewer": "Reviewer_Jx5G", "summary": "In this paper, the authors consider the problem of uniform sampling from general convex body. The algorithm works by augmenting the state space followed by performing alternative Gibbs sampling, where one of the inner steps is implemented by rejection sampling. Non-asymptotic end-to-end bounds on the mixing time in Renyi divergence under warmness assumption is established. The analysis takes the view of the two updates as forward / backward heat flows, building on existing proximal sampler work, therefore offers a clean stochastic process perspective on the algorithm. Various connections of the proposed algorithm to ball walk and speedy walk are also discussed.", "questions": "- I haven't given this a careful thought - does the result follow from the proximal sampler result by taking some suitable limit? (since the target is log-concave here and \"discretization\" isn't an issue for Gibbs sampler) Since I'm confused as to why warmness would show up here but not in the original proximal sampler?\n\n- I didn't quite follow Line 146-149 - how would In-and-Out compare to projection-based method? \n\n\n- Line 234-236 the comment about being lazy: In the proposed algorithm, if it doesn't make a proper move (i.e., declares \"Failure\"), wouldn't that be equivalent to a \"lazy\" step where things don't move? Or maybe another way to say this is - how should one take ergodic averages along the chain for computing expectation of some observable? It's not entirely clear from first reading.\n\n\n- How does one obtain a warm start in practice?", "limitations": "Yes the work is mostly theoretical.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is clearly written and well-structured. Relevant related works are adequately surveyed with the topic being of great interest to many problems in machine learning and computational statistics. While the results and analysis build on the existing framework of proximal sampler for log-concave sampling, I think there are contributions in the paper to this new setting that's worth sharing with the community. The approach is conceptually simple and offers a fresh perspective on constrained sampling.", "weaknesses": "I have listed some questions in the section below. My main concern is that while I understand the authors provide guarantee in a stronger metric compared to existing algorithm / analysis, given that the query complexity of In-and-Out matches that of some previous work, and the methods are similar in some regard (for example, the second step is conceptually similar to a projection step), it's unclear to me what the practical advantage of the proposed method may be.\n\nMinor comment: Some kind of table putting together all the mentioned rates under different assumptions / metrics alongside related previous results in the literature will help the reader digest things a bit better.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "$\\textbf{What practical advantage of the method?}$\n\nThe main advantage of our method is the simplicity of the algorithm and the analysis with provable guarantees in commonly used probabilistic metrics, more general than previously known. Not only is our algorithm much simpler to analyze, but it also provides some tangible improvements (such as improving the guarantee from $\\mathsf{TV}$ to $\\mathsf{KL}$ and $\\mathcal{R}_q$); it also shows a clear and direct connection between isoperimetry and convergence.\nIn practice, we might expect comparable performance between all these approaches, although this would depend on the details of the implementation.\n\n$\\textbf{Does the result follow from the proximal sampler by taking some suitable limit}$\n\nAs demonstrated in Lemma 12 and Theorem 3, the mixing guarantee of our sampler (i.e., how many outer loops are needed) does follow from a limiting argument. However, what matters in the end is a bound on query complexity (not just mixing rate), which essentially requires us to bound the number of rejections throughout backward steps.\n\nThe approach required for the constrained case is not comparable to the unconstrained case. Previous work on proximal sampling works under a well-conditioned setting without hard constraints, where the number of trials for rejection sampling (for the backward step) is always $\\mathcal{O}(1)$ regardless of the forward step. However, in the presence of constraints, this type of analysis for the backward step is no longer possible. Analyzing proximal-type sampling for this setting has been a well-known open problem. Instead, we carried out the analysis for the backward step in a more careful way. As a result, there are a number of new ideas in the rejection analysis.\n\n$\\textbf{Line 146-149: How would INO compare to projection-based methods}$\n\nIn general, a projection oracle is stronger than a membership oracle, and its implementation using a membership oracle requires $O(d^2)$ membership calls per projection in the worst case.\nOne can ask instead what happens if we assume a projection oracle which is roughly the same cost as a membership oracle. In this case, leveraging projection might be faster, but this is a non-trivial problem. We leave this for future work.\n\n$\\textbf{Failure = Lazy? How should one take ergodic averages along the chain for computing expectation of some observable?}$\n\nWe thank the reviewer for this question. In our view, failure of our chain is not the same as taking lazy steps in e.g. Ball walk. Lazy chains have a 1/2 chance to remain stationary at each instant, potentially doubling the iterations needed for convergence.\nBy contrast, our algorithm has an arbitrarily small failure probability (moreover, the mixing guarantee has only a poly-log dependence $\\text{polylog}(1/\\eta)$). In the event of failure, we restart the algorithm until we succeed, which does not introduce any bias.\n\nRegarding the second question, it is still possible to take ergodic averages along the chain (assuming you pick the failure probability at each iteration to be sufficiently small so that your run rarely fails during the entire horizon of your run). This is because our Markov chain still has a spectral gap, and so the same techniques used to obtain guarantees for ergodic averages continue to work in our case.\n\n$\\textbf{How to obtain a warm start in practice}$\n\nObtaining warm-starts in practice is non-trivial, and requires some type of annealing algorithm in general. Indeed, warm-start generation has been studied for more than two decades in theoretical computer science. See e.g., [1, 2] for how this can be done. For simplicity, we assume that a warm start is provided in our algorithm, although one can use the guarantees in [1, 2] to provide a rigorous justification.\n\n***\n\n[1] Gaussian Cooling and $O^*(n^3)$ Algorithms for Volume and Gaussian Volume, Ben Cousins and Santosh S. Vempala.\n\n[2] Reducing Isotropy and Volume to KLS: An $O(n^3\\psi^2)$ Volume Algorithm, Jia et al.", "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 thank all the reviewers for their time and detailed comments. We respond to specific points below. We note at the outset that main high-level contributions are that (a) we provide the first guarantees for KL and Renyi divergences and (b) we directly relate the convergence rates to classical isoperimetric constants of the target distribution.  

We make extensive simplifications to the convergence analysis through our approach, which also exposes a clear relationship between the complexity and the isoperimetry of the target distribution. This immediately gives improvements to guarantees for this problem, with rate: $\mathcal{O}(qd^2 M \Lambda \log 1/\varepsilon)$ in general, where $\Lambda$ is the maximum eigenvalue of the covariance matrix and the convergence is in $q$-Renyi.

$\textbf{Rate Comparison}$: One question raised by multiple reviewers concerns the relationship of the rates obtained in our work, as compared to the best known prior results in this setting. Below, we highlight the main results in constrained uniform sampling under the membership oracle before this work:
- Ball walk: the rate is $\mathcal{O}(Md^2 \psi_{\text{Cheeger}} \log 1/\varepsilon)$ in TV. It relies on a conductance argument.
- Hit-and-run: the rate is $\mathcal{O}(d^2 R^2 \log M/\varepsilon)$ to mix in $\chi^2$, where $R^2$ is the trace of the covariance. It also relies on a conductance argument. 

These rates were given in the related work section of our paper. In our updated draft, we will also state them immediately after our theorems.

Meta-review: The paper gives a new algorithm for the classical problem of sampling from a convex body. The new algorithm uses a different approach from many previous works for this problem, yielding convergence guarantees in Renyi divergences, which are more general than previous results. All reviewers support the paper to varying degrees with several putting it at strong accept.

The paper is purely theoretical and does not include any numerical experiment comparing with existing methods.
Decision: Accept (spotlight)