In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies

Authors: yunbum  kook
santosh s vempala
matthew s zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 14:30:50

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.

Main paper: 
 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 a randomized polynomial-time algorithm for computing the volume of a convex body, was the first polynomial-time algorithm for uniformly sampling convex bodies. In the decades since, the study of sampling has led to a long series of improvements in its algorithmic complexity [2, 3, 4, 5, 6] , often based on uncovering new mathematical/geometric structure, establishing connections to other fields (e.g., functional analysis, matrix concentration) and developing new tools for proving isoperimetric inequalities and analyzing Markov chains. With the proliferation of data and the increasing importance of machine learning, sampling has also become an 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 a summary). Their analysis is 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 inequalities for convex bodies. An archetypal example of the latter is the following: for any measurable partition S 1 , S 2 , S 3 of a convex body K ⊂ R d , we have vol(S 3 ) ≥ d(S1,S2) C K min{vol(S 1 ), vol(S 2 )} , where d(•, •) is the (minimum) Euclidean distance, and C K is an isoperimetric constant of the uniform distribution over K. (The KLS conjecture posits that C K = O(1) for any convex body K in isotropic position, i.e., under the normalization that a random point from K has identity covariance). The coefficient C 2 K is bounded by the Poincaré constant of the uniform distribution over K (and they are in fact asymptotically equal). The classical proof of conductance uses geometric properties of the random walk at hand to reduce the analysis to a suitable isoperimetric inequality (see e.g., [3, 16] ). The end result is a guarantee on the number of steps after which the total variation distance (TV distance) between the current distribution and the target is 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 is to first analyze a continuous-time diffusion process, typically modeled by a stochastic differential equation (SDE), and then show that a suitable time-discretization of the process, sometimes together with a Metropolis filter, converges to 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 is 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 a high-level analogy (e.g., the Ball walk can be viewed as a 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-based algorithm that can be mapped to a stochastic process (and, importantly, to a 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 a consequence, for the first time, we obtain clean end-to-end guarantees in the Rényi divergence (which implies guarantees in other well known quantities such as W 2 , TV, KL, χ 2 etc.), while giving state-of-the-art runtime complexity for sampling convex bodies (e.g., Ball walk or Speedy walk [3, 4] ). Besides being a stronger guarantee on the output, Rényi divergence is of particular interest for differential privacy [13] . Perhaps most interesting is that our proof approach is completely different from prior work on convex body sampling. In summary,• The guarantees hold for the q-Rényi 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 it with the analysis of Ball walk, Speedy walk. Lastly, we provide a detailed survey of the relevant literature in §5 before concluding. 
preliminaries: 
 Unless otherwise specified, we will use ∥ • ∥ for the 2-norm on R d . We write a = O(b), a ≲ b to mean that a ≤ cb for some universal constant c > 0. Similarly, a ≳ b, a = Ω(b) for a ≥ cb, while a = Θ(b) means a ≲ b, b ≲ a simultaneously. We will also use a = O(b) to denote a = O(b polylog(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 µ, ν on R d , the total variation distance between them is defined by ∥µ -ν∥ TV := supB∈F |µ(B) -ν(B)| ,where F is the collection of all measurable subsets of R d . The 2-Wasserstein distance is given by W 2 2 (µ, ν) := inf γ∈Γ(µ,ν) where Γ is the set of all couplings between µ, ν. Next, we define the f -divergence of µ towards ν with µ ≪ ν (i.e., µ is absolutely continuous with respect to ν) as, for some convex function f : R + → R with f (1) = 0 and f ′ (∞) = ∞,E (X,Y )∼γ [∥X -Y ∥ 2 ] ,D f (µ ∥ ν) := f dµ dν dν .The KL-divergence arises when taking f (x) = x log x, the χ q -divergence when taking f (x) = x q -1, and the q-Rényi divergence is given byR q (µ ∥ ν) := 1 q-1 log χ q (µ ∥ ν) + 1 .Definition 2. We say that a probability measure ν on R d satisfies a Poincaré inequality (PI) with parameter C PI (ν) if for all smooth functions f : R d → R,EQUATIONwhereVar ν f := E ν [|f -E ν f | 2 ].The Poincaré inequality is implied by the log-Sobolev inequality. Definition 3. We say that a probability measure ν on R d satisfies a log-Sobolev inequality (LSI) with parameter C LSI (ν) if for all smooth functions f : R d → R,Ent ν (f 2 ) ≤ 2C LSI (ν) E ν [∥∇f ∥ 2 ] , (LSI-I)whereEnt ν (f 2 ) := E ν [f 2 log f 2 ] -E ν [f 2 ] log(E ν [f 2 ]). Equivalently, for any probability measureµ over R d with µ ≪ ν, 2 KL(µ ∥ ν) ≤ C LSI (ν) FI(µ ∥ ν) , (LSI-II)whereFI(µ ∥ ν) := E µ [∥∇ log dµ dν ∥ 2 ]is the Fisher information of µ with respect to ν. 
diffusion for uniform sampling: 
 We propose the following In-and-Out1 sampler for uniformly sampling from K. Each iteration consists of two steps, one that might leave the body and the second accepted only if it is (back) in K.It might be illuminating for the reader to compare this algorithm to the well-studied Ball walk (Algorithm 2); each proposed step is 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 K. In contrast, each iteration of In-and-Out is a two-step process, where the first step (Line 2) ignores the boundary of the body, and Algorithm 1 In-and-Out Input: initial point x 0 ∼ π 0 , convex body K ⊂ R d , iterations T , threshold N , and h > 0.Output: x T +1 . 1: for i = 0, . . . , T doSample y i+1 ∼ N (x i , hI d ).Repeat: Sample x i+1 ∼ N (y i+1 , hI d ) until x i+1 ∈ K or #attempts i ≥ N (declare Failure). 4: end for the second step (Line 3) is accepted only if a proposal x i+1 is a feasible point in K. 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 on the convexity of K. This is reminiscent of the Speedy walk in the literature on convex body sampling (Algorithm 3), which is used as a 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.This simple algorithm can be interpreted as a composition of "flows" in the space of measures. This 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 as alternating forward and backward heat flows. We begin by defining an augmented probability measure onR d × R d by π(x, y) ∝ exp -1 2h ∥x -y∥ 2 1 K (x) .We denote by π X , π X|Y (•|y) the marginal distribution of its first component (resp. conditional distribution given the second component), and similarly denote by π Y , π Y |X (•|x) for the second component. In particular, the marginal in the first component π X is the uniform distribution over K. Sampling from such a joint distribution to obtain the marginal on X (say), can be more efficient than directly working only with π X . This idea was utilized in Gaussian Cooling [6] and later as the restricted Gaussian Oracle (RGO) [26, 27] .Under this notation, Algorithm 1 corresponds to a Gibbs sampling scheme from the two marginals of π(x, y). To be precise, Line 2 and Line 3 correspond to sampling fromy i+1 ∼ π Y |X (•|x i ) = N (x i , hI d ) and x i+1 ∼ π X|Y (•|y i+1 ) = N (y i+1 , hI d )| K .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. It is well known that such a Gibbs sampling procedure will ensure the desired stationarity of π(x, 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 to 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 i and y i by µ X i and µ Y i , respectively. Recall that the first step of sampling fromπ Y |X (•|x i ) (Line 2) yields µ Y i+1 = π Y |X=x dµ X i (x). This is the result of evolving a probability measure under (forward) heat flow of µ X i for some time h, given by the following stochastic differential equation: forZ 0 ∼ µ X i , dZ t = dB t (FH)where B t is the standard Brownian process. We write law(Z t ) = µ X i P t . In particular, Z h = Z 0 +ζ ∼ µ X i * N (0, hI d ) = µ Y i+1 for ζ ∼ N (0, hI d ). When µ X i = π X , the first step of Algorithm 1 gives π Y (y) = [π X * N (0, hI d )](y) = 1 vol(K) (2πh) d/2 K exp - 1 2h ∥y -x∥ 2 dx . (3.1)SDE dZ t = dB t dZ ← t = ∇ log(π X P h-t )(Z ← t ) dt + dB t Fokker-Planck ∂ t µ t = 1 2 ∆µ t ∂ t µ ← t = -div µ ← t ∇ log(π X P h-t ) + 1 2 ∆µ ← tThe second step of sampling from π X|Y (•|y i+1 ) can be represented by µ X i+1 = π X|Y =y dµ Y i+1 (y) (Line 3). The continuous-time process corresponding to this step might not be obvious. However, let us consider (FH) with Z 0 ∼ π X . Then, Z h ∼ π Y , so the joint distribution of (Z 0 , Z h ) is simply π. This implies that (Z 0 |Z h = y) ∼ π X|Y =y . Imagine there is an SDE reversing the forward heat flow in a sense that if we are initialized deterministically at Z h ∼ δ y at time 0, then the law of the SDE at time h would be law(Z 0 |Z h = y) = π X|Y =y . 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(Z ← t ) t∈[0,h] initialized at Z ← 0 ∼ π Y = π X P h ensures Z h-t ∼ law(Z ← t ) = π X P h-t : dZ ← t = ∇ log(π X P h-t )(Z ← t ) dt + dB t for t ∈ [0, h] . (BH)Although this is designed to reverse (FH) initialized by Z 0 ∼ π X (soZ h = Z ← 0 ∼ π Y ), its construc- tion also ensures that if Z ← 0 ∼ δ y , a point mass, then Z ← h ∼ law(Z 0 |Z h = y) = π X|Y =y . Thus, if we initialize (BH) with Z ← 0 ∼ µ Y i+1 , then the law of Z ← h corresponds to π X|Y =y dµ Y i+1 (y) = µ X i+1 . Remark 1.We note that In-and-Out is exactly the proximal sampling scheme [26, 27, 29] for uniform distributions. The proximal sampler with a target density proportional to exp(-V (x)) considers an augmented distribution π(x, y) ∝ exp(-V (x) -1 2h ∥x -y∥ 2 ) and then repeats the following two steps: (1) y i+1 ∼ π Y |X=xi = N (x i , hI d ) and then (2) x i+1 ∼ π X|Y =yi+1 . Naïvely, the proximal sampler is implemented by performing rejection sampling, with the Gaussian centered at the minimizer of log π •|Y =yi+1 as the proposal. Realizing this would require a projection oracle (to K), which is only known to be implementable with O(d 2 ) membership queries. In-and-Out completely avoids the need for a projection oracle. 
results: 
 Our computational model is the classical general model for convex bodies [30] . We assume vol(K) > 0 throughout this paper. Below, B r (x) denotes the d-dimensional ball of radius r centered at x. Definition 4 (Convex body oracle). A well-defined membership oracle for a convex body K ⊂ R d is given by a point x 0 ∈ K, a number D > 0, with the guarantee that B 1 (x 0 ) ⊆ K ⊆ B D (x 0 ), and an oracle that correctly answers YES or NO to any query of the form "x ∈ K?" Definition 5 (Warmness). A distribution µ is M -warm with respect to another distribution π if for every x in the support of π, we have dµ(x) ≤ M dπ(x).We now summarize our main result, which is further elaborated in Appendix B.4 (Theorem 5). Below, π K is the uniform distribution over K, and R q is the Rényi-divergence of order q (see Definition 1). Theorem 1 (Informal version of Theorem 5). For any given η, ε ∈ (0, 1), q ≥ 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 -warm distribution, with probability at least 1 -η, returns X ∼ µ such that R q (µ ∥ π K ) ≤ ε. The number of proper steps is O(qd 2 Λ log 2 M ηε ), and the expected total number of membership queries is O(qM d 2 Λ log 6 1 ηε ), where Λ is the largest eigenvalue of the covariance of π K . Remark 2. Despite our guarantee being in the much stronger "metric" of R q 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 = Θ(d 2 log qM Λ η log log 1 ε ), N = Θ( qM d 2 Λ log 5 (1/ε) η). See Lemma 3 for more details.Finally, while the assumption of warmness for the initialization may seem strong at the outset, for well-rounded convex bodies (E X∼π [∥X∥ 2 ] ≤ C 2 d for some constant C), it is possible to generate an O(1) warm-start with complexity O(d 3 ). See [6, 31] for details.We note that for X ∼ π K ,∥Cov(π K )∥ op ≤ tr(Cov(π K )) = E[∥X -EX∥ 2 ] ≤ D 2 .The above guarantee in the Rényi divergence immediately provides W 2 , TV, KL, and χ 2 guarantees as special cases. For two distributions µ and π, we have1. KL(µ∥π) = lim q↓1 R q (µ∥π) ≤ R q (µ∥π) ≤ R q ′ (µ∥π) ≤ R ∞ (µ∥π) = log sup dµ dπ , 1 < q ≤ q ′ . 2. 2 ∥µ -π∥ 2 TV ≤ KL(µ ∥ π) ≤ log(χ 2 (µ ∥ π) + 1) = R 2 (µ ∥ π). 3. W 2 2 (µ, π) ≤ 2C LSI (π) KL(µ ∥ π) (Talagrand's T 2 -inequality) and C LSI (π K ) ≲ D 2 . 4. W 2 2 (µ, π) ≤ 2C PI (π) χ 2 (µ ∥ π) [32] and C PI (π K ) ≲ ∥Cov(π K )∥ op log d.The query complexity is better if the convex body is (near-)isotropic, i.e., the uniform distribution over the body has (near-)identity 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 a 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 as above, In-and-Out succeeds with probability 1 -η, returning X ∼ µ such that R q (µ ∥ π K ) ≤ ε. The number of proper steps is O(qd 2 log 2 M ηε ), and the expected total number of membership queries is O(qM d 2 log 6 1 ηε ).Our analysis will in fact show that the bound on the number of proper steps holds for general nonconvex 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 ε ∈ (0, 1) and set K ⊂ B D (0) with vol(K) > 0, In-and-Out with variance h and M -warm initial distribution achieves R q (µ X m ∥ π X ) ≤ ε after the following number of iterations:m = min O qh -1 C PI (π X ) log M ε for q ≥ 2 , O qh -1 C LSI (π X ) log log M ε for q ≥ 1 .We have two different convergence results above under (LSI-I) and (PI). Under (LSI-I) we have a doubly-logarithmic dependence on the warmness parameter M . On the other hand, using (PI), which is weaker than (LSI-I) (in general, C PI ≤ C LSI ), the dependence on M is logarithmic. We discuss implications of our results further in §4.2.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 t and Z ← t 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 µ 0 is given by∂ t µ t = 12 ∆µ t , and its backward heat flow equation is given by∂ t µ ← t = -div µ ← t ∇ log(π X P h-t ) + 1 2 ∆µ ← t with µ ← 0 = µ h .These admit (weak) solutions on [0, h] for any initial distribution µ 0 with dµ0 dπ X ≤ M < ∞.One successful iteration of In-and-Out is exactly the same as the composition of running the forward heat flow and then backward heat flow, both for time h.Lemma 2. Let µ X k be the law of the k-th iterate x k of In-and-Out.If (FH) is initialized with law(Z 0 ) = µ X k , then law(Z h ) = µ Y k+1 . If (BH) is initialized with law(Z ← 0 ) = µ Y k+1 , then law(Z ← h ) = µ X k+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 we 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 is rapidly mixing. Here, we use the heat flow perspective to derive mixing rates under any suitable divergence measure (such as KL, χ 2 , or R q ). 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 µ X k be the law of the k-th output of In-and-Out with initial distribution µ X 0 . Let C LSI be the (LSI-I) constant of the uniform distribution π X over K. Then, for any q ≥ 1,R q (µ X k ∥ π X ) ≤ R q (µ X 0 ∥ π X ) (1 + h/C LSI ) 2k/q . For C PI the (PI) constant of π X , χ 2 (µ X k ∥ π X ) ≤ χ 2 (µ X 0 ∥ π X ) (1 + h/C PI ) 2k . Furthermore, for any q ≥ 2, R q (µ X k ∥ π X ) ≤    R q (µ X 0 ∥ π X ) -2k log(1+h/C PI ) q if k ≤ q(Rq(µ X 0 ∥π X )-1) 2 log(1+h/C PI ) , (1 + h/C PI ) -2(k-k0)/q if k ≥ k 0 := q(Rq(µ X 0 ∥π X )-1) 2 log(1+h/C PI ).The final result reduces the problem of obtaining a mixing guarantee to that of demonstrating a functional inequality on the target distribution. For this, it is not strictly necessary that K be convex.Part (ii). Convexity of K 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 a 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 R d presented by a well-defined membership oracle, π X the uniform distribution over K, and µ an M -warm initial distribution with respect to π X . For any given m ∈ N and η ∈ (0, 1),set Z = 9mM η (≥ 9), h = log log Z 2d 2 log Z and N = Z log 4 Z = O( mM η ).Then, the failure probability of one iteration of In-and-Out is at most η/m, and the expected membership queries per iteration is O M log 4 mM η .No need to be lazy. Previous uniform samplers like Ball walk are made lazy (i.e., with probability 1/2, it does nothing), to 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 in a unified framework. Existing tight guarantees for Speedy walk are in TV distance and based on the log-Sobolev constant, assuming an oracle for implementing each step [37] .The known convergence guarantees of Ball walk (see Appendix C for details), namely the mixing time of O(M d 2 D 2 log 1 ε ) for TV distance, are for the composite algorithm [Speedy walk+rejection sampling]. Here Speedy walk records only the accepted steps of Ball walk, so its stationary distribution 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 π K 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 log-Sobolev).Effective step size. The Ball walk's largest possible step size is of order 1/ √ d (see Appendix C) to keep the rejection probability bounded by a constant. This bound could also be viewed as an "effective" step size of In-and-Out, since the ℓ 2 -norm of the Gaussian N (0, hI) is concentrated around √ hd and we will set the variance h of In-and-Out to O(1/d 2 ), so we have√ hd ≈ 1/ √ d.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 is[random step (y ∈ B δ (x)) + Metropolis-filter (accept if y ∈ K)].This filtering is an abrupt discrete step, and it is unclear how to control contraction. It could be replaced by a step of Speedy walk(x ∼ Unif(B δ (y) ∩ K)).Then, each iteration of In-and-Out can be viewed as a 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 distribution. 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. 
related work: 
 Sampling from constrained 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 a randomized volume-computation 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 diffusiontype 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 a ball of radius δ centered at a current point x, and moves to y if y ∈ K and stays at x otherwise. In the literature, Ball walk actually refers to a 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 O(d -1/2 ) to avoid stepping outside of K. [4] showed that Ball walk needs O(M d 2 D 2 log 1 ε ) membership queries to be ε-close to π K 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 π K .Hit-and-Run is another zeroth-order algorithm that needs no step size; it picks a uniform random line ℓ passing a current point, and move to a uniform random point on ℓ ∩ K. [5] shows that, if we define the second moment asR 2 := E X∼π K [∥X -EX∥ 2 ], then Hit-and-Run requires O(d 2 R 2 log M ε ) queries.Notably, this algorithm has a poly-logarithmic 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 are combined with pre-processing step called rounding. This procedure finds a linear transformation that makes the geometry of K less skewed and so more amenable to sampling. In literature, there exists a randomized algorithm [35] that rounds K and generates a good warm start (i.e., M = O(1)), with Ball walk used as a core subroutine. This algorithm takes up O(d 3.5 ) queries in total, and in such position with the good warm start, Ball walk only needs O(d 2 log 1 ε ) queries to sample from π K .Structured samplers. The aforementioned samplers based on geometric random walks require only access to the membership oracle of the convex body without any additional structural assumptions.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 a self-concordant barrier function ϕ which has regularity on its high-order derivatives and blows up when approaching the boundary ∂K. The Hessian of ϕ encodes the local geometry of the constraint, and the samplers often work directly with ∇2 ϕ.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 ∇ 2 ϕ) 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 algorithm requires no rounding, but still needs a good warm-start, which can be achieved by an annealing-type algorithm using O(md) iterations of Dikin walk [41] .Riemannian Hamiltonian Monte Carlo is a structured sampler that exploits the first-order information of the potential (i.e., ∇ log(1/π)) [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(md 2/3 log M ε ) many iterations to achieve ε-close distance to π K [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 ∇ϕ. The algorithm can also be metropolized [49] . The best known rate for this algorithm is O(d log 1 ε ) under some strong assumptions on ϕ.Diffusion-type samplers. Samplers based on discretizations of Itô diffusions, stochastic processes which rapidly mix to π 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 πX ∝ e -f 1 K , by incorporating first order information from f .The first approach for adapting diffusion-based samplers [50, 25, 51] iterates a two-step procedure. First, a random step is taken, with x k+1/2 ∼ N (x k , 2hI d ) for some appropriately chosen step h, 2 and then project it to K, i.e., x k+1 = proj K (x k+1/2 ). The complexity is given in terms of queries to a projection oracle, each call to which can be implemented with a polynomial number of membership oracle queries; a total of Õ( d 2 D 3 /ε 4 ) queries are needed to be ε-close in W 2 to π X . Another approach, which uses an algorithmically designed "soft" penalty instead of a projection, was proposed in [52] , and achieves a rate estimate of Õ( d /ε 10 ).A second approach, suggested by [24] , considers a different proximal scheme, which performs a "soft projection" onto K, by taking steps like N ((1 -hλ -1 )x k + hproj K (x k ), 2hI d ). It is called 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 Õ(d 5 /ε 6 ) to be ε-close in TV distance to π X .Observing the prior work integrating diffusion-based sampling with convex constraints, the dependence on the key parameters d, ε, 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] .This formulation proved surprisingly powerful, allowing many existing rates in unconstrained sampling 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 on general convex bodies. 
conclusion: 
 We propose In-and-Out for uniform sampling on convex bodies, and show that it obtains guarantees in R q divergence from an M -warm start, substantially stronger than prior work, and without increasing the computational complexity. Notably, our proof technique is quite different and provides a direct reduction to isoperimetric constants of the target distribution.While the current work focuses on uniform sampling of convex bodies, there are a number of natural extensions that may be considered. It may be possible to prove analogous results for general logconcave 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 a Poincaré inequality presented by a function oracle (with no smoothness assumptions). 
safeguards: 
 Question: 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 (e.g., pretrained language models, image generators, or scraped datasets)? 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 a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a 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?Answer: [NA] Justification: The paper does not use existing assets. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.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 of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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 submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Before proceeding, we state two important lemmas which are needed for our proofs. The first is the data-processing inequality for Rényi divergence and f -divergence, given below. Lemma 4 (Data-processing inequality). For measures µ, ν, Markov kernel P , f -divergence D f , and q ≥ 1, it holds thatD f (µP ∥ νP ) ≤ D f (µ ∥ ν) , and R q (µP ∥ νP ) ≤ R q (µ ∥ ν) .Functional inequalities allow us to show exponential contraction of various divergences, through the following helpful inequality. Lemma 5 (Grönwall). Suppose that u, g : [0, T ] → R are two continuous functions, with u being differentiable on [0, T ] and satisfyingu ′ (t) ≤ g(t) u(t) for all t ∈ [0, T ] .Then,u(t) ≤ exp t 0 g(s) ds u(0) for all t ∈ [0, T ] .Before proceeding, we first give the proof of Lemma 2 in the main text. A more general version of Lemma 1 is proved in the form of Lemma 12.Proof of Lemma 2. We explicitly show that the forward and backward heat flows indeed interpolate the two discrete steps given in Algorithm 1. For the forward part, we haveZ h = Z 0 + ζ for ζ ∼ N (0, hI d ), so law(Z h ) = law(Z 0 ) * N (0, hI d ) = µ X k * N (0, hI d ) = µ Y k+1 .Regarding the backward part, it is known from [27, Lemma 14 ] that the construction of the timereversal SDE ensures that (Z ← h , Z ← 0 ) and (Z 0 , Z h ) have the same joint distribution, when Z 0 ∼ π X (and soZ h ∼ π Y ). Hence, law(Z ← h |Z ← 0 = y) = law(Z 0 |Z h = y) = π X|Y =y, where the last equality follows from (Z 0 , Z h ) ∼ π. Since we initialize (BH) withZ ← 0 = y ∼ µ Y k+1 , we have law(Z ← h ) = law(Z ← h |Z ← 0 = y) µ Y k+1 (dy) = π X|Y (•|y) µ Y k+1 (dy) = µ X k+1 ,where the last follows from the definition of Line 3.The contraction of an outer loop of our 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 (PI) 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 log-Cheeger inequalities.Below, we use µ, ν to denote two arbitrary probability measures over R d . The relationship between a Poincaré inequality and the χ 2 -divergence is derived by substituting f = dν dµ into (PI). Lemma 6. Assume that ν satisfies (PI) with parameter C PI (ν). For any probability measure µ over R d with µ ≪ ν, it holds thatχ 2 (µ ∥ ν) ≤ C PI (ν) 2 E ν ∇ dµ dν 2 .The Poincaré inequality implies functional inequalities for the Rényi divergence.Lemma 7 ([23, Lemma 9] ). Assume that ν satisfies (PI) with parameter C PI (ν). For any q ≥ 2 and probability measure µ over R d , it holds that1 -exp(-R q (µ ∥ ν)) ≤ q C PI (ν) 4 RF q (µ ∥ ν) ,where RF q (µ∥ν) := q E ν dµ dνq ∥∇ log dµ dν ∥ 2 / E ν dµ dνq is the Rényi Fisher information of order q of µ with respect to ν.The log-Sobolev inequality paired with the KL-divergence (LSI-II) can be understood as a special case of the following inequality3 paired with the q-Rényi divergence for q ≥ 1. Lemma 8 ([23, Lemma 5] ). Assume that ν satisfies (LSI-II) with parameter C LSI (ν). For any q ≥ 1 and probability measure µ over R d , it holds thatR q (µ ∥ ν) ≤ q C LSI (ν) 2 RF q (µ ∥ ν) .Note that lim q→1 R q = KL and RF 1 = FI.We have collected below the functional inequalities used to establish the mixing of our algorithm (see Appendix D for a detailed presentation). Lemma 9. Let K ⊂ R d be a convex body with diameter D, and π be the uniform distribution over K.Then, C PI (π) ≲ ∥Cov(π)∥ op log d and C LSI (π) ≲ D 2 . If π is isotropic, then C PI (π) ≲ log d and C LSI (π) ≲ D.We start by analyzing how many outer iterations of In-and-Out are required to be ε-close to π X , the uniform distribution over K. The contraction of Algorithm 1 comes from analyzing Lines 2 and 3 through the perspective of heat flows (see §3). To exploit this view, we first revisit the previous contraction analysis in [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 to extend previously known results to the uniform distribution. Lastly, combining the previous results with our technical lemma, we obtain clean contraction results of Algorithm 1 toward the uniform distribution π X in Theorem 3.Part I: Contraction analysis for smooth distributions. In this part, we 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 as the computations for measures evolving under simultaneous forward/backward heat flows. We refer interested readers to Appendix E for additional details. Only in Part I, we assume that ν denotes a probability measure with smooth density.Forward heat flow. We begin by introducing the "heat flow" equation (or also known as the Fokker-Planck equation), which describes the evolution of the law of Z t under (FH),∂ t µ t = 1 2 ∆µ t = 1 2 div(µ t ∇ log µ t ) . (FP-FH)It is well known that one can realize this equation in discrete time through a Gaussian transition density, in the sense that, for µ h (the solution at time h > 0 to (FP-FH) with initial condition µ 0 ), and for any smooth function f :R d → R, E µ h [f (x)] = E µ0 [P h f (x)] ,whereP h f (x) = E N (x,hI d ) [f ]. 4 By this we can formally identify µ h = µ 0 P h , and also write µ h for the law of Z h , where {Z h } h≥0 solves (FH).Proof. Since the SDE in (B.1) captures the forward heat flow (FH), we set µ 0 and ν 0 in Lemma 10 to µ and ν, 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 R q (µ ∥ ν) := 1 q-1 log(D f (µ ∥ ν) + 1), with f (x) = x q -1 and g(x) = 1 q-1 log(x + 1),∂ t R q (µP t ∥ νP t ) = - q 2 E µPt ∇ µPt νPt q-1 , ∇ log µPt νPt (q -1) E νPt µPt νPt q = (i) - q 2 E µPt µPt νPt q-2 ⟨∇ µPt νPt , ∇ log µPt νPt ⟩ E νPt µPt νPt q = (ii) - q 2 E νPt µPt νPt q ∥∇ log µPt νPt ∥ 2 E νPt µPt νPt q = - 1 2 RF q (µP t ∥ νP t ) ,where in (i), we use again that∇ f ′ µt νt µt νt = ∇ f ′ • µt νt • µt νt + f ′ µt νt ∇ µt νt, and (ii) uses that ∇ µPt νPt = µPt νPt ∇ log µPt νPt , and the last equality recalls the definition of the Rényi Fisher information. This yields∂ t R q (µP t ∥ νP t ) = - 1 2 RF q (µP t ∥ νP t ) ≤ (i) - 1 q R q (µP t ∥ νP t ) C LSI (νP t ) ≤ (ii) - 1 q R q (µP t ∥ νP t ) C LSI + t ,where we used Lemma 8 in (i) and Lemma 11 in (ii). Applying Grönwall's inequality (Lemma 5),R q (µP h ∥ νP h ) ≤ exp - 1 q h 0 1 C LSI + t dt R q (µ ∥ ν) ≤ R q (µ ∥ ν) (1 + h/C LSI ) 1/q .Since the SDE (B.1) also captures the backward equation (BH), we set µ 0 and ν 0 in Lemma 10 to µP h and ν := νP h respectively, obtaining contraction along the backward heat flow:∂ t R q (µP h Q t ∥ νQ t ) = - 1 2 RF q (µP h Q t ∥ νQ t ) ≤ - 1 q R q (µP h Q t ∥ νQ t ) C LSI (νQ t ) ≤ (i) - 1 q R q (µP h Q t ∥ νQ t ) C LSI + h -t ,where (i) follows from that νQ t = νP h Q t = νP h-t and C LSI (νQ t ) ≤ C LSI +h-t due to Lemma 11. Applying Lemma 5 again yieldsR q (µP h Q h ∥ ν) ≤ R q (µP h ∥ ν) (1 + h/C LSI ) 1/q .Composing these two inequalities leads to the decay rate claimed in the theorem.The result in the χ 2 -divergence can be derived entirely analogously. For instance, the decay from the forward part can be shown as follows:∂ t χ 2 (µP t ∥ νP t ) = - 1 2 E νPt ∇ µP t νP t 2 ≤ (i) - χ 2 (µP t ∥ νP t ) C PI (νP t ) ≤ - χ 2 (µP t ∥ νP t ) C PI + t ,where (i) follows from Lemma 6. Applying Grönwall's inequality then givesχ 2 (µP h ∥ νP h ) ≤ exp - h 0 1 C PI + t dt χ 2 (µ ∥ ν) ≤ χ 2 (µ ∥ ν) 1 + h/C PI .The decay along the backward heat flow in χ 2 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 R q under (PI) can be shown in a 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:1 -exp -R q (µ ∥ ν) ≥ 1 2 if R q (µ ∥ ν) ≥ 1 , 1 2 R q (µ ∥ ν) if R q (µ ∥ ν) ≤ 1 .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 3 in In-and-Out, in addition to lower-semicontinuity of f -divergence. We shall prove it for any measure that is absolutely continuous with respect to π X , since this imposes no additional technical hurdles.Lemma 12. Let ν be a measure, absolutely continuous with respect to the uniform measure π X . The forward and backward heat flow equations given by∂ t µ t = 1 2 ∆µ t , ∂ t µ ← t = -div µ ← t ∇ log(νP h-t ) + 1 2 ∆µ ← t with µ ← 0 = µ h ,admit solutions on (0, h], and the weak limit lim t→h µ ← t = µ ← h exists for any initial measure µ 0 with bounded support. Moreover, for any f -divergence with f lower semi-continuous,D f (µ ← h ∥ ν) ≤ lim t↓0 D f (µ ← h-t ∥ ν t ) .Proof. The existence of weak solutions for the forward equation is well-known, since µ 0 can be weakly approximated by measures with continuous density, for which the heat equation admits a unique solution for all time. In particular, the weak solution is C ∞ for t > 0.The reverse SDE is more subtle, since ∇ log νP t will in general cease to be Lipschitz as t → 0. On the other hand, for any h > 0, we can write explicitlyµ h (x) = 1 (2πh) d/2exp -∥x -y∥ 2 2h dµ 0 (y) .If one considers the system started at μ0 = µ ϵ = νP ϵ and solve the forward-backward Fokker-Planck equations on times [0, h -ϵ], then μh-ϵ = µ h = µ ← 0 = μ← 0 andµ ← h-ϵ (x) = μ← h-ϵ (x) = exp -∥x-y∥ 2 2(h-ϵ) νP ϵ (x) exp -∥z-y∥ 2 2(h-ϵ) νP ϵ (z) dz dµ h (y) .This follows from that if we consider system started at time ϵ > 0, with initial distribution µ ϵ , 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, so μ← h is well-defined:μ← h (x) := exp -∥x-y∥ 2 2h ν(x) exp -∥z-y∥ 2 2h ν(z) dz dµ h (y) .For fixed x and ϵ < h/2,exp - ∥z -y∥ 2 2(h -ϵ) ν(z) dz ≳ exp - (∥y -x 0 ∥ + D) 2 2(h -ϵ) ,as the support of ν is constrained to K ⊂ B D (x 0 ). Since µ 0 has bounded support, µ h (y) ≲ exp(-∥y∥ 2 a ) for some constant a > 0. Thus,exp -∥x-y∥ 2 2(h-ϵ) µ h (y) exp -∥z-y∥ 2 2(h-ϵ) νP ϵ (z) dz ≲ exp -∥x-y∥ 2 2(h-ϵ) µ h (y) exp(-(∥y-x0∥+D) 2 2(h-ϵ) ) ≲ exp ⟨2(x -x 0 ), y⟩ + 2D∥y -x 0 ∥ h - ∥y∥ 2 a ,and the last bound is integrable in y.We then show the pointwise convergence of μ← h-ϵ to μ← h as ϵ → 0. Note that νP ϵ → ν, as ν has a bounded support. Also, the denominator is independent of ϵ due to1 (2π(h -ϵ)) d/2 exp - ∥z -y∥ 2 2(h -ϵ) νP ϵ (z) dz = N (0, (h -ϵ)I) * νP ϵ = ν * N (0, hI) . Hence, for ϵ ≤ d -1 , exp -∥x-y∥ 2 2(h-ϵ) exp -∥z-y∥ 2 2(h-ϵ) νP ϵ (z) dz ≤ h h -ϵ d/2 exp -∥x-y∥ 2 2h exp -∥z-y∥ 2 2h ν(z) dz ≲ exp -∥x-y∥ 2 2h exp -∥z-y∥ 2 2h ν(z) dz .As shown above, the last bound is integrable with respect to µ h , so the dominated convergence theorem implieslim ϵ→0 exp -∥x-y∥ 2 2(h-ϵ) exp -∥z-y∥ 2 2(h-ϵ) νP ϵ (z) dz dµ h (y) = exp -∥x-y∥ 2 2h exp -∥z-y∥ 2 2h ν(z) dz dµ h (y) ,Thus, the pointwise convergence follows. Note that if we take ν(x) = π X (x) = 1 K (x) vol(K) , then μ← h is the distribution of the backwards step of our algorithm. In particular, this corresponds to first sampling x ∼ µ h , then y ∼ Q ν,h h (•|x), which is precisely the law of µ ← h given by (FP-BH). As for the second statement, it follows from Scheffé's lemma [59, Theorem 16 .12] that the pointwise convergence of µ ← h-ε → µ ← h leads to its TV-convergence, which in turn implies the weak convergence. It follows from lower semicontinuity of D f [60, Theorem 2.34] that the weak convergence ensuresD f (µ ← h ∥ ν) ≤ lim t↓0 D f (µ ← h-t ∥ ν ← h-t ).In the sequel, we will only consider ν = π X . Since the Rényi divergence is a continuous function of the χ q divergence (see Definition 1), which itself is an f -divergence, it enjoys the same lower-semicontinuity properties. Using this lower-semicontinuity together with the decay results in Theorem 4, we can easily derive the contraction results of In-and-Out in R q and χ q for any q ≥ 1.We remark that this result does not require convexity of K.Proof of Theorem 3. Let us set µ 0 = µ X 0 and π 0 = π X . Then,µ h = µ ← 0 = µ Y 1 , π h = π ← 0 = π Y , and µ ← h = µ X 1 , π ← h = π X . For small ϵ > 0, as µ ϵ = (µ X 0 ) ϵ = µ X 0 * N (0, ϵI d ) is C ∞ -smooth, we can now invoke the decay results with step size h -ϵ in Theorem 4. Thus, for contraction constantsC ϵ = (1 + h-ϵ C LSI +ϵ ) -2/q and C ϵ = (1 + h-ϵ C PI +ϵ ) -2 respectively when Φ = R q and Φ = χ 2 , Φ(µ ← h-ϵ ∥ π ϵ ) ≤ C ϵ • Φ(µ ϵ ∥ π ϵ ) ≤ C ϵ • Φ(µ 0 ∥ π 0 ), where we used the data-processing inequality for the last inequality. By the second result of Lemma 12, sending ϵ → 0 leads toΦ(µ X 1 ∥ π X ) = Φ(µ ← h ∥ π 0 ) ≤ C • Φ(µ 0 ∥ π 0 ) = C • Φ(µ X 0 ∥ π X ) .Repeating this argument k times completes the proof.We begin by defining a suitable version of local conductance [4] . Definition 6 (Local conductance). The local conductance ℓ on R d is defined byℓ(x) def = K exp(-1 2h ∥x -y∥ 2 ) dy R d exp(-1 2h ∥x -y∥ 2 ) dy = K exp(-1 2h ∥x -y∥ 2 ) dy (2πh) d/2.The local conductance at y quantifies the success probability of the proposal at y in Line 3. Then the expected number of trials until the first success of Line 3 is 1/ℓ(y). Revisiting (3.1), we can notice π Y (y) = ℓ(y)/ vol(K).Naïve analysis for expected number of trials. Starting from π X , when we just naïvely sample from π Y |X (•|x) for all x without imposing any failure condition, the expected number of trials for one iteration is that for the probability density p x of N (x, hI d ),K R d 1 ℓ(y) p x (dy)π X (dx) = R d 1 ℓ(y) π Y (dy) = R d 1 ℓ(y) ℓ(y) vol(K) dy = ∞ .This suggests that one should consider the algorithm as 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 previous work for uniform sampling algorithms. By induction we have dµ X i dπ X ≤ M for all i. Lemma 13 (Propagation of warm-start). From an M -warm start, we have dµ X i /dπ X ≤ M for all i.Proof. Assume that µ X i satisfies the M -warm start. Then, for any measurable S and the transition kernelT x of Algorithm 1 at x, µ X i+1 (S) = K T x (S) dµ X i (x) ≤ M K T x (S) dπ X (x) = M π X (S) ,where the last equality follows from the stationarity of π. Hence, dµ X i+1 /dπ X ≤ M .We now establish a lemma that comes in handy when analyzing the failure probability of the algorithm. In essence, this lemma bounds the probability that taking a Gaussian step from π X in Line 2 gets δ-distance away from K. Let us denote the δ-blowup of K byK δ := {x ∈ R d : d(x, K) ≤ δ}. Lemma 14. For a convex body K ⊂ R d containing a unit ball B 1 (0), π Y (K c δ ) ≤ exp - δ 2 2h + δd .Proof. For y ∈ ∂K δ , we can take the supporting half-space H(y) at proj K (y) containing K, due to convexity of K. Then,π Y (K c δ ) = 1 vol(K) K c δ K exp(-1 2h ∥y -x∥ 2 ) (2πh) d/2dx dy≤ 1 vol(K) K c δ H(y) exp(-1 2h ∥y -x∥ 2 ) (2πh) d/2 dx dy = 1 vol(K) K c δ ∞ d(y,K) exp(-z 2 2h ) √ 2πh dz dy . (B.3)Let us denote the tail probability of the 1-dimensional Gaussian with variance h byT(s) := P N (0,h) (Z ≥ s) = 1 -Φ(h -1/2 s) ,where Φ is the CDF of the standard Gaussian. By the co-area formula and integration by parts,K c δ ∞ d(y,K) exp(-1 2h z 2 ) √ 2πh dzdy = ∞ δ T(s) vol(∂K s ) ds = T(s) s 0 vol(∂K z ) dz =:F ∞ δ + ∞ δ 1 √ 2πh exp - s 2 2h s 0 vol(∂K z ) dz ds . (B.4)Recall that T(s) ≤ 1 2 exp(-1 2 (h -1/2 s) 2 ) for h -1/2 s ≥ 0 due to a standard tail bound on a Gaussian distribution. This tail bound, combined withs 0 vol(∂K z ) dz = vol(K s ) -vol(K) ≤ vol (1 + s) K -vol(K) = (1 + s) d -1 vol(K) ,ensures that F vanishes at s = ∞. Hence, bounding the first term in (B.4) by 0 results inK c δ ∞ d(y,K) exp(-1 2h z 2 ) √ 2πh dz dy ≤ 1 √ 2πh ∞ δ exp - s 2 2h (1 + s) d ≤exp(sd) -1 vol(K) ds ≤ vol(K) √ 2πh exp(hd 2 /2) ∞ δ exp - 1 2h (s -hd) 2 ds ≤ (i) vol(K) exp(hd 2 /2) exp - (δ -hd) 2 2h = vol(K) exp - δ 2 2h + δd ,where in (i) we used the tail bound for a Gaussian.This core lemma suggests taking δ = t /d and h = c /d 2 for some t, c > 0, under which we haveπ Y (K c δ ) ≤ exp - t 2 2c + t .Now we choose a suitable threshold N for bounding the failure probability. Following (B.3) in the proof, one can notice that for y ∈ K c δ , δ = Ω(1/d), andh = Θ(d -2 ), ℓ(y) ≤ ∞ d(y,K) exp(-1 2h z 2 ) √ 2πh dz = P Z∼N (0,h) (Z ≥ δ) ≤ exp(-Ω(t 2 )) .Thus, the expected number of trials from K c δ for the rejection sampling in Line 3 is ℓ(y) -1 ≥ exp(Ω(t 2 )). Intuitively, one can ignore whatever happens in K c δ , since K δ takes up most of measure of π Y . As the number of trials from K c δ is at least exp(Ω(t 2 )) in expectation, the most straightforward way to ignore algorithmic behaviors from K c δ is simply to set the threshold to N = O(exp(t 2 )). Even though the threshold is N , the expected number of trials is much lower. Lemma 3 bounds the failure probability and expected number of trials per iteration.Proof of Lemma 3. For µ h := µ * N (0, hI d ), the failure probability isE µ h [(1 -ℓ) N ]. Since dµ/dπ X ≤ M implies dµ h /d(π X ) h = dµ h /dπ Y ≤ M , it follows that E µ h [(1 -ℓ) N ] ≤ M E π Y [(1 -ℓ) N ] . Then, R d (1 -ℓ) N dπ Y =:A = K c δ A + K δ ∩[ℓ≥N -1 log(3mM/η)] A + K δ ∩[ℓ<N -1 log(3mM/η)] A ≤ π Y (K c δ ) + [ℓ≥N -1 log(3mM/η)] exp(-ℓN ) dπ Y + K δ ∩[ℓ<N -1 log(3mM/η)] ℓ(y) vol(K) dy ≤ exp - t 2 2c + t + η 3mM + log(3mM/η) N vol(K δ ) vol(K) ≤ exp - t 2 2c + t + η 3mM + e t N log 3mM η ,where we used vol(K δ ) ⊂ vol (1 + δ)K = (1 + δ) d vol(K) ≤ e t vol(K). Taking c = log log Z 2 log Z , t = √ 8 log log Z, and N = Z(log Z) 4 , we can bound the last line by η mM . Therefore,E µ h [(1 -ℓ(•)) N ] ≤ M E π Y [(1 -ℓ(•)) N ] ≤ η m .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 is bounded by M E π Y X since dµ h /dπ Y ≤ M . Thus,R d 1 ℓ ∧ N dπ Y ≤ K δ 1 ℓ dπ Y + N π Y (K c δ ) = vol(K δ ) vol(K) + N π Y (K c δ ) ≤ e t + N exp - t 2 2c + t ≤ (log Z) 3 + 3(log Z) 4 = O log 4 mM η .Therefore, the expected number of trials per step is O(M log 4 mM η ), and the claim follows since each trial uses one query to the membership oracle of K.We can now show that In-and-Out subsumes previous results on 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∥ • ∥ 2 TV ≤ KL ≤ log(1 + χ 2 ) ≤ χ 2 . Theorem 5. For any given η, ε ∈ (0, 1), q ≥ 1, m ∈ 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 µ X 0 , h = (2d 2 log 9mM η ) -1 , and N = O( mM η ). For π X the uniform distribution over K,• It achieves R q (µ X m ∥ π X ) ≤ ε after m = O(qd 2 ∥Cov(π X )∥ op log 2 M ηε ) iterations.With probability 1 -η, the algorithm iterates this many times without failure, using O(qM d 2 ∥Cov(π X )∥ op log 6 1 ηε ) expected number of membership queries in total.• For isotropic π X , with probability 1 -η, the algorithm achievesR q (µ X m ∥ π X ) ≤ ε with m = O(qd 2 log 2 M ηε ) iterations, using O(qM d 2 log 6 1 ηε ) membership queries in expectation.Proof. We just put together Lemma 3 and Theorem 3. For target accuracy ε > 0, we use the R q -decay under (PI) for q ≥ 2 in Theorem 3. The M -warm start assumption guarantees R q (µ X 0 ∥π X ) ≲ log M . Due to C PI (π X ) = O(∥Cov(π X )∥ op log d) (Lemma 9), In-and-Out can achieve R q (µ X m ∥ π X ) ≤ ε after m = O(qd 2 ∥Cov(π X )∥ op log 2 M ηε ) iterations. Since each iteration has η/m-failure probability by Lemma 3, the union bound ensures that the total failure probability is at most η throughout m iterations. Lastly, each iteration requires O(M log 4 1 ηε ) membership queries in expectation by Lemma 3. Therefore, In-and-Out uses O(qM d 2 min(D 2 , ∥Cov(π X )∥ op ) log 6 1 ηε ) expected number of membership queries over m iterations. Since R q is non-decreasing in q, we can obtain the desired bound on R q for q ∈ [1, 2).For isotropic π X , we have Cov(π X ) = I d , so the claim immediately follows from C PI (π X ) = O(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 an M -warm start (Theorem 2).Proof of Theorem 2. By the Rényi-decay under (LSI-I) in Theorem 3, In-and-Out can achieve ε-distance to π X after O qh -1 C LSI (π X ) log Rq(µ X 1 ∥π X ) ε iterations for q ≥ 1.For q ≥ 2, we use the decay result under (PI). In this case, In-and-Out decays under two different rates depending on the value ofR q (• ∥ π X ). It first needs O(qh -1 C PI (π X )R q (µ X 0 ∥ π X )) iterations until R q (• ∥ π X ) reaches 1. Then, In-and-Out additionally needs O(qh -1 C PI (π X ) log 1 ε ) iterations, and thus it needs O(qh -1 C PI (π X ) R q (µ X 0 ∥ π X ) + log 1 ε ) iterations in total. By substituting R q (µ X 0 ∥ π X ) ≲ log M , we complete the proof.Next, we show that In-and-Out mixes from any start.Corollary 2. For any given ε ∈ (0, 1) and set K ⊂ B D (0), In-and-Out with variance h and any feasible startx 0 ∈ K achieves R q (µ X m ∥ π X ) ≤ ε after m = O(qh -1 C LSI (π X ) log d+D 2 /h ε ) iterations.Proof. We first bound the warmness of µ X 1 w.r.t. π X when µ X 0 = δ x0 . One can readily check thatµ X 1 (x) = 1 K (x) • exp -1 2h ∥y -x∥ 2 exp -1 2h ∥y -x 0 ∥ 2 (2πh) d/2 K exp -1 2h ∥y -x∥ 2 dx dy .By Young's inequality, ∥y -x∥ 2 ≤ (∥y∥ + D) 2 ≤ 3 2 ∥y∥ 2 + 3D 2 for x ∈ K. Hence, exp -1 2h ∥y -x∥ 2 exp -1 2h ∥y -x 0 ∥ 2 K exp -1 2h ∥y -x∥ 2 dx dy ≤ exp(2h -1 D 2 ) vol(K) exp - 1 2h ∥y -x∥ 2 + ∥y -x 0 ∥ 2 - 3 2 ∥y∥ 2 dy = exp(2h -1 D 2 ) vol(K) exp - 1 2h 1 2 ∥y -2(x + x 0 )∥ 2 + (∥x∥ 2 + ∥x 0 ∥ 2 -2∥x + x 0 ∥ 2 ) dy ≤ exp(5h -1 D 2 ) vol(K) exp - 1 4h ∥y -2(x + x 0 )∥ 2 dy = exp(5h -1 D 2 ) vol(K) (4πh) d/2 .Therefore, M = ess supµ X 1 π X ≤ 2 d/2 exp(5h -1 D 2 ). By Theorem 2 under (LSI-I), In-and-Out needsO(qh -1 C LSI (π X ) log d+D 2 /h ε ) iterations.We then obtain the following corollary for a convex body K. Corollary 3. For any given ε ∈ (0, 1) and convex body K ⊂ B D (0), In-and-Out with variance h and an M -warm initial distribution achievesR q (µ X m ∥ π X ) ≤ ε after m = O(qh -1 D 2 log 1 ε ) iterations. If π X is isotropic, then In-and-Out only needs O(qh -1 D log d+d 2 /h ε ) iterations.Proof. For convex K, it follows from Lemma 9 that C LSI (π X ) = O(D 2 ) and C LSI (π X ) = O(D) for isotropic K. The rest of the proof can be completed in a similar way.For h = Θ(d -2 ), In-and-Out requires O(qd 2 D 2 ) iterations and in particular O(qd 2 D) iteration for isotropic uniform distributions. These results match those of Speedy walk [61, 37] (see Theorem 7) .We restate the previously known guarantees for uniform sampling by Ball walk and Speedy walk. Below, let B r (x) denote the d-dimensional ball of radius r centered at x.Input: initial distribution π 0 , convex body K ⊂ R d , iterations T , step size δ > 0. 1: Sample x 0 ∼ π 0 . 2: for i = 1, . . . , T do 3:Sample y ∼ Unif(B δ (x i-1 )).If y ∈ K, then x i ← y. Else, x i ← x i-1 . 5: end for Ball walk is particularly simple; draw a uniform random point from B δ around the current point, and go there if the drawn point is inside of K and stay at the current point otherwise. Its stationary distribution can be easily seen to be π ∝ 1 K , the uniform distribution over K.In the literature, there are two approaches to analyzing the convergence rate of this sampler: (i) a 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 π. We refer interested readers to [16, §5] . Theorem 6 (Convergence of Ball walk). For any ε ∈ (0, 1) and convex body K ⊂ R d presented by a well-defined membership oracle, let π t be the distribution after t steps of Ball walk with an M -warm initial distribution π 0 . Then, Ball walk with step size δ = Θ( εM √ d ) achieves ∥π t -π∥ TV ≤ ε for t ≳ d 2 D 2 M 2 ε 2 log M ε . If π is isotropic, then Ball walk needs O(d 2 M 2 ε 2 log d log M ε ) iterations.The mixing time of Ball walk under this approach has a polynomial dependence on 1/ε, rather than a 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 to 'Speedy walk combined with the conversion step', rather than a direct implementation of Algorithm 2. Strictly speaking, a mixing guarantee of this combined algorithm should not be referred to as a provable guarantee of Ball walk.Input: initial distribution π 0 , convex body K ⊂ R d , iterations T , step size δ > 0. 1: Sample x 0 ∼ π 0 . 2: for i = 1, . . . , T do 3: Sample x i ∼ Unif(K ∩ B δ (x i-1 )).As opposed to Ball walk, Speedy walk always takes some step at each iteration. However, the problem of sampling from x i ∼ Unif(K ∩ B δ (x i-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(B δ (x i-1 )). • Set x i+1 ← y if y ∈ K. Otherwise, repeat the proposal.Each actual step (indexed by i) in Speedy walk is called a proper step, and rejected steps during ( * ) are called improper steps. For example, if x 1 , x 1 , x 2 , x 3 , x 3 , x 3 , x 4 , . . . are the positions produced by Ball walk, then only proper steps x 1 , x 2 , x 3 , x 4 , . . . are recorded by Speedy walk.To describe the theoretical guarantees of Speedy walk, we define the local conductance ℓ(x) at x ∈ K, which measures the success probability of the rejection sampling scheme in ( * ):ℓ(x) := vol(K ∩ B δ (x)) vol(B δ (x)) ,and define the average conductance:λ := E π ℓ = 1 vol(K) K ℓ(x) dx . Proposition 1 ([4]). The stationary distribution ν of Speedy walk has densityν(x) = ℓ(x) 1 K (x) K ℓ(x) dx .The speedy distribution ν is indeed different from the uniform distribution π, and this discrepancy is quantified in terms of the average conductance.Proposition 2 ([4, Page 22] ). ∥ν -π∥ TV ≤ 1-λ λ . One can relate the step size δ to the average conductance. Proposition 3 (Bound on average conductance, [4, Corollary 4.5] ). λ ≥ 1 -δ √ d2 . The best known result for Speedy walk's mixing is due to [61] devising the blocking conductance and using the log-Cheeger inequality. When ν is isotropic (i.e., it has covariance proportional to the identity matrix), [37] improves the mixing bound via the log-Cheeger constant. Theorem 7 (Mixing of Speedy walk). For any ε ∈ (0, 1) and convex body K ⊂ R d presented by a well-defined membership oracle, let ν t be the distribution after t proper steps of Speedy walk started at any feasible point x 0 ∈ K. Then, Speedy walk with step size δ = Θ(d -1/2 ) achieves ∥ν t -ν∥ TV ≤ ε for t ≳ (D 2 + log(D √ d)) d 2 log 1 ε . From an M -warm start, the expected number of improper steps during t iterations is O(tM ). When ν is isotropic, Speedy walk needs O(d 2 D log 1 ε log log D) proper steps to achieve ε-TV distance to ν.Then, [4] uses the following post-processing step to obtain an approximately uniform distribution on K, with a provable guarantee.A: Call Speedy walk to obtain a sample X ∼ ν t until 2d 2d-1 X ∈ K. If so, return X = 2d 2d-1 X. Proposition 4 ([4, Theorem 4.16] ). Under the same setting above, assume ∥ν t -ν∥ TV ≤ ε for step size δ ≤ (8d log d ε ) -1/2 and fixed t ∈ N. For ν = law( X) given by A, it holds that ∥ν -π∥ TV ≤ ε, and the expected number of calls on 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 ε-close to π in TV is O(M d 2 D 2 log 1 ε ), which now has a poly-logarithmic dependence on 1/ε. Remark 3 (Backward heat flow analysis of Speedy walk). Consider a Gaussian version of Speedy walk, whose one-step corresponds to x i+1 ∼ N (x i , hI d )| K , and this transition kernel exactly matches integrating (BH) for time h. Thus, νQ π X ,h h = ν due to the stationarity of ν under Speedy walk, where Q π X ,h h is the transition kernel defined by the backward heat flow for time h that reverses π X * N (0, hI d ) to π X . Hence, if we can control the LSI/PI constants of ν along the backward heat-flow's trajectory, then we could directly analyze Speedy walk by emulating computations in Lemma 4.We provide full details on functional inequalities omitted in Appendix B.1. We use µ and µ LC to denote a probability measure and log-concave probability measure over R d , respectively.Cheeger and PI constants. The Cheeger isoperimetric constant C Ch (µ) measures how large surface area a measurable subset with larger volume has, defined byC Ch (µ) := inf S⊂R d µ + (S) min(µ(S), µ(S c )),where the infimum is taken over all measurable subsets S, and µ + (S) is the Minkowski content of S under µ defined as, for S ε := {x ∈ X : d(x, S) < ε}, µ + (S) := lim inf ε→0 µ(S ε ) -µ(S) ε .[62] established C PI (µ) ≲ C -2 Ch (µ) 5 , and then [33] showed that for covariance matrixΣ µ := E µ [(• -E µ X)(• -E µ X) T ], C Ch (µ LC ) ≳ 1 (E µ LC [∥X -E µ LC X∥ 2 ]) 1/2 = 1 (tr Σ µ LC ) 1/2 . (D.1)This immediately leads to C PI (π) ≲ (E π [∥X -E π X∥ 2 ]) 1/2 ≤ D 2 for the uniform distribution π over a convex body K with diameter D > 0.Kannan et al. proposed the KLS conjecture in the same paper, which says that for the spectral norm∥ • ∥ 2 , C Ch (µ LS ) ≳ 1 ∥Σ µ LS ∥ 1/2 2.While the original result in [33] ensures C Ch ≳ d -1/2 for an isotropic log-concave distribution (due to Σ = I d ), this conjecture indeed claims C Ch ≳ 1 for such case. Following a line of work [37, 55, 65, 34] , the current bound isC Ch (µ LS ) ≳ (log d) -1/2 ∥Σ µ LS ∥ 1/2 2, which implies that C PI (π) ≲ log d when π is isotropic for convex K.Log-Cheeger and LSI constants. Just as the Cheeger and PI constants are related above, there are known connections between LSI and log-Cheeger constants. The log-Cheeger constant C logCh (µ) of a distribution µ ∈ P(R d ) is defined asC logCh (µ) := inf S⊂R d :µ(S)≤ 1 2 µ + (S) µ(S) log 1 µ(S).[64] established that C LSI (µ) ≲ C -2 logCh (µ) 6 , and [61] showed that any log-concave distributions with support of diameter D > 0 satisfy C logCh (µ LS ) ≳ D -1 . Later in 2016, [37] improved this to C logCh (µ LS ) ≳ D -1/2 under isotropy. Therefore, for convex K, it follows that C LSI (π) ≲ D 2 and that C LSI (π) ≲ D if π is isotropic.We present additional technical background on the Wasserstein geometry and Markov semigroup theory. Interested readers can refer to [66, 67, 28] for standard references on Wasserstein spaces and applications to sampling.Wasserstein gradient. Let P 2,ac (R d ) be the space of probability measures admitting densities on R d with finite second moment. Although there are many ways to metrize P 2,ac (R d ), the geometry induced by the Wasserstein-2 distance W 2 is a particularly useful structure for analysis.Under the W 2 -geometry, one can define a "gradient" of a functional defined over P 2,ac (R d ). Specifically, for a functionalF : P 2,ac (R d ) → R ∪ {∞}, the Wasserstein gradient of F at µ ∈ P 2,ac (R d ) is defined as ∇ W2 F(µ) = ∇(δF)(µ) ∈ L 2 (µ), where ∇ is the standard gradient and δF is the first variation of F 7 . Equipped with this W 2 -gradient, one can define the Wasserstein gradient flow of F that describes the evolution of a measure {µ t } t≥0 , from some initial measure µ 0 , as follows:∂ t µ t = div µ t ∇ W2 F(µ t ) .More generally, we can identify the Wasserstein "velocity" for some measure µ t as v t if the time derivative of µ t can be written in the form∂ t µ t = -div(µ t v t ) .Under this identification, the time derivative of a functional F on P 2,ac (R d ) with smooth Wasserstein gradient under these dynamics can be written as 6 The opposite direction holds under dimension-scaling due to [64] : C LSI (µ) ≳ C -2 logCh (µ)/d. 7 The first variation can be defined, for any measures ν0, ν1 ∈ P2,ac(R d ), as lim t↓0 F ((1-t)ν 0 +tν 1 )-F (ν 0 ) t = ⟨δF(ν0), ν1 -ν0⟩. This definition is unique up to an additive constant, which is irrelevant as we are only concerned with its gradient.∂ t F(µ t ) = E µt ⟨∇ W2 F(µ t ), v t ⟩ ,when v t ∈ {∇ψ : ψ ∈ C ∞ c (R d )} L 2 (µt), where{•} L 2 (µt)denotes the closure of a set with respect to L 2 (µ t ). This is the appropriate notion of tangent space in this geometry.For instance, when we take the functional to be the entropy of the measure, H(µ) := ∂ t µ ← t = -div(µ ← t a T -t ) - 1 2 ∆µ ← t = -div µ ← t (a T -t + ∇ log µ T -t ) + 1 2 ∆µ ← tIn particular, this describes the evolution of law(X t ) of the stochastic differential equation:dX t = a T -t (X t ) + ∇ log µ T -t (X t ) dt + dB t with X 0 ∼ µ ← 0 = µ T . (E.3)While the law of this process will give µ ← T = µ 0 at time T , it is also true that it will give µ 0|T (•|z) if one starts (E.3) at X 0 = z. This is a subtle fact, whose justification requires the introduction of a tool called Doob's h-transform. The presentation of this subject is beyond the scope of this paper, and we refer interested readers to [53] as a reference to its application in this context.• If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, 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 to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. Justification: 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. Guidelines:• The answer NA means that there is no 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 or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or 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 in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).38th Conference on Neural Information Processing Systems (NeurIPS 2024).This name reflects the "geometry" of how the iterates are moving. As we elaborate in Remark 1, the name 'proximal sampler' may be more familiar to those from an optimization background.A gradient step can be added in the more general case, for sampling from πX .Such inequalities are often called Polyak-Łojasiewicz inequalities, which say for f : R d → R, and all y ∈ R d that f (y) ≤ c ∥∇f (y)∥ 2 for some constant c, if min f (x) = 0.{P h } h≥0 is often called the heat semigroup.The opposite direction C PI (µ LC ) ≳ C -2 Ch (µ LC ) also holds for log-concave distributions due to[63], whileC PI (µ) ≳ C -2Ch (µ)/d for general distributions due to[64]. 


Decision: 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.

Reviews: review: paper_summary: paper_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).
strength_weakness: strength_weakness: - 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.

Some minor suggestions:
- 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.
- 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.
- 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).
- 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.
questions: questions: - Regarding the first point in "Weaknesses": what are some application cases in machine learning where your work applies?
- 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)
- 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)
- 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: limitations: The authors have adequately addressed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: - The analysis techniques used in the paper already exist in the literature, which limits the technical contribution.
-The paper does not provide a comparison of iteration/query complexity with existing works.
questions: questions: - Is it possible to extend these results to the log-concave setting?
- The membership oracle used is standard. What if we are given the polytope constraint explicitly?
limitations: limitations: NA
paper_summary: paper_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. 
Sampling 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.

The 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. 
The 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.
strength_weakness: strength_weakness: - 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].
questions: questions: - Can you provide more details on the initialization process and parameter selection (e.g., h, N) for the algorithm?
- Could you elaborate on how the functional isoperimetric constants influence the convergence rate of the algorithm for specific geometry (polytopes, ellipsoids, etc...) ?
- 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 ?]
-
limitations: limitations: yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

Minor 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.
questions: 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?

- I didn't quite follow Line 146-149 - how would In-and-Out compare to projection-based method? 


- 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.


- How does one obtain a warm start in practice?
limitations: limitations: Yes the work is mostly theoretical.

Comments: comment: Thank you very much for your detailed response.
This is a good paper. I will keep my score !
We are unclear on the reviewer's "reservation". The problem of sampling constrained convex bodies has been widely studied for decades and so far did not have guarantees beyond TV distance; moreover, in recent years, it has been a well-known open problem to see if diffusion-based methods could be used to obtain a polytime algorithm. Our main results show stronger guarantees for the classical problem using a simple and clean diffusion approach. The resulting analysis brings together several well-known analysis components, along with some extensions (to the constrained setting) and some new ideas (rejection analysis). We feel that the fact the solution is relatively simple and does not need substantial technical sophistication is an attractive feature.
Thanks for clarifying and the explanation. I do think the paper makes contribution that the community would benefit from seeing. 

My slight reservation comes from the fact that most of the contribution comes from analyzing the rejection sampling part, in which the M-warmness condition is doing most of the heavy-lifting, so perhaps in some sense the stated results are expected.
Re Applications: I would still recommend adding a few words on practical applications where the membership oracle model is the way to go, if you know of some and they are not too complicated to explain. Otherwise that's ok.

Re Line 175: Thank you for clarifying this in the final version.

Re Making it isotropic: My bad, I had somehow missed this. But mentioning this procedure earlier in the paper would indeed be beneficial.

Re potentials and pointwise time-reversal: fair enough.

I maintain my positive rating. Congratulations for a very nice paper :)