Faster Logconcave Sampling from a Cold Start in High Dimension Yunbum Kook, Santosh S. Vempala Abstract We present a faster algorithm to generate a warm start for sampling an arbitrary logconcave density specified by an evaluation oracle, leading to the first sub-cubic sampling algorithms for inputs in (near-)isotropic position. A long line of prior work incurred a warm-start penalty of at least linear in the dimension, hitting a cubic barrier, even for the special case of uniform sampling from convex bodies. Our improvement relies on two key ingredients of independent interest. (1) We show how to sample given a warm start in weaker notions of distance, in particular q q -Rényi divergence for q = 𝒪 ~ ​ ( 1 ) q=\widetilde{\mathcal{O}}(1) , whereas previous analyses required stringent ∞ \infty -Rényi divergence (with the exception of Hit-and-Run, whose known mixing time is higher). This marks the first improvement in the required warmness since Lovász and Simonovits (1991). (2) We refine and generalize the log-Sobolev inequality of Lee and Vempala (2018), originally established for isotropic logconcave distributions in terms of the diameter of the support, to logconcave distributions in terms of a geometric average of the support diameter and the largest eigenvalue of the covariance matrix. 1 Introduction Sampling from high-dimensional distributions is a fundamental problem that arises frequently in differential privacy [ MT07 , HT10 , Mir17 ] , scientific computing [ CV16 , KLSV22 ] , and system biology [ T+13 , HCT+17 ] . It has broad applications, ranging from volume estimation of convex bodies and integration of high-dimensional functions to Bayesian inference and stochastic optimization. In this paper, we focus on the problem of sampling arbitrary logconcave functions given access to an evaluation oracle. An important special case of this problem, which captures many of its challenges and has provided the gateway to efficient algorithms, is uniform sampling from a convex body given by a membership oracle (Definition 1.11 ). We introduce new ideas and analyses first for uniform sampling, and later extend them to general logconcave sampling. To put our results in context, we begin with a brief account of the history of sampling and the crucial role of warm starts. A brief history of sampling and warmth. In high-dimensional regimes, Markov chain Monte Carlo (MCMC) (or random walk ) serves as the primary general approach. At its core, MCMC leverages a transition kernel designed to explore a space in a way that, after sufficiently many iterations, the resulting sample has distribution close to a desired one. The efficiency of an MCMC algorithm is quantified by its query complexity: given target accuracy \varepsilon>0 , query complexity measures the number of oracle queries required to generate a sample whose law is \varepsilon -close to the target distribution, measured by metrics such as total variation ( \mathsf{TV} ) distance or \chi^{2} -divergence (see § 1.3 for definitions). Dyer, Frieze, and Kannan [ DFK91 ] proposed the first algorithm for uniformly sampling a convex body \mathcal{K}\subset\mathbb{R}^{n} in polynomial time, the central ingredient in the first polynomial time (randomized) algorithm for volume estimation. They used a walk on a sufficiently fine grid in a suitably “smoothened” body and bounded its conductance (i.e., conditional escape probability) from below by an inverse polynomial in the dimension n and the Euclidean diameter D of the body. Following this, Lovász and Simonovits [ Lov90 , LS90 ] introduced the \mathsf{Ball\ walk} , where each proposed step is a uniform random point in a ball of fixed radius around the current point, and is accepted if the proposal is in the body. They developed a general framework for sampling in continuous domains, bounded the conductance via isoperimetry of the target distribution, and introduced s -conductance , which lower-bounds the conductance of the Markov chain for subsets of measure at least s>0 . Since the \mathsf{Ball\ walk} can have bad starts (e.g., near the corner of a convex body), this notion led to a mixing rate of the \mathsf{Ball\ walk} from a warm start (i.e., M=\operatorname{ess\,sup}_{\pi_{0}}\mathrm{d}\pi_{0}/\mathrm{d}\pi\lesssim 1 for initial \pi_{0} and target \pi ), where the mixing rate depends polynomially on M . In words, the warm start refers to an initial distribution already close to a target in this sense. Hereafter, we use the q -Rényi divergence ( \mathcal{R}_{q} ) for q\in(1,\infty] to quantify the warmness (see § 1.3 ; recall the monotonicity of \mathcal{R}_{q} in q , so \mathcal{R}_{\infty} -warm is stronger than \mathcal{R}_{2} -warm for instance). To achieve such an M -warm start, they used a basic annealing procedure—starting from a unit ball contained in \mathcal{K} and gradually growing the ball truncated to \mathcal{K} ; each distribution in the sequence provides an \mathcal{O}(1) -warm start to the next one. In their analysis, the dependence on the distance \varepsilon to the target distribution is also inverse polynomial, \operatorname{poly}\nicefrac{{1}}{{\varepsilon}} . We note that in their paper and in all subsequent work till very recently [ KZ25 , KV25 ] , even though the initial distribution has bounded pointwise distance (i.e., in \mathcal{R}_{\infty} ), the final distribution has weaker guarantees (in \chi^{2} or \mathsf{TV} ). The next major improvement came in [ KLS97 ] which introduced the \mathsf{Speedy\ walk} , an analytical tool to overcome some challenges of the \mathsf{Ball\ walk} . It directly uses conductance (rather than s -conductance), so its mixing rate achieves \log\nicefrac{{M}}{{\varepsilon}} , log-dependence on both the warmness and the target distance. However, its implementation uses rejection sampling, so its query complexity scales as \operatorname{poly}M . They used the annealing approach in earlier work to generate a warm start. Nevertheless, from an \mathcal{O}(1) -warm start in \mathcal{R}_{\infty} , they achieved an improved n^{3} -complexity of sampling an isotropic convex body. In a companion paper [ KLS95 ] , directly motivated by the mixing rate of the \mathsf{Ball\ walk} in the same setup, they posited the Kannan-Lovász-Simonovits (KLS) conjecture, which has since become a central and unifying problem for asymptotic convex geometry and functional analysis. Following a long line of progress, the current best bound is \mathcal{O}(\log^{1/2}n) [ Kla23 ] , which in particular implies a mixing rate of \widetilde{\mathcal{O}}(n^{2}) for the \mathsf{Ball\ walk} in an isotropic convex body from an \mathcal{O}(1) -warm start. So far, the mixing rate was analyzed based on Cheeger or Poincaré inequalities, which have, at best, logarithmic dependence on the warmness parameter. Kannan, Lovász, and Montenegro [ LK99 , KLM06 ] introduced blocking conductance to improve the analysis of the \mathsf{Speedy\ walk} . They established a logarithmic Cheeger inequality for convex bodies, improving the mixing rate to n^{3} for isotropic convex bodies without a warm start. While this does not yield an algorithmic improvement (as the \mathsf{Speedy\ walk} has to ultimately be implemented with the \mathsf{Ball\ walk} and rejection sampling), this framework has turned out to be useful for the analysis of Markov chains. In a parallel line of work, Lovász and Vempala [ LV06b ] analyzed the \mathsf{Hit\text{-}and\text{-}Run} sampler [ Smi84 ] , showing a mixing rate of n^{2}D^{2} for a convex body with diameter D under a weaker warm start, namely in \mathcal{R}_{2} -divergence (i.e., M_{2}=\lVert\mathrm{d}\pi_{0}/\mathrm{d}\pi\rVert_{L^{2}(\pi)} ) with a logarithmic dependence on M_{2} . This was later extended by [ LV06a ] to logconcave distributions and has remained the only rapidly mixing Markov chain from any start for general logconcave distributions. It played a crucial role in an improved volume algorithm [ LV06c ] . However, unlike the \mathsf{Ball\ walk} , the KLS conjecture does not imply a faster mixing rate for \mathsf{Hit\text{-}and\text{-}Run} even in isotropic convex bodies. In 2015, using the \mathsf{Ball\ walk} , Cousins and Vempala [ CV15 ] showed how to sample a well-rounded convex body (a condition weaker than isotropy) with n^{3} queries via a new annealing scheme called \mathsf{Gaussian\ cooling} , without any warm start assumption. It uses a sequence of Gaussians of increasing variance restricted to the convex body, each providing a warm start to the next. This is the current state-of-the-art and was recently extended to arbitrary logconcave densities for sampling (and integration) while preserving the same complexity as the special case of convex bodies [ KV25 ] . Going below n^{3} has remained an open problem, even after the near-resolution of the KLS conjecture. There is, however, one other development that raises the possibility of going below cubic time. In 2018, Lee and Vempala [ LV24 ] established logarithmic Sobolev inequality for isotropic logconcave distributions, improving the log-Sobolev isoperimetric constant from \mathcal{O}(D^{2}) to tight \mathcal{O}(D) . This leads to an improved n^{2.5} -mixing of the \mathsf{Speedy\ walk} in an isotropic convex body from any start. Again, since the \mathsf{Speedy\ walk} is a conceptual process, it does not give an algorithmic improvement. The leads us to the main motivating question of this paper. Question . Is there an algorithm of sub-cubic complexity to sample a convex body in near-isotropic position? Can the sub-cubic complexity of the \mathsf{Speedy\ walk} be realized algorithmically? Besides uniform sampling (and general logconcave sampling), a special case of considerable interest is sampling a truncated Gaussian, i.e., a standard Gaussian distribution restricted to an arbitrary convex body containing the origin. The above question opens up a set of concrete challenges, which are also interesting in their own right. We discuss them in more detail below. To give a quick preview, we mention briefly that our main result is an affirmative answer to this main motivating question. Uniform sampling from a warm start. [ LS90 ] connected the convergence rate of the \mathsf{Ball\ walk} to the Cheeger constant C_{\mathsf{Ch}}(\pi) defined as follows: for a probability measure \pi over \mathbb{R}^{n} and Euclidean distance d , C_{\mathsf{Ch},d}(\pi):=\inf_{S:\pi(S)\leq\frac{1}{2}}\frac{\pi(\partial S)}{\pi(S)}\,, where S is any open subset of \mathbb{R}^{n} with smooth boundary, \pi(\partial S):=\liminf_{\varepsilon\downarrow 0}\frac{\pi(S_{\varepsilon})-\pi(S)}{\varepsilon} , and S_{\varepsilon}=\{x:d(x,S)\leq\varepsilon\} . The \mathsf{Ball\ walk} requires \widetilde{\mathcal{O}}(n^{2}C_{\mathsf{Ch},d}^{-2}(\pi)) queries in expectation to reach a distribution that is \varepsilon -close to the target uniform distribution \pi over a convex body in \mathsf{TV} -distance, starting from a \mathcal{R}_{\infty} -warm start. We use the notation \mathsf{Ball\ walk}:\mathcal{R}_{\infty}\to\mathsf{TV} to indicate the required input warmness and output metric. Significant breakthroughs have refined the Cheeger bound [ PW60 , KLS95 , Eld13 , LV24 , Che21 , KL22 , Kla23 ] , leading to the current best bound C_{\mathsf{Ch},d}^{-2}(\pi)\lesssim\lVert\operatorname{cov}\pi\rVert\log n by Klartag [ Kla23 ] , where \lVert\operatorname{cov}\pi\rVert denotes the largest eigenvalue of the covariance matrix of \pi . A different sampler \mathsf{Hit\text{-}and\text{-}Run}:\mathcal{R}_{2}\to\mathcal{R}_{2} , studied in [ Lov99 , LV06b ] , was shown to mix using n^{2}D^{2}C_{\mathsf{Ch},d_{\mathcal{K}}}^{-2}(\pi) queries, where d_{\mathcal{K}} is the cross-ratio distance. Unlike the \mathsf{Ball\ walk} , since C_{\mathsf{Ch},d_{\mathcal{K}}}\leq 1 is tight, progress on the KLS conjecture does not lead to an improvement in its complexity. Since \lVert\operatorname{cov}\pi\rVert0 and logconcave distributions \pi supported on diameter- D domains. In the example above, our bound yields C_{\mathsf{LSI}}(\pi\gamma_{\sigma^{2}})\lesssim n for any \sigma^{2} . Back to warm-start generation. With this new machinery in hand, we return to the warm-start generation problem. It is now apparent that our improved LSI bound should have direct algorithmic implications. In the Gaussian-annealing method, we may assume that the diameter is of order R by a suitable preprocessing, and thus once we reach \sigma^{2}\gtrsim R\,\lVert\operatorname{cov}\pi\rVert^{1/2} , sampling from \pi\gamma_{\sigma^{2}} can be accelerated due to the faster mixing rate of n^{2}C_{\mathsf{LSI}}(\pi\gamma_{\sigma^{2}})\leq n^{2}R\,\lVert\operatorname{cov}\pi\rVert^{1/2} . The complexity for doubling \sigma^{2} before reaching this accelerated phase is bounded by n^{2}R\sigma\lesssim n^{2}R^{3/2}\,\lVert\operatorname{cov}\pi\rVert^{1/4} , and similarly, subsequent doublings within the accelerated phase also incur at most the same complexity. Therefore, we establish a faster sampling algorithm with total query complexity of n^{2}R^{3/2}\,\lVert\operatorname{cov}\pi\rVert^{1/4} ( Result 3 ) (note \lVert\operatorname{cov}\pi\rVert\leq R^{2} ). Notably, when \pi is near-isotropic, this translates to an n^{2.75} -complexity sampling algorithm, breaking the previous cubic bound first established in [ CV15 , CV18 ] . For the special case of sampling a standard Gaussian restricted to an arbitrary convex body, the complexity is n^{2.5} , again improving on the previous best cubic bound [ CV14 ] . Extension to logconcave distributions. Our approach can be extended to general logconcave distributions under a well-defined function oracle. Although the extension is conceptually similar, it involves some technical complications related to handling general convex potentials. The complexity of logconcave sampling under this zeroth-order oracle has been studied using similar tools, notably by the \mathsf{Ball\ walk} [ LS93 ] , \mathsf{Hit\text{-}and\text{-}Run} [ LV06a , LV07 ] , and the \mathsf{Proximal\ sampler} [ KV25 ] . In [ KV25 ] , sampling from \pi is reduced to sampling from an exponential distribution: \bar{\pi}(x,t)\propto\exp(-nt)\,\mathds{1}_{\mathcal{K}}(x,t)\quad\text{for the covex set }\mathcal{K}:=\{(x,t)\in\mathbb{R}^{n}\times\mathbb{R}:V(x)\leq nt\}\,. To facilitate warm-start generation, they proposed \mathsf{Tilted\ Gaussian\ cooling} that uses “tilted” Gaussians defined as \mu_{\sigma^{2},t}(x,t)\propto\exp(-\rho t)\,\gamma_{\sigma^{2}}(x)\,\mathds{1}_{\mathcal{K}}(x,t) . Here, \exp(-\rho t) controls the augmented t -direction, while \gamma_{\sigma^{2}} tames the original x -direction similar to approaches in uniform sampling. Our Result 4 demonstrates that both the exponential and the tilted Gaussian distributions can also be sampled under relaxed warmness as in the case of uniform sampling. By suitably adapting \mathsf{Tilted\ Gaussian\ cooling} and leveraging the improved LSI bound, we establish that logconcave sampling for a \mathsf{TV} -guarantee can be accomplished using n^{2.5}+n^{2}R^{3/2}\,\lVert\operatorname{cov}\pi\rVert^{1/4} evaluation queries, which is n^{2.75} for near-isotropic distributions, matching the complexity of uniform sampling. This improves the previous best complexity of n^{2}(n\vee R^{2}) for logconcave sampling [ KV25 ] . 1.1 Results Here we state our main results: (1) relaxation of a warmness requirement of the proximal sampler ( \mathsf{PS} ) for uniform and truncated Gaussian distributions, (2) a new bound on ( LSI ) for strongly logconcave distributions with compact support, (3) uniform and Gaussian sampling through faster warm-start generation, and (4) an extension of these results to general logconcave distributions. We defer a detailed discussion of techniques to § 1.2 and preliminaries to § 1.3 . Result 1: Uniform and Gaussian sampling under a relaxed warmness (§ 2 ). The proximal sampler is a general sampling framework consisting of two steps. For a target distribution \pi^{X} and step size h , it considers an augmented distribution defined as \pi^{X,Y}(x,y)\propto\pi^{X}(x)\,\gamma_{h}(y-x) , and then iterates (i) y_{i+1}\sim\pi^{Y|X=x_{i}} and (ii) x_{i+1}\sim\pi^{X|Y=y_{i+1}} . Hence, \mathsf{PS}_{\textup{unif}} can be obtained by setting \pi^{X}\propto\mathds{1}_{\mathcal{K}}(x) , under which the second step corresponds to sampling from \pi^{X|Y=y_{i+1}}=\gamma_{h}(\cdot-y_{i+1})|_{\mathcal{K}} , and it can be implemented by rejection sampling with the Gaussian proposal \gamma_{h}(\cdot-y_{i+1}) . In § 2.1 , we relax warmness requirements of \mathsf{PS}_{\textup{unif}} for uniform distributions from \mathcal{R}_{\infty} to \mathcal{R}_{c} with c=\widetilde{\mathcal{O}}(1) , improving the warmness condition in [ KVZ24 ] (see Theorem 2.1 for details). Below, M_{q} indicates an L^{q} -norm defined as M_{q}:=\lVert\mathrm{d}\pi_{0}/\mathrm{d}\pi\rVert_{L^{q}(\pi)}=\exp(\frac{q-1}{q}\,\mathcal{R}_{q}(\pi_{0}\mathbin{\|}\pi)) . Input: initial point x_{0}\sim\pi_{0} , convex body \mathcal{K}\subset\mathbb{R}^{n} , iterations k\in\mathbb{N} , threshold N , variance h . Output: x_{k+1} . 1: for i=0,\dotsc,k do 2: Sample y_{i+1}\sim\gamma_{h}(\cdot-x_{i})=\mathcal{N}(x_{i},hI_{n}) . 3: Sample x_{i+1}\sim\gamma_{h}(\cdot-y_{i+1})|_{\mathcal{K}}=\mathcal{N}(y_{i+1},hI_{n})|_{\mathcal{K}} . 4: \quad(\uparrow) Repeat x_{i+1}\sim\gamma_{h}(\cdot-y_{i+1}) until x_{i+1}\in\mathcal{K} . If \# attempts {}_{i}\,\geq N , declare Failure . 5: end for Algorithm 1 \mathsf{Proximal\ sampler} \mathsf{PS}_{\textup{unif}} Theorem 1.3 (Uniform sampling from warm start) . Let \pi be a uniform distribution over a convex body \mathcal{K}\subset\mathbb{R}^{n} specified by \mathsf{Mem}_{R}(\mathcal{K}) with \lambda=\lVert\operatorname{cov}\pi\rVert . For any \eta,\varepsilon\in(0,1) , initial distribution \pi_{0} with c=\operatorname{polylog}\frac{n\lambda M_{2}}{\eta\varepsilon} and M_{c}=\lVert\nicefrac{{\mathrm{d}\pi_{0}}}{{\mathrm{d}\pi}}\rVert_{L^{c}(\pi)} , we can use \mathsf{PS}_{\textup{unif}} (Algorithm 1 ) with suitable choices of parameters, so that with probability at least 1-\eta , we obtain a sample whose law \mu satisfies \mathcal{R}_{2}(\mu\mathbin{\|}\pi)\leq\varepsilon , using \widetilde{\mathcal{O}}\bigl(M_{c}n^{2}\lambda\,\operatorname{polylog}\frac{1}{\eta\varepsilon}\bigr) membership queries in expectation. Similarly, we relax the previous \mathcal{R}_{\infty} -warmness condition for \mathsf{PS}_{\textup{Gauss}} [ KZ25 ] in § 2.2 . See Theorem 2.2 for more details. Theorem 1.4 (Restricted Gaussian sampling from warm start) . Let \pi be the uniform distribution \pi over a convex body \mathcal{K}\subset\mathbb{R}^{n} specified by \mathsf{Mem}_{R}(\mathcal{K}) with \lambda=\lVert\operatorname{cov}\pi\rVert and x_{0}=0 . Consider a Gaussian \pi\gamma_{\sigma^{2}} truncated to \mathcal{K} . For any \eta,\varepsilon\in(0,1) , initial distribution \pi_{0} with c=\operatorname{polylog}\frac{n\sigma DM_{2}}{\eta\varepsilon} and M_{c}=\lVert\nicefrac{{\mathrm{d}\pi_{0}}}{{\mathrm{d}\pi}}\rVert_{L^{c}(\pi)} , we can use \mathsf{PS}_{\textup{Gauss}} with suitable choices of parameters, so that with probability at least 1-\eta , we obtain a sample whose law \mu satisfies \mathcal{R}_{2}(\mu\mathbin{\|}\pi\gamma_{\sigma^{2}})\leq\varepsilon , using \widetilde{\mathcal{O}}\bigl(M_{c}n^{2}(\sigma^{2}\wedge D\lambda^{1/2})\,\operatorname{polylog}\frac{1}{\eta\varepsilon}\bigr) membership queries in expectation. Result 2: LSI for strongly logconcave distributions with compact support (§ A ). To attain the improved bound of C_{\mathsf{LSI}}(\pi\gamma_{h})\lesssim D\,\lVert\operatorname{cov}\pi\rVert^{1/2} , we first state two new findings which together yield the improved bound as an immediate corollary. For a logconcave distribution \pi with support of diameter D , we have C_{\mathsf{LSI}}(\pi)\lesssim D^{2} , and C_{\mathsf{LSI}}(\pi)\lesssim D when \pi is near-isotropic. In § 3.1 , we find an interpolation of these two bounds. Theorem 1.5 . Let \pi be a logconcave distribution over \mathbb{R}^{n} with support of diameter D>0 . Then, C_{\mathsf{LSI}}(\pi)\lesssim\max\{D\,\lVert\operatorname{cov}\pi\rVert^{1/2},D^{2}\wedge\lVert\operatorname{cov}\pi\rVert\log^{2}n\}\,, and C_{\mathsf{LSI}}(\pi)\lesssim DC_{\mathsf{PI}}^{1/2}(\pi)\lesssim D\,\lVert\operatorname{cov}\pi\rVert^{1/2}\log^{1/2}n . Since D\geq n^{1/2} for isotropic \pi , this bound recovers the D -bound for the isotropic case. For a general case, as \lVert\operatorname{cov}\pi\rVert=\sup_{v\in\mathbb{S}^{n-1}}\mathbb{E}_{\pi}[(v^{\mathsf{T}}(X-\mathbb{E}_{\pi}X))^{2}]\leq D^{2} , it also recovers the D^{2} -bound. Furthermore, the second bound achieves C_{\mathsf{LSI}}(\pi)\lesssim D\,\lVert\operatorname{cov}\pi\rVert^{1/2} without any logarithmic factor when the KLS conjecture is true. Our second result in § 3.2 is purely relevant to convex geometry, answering a geometric question of how Gaussian weighting affects the largest eigenvalue of a covariance matrix. Theorem 1.6 . For a logconcave distribution \pi over \mathbb{R}^{n} with R=\mathbb{E}_{\pi}\lVert\cdot\rVert and \lambda=\lVert\operatorname{cov}\pi\rVert , and any h\gtrsim R\lambda^{1/2}\log^{2}n\log^{2}\nicefrac{{R^{2}}}{{\lambda}} , it holds that \lVert\operatorname{cov}\pi\gamma_{h}\rVert\lesssim\lVert\operatorname{cov}\pi\rVert\,. Combining these two results and using the classical result of C_{\mathsf{LSI}}(\pi\gamma_{h})\leq h [ BGL14 ] , we state the improved LSI bound in § 3.3 . Corollary 1.7 . Let \pi be a logconcave distribution over \mathbb{R}^{n} with \lambda=\lVert\operatorname{cov}\pi\rVert and support of diameter D>0 . Then, for any h>0 , C_{\mathsf{LSI}}(\pi\gamma_{h})\lesssim D\lambda^{1/2}\log^{2}n\log^{2}\tfrac{D^{2}}{\lambda}\,. Result 3: Faster sampling from uniform and Gaussian distributions (§ 4 ). We accelerate \mathsf{Gaussian\ cooling} further, where truncated Gaussians \pi\gamma_{\sigma^{2}} are the annealing distributions. Sampling from \pi\gamma_{\sigma^{2}} under \mathcal{R}_{c} -warmness with c=\widetilde{\mathcal{O}}(1) ( Result 1 ) makes it possible to anneal \sigma^{2} more rapidly. Moreover, once \sigma^{2} reaches R\,\lVert\operatorname{cov}\pi\rVert^{1/2} , sampling from \pi\gamma_{\sigma^{2}} can also be accelerated due to the improved LSI bound ( Result 2 ). Interweaving these developments together, we sample from uniform distributions over convex bodies using \widetilde{\mathcal{O}}(n^{2}R^{3/2}\,\lVert\operatorname{cov}\pi\rVert^{1/4}) queries, provably less than \widetilde{\mathcal{O}}(n^{2}(n\vee R^{2})) queries given in [ CV18 , KZ25 ] . See Theorem 4.2 for details. Theorem 1.8 (Uniform sampling from cold start) . For any uniform distribution \pi over a convex body \mathcal{K}\subset\mathbb{R}^{n} specified by \mathsf{Mem}_{x_{0},R}(\mathcal{K}) with \lambda=\lVert\operatorname{cov}\pi\rVert , for any given \eta,\varepsilon\in(0,1) , there exists an algorithm that with probability at least 1-\eta , returns a sample whose law \mu satisfies \lVert\mu-\pi\rVert_{\mathsf{TV}}\leq\varepsilon , using \widetilde{\mathcal{O}}\bigl(n^{2}R^{3/2}\lambda^{1/4}\operatorname{polylog}\frac{R\lambda^{-1/2}}{\eta\varepsilon}\bigr) membership queries in expectation. If \pi is near-isotropic, then \widetilde{\mathcal{O}}(n^{2.75}\operatorname{polylog}\nicefrac{{1}}{{\eta\varepsilon}}) queries suffice. As a consequence, we can sample a truncated standard Gaussian in n^{2.5} -complexity without a warm start, improving the previous best complexity by a factor of n^{1/2} than [ CV18 ] . Corollary 1.9 (Restricted Gaussian sampling from cold start) . For any convex body \mathcal{K}\subset\mathbb{R}^{n} given by \mathsf{Mem}_{x_{0}}(\mathcal{K}) , there exists an algorithm that for any given \eta,\varepsilon\in(0,1) , with probability at least 1-\eta returns a sample whose law \mu satisfies \lVert\mu-\gamma|_{\mathcal{K}}\rVert_{\mathsf{TV}}\leq\varepsilon , using \widetilde{\mathcal{O}}(n^{2.5}\operatorname{polylog}\nicefrac{{1}}{{\eta\varepsilon}}) membership queries in expectation. Result 4: Extension to logconcave distributions (§ 5 ). Just as in the uniform sampling, we can relax a previous \mathcal{R}_{\infty} -warmness [ KV25 ] to \mathcal{R}_{c} with c=\widetilde{\mathcal{O}}(1) for samplers for the reduced exponential distribution \bar{\pi}(x,t)\propto\exp(-nt)|_{\mathcal{K}} and tilted Gaussian distribution \mu_{\sigma^{2},\rho}(x,t)\propto\exp(-\rho t)\,\gamma_{\sigma^{2}}(x)\,\mathds{1}_{\mathcal{K}}(x,t) . We refer readers to Theorem 5.2 and 5.3 . Then in § 5.2 , we further accelerate \mathsf{Tilted\ Gaussian\ cooling} proposed in [ KV25 ] , culminating in the following result. Theorem 1.10 (Logconcave sampling from cold start) . For any logconcave distribution \pi over \mathbb{R}^{n} presented by \mathsf{Eval}_{x_{0},R}(V) , there exists an algorithm that, given \eta,\varepsilon\in(0,1) , with probability at least 1-\eta returns a sample whose law \mu satisfies \lVert\mu-\pi\rVert_{\mathsf{TV}}\leq\varepsilon , using \widetilde{\mathcal{O}}\bigl(n^{2}\max\{n^{1/2},R^{3/2}(\lambda^{1/4}\vee 1)\}\operatorname{polylog}\frac{R\lambda^{-1/2}}{\eta\varepsilon}\bigr) evaluation queries in expectation. If \pi is near-isotropic, then \widetilde{\mathcal{O}}(n^{2.75}\operatorname{polylog}\nicefrac{{1}}{{\eta\varepsilon}}) queries suffice. 1.2 Technical overview Here we discuss detailed outlines of our approach and the main proofs. 1.2.1 Sampling under weaker warmness \mathsf{Ball\ walk} under relaxed warmness. Analysis of the \mathsf{Ball\ walk} has hitherto assumed \mathcal{R}_{\infty} -warmness [ LS90 ] . Unlike \mathsf{Hit\text{-}and\text{-}Run} , when the walk is near a corner of a convex body (e.g., the tip of a cone), most steps become wasted and make no progress, because the probability of finding another point within the intersection of the step ball and the convex body can be exponentially small. However, if the initial distribution is already close to the uniform distribution \pi in the \mathcal{R}_{\infty} -sense, then the chance of stepping into such low-probability regions is small, and thus the total expected wasted queries can still be bounded. Precisely, in the analysis of the \mathsf{Ball\ walk} with step size \delta (specifically, the \mathsf{Speedy\ walk} ) in [ KLS97 ] , each step samples uniformly from B_{\delta}(x)\cap\mathcal{K} with proposal uniform in B_{\delta}(x) , so the success probability—called the local conductance —is \ell(x)=\frac{\operatorname{vol}\bigl(B_{\delta}(x)\cap\mathcal{K}\bigr)}{\operatorname{vol}\bigl(B_{\delta}(x)\bigr)}\,. Its stationary distribution \pi^{\mathsf{SW}} is proportional to \ell , so if the initial distribution is already at stationarity, then the expected number of trials per step is \mathbb{E}_{\pi^{\mathsf{SW}}}\ell^{-1}=\mathcal{O}(1) , provided that the body contains a unit ball and the step size is \delta\lesssim n^{-1/2} . Relaxing the warmness requirement is challenging. Suppose one starts from a general initial distribution \mu and attempts a change of reference measure, say, through a Cauchy–Schwarz inequality: \bigl(\mathbb{E}_{\mu}\frac{1}{\ell}\bigr)^{2}\leq\frac{\int_{\mathcal{K}}\ell^{-1}\,\mathrm{d}x}{\int_{\mathcal{K}}\ell\,\mathrm{d}x}\cdot\Bigl\|\frac{\mathrm{d}\mu^{\ \ \ }\,}{\mathrm{d}\pi^{\mathsf{SW}}}\Bigr\|_{L^{2}(\pi^{\mathsf{SW}})}^{2}=\exp\bigl(\mathcal{R}_{2}(\mu\mathbin{\|}\pi^{\mathsf{SW}})\bigr)\,\frac{\int_{\mathcal{K}}\ell^{-1}\,\mathrm{d}x}{\int_{\mathcal{K}}\ell\,\mathrm{d}x}\,. Even if \mu and \pi are close in \mathcal{R}_{2} , it is unclear how to bound \int_{\mathcal{K}}\ell^{-1}\,\mathrm{d}x , and thus previous work has always assumed \mathcal{R}_{\infty} -warmness to replace \mu by \pi^{\mathsf{SW}} without introducing extra \ell^{-\alpha} into \mathbb{E}_{\mu}\ell^{-1} . Proximal sampler. Before introducing \mathsf{PS}_{\textup{unif}} , we briefly discuss the proximal sampler [ LST21 , CCSW22 , FYC23 , Wib25 ] , which has been analyzed in well-conditioned settings, where -\log\pi^{X} is \alpha -strongly convex and \beta -smooth in \mathbb{R}^{n} . Such uniform regularity allows rejection sampling to implement the second step x_{i+1}\sim\pi^{X|Y=y_{i+1}} efficiently, requiring only \mathcal{O}(1) queries for any y_{i+1} . However, constrained settings (such as uniform sampling over a convex body \mathcal{K} ) pose new challenges. For instance, for the uniform target \pi^{X}\propto\mathds{1}_{\mathcal{K}} , one can readily derive that \pi^{Y}(y)=\ell(y)/\operatorname{vol}\mathcal{K} and \pi^{X|Y=y}\propto\mathcal{N}(y,hI_{n})|_{\mathcal{K}} , where \ell(y)=\mathbb{P}_{Z\sim\mathcal{N}(y,hI_{n})}(Z\in\mathcal{K}) serves as a Gaussian version of the local conductance. Even at stationarity \pi^{X} , the expected per-step complexity of rejection sampling with proposal \mathcal{N}(y,hI_{n}) becomes infinite, as \mathbb{E}_{\pi^{Y}}\ell^{-1} is unbounded. To address this, \mathsf{PS}_{\textup{unif}} [ KVZ24 ] introduces a threshold parameter N : the algorithm declares failure if the rejection sampling exceeds N attempts. Under a step size h\asymp n^{-2} , they identify an essential domain as \mathcal{K}_{t/n}=\mathcal{K}+B_{t/n} , and show that \pi^{Y}(\mathbb{R}^{n}\setminus\mathcal{K}_{t/n})\lesssim e^{-t^{2}} . For an M_{\infty} -warm \mu , the expected number of trials can be bounded by carefully choosing parameters t,N . For \delta=t/n , \displaystyle\mathbb{E}_{\mu*\gamma_{h}}\bigl[\frac{1}{\ell}\wedge N\bigr] \displaystyle\leq M_{\infty}\,\mathbb{E}_{\pi^{Y}}\bigl[\frac{1}{\ell}\wedge N\bigr]\leq M_{\infty}\Bigl(\int_{\mathcal{K}_{\delta}}\frac{\mathrm{d}\pi^{Y}}{\ell}+N\pi^{Y}(\mathbb{R}^{n}\backslash\mathcal{K}_{\delta})\Bigr) \displaystyle=M_{\infty}\bigl(\frac{\operatorname{vol}\mathcal{K}_{\delta}}{\operatorname{vol}\mathcal{K}}+N\pi^{Y}(\mathbb{R}^{n}\backslash\mathcal{K}_{\delta})\bigr)\lesssim M_{\infty}(e^{t}+Ne^{-t^{2}})\,, ensuring exponentially small failure probability as well. Nonetheless, similar to the \mathsf{Ball\ walk} , applying Cauchy–Schwarz to relax \mathcal{R}_{\infty} -warmness fails, as \int_{\mathbb{R}^{n}}\ell^{-1}\,\mathrm{d}x still appears in the analysis. Improved analysis under a relaxed warmness. Our approach demonstrates the first successful relaxation of \mathcal{R}_{\infty} -warmness. We avoid such pointwise closeness by carefully using the (p,q) -Hölder inequality and a refined decomposition of \mathbb{E}_{\mu*\gamma_{h}}[\ell^{-1}\wedge N] into three regions: ( \mathsf{A} ) high local conductance in the essential domain, ( \mathsf{B} ) low local conductance in the essential domain, and ( \mathsf{C} ) non-essential domain: for (\cdot)_{h}:=(\cdot)*\gamma_{h} below, \mathbb{E}_{\mu_{h}}\bigl[\frac{1}{\ell}\wedge N\bigr]=\int_{\mathcal{K}_{\delta}\cap[\ell\geq N^{-p}]}\cdot+\int_{\mathcal{K}_{\delta}\cap[\ell0 . We believe each of these results is of independent interest. (1) Functional inequalities: C_{\mathsf{LSI}}(\pi)\lesssim_{\log}D\,\lVert\operatorname{cov}\pi\rVert^{1/2} . This result interpolates known bounds for ( LSI ): C_{\mathsf{LSI}}(\pi)\lesssim D (isotropic case) and C_{\mathsf{LSI}}(\pi)\lesssim D^{2} (general case). Unlike ( PI ), the interpolation via affine transformations does not work well for ( LSI ). Precisely, let X\sim\pi with \Sigma=\operatorname{cov}\pi , Y:=\Sigma^{-1/2}X , and \nu:=\operatorname{law}Y . Then, \nu is isotropic logconcave. For C_{\mathsf{PI}}(n) the largest Poincaré constant of n -dimensional isotropic logconcave distributions and for locally Lipschitz f , \displaystyle\operatorname{var}_{\pi}f \displaystyle=\operatorname{var}_{\nu}(f\circ\Sigma^{1/2})\leq C_{\mathsf{PI}}(n)\,\mathbb{E}_{\nu}[\lVert\nabla(f\circ\Sigma^{1/2})\rVert^{2}] \displaystyle\leq C_{\mathsf{PI}}(n)\,\mathbb{E}_{\nu}[\lVert\Sigma\rVert\lVert\nabla f\circ\Sigma^{1/2}\rVert^{2}]\leq C_{\mathsf{PI}}(n)\,\lVert\Sigma\rVert\,\mathbb{E}_{\pi}[\lVert\nabla f\rVert^{2}]\,, which implies C_{\mathsf{PI}}(\pi)\leq C_{\mathsf{PI}}(n)\,\lVert\Sigma\rVert . Similarly, C_{\mathsf{LSI}}(\pi)\leq C_{\mathsf{LSI}}(n)\,\lVert\Sigma\rVert holds (see § 3.1.1 ). However, C_{\mathsf{LSI}}(n) can be as large as D\asymp n [ LV24 ] , this LSI bound is unsatisfactory unlike the ( PI ) case. Inspired by [ KL24 ] , we present a simple approach leveraging a deep result established by Milman [ Mil10 ] that Gaussian concentration and ( LSI ) are equivalent for logconcave measures. Recall that a concentration function (Definition 3.5 ) of a probability measure \pi is defined as \alpha_{\pi}(r)=\sup_{E:\pi(E)\geq 1/2}\pi(\mathbb{R}^{n}\backslash E_{r})\quad\text{for all }r\geq 0\,. Gaussian concentration with constant C_{\mathsf{Gauss}}(\pi) refers to \alpha_{\pi}(r)\leq 2\exp(-r^{2}/C_{\mathsf{Gauss}}(\pi)) while exponential concentration with constant C_{\mathsf{exp}}(\pi) refers to \alpha_{\pi}(r)\leq 2\exp(-r/C_{\mathsf{exp}}(\pi)) . There are two known results on exponential concentration of logconcave measures. The first one, C_{\mathsf{exp}}^{2}(\pi)\lesssim C_{\mathsf{PI}}(\pi) , is classical and holds under ( PI ) regardless of logconcavity. The second one, \alpha_{\pi}(r)\leq 2\exp(-c\min\{r/\lambda^{1/2},r^{2}/\lambda\log^{2}n\}) for \lambda=\lVert\operatorname{cov}\pi\rVert and universal constant c>0 , is obtained by Bizeul [ Biz24 ] through Eldan’s stochastic localization (SL) [ Eld13 ] . Since the diameter of support is D , we clearly have \alpha_{\pi}(r)=0 if r>D , and r/D\leq 1 otherwise. Then, we have \alpha_{\pi}(r)\leq 2\exp(-\nicefrac{{r}}{{cC_{\mathsf{PI}}^{1/2}(\pi)}})\leq 2\exp(-\nicefrac{{r^{2}}}{{cDC_{\mathsf{PI}}^{1/2}(\pi)}}) . Due to Milman’s result on equivalence, C_{\mathsf{LSI}}(\pi)\lesssim DC_{\mathsf{PI}}^{1/2}(\pi)\lesssim D\lambda^{1/2}\log^{1/2}n . Similarly, when using Bizeul’s concentration, we can obtain C_{\mathsf{LSI}}(\pi)\lesssim\max\{D\lambda^{1/2},\lambda\log^{2}n\} . Taking minimum with the bound of C_{\mathsf{LSI}}(\pi)\lesssim D^{2} and using \lambda\leq D^{2} , we can conclude that C_{\mathsf{LSI}}(\pi)\lesssim\max\{D\lambda^{1/2},D^{2}\wedge\lambda\log^{2}n\}\leq D^{2}\lambda^{1/2}\log n . See Remark 3.9 on a comparison between these two LSI bounds. We present another proof through SL, specifically a simplified version from [ LV24 ] (see § A ), which was our first approach in an earlier version. (2) Convex geometry: \lVert\operatorname{cov}\pi\gamma_{h}\rVert\lesssim\lVert\operatorname{cov}\pi\rVert . Consider the isotropic uniform distribution \pi over a convex body for illustration. We have \lVert\operatorname{cov}\pi\gamma_{h}\rVert\leq C_{\mathsf{PI}}(\pi\gamma_{h})\leq h , where the first inequality follows from ( PI ), and the second from the Brascamp–Lieb (or Lichnerowicz) inequality. Thus, \lVert\operatorname{cov}\pi\gamma_{h}\rVert\leq 1 for h\leq 1 . As we increase h , this pushes the mass toward the boundary \partial\mathcal{K} , likely boosting covariance. On the other hand, for large h\gtrsim n^{2} , the measure \pi\gamma_{h} becomes a \Theta(1) -perturbation of \pi , since the support of \pi has diameter at most n+1 (due to isotropy). Thus, \pi\gamma_{h} is \mathcal{O}(1) -close to \pi in \mathcal{R}_{\infty} , and thus \lVert\operatorname{cov}\pi\gamma_{h}\rVert\lesssim\lVert\operatorname{cov}\pi\rVert=1 . Therefore, it is plausible to conjecture that \lVert\operatorname{cov}\pi\gamma_{h}\rVert\lesssim 1 for all h . We show this conjecture for h\gtrsim\mathbb{E}_{\pi}\|\cdot\|\asymp n^{1/2} , much smaller than n^{2} . To prove this, we bound \mathbb{E}_{\pi\gamma_{h}}[(X\cdot v)^{2}] for any unit vector v . Rewriting \mathbb{E}_{\pi\gamma_{h}}[(X\cdot v)^{2}]=\frac{\mathbb{E}_{\pi}[(X\cdot v)^{2}\,e^{-\lVert X\rVert^{2}/2h}]}{\mathbb{E}_{\pi}e^{-\lVert X\rVert^{2}/2h}}\,, we aim to upper-bound the numerator and lower-bound the denominator, both approximately by e^{-n/2h} . To this end, we examine which regions mainly contribute to each expectation, relying on concentration properties of \pi only. Recall isotropic logconcave distributions concentrate in a thin shell of radius n^{1/2} and width \mathcal{O}(\log\log n) [ Gua24 ] (conjectured to be \mathcal{O}(1) by the well-known thin-shell conjecture [ ABP03 , BK03 ] ). For the thin-shell ( \mathsf{S} ), inner ( \mathsf{I} ), and outer ( \mathsf{O} ) regions, we argue as follows: \displaystyle\mathsf{Den.}: \displaystyle\quad\mathbb{E}_{\pi}e^{-\lVert X\rVert^{2}/2h}\geq\mathbb{E}_{\pi}\inf_{\mathsf{S}}e^{-\lVert X\rVert^{2}/2h}\gtrsim e^{-n/2h}\,\pi(\mathsf{S})\gtrsim e^{-n/2h}\,, \displaystyle\mathsf{Num.}: \displaystyle\quad\mathbb{E}_{\pi}[(X\cdot v)^{2}e^{-\lVert X\rVert^{2}/2h}]=\mathbb{E}_{\pi}[(\cdot)\times\mathds{1}_{\mathsf{I}}]+\mathbb{E}_{\pi}[(\cdot)\times\mathds{1}_{\mathsf{S}}]+\mathbb{E}_{\pi}[(\cdot)\times\mathds{1}_{\mathsf{O}}]\,. As for the numerator, the inner part’s contribution is negligible due to the small ball probabilities [ DP10 , Biz25 ] , while the outer region’s contribution is exponentially small since the Gaussian weight is as small as e^{-n/2h} . Thus, the essential contribution comes from the thin-shell, yielding \mathbb{E}_{\pi}[(X\cdot v)^{2}e^{-\lVert X\rVert^{2}/2h}]\lesssim e^{-n/2h}\,\mathbb{E}[(X\cdot v)^{2}]\leq e^{-n/2h}\lVert\operatorname{cov}\pi\rVert=e^{-n/2h}\,. For general logconcave distributions, we use Lipschitz concentration under ( PI ), given as \pi(\lVert X\rVert-\mathbb{E}_{\pi}\lVert X\rVert\geq t)\leq 3\exp\bigl(-t/C_{\mathsf{PI}}^{1/2}(\pi)\bigr)\,, and the known bound C_{\mathsf{PI}}(\pi)\lesssim\lVert\operatorname{cov}\pi\rVert\log n . We then apply the co-area formula and integration by parts to control contributions from the inner and outer parts. 1.2.3 Faster sampling algorithm We derive a faster sampling algorithm for uniform distributions over convex bodies, with query complexity n^{2}R^{3/2}\,\lVert\operatorname{cov}\pi\rVert^{1/4} , which is n^{2.75} for nearly isotropic ones, the first sub-cubic bound. Algorithm. Our algorithm (§ 4.2.1 ) follows the annealing approach from \mathsf{Gaussian\ cooling} ; it also utilizes truncated Gaussian \gamma_{\sigma^{2}}|_{\mathcal{K}} for annealing, increasing \sigma^{2} from n^{-1} up to R^{2} , with some key differences. First, we eliminate the initial annealing by \sigma^{2}\leftarrow\sigma^{2}(1+n^{-1/2}) . Second, we accelerate it through a faster multiplicative update by 1+\nicefrac{{\sigma}}{{q^{1/2}R}} with q=\widetilde{\mathcal{O}}(1) , instead of the slower update by 1+\nicefrac{{\sigma^{2}}}{{R^{2}}} . Third, once \sigma^{2} surpasses R\,\lVert\operatorname{cov}\pi\rVert^{1/2} (i.e., the geometric mean between R^{2}(\geq\operatorname{tr}\operatorname{cov}\pi) and \lVert\operatorname{cov}\pi\rVert ), our algorithm benefits from a faster mixing of \mathsf{PS}_{\textup{Gauss}} due to our new LSI bound. Complexity. To bound the total complexity, we need a c -Rényi divergence bound for c=\widetilde{\mathcal{O}}(1) between neighboring annealing distributions. We establish in Lemma 4.5 that \mathcal{R}_{q}(\gamma_{\sigma^{2}}|_{\mathcal{K}}\mathbin{\|}\gamma_{\sigma^{2}(1+\alpha)}|_{\mathcal{K}})\leq qR^{2}\alpha^{2}/\sigma^{2} for q>1 , which generalizes the known result for q=2 [ CV18 , Lemma 7.8] . This bound justifies our multiplicative update with \alpha=\nicefrac{{\sigma}}{{q^{1/2}R}} . Setting q=c , we ensure that \gamma_{\sigma^{2}}|_{\mathcal{K}} and \gamma_{\sigma^{2}(1+\alpha)}|_{\mathcal{K}} remain close in \mathcal{R}_{c} , enabling sampling by \mathsf{PS}_{\textup{Gauss}} with provable guarantees. Each \sigma^{2} -doubling requires at most q^{1/2}R/\sigma phases, with each phase run by \mathsf{PS}_{\textup{Gauss}} incurring n^{2}\sigma^{2} queries. Thus, each doubling has total complexity of q^{1/2}n^{2}R\sigma . Given \mathcal{O}(\log nR) doubling phases, the total query complexity up to \sigma^{2}\approx R\,\lVert\operatorname{cov}\pi\rVert^{1/2} is bounded by q^{1/2}n^{2}R^{3/2}\,\lVert\operatorname{cov}\pi\rVert^{1/4} . Beyond \sigma^{2}\gtrsim R\,\lVert\operatorname{cov}\pi\rVert^{1/2} , \mathsf{PS}_{\textup{Gauss}} requires n^{2}R\,\lVert\operatorname{cov}\pi\rVert^{1/2} queries thanks to our improved C_{\mathsf{LSI}} . Thus, each subsequent doubling also contributes q^{1/2}n^{2}R^{3/2}\,\lVert\operatorname{cov}\pi\rVert^{1/4} as well. The final transition from \gamma_{R^{2}}|_{\mathcal{K}} to \pi via \mathsf{PS}_{\textup{unif}} requires n^{2}\,\lVert\operatorname{cov}\pi\rVert queries. Therefore, the total complexity is n^{2}R^{3/2}\,\lVert\operatorname{cov}\pi\rVert^{1/4} . One subtle point we have brushed over is the approximate nature of \mathsf{PS}_{\textup{Gauss}} . Specifically, when sampling from \gamma_{\sigma^{2}}|_{\mathcal{K}} , it actually outputs a sample X_{*} satisfying \mathcal{R}_{2}(\operatorname{law}X_{*}\mathbin{\|}\gamma_{\sigma^{2}}|_{\mathcal{K}})\leq\varepsilon , thus slightly off from \gamma_{\sigma^{2}}|_{\mathcal{K}} . Nonetheless, we have pretended that the output is distributed as \gamma_{\sigma^{2}}|_{\mathcal{K}} . We can readily address this issue by using the triangle inequality for \mathsf{TV} -distance. Let m be the total number of phases during annealing, \gamma_{i} the target distribution for i\in[m] , and P_{i} the Markov kernel defined by \mathsf{PS}_{\textup{Gauss}} with suitable step size. Then, the actual distribution of a sample at each phase i is \hat{\gamma}_{i}:=\gamma_{0}P_{1}\cdots P_{i}=\hat{\gamma}_{i-1}P_{i} . Using the triangle inequality and data-processing inequality, \lVert\hat{\gamma}_{i}-\gamma_{i}\rVert_{\mathsf{TV}}\leq\lVert\hat{\gamma}_{i-1}P_{i}-\gamma_{i-1}P_{i}\rVert_{\mathsf{TV}}+\lVert\gamma_{i-1}P_{i}-\gamma_{i}\rVert_{\mathsf{TV}}\leq\lVert\hat{\gamma}_{i-1}-\gamma_{i-1}\rVert_{\mathsf{TV}}+\varepsilon\,, and induction leads to \lVert\hat{\gamma}_{i}-\gamma_{i}\rVert_{\mathsf{TV}}\leq m\varepsilon . Since the total complexity scales as \operatorname{polylog}\nicefrac{{1}}{{\varepsilon}} , by replacing \varepsilon\leftarrow\varepsilon/m , we can achieve the desired accuracy without increasing complexity significantly. 1.2.4 Extension to general logconcave distributions We now extend our developments thus far to general logconcave distributions, under a well-defined function oracle. The overall strategy parallels our approach for uniform sampling: (1) sampling under weaker warmness, and (2) faster annealing while maintaining these weaker warmness conditions. Logconcave sampling. As studied in [ KV25 ] , sampling from logconcave \pi\propto e^{-V} can be reduced to sampling from the augmented distribution \bar{\pi}(x,t)\propto e^{-nt}\,\mathds{1}_{\mathcal{K}}(x,t) , where \mathcal{K}=\{(x,t)\in\mathbb{R}^{n}\times\mathbb{R}:V(x)\leq nt\} is convex due to the convexity of V , incurring an additive overhead of n^{2} . They used tilted Gaussians of the form \mu_{\sigma^{2},\rho}(x,t)\propto\exp(-\rho t)\,\gamma_{\sigma^{2}}(x)\,\mathds{1}_{\mathcal{K}} for annealing. In § 5.1 , we study the query complexity of the \mathsf{Proximal\ sampler} for these two distributions (denoted by \mathsf{PS}_{\textup{exp}} and \mathsf{PS}_{\textup{ann}} respectively) under \mathcal{R}_{c} -warmness for c=\widetilde{\mathcal{O}}(1) . Building upon prior ideas used for \mathsf{PS}_{\textup{unif}} and \mathsf{PS}_{\textup{Gauss}} , we refine the previous analysis of per-step guarantees for \mathsf{PS}_{\textup{exp}} and \mathsf{PS}_{\textup{ann}} under weaker warmness. Consequently, we establish that \mathsf{PS}_{\textup{ann}} requires n^{2}(\sigma^{2}\vee 1) evaluation queries, while \mathsf{PS}_{\textup{exp}} requires n^{2}(\lVert\operatorname{cov}\pi\rVert\vee 1) queries. Tilted Gaussian cooling. We use \mathsf{Tilted\ Gaussian\ cooling} from [ KV25 ] with extra care for faster warm-start generation for the exponential distribution \bar{\pi} . This algorithm (§ 5.2.1 ) increases \sigma^{2} from n^{-1} to R^{2} , and \rho from 1 to n , and it involves three phases—(1) \sigma^{2} -warming: Increase \sigma^{2} from n^{-1} to 1 , (2) \rho -annealing: With fixed \sigma^{2}=1 , increase \rho from 1 to n , and (3) \sigma^{2} -annealing: With fixed \rho=n , increase \sigma^{2} from 1 to R^{2} . To bound distance between neighboring distributions, we establish a Rényi version of the global update lemma (Lemma 4.4 ), proven for q=2 in [ LV06c , KV06 ] : for logconcave e^{-V} , \mathcal{R}_{q}(e^{-(1+\alpha)V}\mathbin{\|}e^{-V})\lesssim qn\alpha^{2}\,. In Phase I, we update \sigma^{2} multiplicatively by 1+(qn)^{-1/2} , justified by the above guarantee. Since \mathsf{PS}_{\textup{ann}} requires n^{2} queries in this phase, the total complexity for Phase I is n^{2.5} . Phase II is more involved. Initially, with \sigma^{2}=1 , we simultaneously update \rho\leftarrow\rho\,(1+(q\,(q\vee n))^{-1/2}) and \sigma^{2}\leftarrow\sigma^{2}(1+(q\,(q\vee n))^{-1/2})^{-1} , where closeness follows from the global update lemma. To make up for the slight decrease in \sigma^{2} , we further update \sigma^{2}\leftarrow\sigma^{2}(1+\nicefrac{{\sigma}}{{q^{1/2}R}}) until \sigma^{2}\leq 1 , justified by Lemma 4.5 , repeating at most \nicefrac{{2R}}{{(q\vee n)^{1/2}}} times. Note that each annealing by \mathsf{PS}_{\textup{ann}} requires n^{2} queries. Given at most (q\,(q\vee n))^{1/2}\log n phases in \rho -annealing, each followed by at most \nicefrac{{2R}}{{(q\vee n)^{1/2}}} rounds of \sigma^{2} -annealing, the total complexity of Phase II is (q\,(q\vee n))^{1/2}\times\nicefrac{{2R}}{{(q\vee n)^{1/2}}}\times n^{2}\lesssim q^{1/2}n^{2}R. In Phase III, we increase \sigma^{2} multiplicatively by 1+\nicefrac{{\sigma}}{{q^{1/2}R}} , where each annealing takes n^{2}\sigma^{2} queries through \mathsf{PS}_{\textup{ann}} . Each \sigma^{2} -doubling requires q^{1/2}R/\sigma phases, leading to n^{2}R\sigma queries per doubling. Exploiting faster mixing when \sigma^{2}\gtrsim R\,(\lVert\operatorname{cov}\pi\rVert^{1/2}\vee 1) , the total complexity of Phase III is by n^{2}R^{3/2}(\lVert\operatorname{cov}\pi\rVert^{1/4}\vee 1) . Combining complexities across all phases, the final total complexity is n^{2.5}+n^{2}R^{3/2}(\lVert\operatorname{cov}\pi\rVert^{1/4}\vee 1) , which is again n^{2.75} for near-isotropic logconcave distributions. 1.3 Preliminaries A function f:\mathbb{R}^{n}\to[0,\infty) is logconcave if -\log f is convex in \mathbb{R}^{n} , and a probability measure (or distribution) is logconcave if it has a logconcave density function with respect to the Lebesgue measure 2 2 2 In this work, we only consider non-degenerate logconcave distributions whose support cannot be embedded into any proper subspace of \mathbb{R}^{n} . Also, all distributions considered are absolutely continuous with respect to the Lebesgue measure (i.e., \pi\ll\mathfrak{m} ). . This justifies our abuse of notation using the same symbol for a distribution and density. For t\geq 0 , a distribution \pi is called t -strongly logconcave if -\log\pi is t -strongly convex (i.e., -\log\pi-\frac{t}{2}\,\lVert\cdot\rVert^{2} is convex). Recall that the multiplication and convolution preserve logconcavity. A distribution is called isotropic if it is centered (i.e., \mathbb{E}_{\pi}X=0 ) and has the identity covariance matrix (i.e., \mathbb{E}_{\pi}[X^{\otimes 2}]=I_{n} ). Note that as the logconcave distributions decay exponentially fast at infinity, they have finite moments of all orders. We reserve \gamma_{h} for the centered Gaussian distribution with covariance matrix hI_{n} . For a set S , we use \mathds{1}_{S}(x):=[x\in S] to denote its indicator function, and use \mu|_{S} to denote a distribution \mu truncated to S (i.e., \mu|_{S}\propto\mu\cdot\mathds{1}_{S} ). For two probability measures \mu,\pi , we use \mu\pi to denote the new distribution with density proportional to \mu\pi . For a,b\in\mathbb{R} , we use a\vee b and a\wedge b to denote their maximum and minimum, respectively. B_{r}^{n}(x) denotes the n -dimensional ball of radius r>0 centered at x , dropping the superscript n if there is no confusion. Both a\lesssim b and a=\mathcal{O}(b) mean a\leq cb for a universal constant c>0 . a=\Omega(b) means a\gtrsim b , and a\asymp b means a=\mathcal{O}(b) and a=\Omega(b) . Lastly, a=\widetilde{\mathcal{O}}(b) means a=\mathcal{O}(b\operatorname{polylog}b) . For a vector v and a PSD matrix \Sigma , \lVert v\rVert and \lVert\Sigma\rVert denote the \ell_{2} -norm of v and the operator norm of \Sigma , respectively. We recall the basic definition of our computational model. Definition 1.11 (Well-defined membership oracle, [ GLS93 ] ) . It assumes access to a convex body \mathcal{K}\subset\mathbb{R}^{n} through a membership oracle, which answers whether a queried point belongs to \mathcal{K} . We assume that \mathcal{K} contains B_{1}(x_{0}) for some x_{0}\in\mathbb{R}^{n} and has finite diameter D>0 and smooth boundary, and assume that the uniform probability measure \pi over \mathcal{K} , given by \mathrm{d}\pi(x)\propto\mathds{1}_{\mathcal{K}}(x)\,\mathrm{d}x satisfies R^{2}\geq\mathbb{E}_{\pi}[\lVert\cdot-x_{0}\rVert^{2}] for some R>0 . We denote this oracle by \mathsf{Mem}_{\mathcal{P}}(\mathcal{K}) , where \mathcal{P} indicates access to parameter values in \mathcal{P} (e.g., \mathsf{\mathsf{Mem}}_{R}(V) reveals R , while \mathsf{Mem}(\mathcal{K}) reveals none). This can be generalized to a well-defined function oracle. Definition 1.12 (Well-defined function oracle) . It assumes access to an integrable logconcave function \exp(-V) on \mathbb{R}^{n} , through an evaluation oracle for a convex potential V:\mathbb{R}^{n}\to\mathbb{R}\cup\{\infty\} , which returns the value of V(x) for the queried point x\in\mathbb{R}^{n} , and also assumes that the distribution \pi with density \mathrm{d}\pi\propto\exp(-V)\,\mathrm{d}x satisfies (1) \mathbb{E}_{\pi}[\lVert\cdot-x_{0}\rVert^{2}]\leq R^{2} for some R>0 and (2) the ground set \mathsf{L}_{\pi,g}:=\{x\in\mathbb{R}^{n}:V(x)-\min V\leq 10n\} contains B_{r}(x_{0}) . Without loss of generality, we will assume that x_{0}=0 by translation and r=1 by scaling. We denote it by \mathsf{Eval}_{\mathcal{P}}(V) . We recall notions of probability divergences / distances between distributions. Definition 1.13 . For two distributions \mu,\nu over \mathbb{R}^{n} , the f -divergence of \mu towards \nu with \mu\ll\nu is defined as, for a convex function f:\mathbb{R}_{+}\to\mathbb{R} with f(1)=0 and f^{\prime}(\infty)=\infty , D_{f}(\mu\mathbin{\|}\nu):=\int f\bigl(\frac{\mathrm{d}\mu}{\mathrm{d}\nu}\bigr)\,\mathrm{d}\nu\,. For q\in(1,\infty) , the \mathsf{KL} -divergence and \chi^{q} -divergence correspond to f(x)=x\log x and x^{q}-1 , respectively. The q -Rényi divergence is defined as \mathcal{R}_{q}(\mu\mathbin{\|}\nu):=\frac{1}{q-1}\,\log\bigl(\chi^{q}(\mu\mathbin{\|}\nu)+1\bigr)=\frac{1}{q-1}\,\log\,\bigl\|\frac{\mathrm{d}\mu}{\mathrm{d}\nu}\bigr\|_{L^{q}(\nu)}^{q}\,. The Rényi-infinity divergence is defined as \mathcal{R}_{\infty}(\mu\mathbin{\|}\nu):=\log\operatorname{ess\,sup}_{\mu}\frac{\mathrm{d}\mu}{\mathrm{d}\nu}\,. For c\in[1,\infty] , a distribution \mu is said to be M_{c} -warm with respect to a distribution \nu if \lVert\nicefrac{{\mathrm{d}\mu}}{{\mathrm{d}\nu}}\rVert_{L^{c}(\nu)}\leq M (i.e., \mathcal{R}_{c}(\mu\mathbin{\|}\nu)\leq\frac{c}{c-1}\,\log M ) 3 3 3 When c=\infty , we consider the L^{\infty} -norm with respect to \mu , not \nu , to be consistent with \mathcal{R}_{\infty} as well as a prevalent definition of ( \infty -)warmness. . The total variation ( \mathsf{TV} ) distance between \mu and \nu is defined as \lVert\mu-\nu\rVert_{\mathsf{TV}}:=\frac{1}{2}\int|\mu(x)-\nu(x)|\,\mathrm{d}x=\sup_{S\in\mathcal{F}}|\mu(S)-\nu(S)|\,, where \mathcal{F} is the collection of all \mu,\nu -measurable subsets of \mathbb{R}^{n} . We recall \mathsf{KL}=\lim_{q\downarrow 1}\mathcal{R}_{q}\leq\mathcal{R}_{q}\leq\mathcal{R}_{q^{\prime}}\leq\mathcal{R}_{\infty} for 1\leq q\leq q^{\prime} and 2\,\lVert\cdot\rVert_{\mathsf{TV}}^{2}\leq\mathsf{KL}\leq\mathcal{R}_{2}=\log(\chi^{2}+1)\leq\chi^{2} . The following classical lemmas will be useful in the proofs. We refer readers to [ vEH14 ] for more properties of the Rényi divergence. Lemma 1.14 (Data-processing inequality) . For probability measures \mu,\nu , Markov kernel P , f -divergence D_{f} , and q\in[1,\infty] , it holds that D_{f}(\mu P\mathbin{\|}\nu P)\leq D_{f}(\mu\mathbin{\|}\nu)\,,\quad\text{and}\quad\mathcal{R}_{q}(\mu P\mathbin{\|}\nu P)\leq\mathcal{R}_{q}(\mu\mathbin{\|}\nu)\,. Lemma 1.15 (Bounded perturbation, [ HS87 ] ) . Suppose that a probability measure \pi satisfies ( LSI ) with constants C_{\mathsf{LSI}}(\pi)<\infty . If a probability measure \mu satisfies c\leq\frac{\mathrm{d}\mu}{\mathrm{d}\pi}\leq C for c,C\in\mathbb{R}_{>0} , then C_{\mathsf{LSI}}(\mu)\leq\frac{C}{c}\,C_{\mathsf{LSI}}(\pi)\,. 2 Convex body sampling under relaxed warmness In this section, we establish the query complexities of sampling from uniform and Gaussian distributions over a convex body, relaxing the warmness requirement from \mathcal{R}_{\infty} to \mathcal{R}_{c} for small c=\widetilde{\mathcal{O}}(1) . We refine previous analyses of the \mathsf{Proximal\ sampler} for these distributions carried out in [ KVZ24 , KZ25 ] , and prove the following theorems. Theorem 2.1 (Restatement of Theorem 1.3 ) . Consider the uniform distribution \pi over a convex body \mathcal{K}\subset\mathbb{R}^{n} specified by \mathsf{Mem}_{D}(\mathcal{K}) , and an initial distribution \mu with M_{q}=\lVert\mathrm{d}\mu/\mathrm{d}\pi\rVert_{L^{q}(\pi)} for q\geq 2 . For any \eta,\varepsilon\in(0,1) and k\in\mathbb{N} as defined below, \mathsf{PS}_{\textup{unif}} (Algorithm 1 ) with h=(2n^{2}\log\frac{16kM_{2}}{\eta})^{-1} and N=(\frac{16kM_{2}}{\eta})^{2}\log^{4}\frac{16kM_{2}}{\eta} achieves \mathcal{R}_{2}(\mu_{k}\mathbin{\|}\pi)\leq\varepsilon after k=\widetilde{\mathcal{O}}(n^{2}\lVert\operatorname{cov}\pi\rVert\log^{3}\frac{M_{2}}{\eta\varepsilon}) iterations, where \mu_{k} is the law of the k -th iterate. With probability at least 1-\eta , \mathsf{PS}_{\textup{unif}} iterates k times without failure, using \widetilde{\mathcal{O}}\bigl(M_{c}n^{2}\lVert\operatorname{cov}\pi\rVert\log^{7}\frac{1}{\eta\varepsilon}\bigr) membership queries in expectation for any c\geq 12\log\frac{16kM_{2}}{\eta} . This analysis improves the complexity bound of \widetilde{\mathcal{O}}(M_{\infty}n^{2}\,\lVert\operatorname{cov}\pi\rVert\operatorname{polylog}\nicefrac{{1}}{{\eta\varepsilon}}) under \mathcal{R}_{\infty} -warmness condition established in [ KVZ24 ] . If the inner radius of \mathcal{K} is r , then the query complexity includes an additional multiplicative factor of r^{-2} . Using a similar technique, we also improve the complexity bound for truncated Gaussian sampling under a \mathcal{R}_{\infty} -warmness assumption proven in [ KZ25 ] . Theorem 2.2 (Restatement of Theorem 1.4 ) . Along with the uniform distribution \pi above with x_{0}=0 (i.e., \mathsf{Mem}_{x_{0}=0,D}(\mathcal{K}) ), consider a Gaussian \pi\gamma_{\sigma^{2}} truncated to \mathcal{K} for \sigma>0 , and initial distribution \mu with M_{q}=\lVert\mathrm{d}\mu/\mathrm{d}(\pi\gamma_{\sigma^{2}})\rVert_{L^{q}(\pi\gamma_{\sigma^{2}})} for q\geq 2 . For any \eta,\varepsilon\in(0,1) , k\in\mathbb{N} defined below, \mathsf{PS}_{\textup{Gauss}} with h=(10n^{2}\log\frac{16kM_{2}}{\eta})^{-1} and N=(\frac{16kM_{2}}{\eta})^{2}\log^{3}\frac{16kM_{2}}{\eta} achieves \mathcal{R}_{2}(\mu_{k}\mathbin{\|}\pi\gamma_{\sigma^{2}})\leq\varepsilon after k=\widetilde{\mathcal{O}}(n^{2}\sigma^{2}\log^{3}\frac{M_{2}}{\eta\varepsilon}) iterations, where \mu_{k} is the law of the k -th iterate, and with probability at least 1-\eta successfully iterates k times without failure, using \widetilde{\mathcal{O}}\bigl(M_{c}n^{2}\sigma^{2}\log^{6}\frac{1}{\eta\varepsilon}\bigr) membership queries in expectation for any c\geq 6\log\frac{16kM_{2}}{\eta} . When \sigma^{2}\gtrsim D\lambda^{1/2}\log^{2}n\log^{2}\frac{D^{2}}{\lambda} for \lambda=\lVert\operatorname{cov}\pi\rVert , it suffices to run k=\widetilde{\mathcal{O}}(n^{2}D\lambda^{1/2}\log^{3}\frac{M_{2}}{\eta\varepsilon}) times with total query complexity \widetilde{\mathcal{O}}\bigl(M_{c}n^{2}D\lambda^{1/2}\log^{6}\frac{1}{\eta\varepsilon}\bigr)\,. We remark that the new complexity benefits not only from the relaxed warmness requirement but also from the tighter bound on C_{\mathsf{LSI}}(\pi\gamma_{\sigma^{2}}) , which will be proven in § A . 2.1 Uniform sampling We recall the \mathsf{Proximal\ sampler} for the uniform distribution over a convex body \mathcal{K} (denoted as \mathsf{PS}_{\textup{unif}} here), referred to as \mathsf{\mathsf{In\text{-}and\text{-}Out}} in [ KVZ24 ] . Given a step size h , a preset threshold N , and the uniform target \pi^{X}(x)\propto\mathds{1}_{\mathcal{K}}(x) , one iteration consists of • [Forward] y_{i+1}\sim\pi^{Y|X=x_{i}}=\mathcal{N}(x_{i},hI_{n}) . • [Backward] x_{i+1}\sim\pi^{X|Y=y_{i+1}}=\mathcal{N}(y_{i+1},hI_{n})|_{\mathcal{K}}\propto\exp(-\frac{1}{2h}\,\lVert\cdot-y_{i+1}\rVert^{2})\,\mathds{1}_{\mathcal{K}}(\cdot) . – This is implemented by repeating x_{i+1}\sim\gamma_{h}(\cdot-y_{i+1}) until x_{i+1}\in\mathcal{K} . If the number of attempts in this iteration exceeds N , then we declare Failure . We recall that \pi^{Y}=\pi^{X}*\gamma_{h}=:\pi_{h} . One notable advantage of this sampler is that it separates (i) the convergence-rate analysis and (ii) the query-complexity analysis of the backward step. The first question is how many iterations — each consisting of a successful execution of both the forward and backward steps — are required to achieve a target accuracy in a desired metric. The second is how many queries are needed to successfully implement the rejection sampling in each backward step. As a result, the total query complexity is simply the product of these two quantities. 2.1.1 Mixing analysis Previous work on the \mathsf{Proximal\ sampler} established its convergence rate under various assumptions on the target, including ( PI ) and ( LSI ). It was first proven for smooth densities [ CCSW22 , Theorem 3 and 4] and extended to distributions truncated to convex constraints [ KVZ24 , Lemma 22] . For rigorous treatments of these types of strong data-processing inequalities, we refer readers to [ KO25 ] . Lemma 2.3 ( [ CCSW22 , Theorem 3 and 4] ) . Assume that a probability measure \pi is absolutely continuous with respect to the Lebesgue measure over a convex body \mathcal{K} , and let P denote the Markov kernel of the \mathsf{Proximal\ sampler} . If \pi satisfies ( LSI ) with constant C_{\mathsf{LSI}} , then for any q\geq 1 and distribution \mu with \mu\ll\pi , \mathcal{R}_{q}(\mu P\mathbin{\|}\pi)\leq\frac{\mathcal{R}_{q}(\mu\mathbin{\|}\pi)}{(1+h/C_{\mathsf{LSI}})^{2/q}}\,. (2.1) If \pi satisfies ( PI ) with constant C_{\mathsf{PI}} , then \chi^{2}(\mu P\mathbin{\|}\pi)\leq\frac{\chi^{2}(\mu\mathbin{\|}\pi)}{(1+h/C_{\mathsf{PI}})^{2}}\,. (2.2) Thus, the \mathsf{Proximal\ sampler} mixes in roughly qh^{-1}C_{\mathsf{LSI}}\log\frac{\mathcal{R}_{q}}{\varepsilon} and h^{-1}C_{\mathsf{PI}}\log\frac{\chi^{2}}{\varepsilon} iterations under ( LSI ) and ( PI ), respectively. Since any logconcave distribution \pi satisfies ( PI ), and the current best bound [ Kla23 ] gives \lVert\operatorname{cov}\pi\rVert\leq C_{\mathsf{PI}}(\pi)\lesssim\lVert\operatorname{cov}\pi\rVert\log n\,, \mathsf{PS}_{\textup{unif}} requires no more than h^{-1}\lVert\operatorname{cov}\pi\rVert\log n\log\frac{\chi^{2}(\pi_{0}\mathbin{\|}\pi)}{\varepsilon} iterations to achieve \chi^{2}(\pi_{0}P^{n}\mathbin{\|}\pi)\leq\varepsilon . 2.1.2 Complexity of the backward step Under the relaxed warmness condition, there is no change in the mixing analysis, but we must refine previous analysis of the backward step. Here, we show that both the failure probability and the expected query complexity (i.e., the expected number of trials until the first success of rejection sampling) can be moderately bounded under weaker warmness. In analysis, we can assume that x_{0}=0 by translation without loss of generality. As briefly sketched in § 1.2 , the essential domain of \pi^{Y}=\pi_{h} can be identified as \mathcal{K}_{\delta}=\mathcal{K}+B_{\delta} : Lemma 2.4 ( [ KVZ24 , Lemma 26] ) . For a convex body \mathcal{K}\subset\mathbb{R}^{n} containing B_{1}(0) , \pi^{Y}(\mathcal{K}_{\delta}^{c})\leq\exp\bigl(-\frac{\delta^{2}}{2h}+\delta n\bigr)\,. By taking \delta=\frac{t}{n},\,h=\frac{c}{n^{2}} for some c,t>0 , the measure of the non-essential part is bounded as \pi^{Y}(\mathcal{K}_{\delta}^{c})\leq\exp\bigl(-\frac{t^{2}}{2c}+t\bigr)\,. We now proceed to analyze the failure probability (i.e., the probability of hitting the threshold at least once before mixing) and the expected number of trials under wearer warmness, \mathcal{R}_{q}(\mu^{X}\mathbin{\|}\pi^{X})=\mathcal{O}(1) with q\geq 2 . While the former can be bounded straightforwardly using the Cauchy–Schwarz inequality, the latter requires a more delicate analysis as seen shortly. (1) Failure probability. Recall that \mathcal{R}_{q}(\mu\mathbin{\|}\pi)=\frac{1}{q-1}\,\log\,\Bigl\|\frac{\mathrm{d}\mu}{\mathrm{d}\pi}\Bigr\|_{L^{q}(\pi)}^{q}=\frac{1}{q-1}\,\log\bigl(\chi^{q}(\mu\mathbin{\|}\pi)+1\bigr)\,. Suppose we run \mathsf{PS}_{\textup{unif}} with initial distribution \mu^{X}\ll\pi^{X} . Denoting \mu_{h}:=\mu^{X}*\gamma_{h} , we can bound the failure probability of one iteration as \mathbb{E}_{\mu_{h}}[(1-\ell)^{N}]\leq\sqrt{\mathbb{E}_{\pi_{h}}[(1-\ell)^{2N}]}\,\Bigl\|\frac{\mathrm{d}\mu_{h}}{\mathrm{d}\pi_{h}}\Bigr\|_{L^{2}(\pi_{h})}\leq\sqrt{\mathbb{E}_{\pi_{h}}[(1-\ell)^{2N}]}\,\Bigl\|\frac{\mathrm{d}\mu}{\mathrm{d}\pi}\Bigr\|_{L^{2}(\pi)}\,, where the first inequality follows from the Cauchy–Schwarz inequality, and the second follows from the data-processing inequality (e.g., the DPI for the Rényi divergence, Lemma 1.14 ). To bound \mathbb{E}_{\pi_{h}}[(1-\ell)^{2N}] , we adapt the analysis in [ KVZ24 ] . For M_{2}=\lVert\mathrm{d}\mu/\mathrm{d}\pi\rVert_{L^{2}(\pi)} , we decompose \int_{\mathbb{R}^{n}}(1-\ell)^{2N}\,\mathrm{d}\pi_{h}=\int_{\mathcal{K}_{\delta}^{c}}\cdot+\int_{\mathcal{K}_{\delta}\cap[\ell\geq N^{-1}\log(3kM_{2}/\eta)]}\cdot+\int_{\mathcal{K}_{\delta}\cap[\ell0 , we can satisfy \delta\geq hn . Another is the following: Lemma 2.6 ( [ KZ25 , Lemma 24] ) . Let \mathcal{K}\subset\mathbb{R}^{n} be a convex body containing a unit ball B_{1}(0) . For \tau=\tfrac{\sigma^{2}}{h+\sigma^{2}} and s>0 , \tau^{-n/2}\int_{\mathcal{K}_{s}}\exp\bigl(-\frac{1}{2\tau\sigma^{2}}\,\lVert z\rVert^{2}\bigr)\,\mathrm{d}z\leq 2\exp(hn^{2}+sn)\int_{\mathcal{K}}\exp\bigl(-\frac{1}{2\sigma^{2}}\,\lVert z\rVert^{2}\bigr)\,\mathrm{d}z\,. (1) Failure probability. Just as in the analysis of \mathsf{PS}_{\textup{unif}} , we adapt the analysis of \mathsf{PS}_{\textup{Gauss}} from [ KZ25 ] . For an initial distribution \nu\ll\mu , the failure probability can be bounded using the Cauchy–Schwarz as follows: \mathbb{E}_{\nu_{h}}[(1-\ell)^{N}]\leq\sqrt{\mathbb{E}_{\mu_{h}}[(1-\ell)^{2N}]}\,\Bigl\|\frac{\mathrm{d}\nu}{\mathrm{d}\mu}\Bigr\|_{L^{2}(\mu)}=:M_{2}\sqrt{\mathbb{E}_{\mu_{h}}[(1-\ell)^{2N}]}\,. Then, \int_{\mathbb{R}^{n}}(1-\ell)^{2N}\,\mathrm{d}\mu_{h}=\int_{R^{c}}\cdot+\int_{R\cap[\ell\geq N^{-1}\log(3kM_{2}/\eta)]}\cdot+\int_{R\cap[\ell0 , we use \pi\gamma_{t} to denote the t^{-1} -strongly logconcave distribution obtained by weighting \pi with a Gaussian \gamma_{t} (i.e., \mathrm{d}(\pi\gamma_{t})(x)\propto\pi(x)\,\gamma_{t}(x)\,\mathrm{d}x ). We also denote \Sigma_{t}:=\operatorname{cov}\pi\gamma_{t} and \lambda_{t}:=\lVert\Sigma_{t}\rVert . We begin by proving a bound on C_{\mathsf{LSI}}(\pi) for logconcave \pi supported with diameter D>0 , which interpolates the D -bound for isotropic logconcave distributions [ LV24 ] and the classical D^{2} -bound for general logconcave distributions [ FK99 ] . Theorem 3.1 (Restatement of Theorem 1.5 ) . For a logconcave distribution \pi with support of diameter D>0 in \mathbb{R}^{n} , C_{\mathsf{LSI}}(\pi)\lesssim\max\{D\lambda^{1/2},D^{2}\wedge\lambda\log^{2}n\}\,. It also holds that C_{\mathsf{LSI}}(\pi)\lesssim DC_{\mathsf{PI}}^{1/2}(\pi)\lesssim D\lambda^{1/2}\log^{1/2}n . Our second result addresses how a Gaussian factor affects the largest eigenvalue of the covariance matrix of a logconcave distribution. Theorem 3.2 (Restatement of Theorem 1.6 ) . For a logconcave distribution \pi with R=\mathbb{E}_{\pi}\lVert\cdot\rVert in \mathbb{R}^{n} , if \sigma^{2}\gtrsim R\lambda^{1/2}\log^{2}n\log^{2}\frac{R^{2}}{\lambda} , then \lambda_{\sigma^{2}}\lesssim\lambda\,. Combining these two together with the classical result C_{\mathsf{LSI}}(\pi\gamma_{\sigma^{2}})\leq\sigma^{2} , we obtain the following bound for strongly logconcave probability measures with compact support. Corollary 3.3 (Restatement of Corollary 1.7 ) . Let \pi be a logconcave distribution in \mathbb{R}^{n} with support of diameter D>0 . Then, for any \sigma^{2}>0 , C_{\mathsf{LSI}}(\pi\gamma_{\sigma^{2}})\lesssim D\lambda^{1/2}\log^{2}n\log^{2}\frac{D}{\lambda^{1/2}}\,. 3.1 Log-Sobolev constant for logconcave distributions with compact support It follows from the curvature-dimension condition [ BGL14 ] that C_{\mathsf{LSI}}(\gamma_{h}|_{\mathcal{K}})\leq C_{\mathsf{LSI}}(\gamma_{h})=h (i.e., truncating a strongly logconcave measure to a convex set does not worsen the LSI constant), but how about the other natural possible inequality C_{\mathsf{LSI}}(\gamma_{h}|_{\mathcal{K}})\leq C_{\mathsf{LSI}}(\mathds{1}_{\mathcal{K}}) (i.e., Multiplying a radially symmetric Gaussian does not increase the LSI constant)? Why do we care about this? To motivate this question, suppose \pi\propto\mathds{1}_{\mathcal{K}} is an isotropic logconcave distribution with support of diameter \Theta(n) , so C_{\mathsf{LSI}}(\pi)\lesssim n [ LV24 , Theorem 49] . Now consider h\asymp n^{2} . Then, the distribution \gamma_{h}|_{\mathcal{K}} is a \Theta(1) -perturbation to \pi , so by the Holley–Stroock perturbation principle, we obtain C_{\mathsf{LSI}}(\gamma_{h}|_{\mathcal{K}})\lesssim C_{\mathsf{LSI}}(\pi)\lesssim n . Note that the straightforward bound C_{\mathsf{LSI}}(\gamma_{h}|_{\mathcal{K}})\leq h only yields an \mathcal{O}(n^{2}) -bound. This suggests that as h increases from n to n^{2} , if the LSI constant C_{\mathsf{LSI}}(\gamma_{h}|_{\mathcal{K}}) initially increases, it must start to decrease somewhere to satisfy C_{\mathsf{LSI}}(\gamma_{n^{2}}|_{\mathcal{K}})\lesssim n . This naturally leads us to ask if C_{\mathsf{LSI}}(\gamma_{h}|_{\mathcal{K}})\lesssim n for all h>0 . This question can be phrased more generally as follows. Question 3.4 . For any logconcave distribution \pi with compact support, and any h>0 , do we have C_{\mathsf{LSI}}(\pi\gamma_{h})\lesssim C_{\mathsf{LSI}}(\pi)\,? We may first ask whether C_{\mathsf{LSI}}(\pi\gamma_{h}) remains close to the known bound on C_{\mathsf{LSI}}(\pi) . In § 3.3 , we show that this is indeed the case. Before proceeding, however, we mention what is currently known about C_{\mathsf{LSI}}(\pi) . The classical upper bound for the LSI constant of any logconcave distribution \pi with compact support of diameter D>0 is \mathcal{O}(D^{2}) , while for isotropic logconcave distributions, a stronger bound C_{\mathsf{LSI}}(\pi)\lesssim D holds. In the context of ( PI ), the known bound C_{\mathsf{PI}}(\pi)\lesssim\lambda\log n nearly interpolates the \mathcal{O}(\log n) bound for isotropic cases and \mathcal{O}(D^{2}) for general cases (noting that \lambda\leq D^{2} ). This motivates the following mathematical question, which we will address in this section. Question . What is a general bound on ( LSI ) that interpolates those two known bounds on ( LSI ) for logconcave distributions with compact support? 3.1.1 A naïve approach: Interpolation via a Lipschitz map As sketched earlier in § 1.2 , one justification for focusing on the Poincaré constant of isotropic logconcave distributions is via the affine map T:x\mapsto\Sigma^{1/2}x , which has Lipschitzness \lVert\Sigma\rVert^{1/2} . This approach does not work well for ( LSI ). Indeed, let \nu:=(T^{-1})_{\#}\pi be the pushforward of \pi under the inverse affine map, so that \nu is isotropic. For any test function f:\mathbb{R}^{n}\to\mathbb{R} , we have \displaystyle\mathsf{Ent}_{\pi}[f^{2}] \displaystyle=\mathsf{Ent}_{\nu}[(f\circ\Sigma^{1/2})^{2}]\leq C_{\mathsf{LSI}}(\nu)\,\mathbb{E}_{\nu}[\lVert\nabla(f\circ\Sigma^{1/2})\rVert^{2}] \displaystyle\leq C_{\mathsf{LSI}}(\nu)\,\mathbb{E}_{\nu}[\lVert\Sigma^{1/2}\rVert^{2}\lVert\nabla f\circ\Sigma^{1/2}\rVert^{2}]\leq C_{\mathsf{LSI}}(\nu)\,\lVert\Sigma\rVert\,\mathbb{E}_{\pi}[\lVert\nabla f\rVert^{2}]\,, which implies that C_{\mathsf{LSI}}(\pi)\leq C_{\mathsf{LSI}}(\nu)\,\lVert\Sigma\rVert\,. This bound has several downsides. First, the best-known bound for isotropic logconcave distributions is C_{\mathsf{LSI}}(\nu)\lesssim D , and this cannot be improved in general [ LV24 , Lemma 55] . Moreover, isotropy implies D\geq\sqrt{n} , so we cannot hope for a better general bound on C_{\mathsf{LSI}}(\nu) than \sqrt{n} . Second, since \lVert\Sigma\rVert=\sup_{v\in\mathbb{S}^{n-1}}\mathbb{E}_{\pi}[(v^{\mathsf{T}}(X-\mathbb{E}_{\pi}X))^{2}]\leq D^{2} , it is unclear how the RHS of the inequality could even recover the classical \mathcal{O}(D^{2}) bound for C_{\mathsf{LSI}}(\pi) . Thus, this affine reduction fails to interpolate the known two bounds and motivates the need for a more intrinsic analysis. 3.1.2 A better approach via Gaussian concentration We prove the following two bounds presented in Theorem 3.1 : C_{\mathsf{LSI}}(\pi)\lesssim\min\bigl\{DC_{\mathsf{PI}}^{1/2}(\pi),\max\{D\lambda^{1/2},D^{2}\wedge\lambda\log^{2}n\}\bigr\}\,. Inspired by [ KL24 , §8] , we present a simple proof using a known equivalence between Gaussian concentration and ( LSI ) for logconcave measures. We first define a concentration function of a measure. Definition 3.5 (Concentration) . For a probability measure \pi over \mathbb{R}^{n} , consider the concentration function of \pi defined as \alpha_{\pi}(r)=\sup_{S:\pi(S)\geq 1/2}\pi(S^{c})\,. The measure \pi is said to satisfy exponential concentration with constant C_{\mathsf{exp}}(\pi) if \alpha_{\pi}(r)\leq 2\exp\bigl(-\frac{r}{C_{\mathsf{exp}}(\pi)}\bigr)\quad\text{for all }r\geq 0\,, and is said to satisfy Gaussian concentration with constant C_{\mathsf{Gauss}}(\pi) if \alpha_{\pi}(r)\leq 2\exp\bigl(-\frac{r^{2}}{C_{\mathsf{Gauss}}(\pi)}\bigr)\quad\text{for all }r\geq 0\,. Milman [ Mil10 ] established that for a logconcave distribution, exponential concentration is equivalent to ( PI ), and Gaussian concentration is equivalent to ( LSI ). Theorem 3.6 . For any logconcave probability measure \pi , it holds that C_{\mathsf{LSI}}(\pi)\asymp C_{\mathsf{Gauss}}(\pi) . To use this result, we recall two known results on exponential concentration. The first is a standard result on exponential concentration under ( PI ). Precisely, this is a combination of concentration of Lipschitz functions (around its median or mean) [ BGL14 , §4.4.3] and its equivalence with exponential concentration. Theorem 3.7 . For a probability measure \pi with C_{\mathsf{PI}}(\pi)<\infty , there exists a universal constant c>0 such that \alpha_{\pi}(r)\leq 2\exp\bigl(-\frac{r}{cC_{\mathsf{PI}}^{1/2}(\pi)}\bigr)\,. There is another bound established by [ Biz24 , Theorem 1.1] using Eldan’s stochastic localization (see another proof based on this technique in § A ). Theorem 3.8 . For any logconcave probability measure \pi over \mathbb{R}^{n} , there exists a universal constant c>0 such that \alpha_{\pi}(r)\leq 2\exp\Bigl(-c\min\bigl(\frac{r}{\lVert\operatorname{cov}\pi\rVert^{1/2}},\frac{r^{2}}{\lVert\operatorname{cov}\pi\rVert\log^{2}n}\bigr)\Bigr)\,. We now prove the desired LSI bound in a simple way by combining these two bounds. Proof of Theorem 3.1 . Since the diameter of the support is D , it clearly holds that \alpha_{\pi}(r)=0 for r>D . For r\leq D , using r/D\leq 1 and letting \lambda=\lVert\operatorname{cov}\pi\rVert , by Theorem 3.8 , \alpha_{\pi}(r)\leq 2\exp\Bigl(-c\min\bigl(\frac{r^{2}}{D\lambda^{1/2}},\frac{r^{2}}{\lambda\log^{2}n}\bigr)\Bigr)=2\exp\Bigl(-\frac{cr^{2}}{D\lambda^{1/2}\vee\lambda\log^{2}n}\Bigr)\,. By Theorem 3.6 , since \pi is logconcave, C_{\mathsf{LSI}}(\pi)\asymp C_{\mathsf{Gauss}}(\pi)\lesssim D\lambda^{1/2}\vee\lambda\log^{2}n\,. Combining with C_{\mathsf{LSI}}(\pi)\lesssim D^{2} , we can deduce that \displaystyle C_{\mathsf{LSI}}(\pi) \displaystyle\lesssim D^{2}\wedge(D\lambda^{1/2}\vee\lambda\log^{2}n)=\max\{D\lambda^{1/2}\wedge D^{2},D^{2}\wedge\lambda\log^{2}n\} \displaystyle=\max\{D\lambda^{1/2},D^{2}\wedge\lambda\log^{2}n\}\,. Regarding the second bound, it follows from Theorem 3.7 that for some universal constant c>0 , \alpha_{\pi}(r)\leq 2\exp\bigl(-\frac{r}{cC_{\mathsf{PI}}^{1/2}(\pi)}\bigr). Using a similar argument above, we have \alpha_{\pi}(r)\leq 2\exp\bigl(-\frac{r^{2}}{cDC_{\mathsf{PI}}^{1/2}(\pi)}\bigr)\,. Thus, by the equivalence between ( LSI ) and Gaussian concentration (Theorem 3.6 ), C_{\mathsf{LSI}}(\pi)\asymp C_{\mathsf{Gauss}}(\pi)\lesssim DC_{\mathsf{PI}}^{1/2}(\pi)\leq D\lambda^{1/2}\log^{1/2}n\,, where the last inequality follows from C_{\mathsf{PI}}(\pi)\lesssim\lambda\log n . ∎ Remark 3.9 (Comparison of two bounds) . The first bound successfully interpolates the \mathcal{O}(D) -bound of isotropic logconcave distributions and \mathcal{O}(D^{2}) -bound of general logconcave ones. However, it cannot attain \mathcal{O}(D\lambda^{1/2}) even if the KLS conjecture is true. On the other hand, the second bound almost interpolates those two bounds (up to \log^{1/2}n ), while it attains \mathcal{O}(D\lambda^{1/2}) when the KLS conjecture is true. 3.2 Covariance of strongly logconcave distributions We have just shown that C_{\mathsf{LSI}}(\pi)\lesssim D\lambda^{1/2} and C_{\mathsf{LSI}}(\pi\gamma_{h})\lesssim D\lambda_{h}^{1/2} (ignoring logarithmic factors). How does this new bound compare to the previous two bounds of C_{\mathsf{LSI}}(\pi\gamma_{h})\leq h\wedge\mathcal{O}(D^{2}) , from strong logconcavity and from the support diameter respectively? A standard upper bound on the operator norm \lambda_{h} can be obtained via \lambda_{h}\leq C_{\mathsf{PI}}(\pi\gamma_{h})\leq h\,, where the second inequality follows from the Brascamp–Lieb inequality. Plugging this into our bound yields C_{\mathsf{LSI}}(\pi\gamma_{h})\lesssim Dh^{1/2} , which is the geometric mean of the previous two bounds ( h and D^{2} ), and making no essential gain. However, for sufficiently large h , one can expect that \pi\gamma_{h} is closer to \pi , suggesting that \lVert\Sigma_{h}\rVert may be comparable to \lVert\Sigma\rVert . In fact, when h\geq D^{2} , the distribution \pi\gamma_{h} becomes a \Theta(1) -perturbation of \pi , and the Holley–Stroock perturbation principle gives C_{\mathsf{LSI}}(\pi\gamma_{h})\lesssim C_{\mathsf{LSI}}(\pi)\lesssim D\lambda^{1/2} . If this bound is true for any h , and particularly when \pi is isotropic, then this would already yield a substantial gain, since D\lambda^{1/2}=D is smaller than the naïve h -bound, which only gives \Omega(D^{2}) . Our main goal at this point is to show \lambda_{h}\lesssim\lambda for h\gtrsim\lambda^{1/2}RC_{\mathsf{PI}}^{2}(n)\log^{2}\nicefrac{{R^{2}}}{{\lambda}} (Theorem 3.2 ), where C_{\mathsf{PI}}(n) is the largest possible Poincaré constant of n -dimensional isotropic logconcave distributions. Since C_{\mathsf{PI}}(n)\lesssim\log n [ Kla23 ] , a sufficient condition is h\gtrsim\lambda^{1/2}R\log^{2}n\log^{2}\nicefrac{{R^{2}}}{{\lambda}} . We remark that the logarithmic factor in the guarantee can be further improved by using a thin-shell estimate instead of C_{\mathsf{PI}}(n) and tightening some computations in the proof. Proof of Theorem 3.2 . We start off by scaling the coordinate system via T:x\mapsto\lambda^{-1/2}x , so that \nu:=T_{\#}\pi satisfies \lVert\operatorname{cov}\nu\rVert=1 . We show that if \eta\gtrsim\mathbb{E}_{\nu}\lVert Y\rVert\log^{2}n\log^{2}\mathbb{E}_{\nu}\lVert Y\rVert , then \lVert\operatorname{cov}\nu_{\eta}\rVert\lesssim 1 for \nu_{\eta}=\nu\gamma_{\eta} . Then, by scaling back through T^{-1} , we can deduce the main claim in the theorem (due to \mathbb{E}_{\nu}\lVert Y\rVert=\lambda^{-1/2}\,\mathbb{E}_{\pi}\lVert X\rVert and h=\eta\lambda ). Throughout the proof, we use c and c_{1} to denote positive universal constants. By rotating the coordinate system, it suffices to bound that for \mu , the barycenter of \nu , Q:=\mathbb{E}_{\nu_{\eta}}[(Y-\mu)_{1}^{2}]\lesssim 1\,. To this end, we instead bound Q=\frac{\mathbb{E}_{\nu}\bigl[(Y-\mu)_{1}^{2}\,\exp(-\frac{\lVert Y\rVert^{2}}{2\eta})\bigr]}{\mathbb{E}_{\nu}\bigl[\exp(-\frac{\lVert Y\rVert^{2}}{2\eta})\bigr]}=:\frac{N}{D}\,, where N and D refer to the numerator and denominator, respectively. Recall the classical Lipschitz concentration that for 1 -Lipschitz f : for any t\geq 0 , \nu(f-\mathbb{E}_{\nu}f\geq t)\leq 3\exp\bigl(-\frac{t}{C_{\mathsf{PI}}^{1/2}(\nu)}\bigr)\,. (3.1) Let R:=\mathbb{E}_{\nu}\lVert\cdot\rVert_{2}(\geq 1) and C_{\mathsf{PI}}:=C_{\mathsf{PI}}(n) . Noting C_{\mathsf{PI}}(\nu)\lesssim C_{\mathsf{PI}} , and taking f(\cdot)=\lVert\cdot\rVert_{2} and t=c_{1}C_{\mathsf{PI}}^{1/2}\log R , we have that \nu(\lVert Y\rVert\in[R\pm t])\geq 1-6\exp(-c_{2}\log R)\,, where [R\pm t]:=[R-t,R+t] . Hence, the thin-shell \mathcal{S}:=\{y\in\mathbb{R}^{n}:\lVert y\rVert\in[R\pm t]\} takes up more than a half of \nu -measure by taking c_{1} large enough. Since \eta\gtrsim RC_{\mathsf{PI}}^{2}\log^{2}R\gtrsim t\,(R\vee t)=Rt\vee t^{2} , D\geq\mathbb{E}_{\nu}\bigl[\exp\bigl(-\frac{\lVert Y\rVert^{2}}{2\eta}\bigr)\,\mathds{1}_{\mathcal{S}}\bigr]\geq\exp\bigl(-\frac{R^{2}+2Rt+t^{2}}{2\eta}\bigr)\,\nu(\mathcal{S})\gtrsim\exp\bigl(-\frac{R^{2}}{2\eta}\bigr)\,. As for the upper bound on the numerator N , we decompose N as follows: N=\underbrace{\mathbb{E}_{\nu}\bigl[(Y-\mu)_{1}^{2}\,\exp\bigl(-\frac{\lVert Y\rVert^{2}}{2\eta}\bigr)\,\mathds{1}_{\mathcal{S}}\bigr]}_{=:\mathsf{(I)}}+\underbrace{\mathbb{E}_{\nu}\bigl[(Y-\mu)_{1}^{2}\,\exp\bigl(-\frac{\lVert Y\rVert^{2}}{2\eta}\bigr)\,\mathds{1}_{\mathcal{S}^{c}}\bigr]}_{=:\mathsf{(II)}}\,. For (\mathsf{I)} , we have \displaystyle\mathbb{E}_{\nu}\bigl[(Y-\mu)_{1}^{2}\,\exp\bigl(-\frac{\lVert Y\rVert^{2}}{2\eta}\bigr)\,\mathds{1}_{\mathcal{S}}\bigr] \displaystyle\leq\exp\bigl(-\frac{R^{2}}{2\eta}+\frac{Rt}{\eta}\bigr)\,\mathbb{E}_{\nu}\bigl[(Y-\mu)_{1}^{2}\,\mathds{1}_{\mathcal{S}}\bigr]\lesssim\exp\bigl(-\frac{R^{2}}{2\eta}\bigr)\,\mathbb{E}_{\nu}[(Y-\mu)_{1}^{2}] \displaystyle\leq\exp\bigl(-\frac{R^{2}}{2\eta}\bigr)\,. For \mathsf{(II)} , since \lVert\mu\rVert\leq\mathbb{E}_{\nu}\lVert\cdot\rVert=R , we have \displaystyle\mathbb{E}_{\nu}\bigl[(Y-\mu)_{1}^{2}\,\exp\bigl(-\frac{\lVert Y\rVert^{2}}{2\eta}\bigr)\,\mathds{1}_{\mathcal{S}^{c}}\bigr] \displaystyle=\mathbb{E}_{\nu}\bigl[(Y-\mu)_{1}^{2}\,\exp\bigl(-\frac{\lVert Y\rVert^{2}}{2\eta}\bigr)\,(\mathds{1}_{\{\lVert Y\rVert\leq R-t\}}+\mathds{1}_{\{\lVert Y\rVert\geq R+t\}})\bigr] \displaystyle\lesssim R^{2}\,\mathbb{E}_{\nu}\bigl[\exp\bigl(-\frac{\lVert Y\rVert^{2}}{2\eta}\bigr)\,\mathds{1}_{\{\lVert Y\rVert\leq R-t\}}\bigr]+\mathbb{E}_{\nu}\bigl[(R^{2}+\lVert Y\rVert^{2})\exp\bigl(-\frac{\lVert Y\rVert^{2}}{2\eta}\bigr)\,\mathds{1}_{\{\lVert Y\rVert\geq R+t\}}\bigr] \displaystyle\leq R^{2}\,\mathbb{E}_{\nu}\bigl[\exp\bigl(-\frac{\lVert Y\rVert^{2}}{2\eta}\bigr)\,\mathds{1}_{\{\lVert Y\rVert\leq R-t\}}\bigr]+2\,\mathbb{E}_{\nu}\bigl[\lVert Y\rVert^{2}\,\exp\bigl(-\frac{\lVert Y\rVert^{2}}{2\eta}\bigr)\,\mathds{1}_{\{\lVert Y\rVert\geq R+t\}}\bigr]\,. By the co-area formula, for the (n-1) -dimensional Hausdorff measure \mathcal{H}^{n-1} , \displaystyle\mathbb{E}_{\nu}\bigl[\exp\bigl(-\frac{\lVert Y\rVert^{2}}{2\eta}\bigr)\,\mathds{1}_{\{\lVert Y\rVert\leq R-t\}}\bigr] \displaystyle=\int_{0}^{R-t}e^{-\frac{r^{2}}{2\eta}}\underbrace{\int_{\partial B_{r}}\nu(x)\,\mathrm{d}\mathcal{H}^{n-1}(x)}_{=:\nu_{n-1}(\partial B_{r})}\,\mathrm{d}r\,, \displaystyle\mathbb{E}_{\nu}\bigl[\lVert Y\rVert^{2}\exp\bigl(-\frac{\lVert Y\rVert^{2}}{2\eta}\bigr)\,\mathds{1}_{\{\lVert Y\rVert\geq R+t\}}\bigr] \displaystyle=\int_{R+t}^{\infty}r^{2}e^{-\frac{r^{2}}{2\eta}}\,\nu_{n-1}(\partial B_{r})\,\mathrm{d}r\,. Using integration by parts for the first expectation, \displaystyle\int_{0}^{R-t}e^{-\frac{r^{2}}{2\eta}}\,\nu_{n-1}(\partial B_{r})\,\mathrm{d}r \displaystyle=[e^{-\frac{r^{2}}{2\eta}}\,\nu(B_{r})]_{0}^{R-t}+\int_{0}^{R-t}\frac{r}{\eta}\,e^{-\frac{r^{2}}{2\eta}}\,\nu(B_{r})\,\mathrm{d}r \displaystyle\underset{\eqref{eq:PI-Lips-concent}}{\leq}3\exp\bigl(-\frac{(R-t)^{2}}{2\eta}\bigr)\,\exp\bigl(-\frac{t}{C_{\mathsf{PI}}^{1/2}}\bigr)+\eta^{-1}\int_{0}^{R-t}re^{-\frac{r^{2}}{2\eta}}\,\exp\bigl(-\frac{R-r}{C_{\mathsf{PI}}^{1/2}}\bigr)\,\mathrm{d}r \displaystyle\lesssim\exp\bigl(-\frac{R^{2}}{2\eta}\bigr)\,\exp(-c_{1}\log R)+\frac{R}{\eta}\int_{t}^{R}\exp\bigl(-\frac{(R-r)^{2}}{2\eta}\bigr)\,\exp\bigl(-\frac{r}{C_{\mathsf{PI}}^{1/2}}\bigr)\,\mathrm{d}r \displaystyle\leq\exp\bigl(-\frac{R^{2}}{2\eta}\bigr)\,R^{-c_{1}}+\frac{R}{\eta}\,\exp\bigl(-\frac{R^{2}}{2\eta}\bigr)\int_{t}^{R}\exp\bigl(\frac{Rr}{\eta}-\frac{r}{C_{\mathsf{PI}}^{1/2}}\bigr)\,\mathrm{d}r\,. Using \eta\gtrsim Rt and taking c_{1} large enough, \displaystyle\int_{t}^{R}\exp\bigl(\frac{Rr}{\eta}-\frac{r}{C_{\mathsf{PI}}^{1/2}}\bigr)\,\mathrm{d}r \displaystyle\leq\int_{t}^{R}\exp\Bigl(r\,\bigl(\frac{c_{3}}{c_{1}C_{\mathsf{PI}}^{1/2}}-\frac{1}{C_{\mathsf{PI}}^{1/2}}\bigr)\Bigr)\,\mathrm{d}r\leq\int_{t}^{R}\exp\bigl(-\frac{r}{2C_{\mathsf{PI}}^{1/2}}\bigr)\,\mathrm{d}r \displaystyle\leq 2C_{\mathsf{PI}}^{1/2}\exp\bigl(-\frac{t}{2C_{\mathsf{PI}}^{1/2}}\bigr)\leq 2C_{\mathsf{PI}}^{1/2}R^{-c_{1}/2}\,. Substituting these back to above, for large enough c_{1}>0 , we obtain that \int_{0}^{R-t}e^{-\frac{r^{2}}{2\eta}}\,\nu_{n-1}(B_{r})\,\mathrm{d}r\leq\exp\bigl(-\frac{R^{2}}{2\eta}\bigr)\,\bigl(R^{-c_{1}}+\frac{2RC_{\mathsf{PI}}^{1/2}R^{-c_{1}/2}}{\eta}\bigr)\lesssim R^{-c_{1}/2}\exp\bigl(-\frac{R^{2}}{2\eta}\bigr)\,. We can bound the second expectation in a similar way: \displaystyle\int_{R+t}^{\infty}r^{2}e^{-\frac{r^{2}}{2\eta}}\,\nu_{n-1}(\partial B_{r})\,\mathrm{d}r \displaystyle=\bigl[r^{2}e^{-\frac{r^{2}}{2\eta}}\,\nu(B_{r})\bigr]_{R+t}^{\infty}+\int_{R+t}^{\infty}\bigl(\frac{r^{3}}{\eta}-2r\bigr)\,e^{-\frac{r^{2}}{2\eta}}\,\nu(B_{r})\,\mathrm{d}r \displaystyle\lesssim\lim_{r\to\infty}r^{2}\exp\bigl(-\frac{r^{2}}{2\eta}-\frac{r-R}{C_{\mathsf{PI}}^{1/2}}\bigr)+\eta^{-1}\int_{R+t}^{\infty}r^{3}\exp\bigl(-\frac{r^{2}}{2\eta}-\frac{r-R}{C_{\mathsf{PI}}^{1/2}}\bigr)\,\mathrm{d}r \displaystyle=\eta^{-1}\int_{t}^{\infty}(r+R)^{3}\exp\bigl(-\frac{(r+R)^{2}}{2\eta}-\frac{r}{C_{\mathsf{PI}}^{1/2}}\bigr)\,\mathrm{d}r \displaystyle\leq 4\eta^{-1}\exp\bigl(-\frac{R^{2}}{2\eta}\bigr)\int_{t}^{\infty}(r^{3}+R^{3})\,\exp\bigl(-\frac{r}{C_{\mathsf{PI}}^{1/2}}\bigr)\,\mathrm{d}r\,. We can bound each integral as follows: \displaystyle\int_{t}^{\infty}R^{3}\exp\bigl(-\frac{r}{C_{\mathsf{PI}}^{1/2}}\bigr)\,\mathrm{d}r \displaystyle=R^{3}C_{\mathsf{PI}}^{1/2}\exp\bigl(-\frac{t}{C_{\mathsf{PI}}^{1/2}}\bigr)\leq R^{3-c_{1}}C_{\mathsf{PI}}^{1/2}\,, \displaystyle\int_{t}^{\infty}r^{3}\exp\bigl(-\frac{r}{C_{\mathsf{PI}}^{1/2}}\bigr)\,\mathrm{d}r \displaystyle\underset{(i)}{\lesssim}t^{3}C_{\mathsf{PI}}^{1/2}\exp\bigl(-\frac{t}{C_{\mathsf{PI}}^{1/2}}\bigr)\leq t^{3}R^{-c_{1}}C_{\mathsf{PI}}^{1/2}\,, where in (i) we used properties of the incomplete Gamma function to compute \int_{a}^{\infty}x^{3}e^{-x/b}\,\mathrm{d}x=6b^{4}e^{-a/b}\,(1+\frac{a}{b}+\frac{a^{2}}{2b^{2}}+\frac{a^{3}}{6b^{3}}) . Thus, \int_{R+t}^{\infty}r^{2}e^{-\frac{r^{2}}{2\eta}}\,\nu_{n-1}(\partial B_{r})\,\mathrm{d}r\lesssim\exp\bigl(-\frac{R^{2}}{2\eta}\bigr)\,\frac{(R^{3-c_{1}}+t^{3}R^{-c_{1}})\,C_{\mathsf{PI}}^{1/2}}{\eta}\lesssim\exp\bigl(-\frac{R^{2}}{2\eta}\bigr)\,. Therefore, for large enough c_{1}>0 , \mathsf{II}\lesssim R^{2}\times R^{-c_{1}/2}\exp\bigl(-\frac{R^{2}}{2\eta}\bigr)+\exp\bigl(-\frac{R^{2}}{2\eta}\bigr)\lesssim\exp\bigl(-\frac{R^{2}}{2\eta}\bigr)\,, and thus N=\mathsf{I}+\mathsf{II}\lesssim\exp\bigl(-\frac{R^{2}}{2\eta}\bigr)\,. Combining all previous bounds, Q=\frac{N}{D}\lesssim 1\,, which completes the proof. ∎ 3.3 Functional inequalities for strongly logconcave distributions with compact support We examine ( LSI ) and ( PI ) for strongly logconcave distributions with compact support. Log-Sobolev constant. We can now answer Question 3.4 in some sense, showing that C_{\mathsf{LSI}}(\pi\gamma_{h}) is bounded by \mathcal{O}(D\lambda^{1/2}\log^{2}n\log^{2}D\lambda^{-1/2}) , which also bounds C_{\mathsf{LSI}}(\pi) . Proof of Corollary 3.3 . Using C_{\mathsf{LSI}}(\pi\gamma_{h})\leq h when h\lesssim D\lambda^{1/2}\log^{2}n\log^{2}D\lambda^{-1/2} , and C_{\mathsf{LSI}}(\pi\gamma_{h})\lesssim D\lambda_{h}^{1/2}\log n (Theorem 3.1 ) otherwise, along with \lambda_{h}\lesssim\lambda (Theorem 3.2 ), we obtain C_{\mathsf{LSI}}(\pi\gamma_{h})\lesssim\max\bigl\{D\lambda^{1/2}\log^{2}n\log^{2}\frac{D}{\lambda^{1/2}},D\lambda^{1/2}\log n\bigr\}\,. ∎ Poincaré constant. We can ask a similar question for ( PI ) whether C_{\mathsf{PI}}(\pi\gamma_{h})\lesssim C_{\mathsf{PI}}(\pi) . Using \lVert\operatorname{cov}\mu\rVert\leq C_{\mathsf{PI}}(\mu)\lesssim\lVert\operatorname{cov}\mu\rVert\log n for any logconcave probability measures \mu , together with Theorem 3.2 , we obtain a simple corollary. Corollary 3.10 . Let \pi be a logconcave probability measure over \mathbb{R}^{n} . Then, if h\gtrsim R\lambda^{1/2}\log^{2}n\log^{2}\frac{R}{\lambda^{1/2}} , C_{\mathsf{PI}}(\pi\gamma_{h})\lesssim C_{\mathsf{PI}}(\pi)\log n\,. In particular, if \pi is further isotropic, then C_{\mathsf{PI}}(\pi\gamma_{h})\lesssim C_{\mathsf{PI}}(\pi)\log n when h\gtrsim n^{1/2}\log^{4}n . Proof. When h\gtrsim R\lambda^{1/2}\log^{2}n\log^{2}R\lambda^{-1/2} , it holds that \lambda_{h}\lesssim\lambda by Theorem 3.2 . Thus, C_{\mathsf{PI}}(\pi\gamma_{h})\lesssim\lambda_{h}\log n\lesssim\lambda\log n\leq C_{\mathsf{PI}}(\pi)\log n\,, which completes the proof. ∎ We remark that this is a significant improvement on the bound for h , as compared to h\asymp n^{2} required for applying a \Theta(1) -perturbation argument. 4 Faster warm-start generation Now that we have a refined understanding of functional inequalities and warmness conditions for the \mathsf{Proximal\ sampler} , we combine these ingredients to design a faster algorithm for sampling without a warm start. We recall the main question. Question 4.1 . Let \pi be the uniform distribution over a convex body \mathcal{K} , presented via \mathsf{Mem}_{x_{0},R}(\mathcal{K}) , with covariance matrix \Sigma and second moment R^{2}:=\mathbb{E}_{\pi}[\lVert\cdot-x_{0}\rVert^{2}] . Given \varepsilon\in(0,1) , how many membership queries to \mathcal{K} are required to generate a sample whose law \mu satisfies \lVert\mu-\pi\rVert_{\mathsf{TV}}\leq\varepsilon ? To address this question, we first bound the \mathcal{R}_{q} -divergence between consecutive annealing distributions in § 4.1 . Then in § 4.2 , we interweave new ingredients together to give an improved answer to this question as follows. Theorem 4.2 (Restatement of Theorem 1.8 ) . In the setting of Question 4.1 , there exists an algorithm that for any given \eta,\varepsilon\in(0,1) , with probability at least 1-\eta returns a sample whose law \mu satisfies \lVert\mu-\pi\rVert_{\mathsf{TV}}\leq\varepsilon , using \widetilde{\mathcal{O}}\bigl(n^{2}R^{3/2}\,\lVert\operatorname{cov}\pi\rVert^{1/4}\log^{7}\frac{R^{2}}{\eta\varepsilon\lVert\operatorname{cov}\pi\rVert}\bigr) membership queries in expectation. In particular, if \pi is also near-isotropic (i.e., \lVert\operatorname{cov}\pi\rVert\lesssim 1 ), then \widetilde{\mathcal{O}}(n^{2.75}\log^{6}\nicefrac{{1}}{{\eta\varepsilon}}) queries suffice. Since \lVert\operatorname{cov}\pi\rVert\leq\operatorname{tr}(\operatorname{cov}\pi)\leq R^{2} , this complexity improves the previous n^{2}(n\vee R^{2}) -bound for a \mathsf{TV} -guarantee [ CV18 ] . Alongside, we improve the query complexity of sampling from a standard Gaussian \pi\gamma=\gamma|_{\mathcal{K}} truncated to an arbitrary convex body, by a factor of n^{1/2} [ CV18 ] . Corollary 4.3 (Restatement of Corollary 1.9 ) . In the setting of Question 4.1 , there exists an algorithm that for any given \eta,\varepsilon\in(0,1) , with probability at least 1-\eta returns a sample whose law \mu satisfies \lVert\mu-\pi\gamma\rVert_{\mathsf{TV}}\leq\varepsilon , using \widetilde{\mathcal{O}}\bigl(n^{2.5}\log^{7}\frac{1}{\eta\varepsilon}\bigr) membership queries in expectation. 4.1 Rényi divergence of annealing distributions Since we have mixing guarantees under \mathcal{R}_{c} -warmness for c=\widetilde{\mathcal{O}}(1) , we can design and leverage a faster annealing scheme with provable guarantees. In this section, we extend existing results on the closeness of consecutive annealing distributions to the setting of q -Rényi divergence. The first type: fixed rate annealing. Previous work used that for logconcave e^{-V} and \alpha=n^{-1/2} , the distributions \exp(-V) and \exp(-(1+\alpha)V) are \mathcal{O}(1) -close in \chi^{2} -divergence (i.e., \mathcal{R}_{2} ) [ LV06c , KV06 ] . We generalize this result to q -Rényi divergence (or equivalently, the relative L^{q} -norm). Lemma 4.4 (Rényi version of universal annealing) . Let \mathrm{d}\nu\propto e^{-V}\,\mathrm{d}x and \mathrm{d}\mu\propto e^{-(1+\alpha)\,V}\,\mathrm{d}x be logconcave probability measures over \mathbb{R}^{n} . For q>1 and \delta>0 such that 1-q\delta>0 , \mathcal{R}_{q}(\mu\mathbin{\|}\nu)\leq\begin{cases}\frac{qn\alpha^{2}}{2}&\text{if }\alpha\geq 0\,,\\ \frac{qn\alpha^{2}}{1-q\delta}&\text{if }\alpha\in[-\delta/2,0]\,.\end{cases} In particular, \alpha=(qn)^{-1/2} yields an \mathcal{O}(1) -bound on \mathcal{R}_{q}(\mu\mathbin{\|}\nu) , and \alpha=-(16q\,(q\vee n))^{-1/2} also yields an \mathcal{O}(1) -bound. Proof. Let us define F(s):=\int e^{-sV(x)}\,\mathrm{d}x\,. We recall from [ KV06 , Lemma 3.2] that s\mapsto s^{n}F(s) is logconcave in s . For q>1 , we compute the L^{q} -warmness of \mu with respect to \nu : \displaystyle\Bigl\|\frac{\mathrm{d}\mu}{\mathrm{d}\nu}\Bigr\|_{L^{q}(\nu)}^{q} \displaystyle=\int\bigl(\frac{\mu}{\nu}\bigr)^{q}\,\mathrm{d}\nu=\int\exp\bigl(-q\,(1+\alpha)\,V(x)+(q-1)\,V(x)\bigr)\,\mathrm{d}x\times\frac{F^{q-1}(1)}{F^{q}(1+\alpha)} \displaystyle=\frac{F(1+q\alpha)\,F^{q-1}(1)}{F^{q}(1+\alpha)}=\Bigl(\frac{(1+\alpha)^{n}}{(1+q\alpha)^{n/q}}\,\frac{(1+q\alpha)^{n/q}F^{1/q}(1+q\alpha)\,F^{1-q^{-1}}(1)}{(1+\alpha)^{n}F(1+\alpha)}\Bigr)^{q} \displaystyle\leq\bigl(\frac{(1+\alpha)^{q}}{1+q\alpha}\bigr)^{n}\,, where the last inequality follows from logconcavity of s^{n}F(s) in s . We now claim that for \alpha\geq 0 , \frac{(1+\alpha)^{q}}{1+q\alpha}\leq\exp\bigl(\frac{q\,(q-1)}{2}\,\alpha^{2}\bigr)\,. For \alpha\geq 0 , let us define g(\alpha):=\frac{q\,(q-1)}{2}\,\alpha^{2}-q\log(1+\alpha)+\log(1+q\alpha)\,. We can compute that g(0)=0 and g^{\prime}(\alpha)=(q-1)\,q\alpha-\frac{q}{1+\alpha}+\frac{q}{1+q\alpha}=\frac{\alpha^{2}q\,(q-1)(\alpha q+q+1)}{(1+\alpha)(\alpha q+1)}\geq 0\,, from which the claim follows. We also show that for \alpha\in[-\delta/2,0] with 1-q\delta>0 , \frac{(1+\alpha)^{q}}{1+q\alpha}\leq\exp\bigl(\frac{q\,(q-1)}{2\,(1-q\delta)}\,\alpha^{2}\bigr)\,. In a similarly way, we define and compute that \displaystyle g(\alpha) \displaystyle:=\frac{q\,(q-1)}{2\,(1-q\delta)}\,\alpha^{2}-q\log(1+\alpha)+\log(1+q\alpha)\,, \displaystyle g^{\prime}(\alpha) \displaystyle=\frac{q-1}{1-q\delta}\,q\alpha-\frac{q}{1+\alpha}+\frac{q}{1+q\alpha}=\alpha q\,(q-1)\,\bigl(\frac{1}{1-q\delta}-\frac{1}{(1+\alpha)\,(1+q\alpha)}\bigr)\leq 0\,, from which the claim follows. Using each bound for \alpha\geq 0 and \alpha\in[-\delta/2,0] , \mathcal{R}_{q}(\mu\mathbin{\|}\nu)=\frac{1}{q-1}\,\log\,\Bigl\|\frac{\mathrm{d}\mu}{\mathrm{d}\nu}\Bigr\|_{L^{q}(\nu)}^{q}\leq\begin{cases}\frac{qn\alpha^{2}}{2}&\text{if }\alpha\geq 0\,,\\ \frac{qn\alpha^{2}}{1-q\delta}&\text{if }\alpha\in[-\delta/2,0]\,.\end{cases} This completes the proof. ∎ The second type: accelerated annealing. In this annealing, the change in the annealing parameter depends on the variance of the current distribution. A bound of this type was previously established for \chi^{2} -divergence in [ CV18 , Lemma 7.8] . We show that this bound also extends to \mathcal{R}_{q} -divergence, enabling control over the closeness of annealing steps under Rényi-divergence. In particular, this allows us to multiply the variance by a factor of 1+\sigma/R in each step. Lemma 4.5 (Rényi version of accelerated annealing) . Let \mu be a logconcave probability density in \mathbb{R}^{n} with support of diameter R>0 . Then, for q>1 and \sigma^{2}>0 , \mathcal{R}_{q}(\mu\gamma_{\sigma^{2}}\mathbin{\|}\mu\gamma_{\sigma^{2}(1+\alpha)})\leq\frac{qR^{2}\alpha^{2}}{\sigma^{2}}\,. In particular, \alpha\lesssim\sigma/(q^{1/2}R) yields an \mathcal{O}(1) -bound on the \mathcal{R}_{q} -divergence. Proof. We define \mu_{\sigma^{2}}(x):=\mu\gamma_{\sigma^{2}}\,,\qquad F(s):=\int\mu(x)\exp\bigl(-\frac{1+\alpha+s}{2\sigma^{2}\,(1+\alpha)}\,\lVert x\rVert^{2}\bigr)\,,\qquad G(s):=\log F(s)\,. Then, \Bigl\|\frac{\mathrm{d}\mu_{\sigma^{2}}}{\mathrm{d}\mu_{\sigma^{2}(1+\alpha)}}\Bigr\|_{L^{q}(\mu_{\sigma^{2}(1+\alpha)})}^{q}=\frac{F^{q-1}(-\alpha)\,F\bigl((q-1)\,\alpha\bigr)}{F^{q}(0)}\,, and \displaystyle\log\,\Bigl\|\frac{\mathrm{d}\mu_{\sigma^{2}}}{\mathrm{d}\mu_{\sigma^{2}(1+\alpha)}}\Bigr\|_{L^{q}(\mu_{\sigma^{2}(1+\alpha)})}^{q} \displaystyle=(q-1)\,G(-\alpha)+G\bigl((q-1)\,\alpha\bigr)-q\,G(0) \displaystyle=(q-1)\,\bigl(G(-\alpha)-G(0)\bigr)+G\bigl((q-1)\,\alpha\bigr)-G(0) \displaystyle=-(q-1)\int_{0}^{\alpha}G^{\prime}(-t)\,\mathrm{d}t+(q-1)\int_{0}^{\alpha}G^{\prime}\bigl((q-1)\,t\bigr)\,\mathrm{d}t \displaystyle=(q-1)\int_{0}^{\alpha}\Bigl(G^{\prime}\bigl((q-1)\,t\bigr)-G^{\prime}(-t)\Bigr)\,\mathrm{d}t \displaystyle=(q-1)\int_{0}^{\alpha}\int_{-t}^{(q-1)\,t}G^{\prime\prime}(u)\,\mathrm{d}u\mathrm{d}t\,. For the strongly logconcave distribution \nu_{u}(x)\propto\mu(x)\exp(-\frac{1+\alpha+u}{2\sigma^{2}(1+\alpha)}\,\lVert x\rVert^{2}) , we have \displaystyle G^{\prime\prime}(u) \displaystyle=-\frac{1}{2\sigma^{2}\,(1+\alpha)}\,\frac{\mathrm{d}}{\mathrm{d}u}\Bigl(\frac{\int\lVert x\rVert^{2}\mu(x)\exp(-\frac{1+\alpha+u}{2\sigma^{2}(1+\alpha)}\,\lVert x\rVert^{2})}{\int\mu(x)\exp(-\frac{1+\alpha+u}{2\sigma^{2}(1+\alpha)}\,\lVert x\rVert^{2})}\Bigr) \displaystyle=\frac{1}{4\sigma^{4}\,(1+\alpha)^{2}}\,\Bigl[\frac{\int\lVert x\rVert^{4}\mu(x)\exp(-\frac{1+\alpha+u}{2\sigma^{2}(1+\alpha)}\,\lVert x\rVert^{2})}{\int\mu(x)\exp(-\frac{1+\alpha+u}{2\sigma^{2}(1+\alpha)}\,\lVert x\rVert^{2})}-\Bigl(\frac{\int\lVert x\rVert^{2}\mu(x)\exp(-\frac{1+\alpha+u}{2\sigma^{2}(1+\alpha)}\,\lVert x\rVert^{2})}{\int\mu(x)\exp(-\frac{1+\alpha+u}{2\sigma^{2}(1+\alpha)}\,\lVert x\rVert^{2})}\Bigr)^{2}\Bigr] \displaystyle=\frac{1}{4\sigma^{4}\,(1+\alpha)^{2}}\operatorname{var}_{\nu_{u}}(\lVert X\rVert^{2})\underset{\eqref{eq:pi}}{\leq}\frac{1}{4\sigma^{4}\,(1+\alpha)^{2}}\,C_{\mathsf{PI}}(\nu_{u})\,\mathbb{E}_{\nu_{u}}[\lVert X\rVert^{2}] \displaystyle\leq\frac{R^{2}}{\sigma^{2}\,(1+\alpha)(1+\alpha+u)}\,, where the last line follows from \sup_{\nu_{u}}\lVert X\rVert\leq R and C_{\mathsf{PI}}(\nu_{u})\leq\frac{\sigma^{2}(1+\alpha)}{1+\alpha+u} . Hence, \displaystyle\mathcal{R}_{q}(\mu\gamma_{\sigma^{2}}\mathbin{\|}\mu\gamma_{\sigma^{2}(1+\alpha)})=\frac{1}{q-1}\,\log\,\lVert\cdot\rVert_{L^{q}}^{q} \displaystyle\leq\frac{R^{2}}{\sigma^{2}\,(1+\alpha)}\int_{0}^{\alpha}\int_{-t}^{(q-1)\,t}\frac{1}{1+\alpha+u}\,\mathrm{d}u\mathrm{d}t \displaystyle=\frac{R^{2}}{\sigma^{2}\,(1+\alpha)}\int_{0}^{\alpha}\log\frac{1+\alpha+(q-1)\,t}{1+\alpha-t}\,\mathrm{d}t \displaystyle=\frac{R^{2}}{\sigma^{2}\,(1+\alpha)}\int_{0}^{\alpha}\log\bigl(1+\frac{qt}{1+\alpha-t}\bigr)\,\mathrm{d}t \displaystyle\leq\frac{qR^{2}}{\sigma^{2}}\int_{0}^{\alpha}\frac{t}{1+\alpha-t}\,\mathrm{d}t \displaystyle\leq\frac{qR^{2}\alpha^{2}}{\sigma^{2}}\,, which completes the proof. ∎ 4.2 Faster warm-start sampling Similar to previous work, we follow an annealing approach based on \mathsf{Gaussian\ cooling} . 4.2.1 Algorithm We can truncate \mathcal{K} to a ball of radius D\asymp R so that for \bar{\mathcal{K}}:=\mathcal{K}\cap B_{D}(0) , the truncated distribution \bar{\pi}:=\pi|_{\bar{\mathcal{K}}}\propto\pi\cdot\mathds{1}_{\bar{\mathcal{K}}} is 2 -warm with respect to \pi . Proposition 4.6 ( [ KZ25 , Proposition 30] ) . Given \varepsilon>0 , there exists a constant L=\log\frac{e}{\varepsilon} such that the volume of \mathcal{K}\cap B_{LR}(0) is at least (1-\varepsilon)\operatorname{vol}\mathcal{K} . In the following description of our algorithm, we proceed as if the output distribution from each iteration matches the intended target distribution. This was justified in § 1.2 by the argument based on the triangle inequality for \mathsf{TV} -distance. Let \mu_{i} denote a logconcave probability measure with density \mathrm{d}\mu_{i}\propto\bar{\pi}\gamma_{\sigma_{i}^{2}}\,\mathrm{d}x\,, and let m denote the number of inner phases in the algorithm. Below, we set failure probability and target accuracy to \eta/m and \varepsilon/m , respectively. • Initialization ( \sigma^{2}=n^{-1} ) – Rejection sampling to sample from \mu_{1}\propto\bar{\pi}\gamma_{n^{-1}} with proposal \gamma_{n^{-1}} . • Annealing ( n^{-1}\leq\sigma^{2}\leq D^{2} ) – Run \mathsf{PS}_{\textup{Gauss}} with initial \mu_{i} and target \mu_{i+1} , where \sigma_{i+1}^{2}=\sigma_{i}^{2}\bigl(1+\frac{\sigma}{q^{1/2}D}\bigr)\,. – Depending on whether \sigma^{2} is below or above \Theta(D\lambda^{1/2}\log^{2}n\log^{2}\nicefrac{{D^{2}}}{{\lambda}}) , use suitable parameters ( h and N ) of \mathsf{PS}_{\textup{Gauss}} according to Theorem 2.2 . • Termination (\sigma^{2}=D^{2}) – Run \mathsf{PS}_{\textup{unif}} with initial \mu_{\text{last}}=\bar{\pi}\gamma_{D^{2}} and target \pi . 4.2.2 Analysis To obtain a provable guarantee on the final query complexity, we should specify the Rényi parameter q . While this is somewhat subtle since parameters are dependent to each other, we walk through how to set all necessary parameters without incurring any logical gaps. Choice of parameters. For q\geq 2 , our algorithm guarantees \mathcal{R}_{2} -warmness between any pair of consecutive distributions (i.e., M_{2}\lesssim 1 ). The number m of inner phases is bounded as m\leq\frac{q^{1/2}D}{\sigma_{0}}\log nD\leq q^{1/2}n^{1/2}D\log nD=:m_{\max}(q)\,. Also, by Theorem 2.2 , the number of iterations required for each inner phase is at most k\leq\widetilde{\mathcal{O}}\bigl(n^{2}D^{2}\log^{3}\frac{m_{\max}^{2}(q)}{\eta\varepsilon}\bigr)\leq\widetilde{\mathcal{O}}(n^{2}D^{2}\log^{3}\frac{q}{\eta\varepsilon})=:k_{\max}(q)\,. To ensure the query complexity bound of \mathsf{PS}_{\textup{Gauss}} , it suffices to choose q such that q\gtrsim\log\frac{qnD}{\eta\varepsilon}\Bigl(\gtrsim\log\frac{k_{\max}(q)\,m_{\max}(q)}{\eta}\gtrsim 6\log\frac{16kmM_{2}}{\eta}\Bigr)\,, to obtain a query complexity bound for \mathsf{PS}_{\textup{Gauss}} via the monotonicity of M_{q} in q . Since the first inequality is satisfied by choosing q\gtrsim\log\frac{nD}{\eta\varepsilon}=\widetilde{\mathcal{O}}(1)\,, we can set q to the RHS, which in turn determines the values of m_{\max}(q) and k_{\max}(q) accordingly. Complexity bound. We now analyze the expected number of membership queries used in each phase of the algorithm. Lemma 4.7 (Initialization) . The initialization can sample from \mu_{1}=\bar{\pi}\gamma_{n^{-1}} , using \mathcal{O}(1) queries in expectation. Proof. Rejection sampling with proposal \gamma_{n^{-1}} succeeds in the following number of trials in expectation: \frac{\int_{\mathbb{R}^{n}}\exp(-\frac{n}{2}\,\lVert x\rVert^{2})\,\mathrm{d}x}{\int_{\bar{\mathcal{K}}}\exp(-\frac{n}{2}\,\lVert x\rVert^{2})\,\mathrm{d}x}=\bigl(\gamma_{n^{-1}}(\bar{\mathcal{K}})\bigr)^{-1}\leq\bigl\{\gamma_{n^{-1}}\bigl(B_{1}(0)\bigr)\bigr\}^{-1}\lesssim 1\,, which completes the proof. ∎ Next, we bound the query complexity of the main annealing phase. Below, we denote \lambda:=\lVert\Sigma\rVert . Lemma 4.8 (Annealing) . With probability at least 1-\eta , the Gaussian annealing outputs a sample whose law \nu satisfies \lVert\nu-\bar{\pi}\gamma_{D^{2}}\rVert_{\mathsf{TV}}\leq\varepsilon , using \widetilde{\mathcal{O}}\bigl(n^{2}D^{3/2}\lambda^{1/4}\log^{6}\frac{1}{\eta\varepsilon}\log\frac{D^{2}}{\lambda}\bigr) membership queries in expectation. Proof. For any given \sigma^{2}\in[n^{-1},D^{2}] , we need at most q^{1/2}D/\sigma phases to double \sigma^{2} . While doubling the initial \sigma^{2} , any consecutive distributions are \mathcal{O}(1) -close in \mathcal{R}_{q} (i.e., M_{q}\lesssim 1 ) by Lemma 4.5 . By Theorem 2.2 , when \sigma^{2}\lesssim D\lambda^{1/2}\log^{2}n\log^{2}\nicefrac{{D^{2}}}{{\lambda}} , with probability at least 1-\eta/m , \mathsf{PS}_{\textup{Gauss}} can sample a next annealing distribution from a current one with a \mathcal{R}_{2} -guarantee, using \widetilde{\mathcal{O}}\bigl(n^{2}\sigma^{2}\log^{6}\frac{m_{\max}^{2}}{\eta\varepsilon}\bigr) queries in expectation. Hence, throughout this doubling, the total query complexity is \widetilde{\mathcal{O}}\bigl(q^{1/2}Dn^{2}\sigma\log^{6}\frac{m_{\max}^{2}}{\eta\varepsilon}\bigr)=\widetilde{\mathcal{O}}\bigl(n^{2}D^{3/2}\lambda^{1/4}\log^{6}\frac{1}{\eta\varepsilon}\log\frac{D^{2}}{\lambda}\bigr)\,. When \sigma^{2} exceeds this threshold, \mathsf{PS}_{\textup{Gauss}} uses \widetilde{\mathcal{O}}(n^{2}D\lambda^{1/2}\log^{6}\frac{m_{\max}^{2}}{\eta\varepsilon}) queries in expectation. Thus, the total query complexity of one doubling is \widetilde{\mathcal{O}}\bigl(\frac{q^{1/2}n^{2}D^{2}\lambda^{1/2}}{\sigma}\log^{6}\frac{m_{\max}^{2}}{\eta\varepsilon}\bigr)=\widetilde{\mathcal{O}}\bigl(n^{2}D^{3/2}\lambda^{1/4}\log^{6}\frac{1}{\eta\varepsilon}\bigr)\,. Adding up these two bounds, we can bound the total complexity during annealing as claimed. Using an argument based on the triangle inequality (explained in § 1.2 ), we can also obtain the final \mathsf{TV} -guarantee. Lastly, the failure probability also follows from the union bound. ∎ The termination simply runs \mathsf{PS}_{\textup{unif}} . Lemma 4.9 (Termination) . With probability at least 1-\eta , the termination phase with initial \bar{\pi}\gamma_{D^{2}} and target \pi outputs a sample whose law \nu satisfies \mathcal{R}_{2}(\nu\mathbin{\|}\pi)\leq\varepsilon , using \widetilde{\mathcal{O}}\bigl(n^{2}\lambda\log^{6}\frac{1}{\eta\varepsilon}\bigr) queries in expectation. Proof. We first show that \bar{\pi}\gamma_{D^{2}} is \mathcal{O}(1) -close to \pi in \mathcal{R}_{\infty} . This is immediate from the following computation: \frac{\bar{\pi}\gamma_{D^{2}}}{\pi}=\frac{\bar{\pi}\gamma_{D^{2}}}{\bar{\pi}}\times\frac{\bar{\pi}}{\pi}=\frac{\operatorname{vol}\bar{\mathcal{K}}\,\exp(-\frac{1}{2D^{2}}\,\lVert x\rVert^{2})}{\int_{\bar{\mathcal{K}}}\exp(-\frac{1}{2D^{2}}\,\lVert x\rVert^{2})\,\mathrm{d}x}\times\frac{\operatorname{vol}\mathcal{K}}{\operatorname{vol}\bar{\mathcal{K}}}\lesssim 1\,, where the last line follows from \sup_{x\in\bar{\mathcal{K}}}\lVert x\rVert\leq D and Proposition 4.6 . Using \mathsf{PS}_{\textup{unif}} [ KVZ24 ] , with probability at least 1-\eta , we can sample from \pi with a \mathcal{R}_{2} -guarantee, using \widetilde{\mathcal{O}}(n^{2}\lambda\log^{6}\nicefrac{{1}}{{\eta\varepsilon}}) queries in expectation. ∎ Combining the previous three lemmas, we can prove Theorem 4.2 . Proof of Theorem 4.2 . Replacing \varepsilon\leftarrow\varepsilon/2 and \eta\leftarrow\eta/2 , and combining the three lemmas together, we conclude that the total failure probability is at most \eta . Also, the total complexity is dominated by annealing near \sigma^{2}\approx D\lambda^{1/2} , leading to the bound of \widetilde{\mathcal{O}}\bigl(n^{2}D^{3/2}\lambda^{1/4}\log^{6}\frac{1}{\eta\varepsilon}\log\frac{D^{2}}{\lambda}\bigr)=\widetilde{\mathcal{O}}\bigl(n^{2}R^{3/2}\lambda^{1/4}\log^{6}\frac{1}{\eta\varepsilon}\log\frac{R^{2}}{\lambda}\bigr)\, This completes the proof. ∎ 4.2.3 Sampling from a truncated Gaussian We can sample from a standard Gaussian truncated to a convex body \mathcal{K} in a similar way. Only difference is that we use the global annealing (Lemma 4.4 ), updating \sigma^{2} by \sigma^{2}(1+(qn)^{-1/2}) . In this case, for q\geq 2 , we can ensure that M_{2}\lesssim 1 . Also, \displaystyle m \displaystyle\leq q^{1/2}n^{1/2}\log n=:m_{\max}(q)\,, \displaystyle k \displaystyle\leq\widetilde{\mathcal{O}}\bigl(n^{2}\log^{3}\frac{m_{\max}^{2}(q)}{\eta\varepsilon}\bigr)\leq\widetilde{\mathcal{O}}\bigl(n^{2}\log^{3}\frac{q}{\eta\varepsilon}\bigr)=:k_{\max}(q)\,. By Theorem 2.2 , it suffices to have q\gtrsim\log\frac{qn}{\eta\varepsilon}\bigl(\gtrsim 6\log\frac{16kmM_{2}}{\eta}\bigr)\,, which is fulfilled if q\gtrsim\log\frac{n}{\eta\varepsilon}=\widetilde{\mathcal{O}}(1) . Hence, we set q to the RHS, and then pick m_{\max} and k_{\max} accordingly. An annealing algorithm for \pi\gamma is almost the same with one for a uniform distribution. • Initialization ( \sigma^{2}=n^{-1} ) – Rejection sampling to sample from \mu_{1}\propto\pi\gamma_{n^{-1}} with proposal \gamma_{n^{-1}} . • Annealing ( n^{-1}\leq\sigma^{2}\leq 1 ) – Run \mathsf{PS}_{\textup{Gauss}} with initial \mu_{i} and target \mu_{i+1} , where \sigma_{i+1}^{2}=\sigma_{i}^{2}\bigl(1+(qn)^{-1/2}\bigr)\,. We can then bound query complexity of the annealing phase. Lemma 4.10 (Annealing) . With probability at least 1-\eta , Gaussian annealing outputs a sample whose law \nu satisfies \lVert\nu-\pi\gamma\rVert_{\mathsf{TV}}\leq\varepsilon , using \widetilde{\mathcal{O}}\bigl(n^{5/2}\log^{7}\frac{1}{\eta\varepsilon}\bigr) queries in expectation. Proof. For any given \sigma^{2}\in[n^{-1},1] , we need at most q^{1/2}n^{1/2} inner phases to double \sigma^{2} . While doubling the initial \sigma^{2} , any consecutive distributions are \mathcal{O}(1) -close in \mathcal{R}_{q} (i.e., M_{q}\lesssim 1 ) by Lemma 4.4 . By Theorem 2.2 , with probability at least 1-\eta/m , \mathsf{PS}_{\textup{Gauss}} can sample a next annealing distribution from a current one with a \mathcal{R}_{2} -guarantee, using \widetilde{\mathcal{O}}\bigl(n^{2}\sigma^{2}\log^{6}\frac{m_{\max}^{2}}{\eta\varepsilon}\bigr) queries in expectation. Hence, throughout this doubling, the total query complexity is \widetilde{\mathcal{O}}\bigl(q^{1/2}n^{5/2}\sigma^{2}\log^{6}\frac{m_{\max}^{2}}{\eta\varepsilon}\bigr)=\widetilde{\mathcal{O}}\bigl(n^{5/2}\log^{7}\frac{1}{\eta\varepsilon}\bigr)\,. The remaining part can be done similarly as in Lemma 4.8 . ∎ Combining this lemma and one on initialization from the previous section yields the proof of Corollary 4.3 . Proof of Corollary 4.3 . Since the query complexity of annealing dominates that for initialization, the claim immediately follows. ∎ 5 Extension to general logconcave distributions We now extend our previous results to general logconcave distributions given access to a well-defined function oracle. In particular, we establish improved query complexity bounds for logconcave sampling, similar to our results for uniform sampling. Theorem 5.1 (Restatement of Theorem 1.10 ) . For a logconcave distribution \pi over \mathbb{R}^{n} presented by \mathsf{Eval}_{x_{0},R}(V) , there exists an algorithm that for any given \eta,\varepsilon\in(0,1) , with probability at least 1-\eta returns a sample whose law \mu satisfies \lVert\mu-\pi\rVert_{\mathsf{TV}}\leq\varepsilon , using \widetilde{\mathcal{O}}(n^{2}\max\{n^{1/2},R^{3/2}(\lambda^{1/4}\vee 1)\}\log^{5}\nicefrac{{R\lambda^{-1/2}}}{{\eta\varepsilon}}) evaluation queries in expectation. If \pi is also near-isotropic , then \widetilde{\mathcal{O}}(n^{2.75}\log^{4}\nicefrac{{1}}{{\eta\varepsilon}}) queries suffice. 5.1 Logconcave sampling under relaxed warmness [ KV25 ] showed that general logconcave sampling can be reduced to more structured exponential sampling: for logconcave \mathrm{d}\pi^{X}\propto\exp(-V)\,\mathrm{d}x , consider \mathrm{d}\pi(x,t)\propto\exp(-nt)\,\mathds{1}_{\mathcal{K}}(x,t)\,\mathrm{d}x\mathrm{d}t\quad\text{subject to }\mathcal{K}:=\{(x,t)\in\mathbb{R}^{n}\times\mathbb{R}:V(x)\leq nt\}\,, ( \mathsf{exp}\text{-}\mathsf{red} ) and then focus on sampling from this \pi , as its X -marginal is exactly \pi^{X} the target distribution [ KV25 , Proposition 2.3] . In this section, we bound the query complexities of sampling from this distribution and related annealing distributions under relaxed warmness conditions on the initial distribution instead of \mathcal{R}_{\infty} -warmness. Theorem 5.2 . Given a logconcave density \pi specified by an evaluation oracle \mathsf{Eval}_{R}(V) , consider \pi(x,t)\propto\exp(-nt)|_{\mathcal{K}} given in ( ⁢ exp - red ) and initial distribution \mu with the relative L^{q} -norm denoted as M_{q}=\lVert\mathrm{d}\mu/\mathrm{d}\pi\rVert_{L^{q}(\pi)} for q\geq 2 . For any \eta,\varepsilon\in(0,1) , k\in\mathbb{N} defined below, \mathsf{PS}_{\textup{exp}} with h=(13^{4}n^{2}\log\frac{16kM_{2}}{\eta})^{-1} and N=(\frac{16kM_{2}}{\eta})^{2}\log^{2}\frac{16kM_{2}}{\eta} , with probability at least 1-\eta , achieves \mathcal{R}_{2}(\mu_{k}\mathbin{\|}\pi)\leq\varepsilon after k=\widetilde{\mathcal{O}}(n^{2}(\lVert\operatorname{cov}\pi^{X}\rVert\vee 1)\log^{2}\frac{M_{2}}{\eta\varepsilon}) iterations, where \mu_{k} is the law of the k -th iterate, using \widetilde{\mathcal{O}}\bigl(M_{c}n^{2}(\lVert\operatorname{cov}\pi^{X}\rVert\vee 1)\log^{3}\frac{1}{\eta\varepsilon}\bigr) evaluation queries in expectation for any c\geq 6\log\frac{16kM_{2}}{\eta} . Moreover, an M_{q} -warm start for \pi^{X} can be used to generate an M_{q} -warm start for \pi . Theorem 5.3 . Under \mathsf{Eval}_{x_{0}=0,R}(V) , consider \mu:=\mu_{\sigma^{2},\rho}(x,t)\propto\exp(-\rho t-\frac{1}{2\sigma^{2}}\,\lVert x\rVert^{2})|_{\bar{\mathcal{K}}} , where the diameters of \bar{\mathcal{K}} (obtained by truncation; see ( 5.1 )) in the x and t -direction are \mathcal{O}(R) and \mathcal{O}(1) , and initial distribution \nu with the relative L^{q} -norm denoted as M_{q}=\lVert\mathrm{d}\nu/\mathrm{d}\mu\rVert_{L^{q}(\mu)} for q\geq 2 . For any \eta,\varepsilon\in(0,1) , k\in\mathbb{N} defined below, \mathsf{PS}_{\textup{ann}} with h=(1200^{2}n^{2}\log\frac{16kM_{2}}{\eta})^{-1} and N=2(\frac{16kM_{2}}{\eta})^{2}\log^{2}\frac{16kM_{2}}{\eta} achieves \mathcal{R}_{2}(\nu_{k}\mathbin{\|}\mu)\leq\varepsilon after k=\widetilde{\mathcal{O}}(n^{2}(\sigma^{2}\vee 1)\log^{2}\frac{M_{2}}{\eta\varepsilon}) iterations, where \nu_{k} is the law of the k -th iterate. With probability at least 1-\eta , \mathsf{PS}_{\textup{ann}} iterates k times without failure, using \widetilde{\mathcal{O}}\bigl(M_{c}n^{2}(\sigma^{2}\vee 1)\log^{3}\frac{1}{\eta\varepsilon}\bigr) evaluation queries in expectation for any c\geq 6\log\frac{16kM_{2}}{\eta} . When \rho=n and \sigma^{2}\gtrsim R\lambda^{1/2}\log^{2}n\log^{2}\frac{D^{2}}{\lambda} for \lambda=\lVert\operatorname{cov}\pi^{X}\rVert , it suffices to run k=\widetilde{\mathcal{O}}(n^{2}(R\vee 1)(\lambda^{1/2}\vee 1)\log^{2}\frac{M_{2}}{\eta\varepsilon}) times with query complexity \widetilde{\mathcal{O}}\bigl(M_{c}n^{2}(R\vee 1)(\lambda^{1/2}\vee 1)\log^{3}\frac{1}{\eta\varepsilon}\bigr)\,, 5.1.1 Sampling from the reduced exponential distribution [ KV25 ] proposed and analyzed the \mathsf{Proximal\ sampler} for this reduced distribution (called \mathsf{PS}_{\textup{exp}} there). For z=(x,t)\in\mathbb{R}^{n}\times\mathbb{R} and parameter h>0 , consider the augmented distribution \pi^{Z,Y}(z,y)\propto\exp\bigl(-\alpha^{\mathsf{T}}z-\frac{1}{2h}\,\lVert z-y\rVert^{2}\bigr)\,\mathds{1}_{\mathcal{K}}(z)\qquad\text{for }\alpha:=ne_{n+1}\,, where the Z -marginal \pi^{Z} is the reduced distribution \pi given in ( ⁢ exp - red ). Then, \mathsf{PS}_{\textup{exp}} alternates the following two steps: • [Forward] y\sim\pi^{Y|Z=z}=\mathcal{N}(z,hI_{n+1}) . • [Backward] z\sim\pi^{Z|Y=y}=\mathcal{N}(y-h\alpha,hI_{n+1})|_{\mathcal{K}} for \alpha=ne_{n+1} . – It is implemented by rejection sampling with proposal \mathcal{N}(y-h\alpha,hI_{n+1}) . Mixing analysis. It follows from [ KV25 , Lemma 29] or ( 2.2 ) that \mathsf{PS}_{\textup{exp}} with initial distribution \pi_{0} can achieve \varepsilon -distance in \mathcal{R}_{2} after k\gtrsim h^{-1}C_{\mathsf{PI}}(\pi^{Z})\log\frac{\chi^{2}(\pi_{0}\mathbin{\|}\pi^{Z})}{\varepsilon} iterations. To bound C_{\mathsf{PI}}(\pi^{Z}) , we recall the following result. Lemma 5.4 ( [ KV25 , Lemma 2.5] ) . The variance of \pi^{Z} in the t -direction is at most 160 . Moreover, \operatorname{tr}\operatorname{cov}\pi^{Z}\leq\operatorname{tr}\operatorname{cov}\pi^{X}+160 , and \lVert\operatorname{cov}\pi^{Z}\rVert\leq 2\,(\lVert\operatorname{cov}\pi^{X}\rVert+160) . Combined with C_{\mathsf{PI}}(\pi^{Z})\lesssim\lVert\operatorname{cov}\pi^{Z}\rVert\log n , the required number of iterations is k\gtrsim h^{-1}(\lVert\operatorname{cov}\pi^{X}\rVert\vee 1)\log\frac{\chi^{2}(\pi_{0}\mathbin{\|}\pi)}{\varepsilon}\,. (5.1) Preliminaries. We note that rejection sampling needs \frac{1}{\ell(y)}:=\frac{(2\pi h)^{(n+1)/2}}{\int_{\mathcal{K}}\exp(-\frac{1}{2h}\,\lVert z-(y-h\alpha)\rVert^{2})\,\mathrm{d}z} expected trials until the first acceptance. Before proceeding to the complexity of the backward step, we recall the density of \pi^{Y}=\pi^{Z}*\gamma_{h} and helper lemmas. Lemma 5.5 ( [ KV25 , Lemma 2.11] ) . For \pi^{Z}\propto\exp(-\alpha^{\mathsf{T}}z)|_{\mathcal{K}} , the density of \pi^{Y}=\pi^{Z}*\gamma_{h} is \pi^{Y}(y)=\frac{\ell(y)\exp(-\alpha^{\mathsf{T}}y+\frac{1}{2}\,h\lVert\alpha\rVert^{2})}{\int_{\mathcal{K}}\exp(-\alpha^{\mathsf{T}}z)\,\mathrm{d}z}\,. Its essential domain is given as follows. Lemma 5.6 ( [ KV25 , Lemma 2.12] ) . Under \mathsf{Eval}(V) , for \widetilde{\mathcal{K}}:=\mathcal{K}_{\delta}+h\alpha , if \delta\geq 13hn , then \pi^{Y}(\widetilde{\mathcal{K}}^{c})\leq\exp\bigl(-\frac{\delta^{2}}{2h}+13\delta n\bigr)\,. We will set h=\tfrac{c}{13^{2}n^{2}} and \delta=\tfrac{t}{13n} for some c,t>0 , under which \delta\geq 13hn is equivalent to t\geq c . Lemma 5.7 ( [ KV25 , Lemma 2.13] ) . Under \mathsf{Eval}(V) , \frac{\int_{\mathcal{K}_{s}}\exp(-\alpha^{\mathsf{T}}v)\,\mathrm{d}v}{\int_{\mathcal{K}}\exp(-\alpha^{\mathsf{T}}v)\,\mathrm{d}v}\leq\exp(13sn)\,. We will use the following bound: \displaystyle\frac{\int_{\widetilde{\mathcal{K}}}\exp(-\alpha^{\mathsf{T}}y+\frac{1}{2}\,h\lVert\alpha\rVert^{2})\,\mathrm{d}y}{\int_{\mathcal{K}}\exp(-\alpha^{\mathsf{T}}v)\,\mathrm{d}v} \displaystyle\underset{(i)}{=}\frac{\int_{\mathcal{K}_{\delta}}\exp(-\alpha^{\mathsf{T}}v-\frac{1}{2}\,h\lVert\alpha\rVert^{2})\,\mathrm{d}v}{\int_{\mathcal{K}}\exp(-\alpha^{\mathsf{T}}v)\,\mathrm{d}v}\leq\frac{\int_{\mathcal{K}_{\delta}}\exp(-\alpha^{\mathsf{T}}v)\,\mathrm{d}v}{\int_{\mathcal{K}}\exp(-\alpha^{\mathsf{T}}v)\,\mathrm{d}v} \displaystyle\underset{(ii)}{\leq}e^{13\delta n}=e^{t}\,, (5.2) where (i) follows from change of variables via y=v+h\alpha , and (ii) follows from Lemma 5.7 . (1) Failure probability. For a distribution \nu\ll\pi^{Z} , the failure probability is bounded as \mathbb{E}_{\nu_{h}}[(1-\ell)^{N}]\leq M_{2}\sqrt{\mathbb{E}_{\pi_{h}}[(1-\ell)^{2N}]}\,, where \nu_{h}=\nu*\gamma_{h} , \pi_{h}=\pi^{Z}*\gamma_{h}=\pi^{Y} , and M_{2}:=\lVert\mathrm{d}\nu/\mathrm{d}\pi^{Z}\rVert_{L^{2}(\pi^{Z})} . Following the proof of [ KV25 , Lemma 2.14] with N there replaced by 2N and M there replaced by M_{2} , we decompose \mathbb{E}_{\pi_{h}}[(1-\ell)^{2N}]=\int_{\widetilde{\mathcal{K}}^{c}}\cdot+\int_{\widetilde{\mathcal{K}}\cap[\ell\geq N^{-1}\log(3kM_{2}/\eta)]}\cdot+\int_{\widetilde{\mathcal{K}}\cap[\ell\leq N^{-1}\log(3kM_{2}/\eta)]}\cdot=:\mathsf{A}+\mathsf{B}+\mathsf{C}\,, where we have, \displaystyle\mathsf{A} \displaystyle\leq\pi^{Y}(\widetilde{\mathcal{K}}^{c})\leq\exp\bigl(-\frac{t^{2}}{2c}+t\bigr)\,, \displaystyle\mathsf{B} \displaystyle\leq\int_{\widetilde{\mathcal{K}}\cap[\ell\geq N^{-1}\log(3kM_{2}/\eta)]}\exp(-2\ell N)\,\mathrm{d}\pi^{Y}\leq\bigl(\frac{\eta}{3kM_{2}}\bigr)^{2}\,, \displaystyle\mathsf{C} \displaystyle\leq\int_{\widetilde{\mathcal{K}}\cap[\ell\leq N^{-1}\log(3kM_{2}/\eta)]}\frac{\ell(y)\exp(-\alpha^{\mathsf{T}}y+\frac{1}{2}\,h\lVert\alpha\rVert^{2})}{\int_{\mathcal{K}}\exp(-\alpha^{\mathsf{T}}v)\,\mathrm{d}v}\,\mathrm{d}y \displaystyle\underset{\text{Lemma }\ref{lem:exp-eff-domain}}{\leq}\frac{\log(3kM_{2}/\eta)}{N}\,\frac{\int_{\widetilde{\mathcal{K}}}\exp(-\alpha^{\mathsf{T}}y+\frac{1}{2}\,h\lVert\alpha\rVert^{2})\,\mathrm{d}y}{\int_{\mathcal{K}}\exp(-\alpha^{\mathsf{T}}v)\,\mathrm{d}v}\underset{\eqref{eq:handy-bound}}{\leq}\frac{\log(3kM_{2}/\eta)}{N}\,e^{t}\,. For S=\frac{16kM_{2}}{\eta}(\geq 16) , by choosing c=\frac{(\log\log S)^{2}}{13^{2}\log S} , t=\log\log S , and N=S^{2}\log^{2}S , we can bound each term by (\frac{\eta}{3kM_{2}})^{2} . Therefore, the total failure probability over k iterations is at most \eta by a union bound. (2) Complexity of the backward step. Let p=1+\frac{1}{\alpha} and q=1+\alpha with \alpha=\log N\geq 1 . Then, \mathbb{E}_{\nu_{h}}\bigl[\frac{1}{\ell}\wedge N\bigr]=\int_{\widetilde{\mathcal{K}}\cap[\ell\geq N^{-p}]}\cdot+\int_{\widetilde{\mathcal{K}}\cap[\ell0 , we can ensure that \delta\geq 24hn and \mu^{W}(\widetilde{\mathcal{K}}^{c})\leq\exp\bigl(-\frac{t^{2}}{2c}+c\bigr)\,. Lemma 5.12 ( [ KV25 , Lemma 3.9] ) . In the setting of Lemma 5.11 , for \tau=\frac{\sigma^{2}}{h+\sigma^{2}}<1 , s>0 , and \rho\in(0,n] , \tau^{-n/2}\int_{\bar{\mathcal{K}}_{s}}e^{-\frac{1}{2\tau\sigma^{2}}\,\lVert z\rVert^{2}-\rho l}\,\mathrm{d}z\mathrm{d}l\leq 2\exp(hn^{2}+24sn)\int_{\bar{\mathcal{K}}}e^{-\frac{1}{2\sigma^{2}}\,\lVert z\rVert^{2}-\rho l}\,\mathrm{d}z\mathrm{d}l\,. We will use the following inequality: \displaystyle\frac{\int_{\widetilde{\mathcal{K}}}\tau^{n/2}\exp(-\frac{1}{2\tau\sigma^{2}}\,\lVert y_{\tau}\rVert^{2}-\rho s+\frac{1}{2}\,\rho^{2}h)}{\int_{\bar{\mathcal{K}}}\exp(-\frac{1}{2\sigma^{2}}\,\lVert x\rVert^{2}-\rho t)} \displaystyle\underset{(i)}{=}\frac{\tau^{-n/2}\int_{\bar{\mathcal{K}}_{\delta}}\exp(-\frac{1}{2\tau\sigma^{2}}\,\lVert y\rVert^{2}-\rho s-\frac{1}{2}\,\rho^{2}h)}{\int_{\bar{\mathcal{K}}}\exp(-\frac{1}{2\sigma^{2}}\,\lVert x\rVert^{2}-\rho t)} \displaystyle\underset{(ii)}{\leq}2\exp(hn^{2}+24\delta n)\leq 2e^{1.1c+24t}\,, (5.5) where (i) follows from change of variables, and (ii) follows from Lemma 5.12 . (1) Failure probability. For a distribution \nu\ll\mu^{V} , the failure probability is bounded as \mathbb{E}_{\nu_{h}}[(1-\ell)^{N}]\leq M_{2}\sqrt{\mathbb{E}_{\mu_{h}}[(1-\ell)^{2N}]}\,, where \nu_{h}=\nu*\gamma_{h} , \mu_{h}=\mu^{V}*\gamma_{h} , and M_{2}:=\lVert\mathrm{d}\nu/\mathrm{d}\mu^{V}\rVert_{L^{2}(\mu^{V})} . Emulating the proof of [ KV25 , Lemma 3.10] with N there replaced by 2N and M there replaced by M_{2} , we decompose \mathbb{E}_{\mu_{h}}[(1-\ell)^{2N}]=\int_{\widetilde{\mathcal{K}}^{c}}\cdot+\int_{\widetilde{\mathcal{K}}\cap[\ell\geq N^{-1}\log(3kM_{2}/\eta)]}\cdot+\int_{\widetilde{\mathcal{K}}\cap[\ell\leq N^{-1}\log(3kM_{2}/\eta)]}=:\mathsf{A}+\mathsf{B}+\mathsf{C}\,. Then, \displaystyle\mathsf{A} \displaystyle\leq\mu^{W}(\widetilde{\mathcal{K}}^{c})\leq\exp\bigl(-\frac{t^{2}}{2c}+c\bigr)\,, \displaystyle\mathsf{B} \displaystyle\leq\int_{\widetilde{\mathcal{K}}\cap[\ell\geq N^{-1}\log(3kM_{2}/\eta)]}\exp(-2\ell N)\,\mathrm{d}\mu^{W}\leq\bigl(\frac{\eta}{3kM_{2}}\bigr)^{2}\,, \displaystyle\mathsf{C} \displaystyle\leq\int_{\widetilde{\mathcal{K}}\cap[\ell\leq N^{-1}\log(3kM_{2}/\eta)]}\frac{\tau^{n/2}\ell(y,s)\exp(-\frac{1}{2\tau\sigma^{2}}\,\lVert y_{\tau}\rVert^{2})\exp(-\rho s+\frac{1}{2}\,\rho^{2}h)}{\int_{\bar{\mathcal{K}}}\exp(-\frac{1}{2\sigma^{2}}\,\lVert x\rVert^{2}-\rho t)} \displaystyle\leq\frac{\log(3kM_{2}/\eta)}{N}\,\frac{\int_{\widetilde{\mathcal{K}}}\tau^{n/2}\exp(-\frac{1}{2\tau\sigma^{2}}\,\lVert y_{\tau}\rVert^{2}-\rho s+\frac{1}{2}\,\rho^{2}h)}{\int_{\bar{\mathcal{K}}}\exp(-\frac{1}{2\sigma^{2}}\,\lVert x\rVert^{2}-\rho t)}\underset{\eqref{eq:tilt-Gaussian-ineq}}{\leq}\frac{\log(3kM_{2}/\eta)}{N}\,2e^{25t}\,, where the last inequality follows from the choice of c=\frac{(\log\log S)^{2}}{4\cdot 24^{2}\log S} and t=\tfrac{1}{25}\log\log S for S=\frac{16kM_{2}}{\eta} . Taking N=2S^{2}\log^{2}S , we obtain that \mathbb{E}_{\mu_{h}}[(1-\ell)^{2N}]\leq\bigl(\frac{\eta}{kM_{2}}\bigr)^{2}\,. Therefore, the total failure probability during k iterations is at most \eta by the union bound. (2) Complexity of the backward step. Let p=1+\frac{1}{\alpha} and q=1+\alpha with \alpha=\log N\geq 1 . Then, \mathbb{E}_{\nu_{h}}\bigl[\frac{1}{\ell}\wedge N\bigr]=\int_{\widetilde{\mathcal{K}}\cap[\ell\geq N^{-p}]}\cdot+\int_{\widetilde{\mathcal{K}}\cap[\ell0 and l=\log\frac{2e}{\varepsilon} , one may assume that x_{0}=0 and then consider \bar{\mathcal{K}}:=\mathcal{K}\cap\{B_{Rl}(0)\times[-21,13l-6]\}\,, (5.1) which satisfies \pi(\mathbb{R}^{n+1}\backslash\bar{\mathcal{K}})\leq\varepsilon . Taking \varepsilon=1/2 , we can ensure that \bar{\pi}=\pi|_{\bar{\mathcal{K}}} is \mathcal{O}(1) -close to \pi in \mathcal{R}_{\infty} . Let D:=Rl . We note that \bar{\mathcal{K}} has the diameter D and 30 in the x and t -direction, respectively. We now adapt and accelerate \mathsf{Tilted\ Gaussian\ cooling} , a warm-start generating algorithm proposed in [ KV25 ] . We denote \mu_{i}:=\mu_{\sigma_{i}^{2},\rho_{i}} and set failure probability and target accuracy to \eta/m and \varepsilon/m , where m is the number of total phases throughout the algorithm. • [Phase I] \sigma^{2} -warming ( n^{-1}\leq\sigma^{2}\leq 1 ) – Initialization: Sample from \mu_{0}\propto\exp(-\frac{n}{2}\,\lVert x\rVert^{2})|_{\bar{\mathcal{K}}} (run rejection sampling with proposal \mathcal{N}(0,n^{-1}I_{n})\otimes\text{Unif}\,([-21,13l-6]) ). – Run \mathsf{PS}_{\textup{ann}} with initial \mu_{i} and target \mu_{i+1} , where \sigma_{i+1}^{2}=\sigma_{i}^{2}\bigl(1+\frac{1}{(qn)^{1/2}}\bigr)\,. • [Phase II] \rho -annealing ( \sigma^{2}\approx 1 , 1\leq\rho\leq n ) – Initialization: Run \mathsf{PS}_{\textup{ann}} with initial \mu_{i}\propto\exp(-\frac{1}{2}\,\lVert x\rVert^{2})|_{\bar{\mathcal{K}}} and target \mu_{i+1}\propto\exp(-\frac{1}{2}\,\lVert x\rVert^{2}-t)|_{\bar{\mathcal{K}}} . – Run \mathsf{PS}_{\textup{ann}} with initial \mu_{i} and target \mu_{i+1} , where \sigma_{i+1}^{2}=\sigma_{i}^{2}\bigl(1+\frac{1}{\bigl(16q\,(q\vee n)\bigr)^{1/2}}\bigr)^{-1}\quad\&\quad\rho_{i+1}=\rho_{i}\bigl(1+\frac{1}{\bigl(16q\,(q\vee n)\bigr)^{1/2}}\bigr)\,. – Run the following inner annealing: until \sigma_{i+1}^{2}\leq 1 , run \mathsf{PS}_{\textup{ann}} with initial \mu_{i+1} and new \mu_{i+1} defined by \sigma_{i+1}^{2}\leftarrow\sigma_{i+1}^{2}\bigl(1+\frac{\sigma_{i+1}}{q^{1/2}D}\bigr)\,, • [Phase III] \sigma^{2} -annealing ( 1\leq\sigma^{2}\leq D^{2} , \rho=n ) – Run \mathsf{PS}_{\textup{ann}} with initial \mu_{i}=\bar{\pi}\gamma_{\sigma_{i}^{2}} and target \mu_{i+1}=\bar{\pi}\gamma_{\sigma_{i+1}^{2}} , where \sigma_{i+1}^{2}=\sigma_{i}^{2}\bigl(1+\frac{\sigma_{i}}{q^{1/2}D}\bigr)\,. – Termination (\sigma^{2}=D^{2}) : run \mathsf{PS}_{\textup{exp}} with initial \mu_{D^{2},n}=\bar{\pi}\gamma_{D^{2}} and target \pi\propto\exp(-nt)|_{\mathcal{K}} . 5.2.2 Analysis Just as in the previous section, we first carefully pick all parameters. Choice of parameters. For q\geq 2 , it is clear that consecutive distributions in Phase I and Phase II are \mathcal{O}(1) in \mathcal{R}_{q} by Lemma 4.4 , while closeness within the inner annealing of Phase II follows from Lemma 4.5 . To see this, we note that an annealing distribution in the inner annealing can be written as \mu_{j}=\exp\bigl(-\rho t-\frac{1}{2\sigma_{j}^{2}}\,\lVert x\rVert^{2}\bigr)\big|_{\bar{\mathcal{K}}}\,, so its X -marginal can be written as \mu_{j}^{X}\propto\nu\gamma_{\sigma_{j}^{2}} for some logconcave distribution \nu over \mathbb{R}^{n} . Then, one can readily check that \Bigl\|\frac{\mathrm{d}\mu_{j}}{\mathrm{d}\mu_{j+1}}\Bigr\|_{L^{q}(\mu_{j+1})}=\Bigl\|\frac{\mathrm{d}\mu_{j}^{X}}{\mathrm{d}\mu_{j+1}^{X}}\Bigr\|_{L^{q}(\mu_{j+1}^{X})}\,. Closeness in Phase III also follows in the same way via Lemma 4.5 . The number of inner phases is bounded by m\leq(qn)^{1/2}\log n+\bigl(16q\,(q\vee n)\bigr)^{1/2}\log n\times\frac{D}{(q\vee n)^{1/2}}+q^{1/2}D\log D^{2}\lesssim q^{1/2}n^{1/2}D\log nD=:m_{\max}(q)\,. By Theorem 5.3 , the number of iterations for each inner phase is k=\widetilde{\mathcal{O}}\Bigl(n^{2}\bigl((\sigma^{2}\vee 1)+(D\vee 1)(\lambda^{1/2}\vee 1)\bigr)\log^{2}\frac{m_{\max}^{2}(q)}{\eta\varepsilon}\Bigr)\lesssim\widetilde{\mathcal{O}}\bigl(n^{2}D^{2}\log^{2}\frac{q}{\eta\varepsilon}\bigr)=:k_{\max}(q)\,, and it suffices to take q\gtrsim\log\frac{qnD}{\eta\varepsilon}\bigl(\gtrsim\log\frac{k_{\max}(q)m_{\max}(q)}{\eta}\gtrsim 6\log\frac{16kmM_{2}}{\eta}\bigr) in order to have a provable bound on a query complexity of \mathsf{PS}_{\textup{ann}} under \mathcal{R}_{q} -warmness. Since the condition on q is fulfilled if q\gtrsim\log\frac{nD}{\eta\varepsilon}=\widetilde{\mathcal{O}}(1)\,, we set q to the RHS above, from which k_{\max}(q) and m_{\max}(q) are determined. Complexity bound. We now bound the query complexity of each phase. Lemma 5.13 (Phase I, \sigma^{2} -warming) . With probability at least 1-\eta , Phase I outputs a sample whose law \nu satisfies \lVert\nu-\gamma|_{\bar{\mathcal{K}}}\rVert_{\mathsf{TV}}\leq\varepsilon\,, using \widetilde{\mathcal{O}}(n^{5/2}\log^{4}\nicefrac{{D}}{{\eta\varepsilon}}) evaluation queries in expectation. Proof. At initialization, one can readily check that \mu_{0} can be sampled by rejection sampling with \mathcal{O}(1) queries in expectation (see [ KV25 , Lemma 5.6] ). For any given \sigma^{2}\in[n^{-1},1] , we need at most (qn)^{1/2} inner phases to double the initial \sigma^{2} . Any pair of consecutive distributions is \mathcal{O}(1) -close in \mathcal{R}_{q} by Lemma 4.4 . By Theorem 5.3 , each inner phase then requires \widetilde{\mathcal{O}}\bigl(n^{2}\log^{3}\frac{m_{\max}^{2}}{\eta\varepsilon}\bigr)=\widetilde{\mathcal{O}}\bigl(n^{2}\log^{3}\frac{D}{\eta\varepsilon}\bigr) evaluation queries in expectation. Therefore, Phase I uses \widetilde{\mathcal{O}}\bigl(n^{2}\log^{3}\frac{D}{\eta\varepsilon}\bigr)\times(qn)^{1/2}\times\log n=\widetilde{\mathcal{O}}\bigl(n^{5/2}\log^{4}\frac{D}{\eta\varepsilon}\bigr) evaluation queries in expectation. The final failure probability is immediate from the union bound, while the final \mathsf{TV} -guarantee follows from the triangle inequality as in § 1.2 . ∎ Lemma 5.14 (Phase II, \rho -annealing) . With probability at least 1-\eta , Phase II started at the output of Phase I returns a sample whose law \nu satisfies \lVert\nu-\bar{\pi}\gamma\rVert_{\mathsf{TV}}\leq\varepsilon\,, using \widetilde{\mathcal{O}}(n^{2}(n^{1/2}\vee D)\log^{4}\nicefrac{{1}}{{\eta\varepsilon}}) evaluation queries in total. Proof. At initialization, the two distributions are \mathcal{O}(1) -close in \mathcal{R}_{\infty} since \bar{\mathcal{K}} has diameter of \mathcal{O}(1) in the t -direction. Hence, the query complexity of \mathsf{PS}_{\textup{ann}} is simply \widetilde{\mathcal{O}}(n^{2}\log^{3}\nicefrac{{D}}{{\eta\varepsilon}}) . The outer annealing, which updates \sigma_{i}^{2} and \rho_{i} simultaneously, happens at most (qn)^{1/2}\log n times. For each outer annealing, the second form of Lemma 4.4 with \alpha=-\gamma\,(1+\gamma)^{-1} for \gamma=(16q\,(q\vee n))^{-1/2} implies that \mathcal{R}_{q}(\mu_{i}\mathbin{\|}\mu_{i+1})=\mathcal{O}(1)\,. Then, the outer annealing via \mathsf{PS}_{\textup{ann}} requires \widetilde{\mathcal{O}}(n^{2}\log^{3}\nicefrac{{D}}{{\eta\varepsilon}}) queries in expectation. This outer annealing is immediately followed by the inner annealing, where it increases \sigma^{2} from (1+(16q\,(q\vee n))^{-1/2})^{-1} to 1 . Under the update of \sigma^{2}\leftarrow\sigma^{2}(1+\frac{\sigma}{q^{1/2}D}) , there would be at most \frac{q^{1/2}D}{\sigma}\times\frac{1}{\bigl(16q\,(q\vee n)\bigr)^{1/2}}\leq\frac{D}{(q\vee n)^{1/2}} inner-annealing phases, and each annealing via \mathsf{PS}_{\textup{ann}} also takes \widetilde{\mathcal{O}}(n^{2}\log^{3}\nicefrac{{D}}{{\eta\varepsilon}}) queries. Putting these together, the total query complexity throughout the \rho -annealing is \bigl(16q\,(q\vee n)\bigr)^{1/2}\log n\times\Bigl(\widetilde{\mathcal{O}}\bigl(n^{2}\log^{3}\frac{D}{\eta\varepsilon}\bigr)+\widetilde{\mathcal{O}}\bigl(n^{2}\log^{3}\frac{D}{\eta\varepsilon}\bigr)\times\frac{D}{(q\vee n)^{1/2}}\Bigr)\leq\widetilde{\mathcal{O}}\bigl(n^{2}(n^{1/2}\vee D)\log^{4}\frac{1}{\eta\varepsilon}\bigr)\,, which completes the proof. ∎ Lemma 5.15 (Phase III, \sigma^{2} -annealing) . For \lambda=\lVert\operatorname{cov}\pi^{X}\rVert , with probability at least 1-\eta , Phase III started at the output of Phase II returns a sample whose law \nu satisfies \lVert\nu-\pi\rVert_{\mathsf{TV}}\leq\varepsilon\,, using \widetilde{\mathcal{O}}(n^{2}D^{3/2}(\lambda^{1/4}\vee 1)\log^{4}\nicefrac{{1}}{{\eta\varepsilon}}\log\nicefrac{{D^{2}}}{{\lambda}}) evaluation queries in expectation. Proof. For any given \sigma^{2}\in[1,D^{2}] , its doubling requires at most q^{1/2}D/\sigma phases. Any consecutive distributions are \mathcal{O}(1) -close in \mathcal{R}_{q} (Lemma 4.5 ), so \mathsf{PS}_{\textup{ann}} requires \widetilde{\mathcal{O}}(n^{2}\sigma^{2}\log^{3}\nicefrac{{D}}{{\eta\varepsilon}}) queries. Thus, one doubling takes \frac{q^{1/2}D}{\sigma}\times\widetilde{\mathcal{O}}\bigl(n^{2}\sigma^{2}\log^{3}\frac{D}{\eta\varepsilon}\bigr)\leq\widetilde{\mathcal{O}}\bigl(n^{2}D^{3/2}(\lambda^{1/4}\vee 1)\log^{4}\frac{1}{\eta\varepsilon}\log\frac{D^{2}}{\lambda}\bigr) until \sigma^{2}\lesssim D\,(\lambda^{1/2}\vee 1)\log^{2}n\log^{2}\nicefrac{{D^{2}}}{{\lambda}} . When \sigma^{2} exceeds this threshold, \mathsf{PS}_{\textup{ann}} requires \widetilde{\mathcal{O}}(n^{2}D\,(\lambda^{1/2}\vee 1)\log^{3}\nicefrac{{1}}{{\eta\varepsilon}}) queries in expectation. Hence, one doubling in this regime takes \frac{q^{1/2}D}{\sigma}\times\widetilde{\mathcal{O}}\bigl(n^{2}D\,(\lambda^{1/2}\vee 1)\log^{3}\frac{1}{\eta\varepsilon}\bigr)\leq\widetilde{\mathcal{O}}\bigl(n^{2}D^{3/2}(\lambda^{1/4}\vee 1)\log^{4}\frac{1}{\eta\varepsilon}\bigr)\,. At termination, we note that \frac{\bar{\pi}\gamma_{D^{2}}}{\pi}=\frac{\bar{\pi}\gamma_{D^{2}}}{\bar{\pi}}\,\frac{\bar{\pi}}{\pi}\leq\bigl(\pi(\bar{\mathcal{K}})\bigr)^{-1}\leq 2\,. By Theorem 5.2 , \mathsf{PS}_{\textup{exp}} requires \widetilde{\mathcal{O}}(n^{2}(\lambda\vee 1)\log^{3}\frac{D}{\eta\varepsilon}) queries in expectation. Adding these up, the total query complexity is \widetilde{\mathcal{O}}\bigl(n^{2}D^{3/2}(\lambda^{1/4}\vee 1)\log^{4}\frac{1}{\eta\varepsilon}\log\frac{D^{2}}{\lambda}\bigr) as claimed. ∎ Combining the previous three lemmas together, we can establish the query complexity of sampling from a logconcave distribution as claimed in Theorem 5.1 . Proof of Theorem 5.1 . We simply add up the query complexities in the previous three lemmas, with D\asymp R . That is, \displaystyle n^{5/2}\log^{4}\frac{R}{\eta\varepsilon}+n^{2}(n^{1/2}\vee R)\log^{4}\frac{1}{\eta\varepsilon}+n^{2}R^{3/2}(\lambda^{1/4}\vee 1)\log^{4}\frac{1}{\eta\varepsilon}\log\frac{D^{2}}{\lambda} \displaystyle=\widetilde{\mathcal{O}}\Bigl(n^{2}\max\bigl\{n^{1/2},R^{3/2}(\lambda^{1/4}\vee 1)\bigr\}\log^{5}\frac{R\lambda^{-1/2}}{\eta\varepsilon}\Bigr)\,. When \pi^{X} is further near-isotropic, the claim follows from R\lesssim n^{1/2} and \lambda\asymp 1 . ∎