betaFeedback

WorksMathematics

Subpolynomial-Query Proximal Sampling Beyond Log-Concavity

Abstract

We study the gradient query complexity of sampling from a density π(x)∝e−V(x)π(x)\propto\mathrm{e}^{-V(x)} on Rd\mathbb{R}^d, where VV has a ββ-Lipschitz gradient but need not be convex. Our approach uses the proximal sampler, which alternates Gaussian perturbation with sampling a position conditional on the noisy observation. We implement its observation chain using the high-order noisy conditional sampler of [OpenAI 2026], obtaining improved dimension dependence under functional inequalities. If ππ satisfies a log-Sobolev inequality (LSI) with constant αα, then for every fixed ν>0ν>0, there is a finite constant CνC_ν depending only on νν such that the algorithm returns a sample within total-variation distance ε\varepsilon using at most Cνκ(d+κ+ε−1+∥∇V(x0)∥2/β)νC_νκ(d+κ+\varepsilon^{-1}+\|\nabla V(x_0)\|^2/β)^ν queries, where κ=β/ακ=β/α and x0x_0 is an arbitrary reference point for initialization. The analysis controls center-dependent local errors along exact proximal histories and removes the final observation noise by conditional decoding. Under a Poincaré inequality (PI), we obtain a corresponding guarantee from a warm start with a known bound on its Rényi divergence. An oracle lower bound shows that a stationary point alone, which suffices under LSI, is insufficient under PI.

Introduction

Sampling from a density π(x)∝e−V(x)\pi(x) \propto e^{-V(x)} on Rd\mathbb{R}^d is a fundamental task in statistics, scientific computing, and machine learning. A major line of research studies how the cost of sampling scales with dimension under strong log-concavity and smoothness. Underdamped Langevin dynamics and randomized midpoint discretizations have improved the polynomial dimension dependence of Wasserstein sampling guarantees [3, 16]. Recently, OpenAI [14] established a qualitatively different result: for C2C^2 potentials with a known minimizer and Id⪯∇2V⪯2IdI_d \preceq\nabla^2 V \preceq2I_d, sampling to total-variation accuracy 1/101/10 requires at most CνdνC_{\nu}d^\nu exact first-order queries for every fixed ν>0\nu> 0, with unrestricted computation between queries. Thus, a fixed positive power of the dimension is not intrinsic to query complexity in this well-conditioned setting.

A parallel line of research replaces strong log-concavity with a log-Sobolev inequality (LSI) or a Poincaré inequality (PI), allowing the potential to be nonconvex. Analyses of Langevin and proximal samplers have established polynomial-complexity guarantees under these weaker assumptions, with appropriate initialization conditions [17 CEL$^{+}$22, 6 FYC23]; see [8] for a comprehensive review. Under LSI and smoothness assumptions, representative improvements include d1/2d^{1/2} dimension dependence for rejection-based proximal sampling [FYC23] and, more recently, d1/5d^{1/5} dependence for the Gaussian cloud sampler [5]. These guarantees have different accuracy and initialization requirements. Together with [14], they raise a natural question: can subpolynomial query complexity in dimension also be achieved for smooth targets satisfying LSI or PI, with the required initialization and its cost made explicit? We investigate this question through the proximal sampling framework.

Introduced in [13], the proximal sampler alternates Gaussian perturbation with sampling a position conditional on the noisy observation. This is Gibbs sampling on an augmented space. The conditional draw, called the restricted Gaussian oracle (RGO), adds quadratic regularization to the potential. When the proximal step size is τ<1/β\tau< 1/\beta, the conditional potential has Hessian bounded below by (τ−1−β)Id(\tau^{-1}-\beta)I_d and is therefore strongly convex. The proximal sampler admits convergence guarantees under LSI and PI [6], with efficient RGO implementations based on approximate rejection sampling [FYC23]. Accelerated variants, including Proximal BPS and reflected proximal dynamics, have also been developed under strong log-concavity [4, 18]. Our goal is to improve the dimension dependence of proximal sampling for smooth targets that need not be log-concave.

We build on the local sampling algorithm of [14] to obtain query bounds with an arbitrarily small positive dimension exponent. Its output includes the Gaussian noise needed for the next proximal step, allowing us to run the chain on noisy positions and recover an approximate sample from π\pi only at the end. The main difficulty is that the error in each sampling step depends on the gradient of the potential at the current noisy position. We use LSI or PI to control these errors along the chain without assuming global convexity.

Contributions. For every fixed ν>0\nu> 0, we obtain the following guarantees with a finite constant CνC_\nu depending only on ν\nu. The algorithm only requires gradient queries to the target potential, and the query complexity holds uniformly over its internal randomness.

  • Under LSI and smoothness assumptions, we obtain a sampler with total-variation error at most ε\varepsilon using

Cνκ(d+κ+ε−1+G0)νC_\nu\kappa\left(d+\kappa+\varepsilon^{-1}+G_0\right)^\nu

gradient queries for every fixed ν>0(xref)‘Thm.3‘).Here\nu> 0 ({xref})`Thm. 3`). Here\kappa = \beta/\alpha$, where β\beta is the smoothness constant and α\alpha is the LSI constant. The algorithm starts from N(x0,β−1Id)\mathcal{N}(x_0,\beta^{-1}I_d) at any supplied point x0x_0, whose quality enters through G0=∥∇V(x0)∥2/βG_0 = \lVert\nabla V(x_0)\rVert^2/\beta.

  • Under PI and smoothness assumptions, suppose an initial sample from η0\eta_0 can be generated using at most QinitQ_{\mathrm{init}} gradient queries, with a known bound D2(η0∥π)≤BD_2(\eta_0\mathbin\Vert\pi) \le B, B≥1B \ge1. For every fixed ν>0\nu> 0, we obtain a sampler with total-variation error at most ε\varepsilon using at most

Qinit+Cνκ[B+log⁡(8/ε)](d+κ+B+ε−1)νQ_{\mathrm{init}}+C_\nu\kappa\left[B+\log(8/\varepsilon)\right]\left(d+\kappa+B+\varepsilon^{-1}\right)^\nu

gradient queries (Thm. 4), where κ=β/α\kappa= \beta/\alpha and α\alpha is the PI constant. We also show that a supplied stationary point alone is insufficient for a uniform query bound under PI, even when it is a strict local minimum (Thm. 11).

Technical overview. The local sampler of [14] approximates a conditional position with an independent Gaussian perturbation added. This is exactly the noise used to form the next proximal observation, so one call implements an observation update. We therefore run the chain on noisy positions and, at the end, approximately sample a position conditioned on the last observation. We call this final conditional sampling procedure the decoder; Figure 1 summarizes the algorithm.

Structure of Algorithm 1

Figure 1. Structure of Alg. 1. The padded target has dimension n≥dn \ge d. After the observation updates and final conditional sampling, we discard the appended coordinates and undo the rescaling to obtain x^\hat{x}.

The error of each local call depends on the potential gradient at the current observation. Our comparison argument averages these errors along the exact proximal chain, where LSI or PI supplies mixing and gradient-moment bounds. This avoids having to control gradient moments along the approximate chain. The decoder error is bounded under the stationary observation law, and Prop. 8 combines the mixing, transition, and decoder errors.

Background and main results

Assumption on the target distribution. Throughout this paper, we consider the target distribution π(x)∝e−V(x)\pi(x) \propto e^{-V(x)} on Rd\mathbb{R}^{d} with d≥2d \ge2, where V∈C2(Rd)V \in C^{2}(\mathbb{R}^{d}) is possibly non-convex but has a β\beta-Lipschitz gradient, so that −βId⪯∇2V⪯βId-\beta I_{d} \preceq\nabla^{2}V \preceq\beta I_{d}. The complexity of our algorithms is quantified through the number of gradient queries x↦∇V(x)x \mapsto\nabla V(x), and potential values V(x)V(x) are not required for the algorithms.

Notations and definitions. For a random variable XX, Law⁡(X)\operatorname{Law}(X) denotes its distribution, and for a measurable map TT, T#μ:=Law⁡(T(X))T_{\#}\mu:= \operatorname{Law}(T(X)) for X∼μX \sim\mu. For probability densities μ\mu and η\eta on Rd\mathbb{R}^{d}, the total-variation distance is TV⁡(μ,η)=sup⁡A∣μ(A)−η(A)∣\operatorname{TV}(\mu,\eta) = \sup_{A}|\mu(A)-\eta(A)|, the Kullback–Leibler (KL) divergence is KL⁡(μ∥η)=∫μ(x)log⁡μ(x)η(x) dx\operatorname{KL}(\mu\mathbin{\|}\eta) = \int\mu(x)\log\frac{\mu(x)}{\eta(x)}\,\mathrm{d}x, the χ2\chi^{2} divergence is χ2(μ∥η)=∫μ(x)2η(x) dx−1\chi^{2}(\mu\mathbin{\|}\eta) = \int\frac{\mu(x)^{2}}{\eta(x)}\,\mathrm{d}x - 1, and the Rényi divergence of order two is D2(μ∥η)=log⁡(1+χ2(μ∥η))D_{2}(\mu\mathbin{\|}\eta) = \log(1+\chi^{2}(\mu\mathbin{\|}\eta)). Pinsker’s inequality gives 2TV⁡2≤KL⁡2\operatorname{TV}^{2} \le\operatorname{KL}, and Jensen’s inequality gives KL⁡≤log⁡(1+χ2)\operatorname{KL} \le\log(1+\chi^{2}). We write CC for a positive constant whose value may change from line to line. It never depends on dd, nn, κ\kappa, ε\varepsilon, or the initialization; when it depends on the fixed parameters (γ,K,ω)(\gamma,K,\omega) of NoisySample (Prop. 5), we mention it explicitly.

The proximal sampler

The proximal sampler [13, 6] augments x∼πx \sim\pi with an auxiliary variable yy under the joint density Γτ(x,y)∝e−V(x)−∥x−y∥2/(2τ)\Gamma_{\tau}(x,y) \propto e^{-V(x)-\lVert x-y\rVert^{2}/(2\tau)}, where τ>0\tau> 0 is the step size. Its xx-marginal is π\pi, and its conditional distributions are

y∣x∼N(x,τId),x∣y∼qτy(x)∝e−V(x)−∥x−y∥2/(2τ).(1)y \mid x \sim\mathcal{N}(x,\tau I_{d}), \qquad x \mid y \sim q_{\tau}^{y}(x) \propto e^{-V(x)-\lVert x-y\rVert^{2}/(2\tau)}. \tag*{(1)}

An exact draw from qτyq_{\tau}^{y} is called a restricted Gaussian oracle (RGO) draw. The proximal sampler is the Gibbs chain that draws yk∼N(xk,τId)y_{k} \sim\mathcal{N}(x_{k},\tau I_{d}) and then xk+1∼qτykx_{k+1} \sim q_{\tau}^{y_{k}}. It preserves Γτ\Gamma_{\tau} for every τ\tau, so the position chain (xk)(x_{k}) has stationary law π\pi, and the observation chain (yk)(y_{k}) has stationary law πτ:=π∗N(0,τId)\pi_{\tau} := \pi* \mathcal{N}(0, \tau I_d). Since ∇2V⪰−βId\nabla^2 V \succeq-\beta I_d, every qyτq_y^\tau is strongly log-concave when τ<1/β\tau< 1/\beta, even if π\pi is not. Smaller step sizes make the RGO easier but slow the mixing of the chain, as we will see in Prop. 2.

Functional inequalities

Definition 1 (Functional inequalities). Let Ent⁡π(g):=Eπ[glog⁡gEπg]\operatorname{Ent}_{\pi}(g) := \mathbb{E}_{\pi}\left[g \log\frac{g}{\mathbb{E}_{\pi}g}\right] for g≥0g \ge0. We say that π\pi satisfies an α\alpha-logarithmic Sobolev inequality (LSI) or an α\alpha-Poincaré inequality (PI) if, respectively, the following inequalities hold for all smooth ff:

Ent⁡π(f2)≤2αEπ∥∇f∥2,\operatorname{Ent}_{\pi}(f^2) \le\frac{2}{\alpha}\mathbb{E}_{\pi}\lVert\nabla f\rVert^2,

(LSI)

Var⁡πf≤1αEπ∥∇f∥2.\operatorname{Var}_{\pi} f \le\frac{1}{\alpha}\mathbb{E}_{\pi}\lVert\nabla f\rVert^2.

(PI)

Note that α\alpha-strongly log-concave targets satisfy α\alpha-LSI, and α\alpha-LSI implies α\alpha-PI [2].

Unlike strong log-concavity, both inequalities are stable under bounded perturbations of VV [2], so they allow saddle points and multiple local minima (see the example at the end of § 4). A larger α\alpha means the distribution is better concentrated and typically implies faster mixing, and κ:=β/α\kappa:= \beta/\alpha plays the role of a condition number as in the strongly log-concave case. Valid constants always satisfy α≤β\alpha\le\beta (Lem. 18), so κ≥1\kappa\ge1.

Proposition 2 (Convergence of the ideal proximal sampler). Fix τ>0\tau> 0 and run (1) with exact conditional draws. Let ρk=Law⁡(xk)\rho_k = \operatorname{Law}(x_k) and assume the relevant initial divergence below is finite. For every integer k≥0k \ge0,

KL⁡(ρk∥π)≤(1+ατ)−2kKL⁡(ρ0∥π),if π satisfies α-LSI,(2)\operatorname{KL}(\rho_k\Vert\pi) \le(1+\alpha\tau)^{-2k}\operatorname{KL}(\rho_0\Vert\pi), \qquad\text{if }\pi\text{ satisfies }\alpha\text{-LSI}, \tag*{(2)}
χ2(ρk∥π)≤(1+ατ)−2kχ2(ρ0∥π),if π satisfies α-PI.(3)\chi^2(\rho_k\Vert\pi) \le(1+\alpha\tau)^{-2k}\chi^2(\rho_0\Vert\pi), \qquad\text{if }\pi\text{ satisfies }\alpha\text{-PI}. \tag*{(3)}

The same respective upper bounds hold for the divergences of the observation law σk=ρk∗N(0,τId)=Law⁡(yk)\sigma_k = \rho_k * \mathcal{N}(0,\tau I_d) = \operatorname{Law}(y_k) from πτ\pi_\tau.

Proof. The position bounds follow from [6], Thms. 3 and 4. Applying the same Gaussian convolution kernel to ρk\rho_k and π\pi contracts both divergences by data-processing inequalities, giving the observation bounds. □\square

These bounds require neither global convexity nor τ<1/β\tau< 1/\beta for the ideal chain, and they furthermore imply geometric convergence in TV with factor (1+ατ)−k(1+\alpha\tau)^{-k}. With a step size τ\tau of order 1/β1/\beta, about O~(κ)\widetilde{O}(\kappa) iterations (up to a logarithmic factor in the initial divergence and the accuracy threshold) therefore suffice for the desired accuracy.

Sampling guarantees

We now state the main theorems of the complexity of the proposed algorithm, Alg. 1.

Theorem 3 (Gaussian-start sampling under LSI). Suppose π\pi satisfies α\alpha-LSI. For every fixed ν>0\nu> 0, there is a finite CνC_\nu such that the following holds. Let x0∈Rdx_0 \in\mathbb{R}^d be any point provided as an input to the algorithm, and set G0=∥∇V(x0)∥2/βG_0 = \lVert\nabla V(x_0)\rVert^2/\beta. For every 0<ε<1/40 < \varepsilon< 1/4, Alg. 1 returns a sample whose law π^\widehat{\pi} satisfies TV⁡(π^,π)≤ε\operatorname{TV}(\widehat{\pi},\pi) \le\varepsilon using at most

Cνκ(d+κ+ε−1+G0)ν(4)C_\nu\kappa(d+\kappa+\varepsilon^{-1}+G_0)^\nu \tag*{(4)}

gradient queries.

Theorem 4 (Finite-Rényi-start sampling under PI). Suppose π\pi satisfies α\alpha-PI. For every fixed ν>0\nu> 0, there is a finite CνC_\nu such that the following holds. Assume an initial sample xinit∼η0x_{\mathrm{init}} \sim\eta_0 can be generated using only gradient access to VV, with deterministic query cost at most QinitQ_{\mathrm{init}}, and a known B≥1B \ge1 satisfies D2(η0∥π)≤BD_2(\eta_0\mathbin\Vert\pi) \le B. For every 0<ε<1/40 < \varepsilon< 1/4, Alg. 1 returns a sample whose law π^\widehat{\pi} satisfies TV⁡(π^,π)≤ε\operatorname{TV}(\widehat{\pi},\pi) \le\varepsilon using at most

Qinit+Cν,κ[B+log⁡(8/ε)](d+κ+B+ε−1)ν(5)Q_{\mathrm{init}}+C_{\nu,\kappa}[B+\log(8/\varepsilon)](d+\kappa+B+\varepsilon^{-1})^\nu \tag*{(5)}

gradient queries.

Interpretation. Both theorems run Alg. 1 and differ only in its initialization. Under LSI, x0x_0 is an arbitrary input point; the cost of finding it is not counted, and its quality enters only through G0G_0, which vanishes at any stationary point, including a saddle point. Under PI, the initial sampler and the bound BB are inputs, and the cost QinitQ_{\mathrm{init}} of the initial sample is charged to the total. The prefactor κ\kappa reflects the roughly κ\kappa iterations needed by the exact proximal sampler (Prop. 2), and all other parameters enter through a power ν>0\nu> 0 that can be taken arbitrarily small, with the algorithm and CνC_\nu depending on ν\nu. Thus, for fixed κ\kappa, ε\varepsilon, and G0G_0 or BB, the number of gradient queries grows more slowly than any positive power of the dimension.

Implementation of the proximal sampler

The proximal sampler of § 2.1 needs an exact draw from the RGO qyτq_y^\tau at every step. Rather than implementing these draws directly, our implementation rests on two observations.

First, the Gaussian noise already present in the proximal sampler allows us to work with a smoothed conditional distribution. Given an observation yy, the next observation is y′=x′+τGy' = x' + \sqrt{\tau}G, where x′∼qyτx' \sim q_y^\tau and G∼N(0,Id)G \sim\mathcal{N}(0,I_d) are independent. Writing x′=y+τZx' = y+\sqrt{\tau}Z, we have y′=y+τ(Z+G)y'=y+\sqrt{\tau}(Z+G), where ZZ follows

Law⁡(Z)(v)∝e−∥v∥22−V(y+τv).\operatorname{Law}(Z)(v) \propto e^{-\frac{\lVert v\rVert^2}{2}-V(y+\sqrt{\tau}v)}.

Thus, updating the observation requires a sample of Z+GZ+G. The additional Gaussian noise smooths the distribution of ZZ. The construction of [14] combines this smoothing with high-order approximation to implement the noisy conditional draw using few gradient queries. This is central to obtaining an arbitrarily small dimension exponent.

Second, we observe that the same sampling construction can extend beyond strong log-concavity to targets satisfying LSI or PI. These weaker assumptions still provide enough control over the chain to establish convergence and bound the accumulated sampling errors. The two settings require different initialization conditions and analysis, which we make explicit below.

In the following, we first state the guarantee of NoisySample from [14] in § 3.1. We then describe how to rescale the target and append independent Gaussian coordinates (§ 3.2), and how to sample a position conditioned on the final noisy observation (§ 3.4). The complete procedure is given in Alg. 1, and Prop. 8 bounds its total approximation error. Throughout, hats denote approximate kernels and probability laws.

The noisy local sampling algorithm

For a perturbation F∈C2(Rn)F \in C^2(\mathbb{R}^n), center c∈Rnc \in\mathbb{R}^n, and scale 0<r≤10 < r \le1, define

ρc,rF(v)∝e−∥v∥2/2−F(c+rv).(6)\rho^F_{c,r}(v) \propto e^{-\lVert v\rVert^2/2-F(c+rv)}. \tag*{(6)}

With n=dn=d, F=FyF=F_y, c=0c=0, and r=1r=1, this is the law of ZZ above after the transformation of the RGO target qyτq_y^\tau. Given cc, rr, and access to ∇F\nabla F, the algorithm NoisySample approximates Z+GZ+G for independent Z∼ρc,rFZ \sim\rho^F_{c,r} and G∼N(0,In)G \sim\mathcal{N}(0,I_n) without exact sample of ZZ. Its construction is explained in App. B.1. The next result establishes the convergence guarantee of NoisySample and the required gradient query complexity.

Proposition 5 (Noisy local sampling guarantee). Fix a localization exponent γ∈(0,1)\gamma\in(0,1), an approximation order K≥2K \ge2, and a query-overhead exponent ω>0\omega> 0 such that

40(K+2)ω<1/4.(7)40(K+2)\omega< 1/4. \tag*{(7)}

There are a constant CC and a dimension threshold, both depending only on (γ,K,ω)(\gamma,K,\omega), and a bound An≤C(1+log⁡n)CA_n \le C(1+\log n)^C, with the following property. For every nn above the threshold, δ=n−γ\delta=n^{-\gamma}, Lip⁡(∇F)≤δ\operatorname{Lip}(\nabla F)\le\delta, c∈Rnc\in\mathbb{R}^n, and 0<r≤10<r\le1, the algorithm NoisySample(F,c,r)(F,c,r) uses at most Anδ−ωA_n\delta^{-\omega} gradient queries to FF and satisfies

TV⁡(Law⁡(NoisySample⁡(F,c,r)),ρc,rF∗N(0,In))≤AnδK(n+∥∇F(c)∥).(8)\operatorname{TV}\bigl(\operatorname{Law}(\operatorname{NoisySample}(F,c,r)),\rho^F_{c,r} * \mathcal{N}(0,I_n)\bigr) \le A_n\delta^K\left(\sqrt{n}+\lVert\nabla F(c)\rVert\right). \tag*{(8)}

The constants are uniform in F,c,rF,c,r.

This guarantee follows from [14 Thm. 2.1]. We suppress the fixed parameters (γ,K,ω)(\gamma,K,\omega) in the notation NoisySample(F,c,r)(F,c,r).

Normalization and Gaussian padding

We now construct the padded target described at the beginning of this section. Let a=x0a=x_0 under LSI and a=0a=0 under PI. For w=(z,ξ)∈Rd×Rn−dw=(z,\xi)\in\mathbb{R}^d\times\mathbb{R}^{n-d}, define the forward and output maps

Ta(x)=β(x−a),Ha(w)=a+z/β,(9)T_a(x)=\sqrt{\beta}(x-a), \qquad H_a(w)=a+z/\sqrt{\beta}, \tag*{(9)}

and the padded potential and target

V~(w)=V(a+z/β)+∥ξ∥2/2,Π=(Ta)#π⊗N(0,In−d)∝e−V~.(10)\widetilde{V}(w)=V(a+z/\sqrt{\beta})+\lVert\xi\rVert^2/2,\qquad\Pi=(T_a)_\#\pi\otimes\mathcal{N}(0,I_{n-d})\propto e^{-\widetilde{V}}. \tag*{(10)}

Then Ha#Π=πH_{a\#}\Pi=\pi, the potential V~\widetilde{V} is 1-smooth with LSI or PI constant 1/κ1/\kappa, and each gradient of V~\widetilde{V} costs one gradient of VV (Lem. 12). In these coordinates the step size becomes h=βτh=\beta\tau.

Proximal chain on the padded target. The two conditionals of (1), for Π\Pi and step size hh, are the kernels

Ah(y∣w)=(2πh)−n/2e−∥y−w∥2/(2h),Rh(w∣y)∝e−V~(w)−∥w−y∥2/(2h).A_h(y\mid w)=(2\pi h)^{-n/2}e^{-\lVert y-w\rVert^2/(2h)},\qquad R_h(w\mid y)\propto e^{-\widetilde{V}(w)-\lVert w-y\rVert^2/(2h)}.

For a law μ\mu, write μAh(y)=∫μ(w)Ah(y∣w) dw\mu A_h(y)=\int\mu(w)A_h(y\mid w)\,\mathrm{d}w, similarly for RhR_h, and compose kernels from left to right by convention. The observation chain y→w′→y′y\to w'\to y' then has kernel Ph=RhAhP_h=R_hA_h. With Πh:=ΠAh=Π∗N(0,hIn)\Pi_h:=\Pi A_h=\Pi*\mathcal{N}(0,hI_n), we have

ΠhPh=Πh,ΠhRh=Π,\Pi_hP_h=\Pi_h,\qquad\Pi_hR_h=\Pi,

i.e., the observation chain is stationary at Πh\Pi_h, and a position drawn given a stationary observation is an exact sample of Π\Pi, the step the decoder in § 3.4 approximates. Let Xj∼λjX_j\sim\lambda_j and Yj∼μjY_j\sim\mu_j be the positions and observations of the exact chain, so that μj=λjAh=μ0Phj\mu_j=\lambda_jA_h=\mu_0P_h^j.

Implementing one observation step

Let Fy(v)=V~(y+hv)F_y(v)=\widetilde{V}(y+\sqrt{h}v). By the argument at the beginning of this section, Ph(⋅∣y)P_h(\cdot\mid y) is the law of y+h(Z+G)y+\sqrt{h}(Z+G) for independent Z∼ρ0,1FZ\sim\rho^F_{0,1} and G∼N(0,In)G\sim\mathcal{N}(0,I_n). The implemented kernel P^h(⋅∣y)\widehat{P}_h(\cdot\mid y) replaces Z+GZ+G by the output of NoisySample:

Y^′=y+h NoisySample⁡(Fy,0,1).\widehat{Y}'=y+\sqrt{h}\,\operatorname{NoisySample}(F_y,0,1).

The gradient gy(v)=∇Fy(v)=h∇V~(y+hv)g_y(v)=\nabla F_y(v)=\sqrt{h}\nabla\widetilde{V}(y+\sqrt{h}v) is hh-Lipschitz, and in Alg. 1 we have h=δ/2≤δh=\delta/2\le\delta and nn above the threshold of Prop. 5. Since TV is unchanged by the common affine map u↦y+huu\mapsto y+\sqrt{h}u, (8) with c=0c=0, r=1r=1, and ∇Fy(0)=h∇V~(y)\nabla F_y(0)=\sqrt{h}\nabla\widetilde{V}(y) gives

TV⁡(P^h(⋅∣y),Ph(⋅∣y))≤AnδK(n+h∥∇V~(y)∥).(11)\operatorname{TV}(\widehat{P}_h(\cdot\mid y),P_h(\cdot\mid y))\le A_n\delta^K\left(\sqrt{n}+\sqrt{h}\lVert\nabla\widetilde{V}(y)\rVert\right). \tag*{(11)}

The final decoder

After NN steps the observation chain is close to Πh\Pi_h, not Π\Pi. A position sample requires one draw from Rh(⋅∣y)R_h(\cdot\mid y) at y=YNy=Y_N, that is, y+hZy+\sqrt{h}Z with Z∼ρ0,1FZ\sim\rho^F_{0,1}, but NoisySample only returns the noisy variable Z+GZ+G. The decoder closes this gap with the following identity.

Lemma 6 (Variance halving [14]). Let Z∼ρc,rFZ\sim\rho^F_{c,r} and G∼N(0,In)G\sim\mathcal{N}(0,I_n) be independent, and set U=Z+GU=Z+G. Then

(Z∣U=u)=lawu/2+Z′/2,where Z′∼ρc+ru/2,r/2F.(12)(Z\mid U=u)\mathrel{\overset{\mathrm{law}}{=}}u/2+Z'/\sqrt{2},\qquad\text{where }Z'\sim\rho^F_{c+ru/2,r/\sqrt{2}}. \tag*{(12)}

Equivalently, given one noisy observation uu, the variable c+rZc+rZ has the law of c′+r′Z′c'+r'Z' for the same family with center c′=c+ru/2c'=c+ru/2 and scale r′=r/2r'=r/\sqrt{2}. Repeating this with fresh calls to NoisySample shrinks the scale geometrically, until the remaining conditional is nearly Gaussian and can be sampled directly. For fixed yy, the decoder runs as follows.

  1. Set c0=0c_0=0, r0=1r_0=1, and J=⌈4log⁡2n⌉J=\lceil4\log_2 n\rceil. For j=0,…,J−1j=0,\ldots,J-1, draw Uj=NoisySample⁡(Fy,cj,rj)U_j=\operatorname{NoisySample}(F_y,c_j,r_j) and set cj+1=cj+rjUj/2c_{j+1}=c_j+r_jU_j/2 and rj+1=rj/2r_{j+1}=r_j/\sqrt{2}.

  1. Now rJ≤n−2r_J\le n^{-2}, so ρcJ,rJF\rho^F_{c_J,r_J} is close to a Gaussian with identity covariance centered at its mode, which is the fixed point of v↦−rJgy(cJ+rJv)v\mapsto-r_Jg_y(c_J+r_Jv). Approximate the mode by m=⌈log⁡n⌉m=\lceil\log n\rceil fixed-point steps,

v(0)=0,v(k+1)=−rJgy(cJ+rJv(k)).(13)v^{(0)}=0,\qquad v^{(k+1)}=-r_Jg_y(c_J+r_Jv^{(k)}). \tag*{(13)}
  1. Draw a fresh G∼N(0,In)G\sim\mathcal{N}(0,I_n) and return

Decode⁡(y)=y+h{cJ+rJ(v(m)+G)}.(14)\operatorname{Decode}(y)=y+\sqrt{h}\{c_J+r_J(v^{(m)}+G)\}. \tag*{(14)}

Write R^h\widehat{R}_h for the kernel y↦Law⁡(Decode⁡(y))y\mapsto\operatorname{Law}(\operatorname{Decode}(y)). With exact draws in place of NoisySample and of the final Gaussian approximation, Lem. 6 shows that Decode⁡(y)∼Rh(⋅∣y)\operatorname{Decode}(y)\sim R_h(\cdot\mid y) exactly. For an approximate implementation, we quantify the error and query complexity in the following proposition.

Proposition 7 (Decoder accuracy). For every smooth normalizable V~\widetilde{V} as in Lem. 13, the decoder satisfies

TV⁡(ΠhR^h,Π)≤CJAnδKn+Cδn−7/2.(15)\operatorname{TV}(\Pi_h\widehat{R}_h,\Pi)\le CJA_n\delta^K\sqrt{n}+C\delta n^{-7/2}. \tag*{(15)}

Its deterministic query cost is at most $JA_n\delta^{-\omega}+m.

Algorithm 1 Subpolynomial-Query Proximal sampling

Require: Normalized and padded potential V~\widetilde V on Rn\mathbb{R}^n; initial position X0X_0; step size hh; number of iterations NN; original dimension dd; shift a∈Rda \in\mathbb{R}^d and scale β>0\beta> 0.

Observation updates

  1. Draw G∼N(0,In)G \sim\mathcal{N}(0,I_n) and set Y0←X0+hGY_0 \gets X_0 + \sqrt{h}G.

  2. for j=0,…,N−1j = 0,\ldots,N-1 do

  3. Define FYj(v)=V~(Yj+hv)F_{Y_j}(v) = \widetilde V(Y_j + \sqrt{h}v).

  4. Uj←NoisySample⁡(FYj,0,1)U_j \gets\operatorname{NoisySample}(F_{Y_j},0,1).

  5. Yj+1←Yj+hUjY_{j+1} \gets Y_j + \sqrt{h}U_j.

  6. end for

Sample a position conditioned on YNY_N

  1. Define F(v)=V~(YN+hv)F(v) = \widetilde V(Y_N + \sqrt{h}v).

  2. Set c←0c \gets0, r←1r \gets1, and J←⌈4log⁡2n⌉J \gets\lceil4\log_2 n\rceil.

  3. for ℓ=1,…,J\ell= 1,\ldots,J do

  4. U←NoisySample⁡(F,c,r)U \gets\operatorname{NoisySample}(F,c,r).

  5. c←c+r2Uc \gets c + \frac{r}{2}U.

  6. r←r/2r \gets r/\sqrt{2}.

  7. end for

Approximate the remaining conditional by a Gaussian

  1. Set v←0v \gets0 and m←⌈log⁡n⌉m \gets\lceil\log n\rceil.

  2. for k=1,…,mk = 1,\ldots,m do

  3. v←−rh∇V~(YN+h(c+rv))v \gets-r\sqrt{h}\nabla\widetilde V\left(Y_N+\sqrt{h}(c+rv)\right). ▷ Approximate the conditional mode

  4. end for

  5. Draw a fresh G∼N(0,In)G \sim\mathcal{N}(0,I_n).

  6. W^←YN+h[c+r(v+G)]\widehat W \gets Y_N+\sqrt{h}\left[c+r(v+G)\right].

Return to the original coordinates

  1. x^←a+β−1/2(W^1,…,W^d)T\widehat x \gets a+\beta^{-1/2}(\widehat W_1,\ldots,\widehat W_d)^{\mathsf T}.

  2. return x^\widehat x.

The proof is in App. § 8. Its global input is the stationary score identity EΠ∥∇V~∥2≤n\mathbb{E}_{\Pi}\lVert\nabla\widetilde V\rVert^2 \le n. It does not require global convexity or proximity to a minimizer.

The outer algorithm Alg. 1 assembles the pieces of this section: padding, NN implemented observation steps, and the decoder. The dimension nn and the number of steps NN are explicit functions of the inputs; they involve a fixed threshold n∗(ν)n_*(\nu) depending only on ν\nu (App. § 13).

Query accounting. All random draws in Alg. 1 are independent, and nn, NN, and all loop lengths are determined by the inputs, so the number of gradient queries has a deterministic upper bound. The algorithm uses only gradients of VV. Taking n≥n∗(ν)n \ge n_*(\nu) also avoids a low-dimensional fallback in [14] that would require function values. Under PI, the initial sampler is likewise assumed to use only gradients.

Accumulation of approximation errors

Alg. 1 has three sources of error: the exact observation chain is run for only NN steps, each step of the observation chain uses NoisySample with error (11), and the decoder is approximate. The following proposition combines them. We remark that this result does not require functional inequalities; those will enter only through the two inputs εmix\varepsilon_{\mathrm{mix}} and MNM_N, which concern the exact chain.

Proposition 8 (From exact histories to implemented samples). Let μj=μ0Phj\mu_j=\mu_0P_h^j be the exact observation laws and μ^N=μ0P^hN\widehat{\mu}_N=\mu_0\widehat{P}_h^N the implemented one. Suppose (11) holds, TV⁡(μN,Πh)≤εmix\operatorname{TV}(\mu_N,\Pi_h)\leq\varepsilon_{\mathrm{mix}}, and TV⁡(ΠhR^h,Π)≤εdec\operatorname{TV}(\Pi_h\widehat{R}_h,\Pi)\leq\varepsilon_{\mathrm{dec}}. Define

MN=∑j=0N−1Eμj[n+h∥∇V~(Y)∥].(16)M_N=\sum_{j=0}^{N-1}\mathbb{E}_{\mu_j}\left[\sqrt{n}+\sqrt{h}\lVert\nabla\widetilde{V}(Y)\rVert\right]. \tag*{(16)}

Then

TV⁡(μ^NR^h,Π)≤εmix+AnδκMN+εdec.(17)\operatorname{TV}(\widehat{\mu}_N\widehat{R}_h,\Pi)\leq\varepsilon_{\mathrm{mix}}+A_n\delta^\kappa M_N+\varepsilon_{\mathrm{dec}}. \tag*{(17)}

Moreover, the number QpostQ_{\mathrm{post}} of gradient queries made after initialization satisfies the deterministic bound

Qpost≤(N+J)Anδ−ω+m.(18)Q_{\mathrm{post}}\leq(N+J)A_n\delta^{-\omega}+m. \tag*{(18)}

Proof. For 0≤k≤N0\leq k\leq N, let θk=μ0PhkP^hN−k\theta_k=\mu_0P_h^k\widehat{P}_h^{N-k} be the law after kk exact steps followed by N−kN-k implemented steps, so that θ0=μ^N\theta_0=\widehat{\mu}_N and θN=μN\theta_N=\mu_N. The laws θk\theta_k and θk+1\theta_{k+1} differ only in step k+1k+1, which starts from μk\mu_k, and TV does not increase under the common remaining kernel P^hN−k−1\widehat{P}_h^{N-k-1} by the data-processing inequality. By the triangle inequality, summing over kk and using (11), we have

TV⁡(μ^N,μN)≤∑k=0N−1EμkTV⁡(P^h(⋅∣Y),Ph(⋅∣Y))≤AnδκMN.(19)\operatorname{TV}(\widehat{\mu}_N,\mu_N)\leq\sum_{k=0}^{N-1}\mathbb{E}_{\mu_k}\operatorname{TV}(\widehat{P}_h(\cdot\mid Y),P_h(\cdot\mid Y))\leq A_n\delta^\kappa M_N. \tag*{(19)}

Applying the same decoder kernel R^h\widehat{R}_h to μ^N\widehat{\mu}_N, μN\mu_N, and Πh\Pi_h and using the triangle inequality,

TV⁡(μ^NR^h,Π)≤TV⁡(μ^N,μN)+TV⁡(μN,Πh)+TV⁡(ΠhR^h,Π),(20)\operatorname{TV}(\widehat{\mu}_N\widehat{R}_h,\Pi)\leq\operatorname{TV}(\widehat{\mu}_N,\mu_N)+\operatorname{TV}(\mu_N,\Pi_h)+\operatorname{TV}(\Pi_h\widehat{R}_h,\Pi), \tag*{(20)}

which gives (17). There are N+JN+J calls to NoisySample and mm fixed-point steps, which proves (18). □

In summary, Prop. 8 reduces the analysis of Alg. 1 to two properties of the exact chain: its mixing error εmix\varepsilon_{\mathrm{mix}} and the score budget MNM_N, which averages the gradient under the exact laws μj\mu_j rather than the implemented ones. In the next two sections, we bound both quantities under LSI (§ 4) and under PI (§ 5).

Sampling under LSI

Under LSI, both εmix\varepsilon_{\mathrm{mix}} and MNM_N follow from a bound on the KL divergence of the Gaussian initialization (Lem. 14). This divergence decays geometrically along the exact chain (Prop. 2), which controls εmix\varepsilon_{\mathrm{mix}}; since it never increases, Talagrand’s transport inequality also bounds the gradient moments in MNM_N (Lem. 15).

Proposition 9 (Exact-chain inputs under LSI). Let n≥max⁡{d,κ,G0,ε−1}n\geq\max\{d,\kappa,G_0,\varepsilon^{-1}\}, δ≤1/2\delta\leq1/2, and h=δ/2h=\delta/2, and let NN be as in (32). For the exact chain started from λ0=N(0,In)\lambda_0=\mathcal{N}(0,I_n),

εmix≤ε/4,MN≤CNκn,N≤Cκδ−1log⁡n.\varepsilon_{\mathrm{mix}}\leq\varepsilon/4,\qquad M_N\leq CN\kappa\sqrt{n},\qquad N\leq C\kappa\delta^{-1}\log n.

Substituting these bounds into Prop. 8, the implementation error is at most Cκ2AnδK−1nlog⁡nC\kappa^2 A_n\delta^{K-1}\sqrt{n}\log n and the algorithm makes at most CκAn(log⁡n)nγ(1+ω)C\kappa A_n(\log n)n^{\gamma(1+\omega)} queries. Choosing γ\gamma small makes the query exponent less than ν\nu, and choosing KK large relative to 1/γ1/\gamma then makes the implementation and decoder errors at most ε/4\varepsilon/4 each. We detail the explicit choices in App. § 13. Mapping the output back with HaH_a gives Thm. 3. Full proof can be found in App. § 9. Note that the initial divergence can be of order κn\kappa n, but it enters NN only logarithmically.

A non-log-concave example. The potential Vd(x)=∥x∥2/2+2cos⁡x1V_d(x)=\lVert x\rVert^2/2+2\cos x_1 is 3-smooth, has a negative Hessian eigenvalue at zero, and has LSI constant at least e−4\mathrm{e}^{-4} by bounded perturbation (App. § 8.§ 6). Since ∇Vd(0)=0\nabla V_d(0)=0, Thm. 3 applies with x0=0x_0=0 and G0=0G_0=0. As κ≤3e4\kappa\leq3\mathrm{e}^4 is a constant, it gives Oν((d+ε−1)ν)O_\nu((d+\varepsilon^{-1})^\nu) gradient queries for every fixed ν>0\nu>0. For fixed accuracy, this improves the dimension dependence of the O~(κd)=O~(d)\widetilde{O}(\kappa\sqrt{d})=\widetilde{O}(\sqrt{d}) bound in [FYC23] and the O~(κd1/5)=O~(d1/5)\widetilde{O}(\kappa d^{1/5})=\widetilde{O}(d^{1/5}) bound in [5], whose condition G0≤d/κG_0\leq d/\kappa holds here.

Sampling under PI and initialization

Proof outline

We outline the proof of Thm. 4. As under LSI, it supplies the two exact-chain inputs εmix\varepsilon_{\mathrm{mix}} and MNM_N of Prop. 8, but two ingredients change. First, PI does not bound the divergence of a simple Gaussian start, so the initial law η0\eta_0 and its bound D2(η0∥π)≤BD_2(\eta_0\Vert\pi)\leq B are inputs. Under PI the exact chain contracts χ2\chi^2 (Prop. 2), and D2≤BD_2\leq B allows χ2\chi^2 as large as eB−1\mathrm{e}^B-1, so the number of steps grows linearly in BB rather than logarithmically. Second, PI alone does not imply the quadratic transport inequality used in the LSI argument. It instead gives exponential concentration of Lipschitz functions (Lem. 16), which, by a change of measure, bounds the first gradient moment under any law within KL divergence BB of Π\Pi (Lem. 17). A first moment is all that MNM_N requires. The result is as follows:

Proposition 10 (Exact-chain inputs under PI). Let n≥max⁡{d,κ(B+1)2}n\geq\max\{d,\kappa(B+1)^2\}, δ≤1/2\delta\leq1/2, and h=δ/2h=\delta/2, let NN be as in (38), and set H=B+log⁡(8/ε)H=B+\log(8/\varepsilon). For the exact chain started from λ0=(T0)#η0⊗N(0,In−d)\lambda_0=(T_0)_\#\eta_0\otimes\mathcal{N}(0,I_{n-d}),

εmix≤ε/4,MN≤CNn,N≤CκHδ−1.\varepsilon_{\mathrm{mix}}\leq\varepsilon/4,\qquad M_N\leq CN\sqrt{n},\qquad N\leq C\kappa H\delta^{-1}.

Substituting these bounds into Prop. 8, the implementation error is at most CκHAnδK−1nC\kappa H A_n\delta^{K-1}\sqrt{n}, and the algorithm makes at most Qinit+CκHAnnγ(1+ω)Q_{\mathrm{init}}+C\kappa H A_n n^{\gamma(1+\omega)} queries. The parameters are then chosen as under LSI (App. § 13), and mapping the output back with H0H_0 gives Thm. 4; App. § 10 contains the full proof.

Initialization under PI

Thm. 4 takes the initial law η0\eta_0 and its bound D2(η0∥π)≤BD_2(\eta_0\Vert\pi)\leq B as inputs. What information about π\pi suffices to construct them? We now demonstrate that a global minimizer does, but an arbitrary stationary point does not.

A global minimizer suffices. If x⋆x_\star is a global minimizer of VV, the Gaussian q0=N(x⋆,(2β)−1Id)q_0=\mathcal{N}(x_\star,(2\beta)^{-1}I_d) satisfies D2(q0∥π)≤d2log⁡(2eκ)D_2(q_0\Vert\pi)\leq\frac{d}{2}\log(2\mathrm{e}\kappa) (see Prop. 19, which also covers approximate minimizers). Thm. 4 thus applies with Qinit=0Q_{\mathrm{init}}=0 and B=max⁡{1,d2log⁡(2eκ)}B=\max\{1,\frac{d}{2}\log(2\mathrm{e}\kappa)\}, which gives O(d1+ζ)O(d^{1+\zeta}) gradient queries for every fixed ζ>0\zeta>0 at fixed κ\kappa and ε\varepsilon. The extra factor of dd compared with LSI comes from BB, which enters the bound linearly.

A stationary point does not. Under LSI, any point x0x_0 works, and its quality is measured by G0G_0. Under PI, no such guarantee is possible, even when x0x_0 is a strict local minimum.

Theorem 11 (No uniform bound from an arbitrary stationary point). For fixed d≥2d \ge2, there is no finite query bound depending only on dd, β\beta, α\alpha, ε\varepsilon and ∥∇V(x0)∥\lVert\nabla V(x_0)\rVert that guarantees TV error ε=1/10\varepsilon= 1/10 for all smooth PI targets from an arbitrary supplied reference point. This holds for randomized adaptive exact value-and-gradient oracle algorithms with unrestricted computation between queries. The reference point can be a strict local minimum with Hessian Id\mathrm{Id}.

The proof uses a one-dimensional family of targets πR∝e−VR\pi_R \propto e^{-V_R}, sketched in Figure 2. Each πR\pi_R is a smoothed Laplace distribution centered at a remote point RR, plus a small bounded bump near the origin that creates a strict local minimum there. The bump changes the potential by a bounded amount, so all πR\pi_R are uniformly smooth and satisfy PI with a common constant. The key property is that, to the left of R−1R-1, the potential and its gradient are the same for every RR. An algorithm with a fixed query budget, started at the origin, therefore receives the same answers for every sufficiently large RR, so its queries and output stay in a bounded region that does not depend on RR. Taking RR large, the output misses the mass of πR\pi_R. Appending Gaussian coordinates extends the example to any d≥2d \ge2. App. § 12 gives the construction and the argument for randomized adaptive algorithms.

Schematic potential $V_R$ with a strict local minimum at $0$ and most of the mass of $\pi_R$ near $R$

Figure 2. Schematic potential behind Thm. 11, not to scale. Every VRV_R has a strict local minimum at the reference point 00, but most of the mass of πR∝e−VR\pi_R \propto e^{-V_R} lies near the remote location RR. Oracle answers in the shaded region x≤R−1x \le R-1 are the same for every RR, so an algorithm with a fixed query budget cannot locate the mass when RR is large.

This lower bound concerns the information in the initialization, not the algorithm: it holds even with access to function values, and it is consistent with Thm. 4, which charges the initialization explicitly.

Conclusions and Discussions

In this paper, we showed that for smooth targets satisfying LSI or PI, the proximal sampler can be implemented with a number of gradient queries that grows more slowly than any power of the dimension at fixed condition number and accuracy. The implementation runs the observation chain with the noisy local sampler of [14], controls the accumulated error by comparison with the exact chain, and removes the observation noise once at the end with a decoder. Under LSI, any supplied point can serve for initialization; under PI, the guarantee requires an initialization with a known bound on its Rényi divergence, and a lower bound shows that a stationary point alone does not suffice.

Several questions remain open. Our dependence on accuracy is a small power ε−ν\varepsilon^{-\nu}, and it is unknown whether an arbitrarily small dimension exponent can be combined with polylogarithmic dependence on ε−1\varepsilon^{-1}. Under PI, it would be useful to find initializations that need less information than a global minimizer, or that have a smaller divergence bound BB, which enters our bound linearly. Finally, intermediate functional inequalities such as the Latała–Oleszkiewicz inequalities [12] may fit the same framework, given suitable convergence and gradient estimates.

AI usage. ChatGPT and Codex assisted with mathematical exploration and proof development, manuscript drafting and revision, literature searches, and generation of code and computational checks. The authors are responsible for the mathematical claims, citations, and final presentation.

Related Work

Functional inequalities provide a way to analyze sampling beyond global log-concavity. [17] proved KL convergence guarantees for the unadjusted Langevin algorithm under LSI and smoothness, without convexity. [7] developed Rényi-divergence guarantees spanning PI and LSI. The proximal analysis in [6] separates global convergence from conditional implementation: exact proximal updates contract under the functional inequality, while the Gaussian quadratic makes each conditional strongly log-concave when the step size satisfies τ<1/β\tau< 1/\beta. Our analysis uses this separation to control implementation errors along exact histories.

Several approaches implement these conditionals. [10] developed rejection sampling for Gaussian-regularized Lipschitz potentials in private convex optimization. [11] treated weakly smooth, nonsmooth, and composite potentials through rejection-based proximal sampling. The approximate rejection sampler in [FYC23] improves dimension dependence through Gaussian concentration. A different approach combines underdamped Langevin warm starts with MALA [1], yielding high-accuracy conditional sampling and proximal guarantees beyond log-concavity. Our implementation instead uses the Gaussian-convolved output in [14] to approximate the observation transition directly; it recovers a position sample only through terminal decoding.

Acceleration offers another direction within the proximal framework. The Proximal Bouncy Particle Sampler [4] combines Gaussian augmentation with local particle dynamics and obtains O~(κd1/4)\widetilde{O}(\sqrt{\kappa}d^{1/4}) expected gradient queries, with polylogarithmic inverse-accuracy dependence, for smooth strongly log-concave targets from an O(1)O(1) order-two Rényi start. Its curvature and initialization assumptions differ from the nonconvex LSI and PI settings considered here.

Gaussian cloud correction for Picard HMC [5 Thm. 1.1] also handles smooth nonconvex LSI targets: it uses O~(κd1/5)\widetilde{O}(\kappa d^{1/5}) expected gradient queries with polylogarithmic inverse-accuracy dependence, assuming G0≤d/κG_0 \le d/\kappa. Our bounds permit any fixed positive dimension exponent, have deterministic query caps, and charge arbitrary G0G_0, but have weaker accuracy dependence. Neither guarantee uniformly dominates.

Auxiliary estimates and local sampling identities

How the noisy local sampler works

This appendix makes the mechanism behind Prop. 5 self-contained at the algorithmic level. The construction has three ingredients: a Gaussian probability flow that reduces sampling to conditional means, a second stationary flow that produces noisy estimates of those means, and a finite recursive implementation of both flows using gradient queries. The quantitative derivative estimates, recursive error analysis, and query bound are proved in [14 Sections 3–7] and are not repeated here.

Gaussian transport reduces sampling to conditional means. For independent Z∼ρc,rFZ \sim\rho^F_{c,r} and G∼N(0,In)G \sim\mathcal{N}(0,I_n), consider the interpolation Ys=sZ+1−s2GY_s = sZ + \sqrt{1-s^2}G, 0≤s<10 \le s < 1, and define

ms(y)=E[∇F(c+rZ)∣Ys=y].m_s(y) = \mathbb{E}[\nabla F(c+rZ) \mid Y_s = y].

Completing the square shows that this is another conditional mean of the same type, at a smaller scale:

ms(y)=EQ∼ρc+rsy,r1−s2F[∇F(c+rsy+r1−s2Q)].(21)m_s(y) = \mathbb{E}_{Q \sim\rho^F_{c+rsy,r\sqrt{1-s^2}}}\left[\nabla F\left(c+rsy+r\sqrt{1-s^2}Q\right)\right]. \tag*{(21)}

The deterministic probability flow

dY‾sds=−rms(Y‾s),Y‾0∼N(0,In),(22)\frac{\mathrm{d}\overline{Y}_s}{\mathrm{d}s}=-r m_s(\overline{Y}_s),\qquad\overline{Y}_0\sim\mathcal{N}(0,I_n), \tag*{(22)}

satisfies Law⁡(Y‾s)=Law⁡(Ys)\operatorname{Law}(\overline{Y}_s)=\operatorname{Law}(Y_s). This is equality of marginal laws: the interpolating process YsY_s does not itself solve the deterministic flow equation. In particular, stopping at s=1/2s=1/\sqrt{2} and rescaling by 2\sqrt{2} gives the law of Z+GZ+G. Gaussian conditioning makes the velocity smooth even though FF has only two derivatives. The analysis in [14] controls its higher derivatives with dimension dependence compatible with high-order approximation.

Conditional velocity. For the interpolation Ys=sZ+1−s2GY_s=sZ+\sqrt{1-s^2}G above, the conditional density gives

E[Z∣Ys=y]=sy−(1−s2)rms(y)\mathbb{E}[Z\mid Y_s=y]=sy-(1-s^2)r m_s(y)

by integration by parts. Since the derivative of the interpolation is (Z−sYs)/(1−s2)(Z-sY_s)/(1-s^2), its conditional expectation given Ys=yY_s=y is −rms(y)-r m_s(y). Differentiating the expectation of a compactly supported smooth test function therefore gives the continuity equation with that velocity. The globally Lipschitz flow in (22) has the same marginals; Proposition 3.3 establishes the required regularity under the stated C2C^2 assumption. Completing the conditional square proves (21).

Finite recursion replaces the unknown means by gradient queries. The flow is discretized by polynomial quadrature and a fixed number of Picard iterations. Here a Picard iteration substitutes the preceding trajectory approximation into the velocity and integrates; repeated substitution gives a finite expression involving conditional means at other centers. These means are not available as oracles. The construction therefore introduces a second algorithm targeting

Eρc,rF∇F(c+rZ)+σG,\mathbb{E}_{\rho^F_{c,r}}\nabla F(c+rZ)+\sigma G,

for a prescribed σ>0\sigma>0 and independent standard Gaussian GG, using a stationary flow with an auxiliary Gaussian momentum. Discretizing that flow produces further conditional-mean expressions. The sampling and mean algorithms call each other with prescribed error orders and perturbation scales until simple gradient-based approximations suffice. For example, a terminal sampling call has the form

G(0)−r∇F(c+rG(0))+3σaux2G(1)+σaux2G(2),G^{(0)}-r\nabla F(c+rG^{(0)})+\frac{\sqrt{3}\sigma_{\mathrm{aux}}}{2}G^{(1)}+\frac{\sigma_{\mathrm{aux}}}{2}G^{(2)},

where σaux>0\sigma_{\mathrm{aux}}>0 is the requested Gaussian noise standard deviation, distinct from the proximal step size hh and the initial density η0\eta_0. With independent standard Gaussian vectors, this approximates ρc,rF∗N(0,σaux2In)\rho^F_{c,r}*\mathcal{N}(0,\sigma_{\mathrm{aux}}^2 I_n) at a terminal accuracy level. Nonterminal calls use the higher-order flow formulas. The recursion depth is fixed before the quadrature mesh is selected. A sufficiently small mesh exponent, followed by a sufficiently high polynomial approximation order, makes the total query exponent as small as prescribed. Gaussian derivative estimates control the dimension cost of raising that order. The entire finite tree satisfies the deterministic query cap in Prop. 5, with constants depending on γ,K,ω\gamma,K,\omega.

Absorbing a noisy center. Suppose a seeded mean algorithm Q(c;g)Q(c;g), with MM vector-valued seed slots, has the deterministic translation identity

Q(c+Δ;g+v⊗Δ/r)=Q(c;g),Q(c+\Delta;g+v\otimes\Delta/r)=Q(c;g),

and preserves every physical gradient-query location in that identity. Here v∈RMv \in\mathbb{R}^{M} is fixed, L>0L > 0, and ∥v∥≤L\lVert v\rVert\le L. Put

b=r/(2L),P=(IM−vvT4L2)1/2.b = r/(2L), \qquad P = \left(I_M - \frac{vv^{\mathsf{T}}}{4L^2}\right)^{1/2}.

For independent standard Gaussian seed slots GG and a standard Gaussian vector ZZ, the call Q(c+bZ;(P⊗In)G)Q(c+bZ; (P \otimes I_n)G) has exactly the law of Q(c;G)Q(c;G). Indeed, the translation identity rewrites its seed array at center cc as PG−v⊗Z/(2L)PG-v\otimes Z/(2L), with the tensor identity suppressed. This array is centered Gaussian with slot covariance

PPT+vvT4L2=IM.PP^{\mathsf{T}}+\frac{vv^{\mathsf{T}}}{4L^2}=I_M.

Its slots are therefore independent standard Gaussians. The translation property is maintained recursively; the covariance identity itself is exact. Approximation errors in supplied centers are handled separately by fixed-seed stability, not by assuming the actual centers already have the ideal law.

Reserved smoothing noise. Let W2(μ,η)W_2(\mu,\eta) be the Wasserstein-2 distance, the infimum of (E∥X−X′∥2)1/2(\mathbb{E}\lVert X-X'\rVert^2)^{1/2} over couplings of X∼μX\sim\mu and X′∼ηX'\sim\eta. The noisy local sampler reserves independent Gaussian noise until all queries are complete. More precisely, the output has the form Upre+G/2U_{\mathrm{pre}}+G/2, where GG is independent of UpreU_{\mathrm{pre}} and all queries, and

W2(Law⁡(Upre),ρc,rF∗N(0,34In))≤AnδK(n+∥∇F(c)∥).(23)W_2\left(\operatorname{Law}(U_{\mathrm{pre}}),\rho^F_{c,r} * \mathcal{N}\left(0,\frac{3}{4}I_n\right)\right) \le A_n\delta^K\left(\sqrt{n}+\lVert\nabla F(c)\rVert\right). \tag*{(23)}

For any two laws with finite second moments and any σ>0\sigma>0, a coupling and the Gaussian shift bound give

TV⁡(μ∗N(0,σ2In),η∗N(0,σ2In))≤W2(μ,η)2σ.\operatorname{TV}\left(\mu* \mathcal{N}(0,\sigma^2 I_n),\eta* \mathcal{N}(0,\sigma^2 I_n)\right) \le\frac{W_2(\mu,\eta)}{2\sigma}.

Apply this with σ=1/2\sigma=1/2 and the pre-reserve laws in (23). Adding the independent reserve raises the Gaussian covariance from 3In/43I_n/4 to InI_n, yielding the TV guarantee.

Normalization and Gaussian padding

Lemma 12 (Coordinate and oracle accounting). Let TaT_a, HaH_a, V~\widetilde{V}, Π\Pi be as in (9) to (10), with n≥dn\ge d. Then ∇V~\nabla\widetilde{V} is 11-Lipschitz, and α\alpha-LSI (respectively PI) for π\pi implies 1/κ1/\kappa-LSI (respectively PI) for Π\Pi. For any law λ\lambda on Rd\mathbb{R}^d, set λ‾=(Ta)#λ⊗N(0,In−d)\overline{\lambda}=(T_a)_\#\lambda\otimes\mathcal{N}(0,I_{n-d}). Its KL and D2D_2 divergences from Π\Pi equal those of λ\lambda from π\pi. Moreover, (Ha)#Π=π(H_a)_\#\Pi=\pi and

TV⁡((Ha)#η,π)≤TV⁡(η,Π)\operatorname{TV}((H_a)_\#\eta,\pi)\le\operatorname{TV}(\eta,\Pi)

for every law η\eta on Rn\mathbb{R}^n. One gradient query to V~\widetilde{V} costs one gradient query to VV.

Proof. The normalized Hessian is β−1∇2V\beta^{-1}\nabla^2V, and the padding block is the identity. A change of variables in either functional inequality gives constant α/β=1/κ\alpha/\beta=1/\kappa for (Ta)#π(T_a)_\#\pi. Since α≤β\alpha\le\beta, tensorization with the standard Gaussian retains this constant. Under the invertible map TaT_a, density ratios are carried along unchanged. Adding the same independent Gaussian to both laws leaves their KL and D2D_2 integrals unchanged as well. Projection and inverse rescaling give (Ha)#Π=π(H_a)_\#\Pi=\pi, and data processing gives the TV bound. Finally, at w=(z,ξ)w=(z,\xi),

∇V~(w)=(β−1/2∇V(a+zβ),ξ),\nabla\widetilde{V}(w)=\left(\beta^{-1/2}\nabla V\left(a+\frac{z}{\sqrt{\beta}}\right),\xi\right),

so the gradient of V~\widetilde{V} follows from a single gradient query at a+z/βa+z/\sqrt{\beta}.

Stationary score control

Lemma 13 (Stationary score identity). If V~∈C2(Rn)\widetilde V \in C^2(\mathbb{R}^n) has 11-Lipschitz gradient and e−V~e^{-\widetilde V} is integrable, then

EΠ∥∇V~∥2=EΠΔV~≤n.(24)\mathbb{E}_{\Pi}\|\nabla\widetilde V\|^2=\mathbb{E}_{\Pi}\Delta\widetilde V\le n. \tag*{(24)}

Proof. Choose smooth compactly supported cutoffs χR\chi_R tending pointwise to one, with 0≤χR≤10\le\chi_R\le1 and ∥∇χR∥≤C/R\|\nabla\chi_R\|\le C/R. Integration by parts gives

IR:=EΠχR2∥∇V~∥2=EΠχR2ΔV~+2EΠχR∇χR⋅∇V~.I_R:=\mathbb{E}_{\Pi}\chi_R^2\|\nabla\widetilde V\|^2=\mathbb{E}_{\Pi}\chi_R^2\Delta\widetilde V+2\mathbb{E}_{\Pi}\chi_R\nabla\chi_R\cdot\nabla\widetilde V.

Since ∣ΔV~∣≤n|\Delta\widetilde V|\le n, Young’s inequality gives IR≤n+IR/2+C/R2I_R\le n+I_R/2+C/R^2. Fatou’s lemma proves square integrability of the score. The cross term then tends to zero by Cauchy–Schwarz. Dominated convergence for the bounded Hessian trace and the integrable squared score proves (24).

Local estimates used by the decoder

We also use the following two local consequences from [14 Lemma 2.2, Eq. (2.6), and Lemma 8.4]. For Lip⁡(∇F)≤δ\operatorname{Lip}(\nabla F)\le\delta and δr2≤1/2\delta r^2\le1/2, if Z∼ρc,rFZ\sim\rho^F_{c,r} and GG is an independent standard Gaussian, then

(E∥Z+G∥2)1/2≤C(n+r∥∇F(c)∥).(25)\left(\mathbb{E}\|Z+G\|^2\right)^{1/2}\le C(\sqrt{n}+r\|\nabla F(c)\|). \tag*{(25)}

If v∗v_* is the mode of ρc,rF\rho^F_{c,r}, then

TV⁡(ρc,rF,N(v∗,In))≤Cδr2n.(26)\operatorname{TV}(\rho^F_{c,r},\mathcal{N}(v_*,I_n))\le C\delta r^2\sqrt{n}. \tag*{(26)}

These are local strongly log-concave estimates and remain valid when the global target is non-log-concave.

Proof of the decoder guarantee

Proof. Let Y=X+hGY=X+\sqrt{h}G with X∼ΠX\sim\Pi and independent standard Gaussian GG. By Lem. 13 and Lipschitz continuity,

E∥∇V~(Y)∥2≤2n+2hn≤3n.\mathbb{E}\|\nabla\widetilde V(Y)\|^2\le2n+2hn\le3n.

Exact-history moments. Define a separate exact process by c0∗=0c_0^*=0, rj=2−j/2r_j=2^{-j/2}, and

Uj∗∣(Y,cj∗)∼ρcj∗,rjF⋆N(0,In),cj+1∗=cj∗+rjUj∗/2.U_j^*\mid(Y,c_j^*)\sim\rho^F_{c_j^*,r_j}\star\mathcal{N}(0,I_n),\qquad c_{j+1}^*=c_j^*+r_jU_j^*/2.

These are exact draws, not calls to NoisySample. Put bj=(E∥gY(cj∗)∥2)1/2b_j=(\mathbb{E}\|g_Y(c_j^*)\|^2)^{1/2}, where expectation includes Y∼ΠhY\sim\Pi_h and the exact history. Initially b0≤3hnb_0\le\sqrt{3hn}. Conditional on Y,cj∗Y,c_j^*, (25) applies directly:

(E[∥Uj∗∥2∣Y,cj∗])1/2≤C(n+rj∥gY(cj∗)∥).\left(\mathbb{E}[\|U_j^*\|^2\mid Y,c_j^*]\right)^{1/2}\le C(\sqrt{n}+r_j\|g_Y(c_j^*)\|).

The exact center update, Lip⁡(gY)≤δ\operatorname{Lip}(g_Y)\le\delta, and the L2L^2 triangle inequality imply

bj+1≤(1+Cδrj2)bj+Cδrjn.b_{j+1}\le(1+C\delta r_j^2)b_j+C\delta r_j\sqrt{n}.

Both ∑jrj\sum_j r_j and ∑jrj2\sum_j r_j^2 are bounded by absolute constants, so iteration gives bj≤Cnb_j\le C\sqrt{n} uniformly in jj.

Implementation error. Let Hj\mathcal{H}_j be the output law, averaged over Y∼ΠhY \sim\Pi_h, obtained with the first jj observations exact and the remaining J−jJ-j observations implemented by NoisySample. Every hybrid uses the same terminal Gaussian rule (13) to (14). Thus H0=ΠhR^h\mathcal{H}_0 = \Pi_h\widehat{R}_h, while HJ\mathcal{H}_J has an entirely exact observation history. Consecutive hybrids share the exact prefix (Y,cj⋆)(Y,c_j^\star). Conditional on this prefix, (8) bounds the differing observation; all subsequent computation is a common Markov kernel. Hence

TV⁡(Hj,Hj+1)≤AnδκE[n+∥gY(cj⋆)∥]≤CAnδκn.\operatorname{TV}(\mathcal{H}_j,\mathcal{H}_{j+1}) \le A_n\delta^\kappa\mathbb{E}\left[\sqrt{n}+\lVert g_Y(c_j^\star)\rVert\right] \le CA_n\delta^\kappa\sqrt{n}.

Summing yields

TV⁡(H0,HJ)≤CJAnδκn=:Edescent.(27)\operatorname{TV}(\mathcal{H}_0,\mathcal{H}_J) \le CJA_n\delta^\kappa\sqrt{n}=:E_{\mathrm{descent}}. \tag*{(27)}

No moment bound for the implemented histories is used.

Terminal approximation. Under the exact history, let v⋆∗v_\star^\ast be the mode of ρcJ⋆,rJFY\rho_{c_J^\star,r_J}^{F_Y} and let v(m),⋆v^{(m),\star} denote the fixed-point iterate at that center. The mode satisfies v⋆∗=−rJgY(cJ⋆+rJv⋆∗)v_\star^\ast=-r_Jg_Y(c_J^\star+r_Jv_\star^\ast). This map is ll-contractive, where l=δrJ2≤δn−4≤1/2l=\delta r_J^2\le\delta n^{-4}\le1/2, so

∥v(m),⋆−v⋆∗∥≤lm∥v⋆∗∥≤lmrJ∥gY(cJ⋆)∥1−l.\lVert v^{(m),\star}-v_\star^\ast\rVert\le l^m\lVert v_\star^\ast\rVert\le\frac{l^m r_J\lVert g_Y(c_J^\star)\rVert}{1-l}.

By (26), the Gaussian shift inequality, and bJ≤Cnb_J\le C\sqrt{n}, the averaged error in replacing this last conditional by the terminal Gaussian is at most

CδrJ2n+C(δrJ2)mrJn1−δrJ2≤Cδn−7/2=:Ebase.C\delta r_J^2\sqrt{n}+C\frac{(\delta r_J^2)^m r_J\sqrt{n}}{1-\delta r_J^2}\le C\delta n^{-7/2}=:E_{\mathrm{base}}.

The last inequality uses m≥1m\ge1 and rJ≤1r_J\le1. Conditional affine reconstruction contracts TV. With an exact terminal draw, repeated use of (12) reconstructs Rh(⋅∣Y)R_h(\cdot\mid Y), whose average under Πh\Pi_h is Π\Pi. Thus TV⁡(HJ,Π)≤Ebase\operatorname{TV}(\mathcal{H}_J,\Pi)\le E_{\mathrm{base}}, and the triangle inequality proves (15). The cost is JJ calls to NoisySample and mm gradient iterations.

The bounded-perturbation example

The LSI comparison used in § 4 follows from

Ent⁡μ(f2)=inf⁡a>0Eμ[f2log⁡(f2/a)−f2+a].\operatorname{Ent}_{\mu}(f^2)=\inf_{a>0}\mathbb{E}_{\mu}\left[f^2\log(f^2/a)-f^2+a\right].

The integrand is nonnegative. If m≤μ/Γ≤Mm\le\mu/\Gamma\le M and Γ\Gamma is standard Gaussian, its LSI gives Ent⁡μ(f2)≤MEnt⁡Γ(f2)≤2(M/m)Eμ∥∇f∥2\operatorname{Ent}_{\mu}(f^2)\le M\operatorname{Ent}_{\Gamma}(f^2)\le2(M/m)\mathbb{E}_{\mu}\lVert\nabla f\rVert^2. For the perturbation 2cos⁡x12\cos x_1, M/m≤e4M/m\le e^4. Its Hessian eigenvalues lie between −1-1 and 33, proving the example’s other claims. Direct Gaussian rejection uses acceptance e−2−2cos⁡x1e^{-2-2\cos x_1}; this additional structure explains why the example is not a complexity-separation witness.

Proofs for the LSI analysis

Throughout, Π\Pi has LSI constant 1/κ1/\kappa (Lem. 12), and since a=x0a=x_0, we have ∥∇Ve(0)∥2=G0\lVert\nabla V^e(0)\rVert^2=G_0.

Lemma 14 (Gaussian initial entropy). For λ0=N(0,In)\lambda_0=\mathcal{N}(0,I_n),

KL⁡(λ0∥Π)≤κ(G0+4n).(28)\operatorname{KL}(\lambda_0\Vert\Pi)\le\kappa(G_0+4n). \tag*{(28)}

Proof. For Z∼N(0,In)Z \sim\mathcal{N}(0,I_n), the relative score is ∇log⁡(λ0/Π)(Z)=∇V~(Z)−Z\nabla\log(\lambda_0/\Pi)(Z)=\nabla\widetilde{V}(Z)-Z. Since ∇V~\nabla\widetilde{V} is 1-Lipschitz,

∥∇V~(Z)−Z∥≤∥∇V~(0)∥+2∥Z∥,\lVert\nabla\widetilde{V}(Z)-Z\rVert\le\lVert\nabla\widetilde{V}(0)\rVert+2\lVert Z\rVert,

so Eλ0∥∇log⁡(λ0/Π)∥2≤2G0+8n\mathbb{E}_{\lambda_0}\lVert\nabla\log(\lambda_0/\Pi)\rVert^2\le2G_0+8n. Apply (LSI), with constant 1/κ1/\kappa, to f=(λ0/Π)1/2f=(\lambda_0/\Pi)^{1/2}. Then Ent⁡Π(f2)=KL⁡(λ0∥Π)\operatorname{Ent}_{\Pi}(f^2)=\operatorname{KL}(\lambda_0\mathbin\Vert\Pi) and 4EΠ∥∇f∥2=Eλ0∥∇log⁡(λ0/Π)∥24\mathbb{E}_{\Pi}\lVert\nabla f\rVert^2=\mathbb{E}_{\lambda_0}\lVert\nabla\log(\lambda_0/\Pi)\rVert^2, so

KL⁡(λ0∥Π)≤2κ4(2G0+8n)=κ(G0+4n).\operatorname{KL}(\lambda_0\mathbin\Vert\Pi)\le\frac{2\kappa}{4}(2G_0+8n)=\kappa(G_0+4n).

The last expectation is finite, so ff is an admissible test function; alternatively, apply (LSI) to truncations and pass to the limit. □

The same argument without padding (n=dn=d) shows that the initialization in the original coordinates satisfies KL⁡(N(x0,β−1Id)∥π)≤κ(G0+4d)\operatorname{KL}(\mathcal{N}(x_0,\beta^{-1}I_d)\mathbin\Vert\pi)\le\kappa(G_0+4d).

Lemma 15 (Gradient moments from relative entropy). If KL⁡(λ∥Π)≤b\operatorname{KL}(\lambda\mathbin\Vert\Pi)\le b, then

Eλ∥∇V~(X)∥2≤2n+4κb.(29)\mathbb{E}_{\lambda}\lVert\nabla\widetilde{V}(X)\rVert^2\le2n+4\kappa b. \tag*{(29)}

If X∼λX\sim\lambda, G∼N(0,In)G\sim\mathcal{N}(0,I_n) is independent, and Y=X+hGY=X+\sqrt{h}G with h≤1/2h\le1/2, then

E∥∇V~(Y)∥2≤5n+8κb.(30)\mathbb{E}\lVert\nabla\widetilde{V}(Y)\rVert^2\le5n+8\kappa b. \tag*{(30)}

Proof. Since Π\Pi satisfies LSI with constant 1/κ1/\kappa, it satisfies Talagrand’s transport inequality [15]

W22(λ,Π)≤2κKL⁡(λ∥Π).(31)W_2^2(\lambda,\Pi)\le2\kappa\operatorname{KL}(\lambda\mathbin\Vert\Pi). \tag*{(31)}

Couple X∼λX\sim\lambda to X∗∼ΠX_*\sim\Pi. Since ∇V~\nabla\widetilde{V} is 1-Lipschitz,

E∥∇V~(X)∥2≤2E∥∇V~(X∗)∥2+2E∥X−X∗∥2.\mathbb{E}\lVert\nabla\widetilde{V}(X)\rVert^2\le2\mathbb{E}\lVert\nabla\widetilde{V}(X_*)\rVert^2+2\mathbb{E}\lVert X-X_*\rVert^2.

Taking the infimum over couplings, the first term is at most 2n2n by Lem. 13, and the second is at most 2W22(λ,Π)≤4κb2W_2^2(\lambda,\Pi)\le4\kappa b by (31). For YY, the same argument gives

E∥∇V~(Y)∥2≤2E∥∇V~(X)∥2+2hE∥G∥2≤4n+8κb+2hn≤5n+8κb.\mathbb{E}\lVert\nabla\widetilde{V}(Y)\rVert^2\le2\mathbb{E}\lVert\nabla\widetilde{V}(X)\rVert^2+2h\mathbb{E}\lVert G\rVert^2\le4n+8\kappa b+2hn\le5n+8\kappa b.

□

Proof of Prop. 9. Set B0=5κnB_0=5\kappa n. Since G0≤nG_0\le n, Lem. 14 gives KL⁡(λ0∥Π)≤B0\operatorname{KL}(\lambda_0\mathbin\Vert\Pi)\le B_0. By Prop. 2, applied to Π\Pi with LSI constant 1/κ1/\kappa and step size hh,

KL⁡(λj∥Π)≤(1+h/κ)−2jB0for all j≥0.\operatorname{KL}(\lambda_j\mathbin\Vert\Pi)\le(1+h/\kappa)^{-2j}B_0\qquad\text{for all }j\ge0.

Choose

N=⌈log⁡(8B0/ε2)2log⁡(1+h/κ)⌉≤Cκδ−1log⁡n,(32)N=\left\lceil\frac{\log(8B_0/\varepsilon^2)}{2\log(1+h/\kappa)}\right\rceil\le C\kappa\delta^{-1}\log n, \tag*{(32)}

where the inequality uses log⁡(1+h/κ)≥h/(2κ)\log(1+h/\kappa)\ge h/(2\kappa) and κ,ε−1≤n\kappa,\varepsilon^{-1}\le n. Then KL⁡(λN∥Π)≤ε2/8\operatorname{KL}(\lambda_N\mathbin\Vert\Pi)\le\varepsilon^2/8. Since μN=λNAh\mu_N=\lambda_NA_h and Πh=ΠAh\Pi_h=\Pi A_h, data processing and Pinsker’s inequality give εmix=TV⁡(μN,Πh)≤TV⁡(λN,Π)≤ε/4\varepsilon_{\mathrm{mix}}=\operatorname{TV}(\mu_N,\Pi_h)\le\operatorname{TV}(\lambda_N,\Pi)\le\varepsilon/4. For the score budget, every λj\lambda_j has divergence at most B0B_0, and μj\mu_j is the law of X+hGX+\sqrt{h}G with X∼λjX\sim\lambda_j. Hence Lem. 15 gives Eμj∥∇V~(Y)∥2≤5n+40κ2n≤45κ2n\mathbb{E}_{\mu_j}\lVert\nabla\widetilde{V}(Y)\rVert^2\le5n+40\kappa^2n\le45\kappa^2n, and by Cauchy–Schwarz each summand of MNM_N is at most CκnC\kappa\sqrt{n}. Therefore

MN≤CNκn,AnδKMN≤Cκ2AnδK−1nlog⁡n.(33)M_N\le CN\kappa\sqrt{n},\qquad A_n^\delta K M_N\le C\kappa^2 A_n^\delta K^{-1}\sqrt{n}\log n. \tag*{(33)}

□

Proof of Thm. 3. By (18), δ−1=nγ\delta^{-1}=n^\gamma, and (32), the algorithm makes at most CκAn(log⁡n)nγ(1+ω)C\kappa A_n(\log n)n^{\gamma(1+\omega)} queries after computing G0G_0. With nn as in (46) and the parameter choices of App. § 13, the implementation error (33) and the decoder error (15) are each at most ε/4\varepsilon/4, so Props. 8 and 9 bound the padded output error by ε\varepsilon, and the query count is of the form (4). Finally, for the law π^\hat{\pi} returned by Alg. 1, Lem. 12 transfers the error back to the original target:

TV⁡(π^,π)=TV⁡(Ha#(μ^NR^h),Ha#Π)≤TV⁡(μ^NR^h,Π)≤ε.(34)\operatorname{TV}(\hat{\pi},\pi)=\operatorname{TV}(H_{a\#}(\hat{\mu}_N\hat{R}_h),H_{a\#}\Pi)\leq\operatorname{TV}(\hat{\mu}_N\hat{R}_h,\Pi)\leq\varepsilon. \tag*{(34)}

Proofs for the PI analysis

Throughout, Π\Pi has PI constant 1/κ1/\kappa (Lem. 12).

Lemma 16 (A PI exponential-moment bound). If Π\Pi satisfies 1/κ1/\kappa-PI and FF is integrable and 11-Lipschitz, then

log⁡EΠe(F−EΠF)/κ≤1.(35)\log\mathbb{E}_{\Pi}e^{(F-\mathbb{E}_{\Pi}F)/\sqrt{\kappa}}\leq1. \tag*{(35)}

Proof. For bounded FF, write M(s)=EesFM(s)=\mathbb{E}e^{sF}. Applying PI to esF/2e^{sF/2} gives

M(s)−M(s/2)2≤κs24M(s).M(s)-M(s/2)^2\leq\frac{\kappa s^2}{4}M(s).

Set s=κ−1/2s=\kappa^{-1/2} and iterate the corresponding logarithmic inequality at s,s/2,s/4,…s,s/2,s/4,\ldots. After subtracting the centered linear term,

log⁡M(s)−sEF≤∑j=0∞2j[−log⁡(1−14⋅4j)]≤12∑j=0∞2−j=1.\log M(s)-s\mathbb{E}F\leq\sum_{j=0}^{\infty}2^j\left[-\log\left(1-\frac{1}{4\cdot4^j}\right)\right]\leq\frac{1}{2}\sum_{j=0}^{\infty}2^{-j}=1.

The omitted limiting centered term is zero because FF is bounded. The second inequality uses −log⁡(1−u)≤2u-\log(1-u)\leq2u for u≤1/4u\leq1/4. Apply this result to Lipschitz truncations of FF. Their means converge by integrability, and Fatou’s lemma gives the claim. Weak-gradient approximation justifies the test functions when FF is only Lipschitz.

Lemma 17 (PI change of measure for the score). If KL⁡(λ∥Π)≤B\operatorname{KL}(\lambda\mathbin\Vert\Pi)\leq B, then

Eλ∥∇V~(X)∥≤n+κ(B+1).(36)\mathbb{E}_{\lambda}\lVert\nabla\widetilde{V}(X)\rVert\leq\sqrt{n}+\sqrt{\kappa(B+1)}. \tag*{(36)}

For X∼λX\sim\lambda and Y=X+hGY=X+\sqrt{h}G with independent G∼N(0,In),G\sim\mathcal{N}(0,I_n),

E∥∇V~(Y)∥≤(1+h)n+κ(B+1).(37)\mathbb{E}\lVert\nabla\widetilde{V}(Y)\rVert\leq(1+\sqrt{h})\sqrt{n}+\sqrt{\kappa(B+1)}. \tag*{(37)}

Proof. The function F=∥∇V~∥F=\lVert\nabla\widetilde{V}\rVert is 11-Lipschitz and EΠF≤n\mathbb{E}_{\Pi}F\leq\sqrt{n} by Lem. 13. The entropy variational inequality and Lem. 16, with s=κ−1/2s=\kappa^{-1/2}, give

sEλF≤KL⁡(λ∥Π)+log⁡EΠesF≤B+sEΠF+1.s\mathbb{E}_{\lambda}F\leq\operatorname{KL}(\lambda\mathbin\Vert\Pi)+\log\mathbb{E}_{\Pi}e^{sF}\leq B+s\mathbb{E}_{\Pi}F+1.

Use nonnegative truncations of FF first if its integrability under λ\lambda has not yet been established. This proves (36). The Gaussian observation adds at most hE∥G∥≤hn\sqrt{h}\mathbb{E}\lVert G\rVert\leq\sqrt{hn} by Lipschitz continuity.

Proof of Prop. 10. By Lem. 12, normalizing the initialization and appending independent Gaussian coordinates preserves its D2D_2 divergence, so χ2(λ0∥Π)≤eB−1\chi^2(\lambda_0\|\Pi) \le e^B-1 and KL⁡(λ0∥Π)≤B\operatorname{KL}(\lambda_0\|\Pi) \le B. By Prop. 2, applied to Π\Pi with PI constant 1/κ1/\kappa and step size hh, together with data processing under AhA_h,

χ2(μj∥Πh)≤(eB−1)(1+h/κ)−2j,KL⁡(λj∥Π)≤B.\chi^2(\mu_j\|\Pi_h) \le(e^B-1)(1+h/\kappa)^{-2j}, \qquad\operatorname{KL}(\lambda_j\|\Pi) \le B.

Choose

N=⌈B+2log⁡(2/ε)2log⁡(1+h/κ)⌉≤CκHδ−1.(38)N = \left\lceil\frac{B+2\log(2/\varepsilon)}{2\log(1+h/\kappa)} \right\rceil\le C_\kappa H\delta^{-1}. \tag*{(38)}

Then χ2(μN∥Πh)≤ε2/4\chi^2(\mu_N\|\Pi_h) \le\varepsilon^2/4, and 4TV⁡2≤χ24\operatorname{TV}^2 \le\chi^2 gives εmix≤ε/4\varepsilon_{\mathrm{mix}} \le\varepsilon/4. For the score budget, μj\mu_j is the law of X+hGX+\sqrt{h}G with X∼λjX\sim\lambda_j, and κ(B+1)≤n\sqrt{\kappa}(B+1)\le\sqrt{n}. Hence Lem. 17 gives Eμj∥∇V~(Y)∥≤3n\mathbb{E}_{\mu_j}\|\nabla\widetilde V(Y)\|\le3\sqrt{n}, and therefore

MN≤CNn,AnδκMN≤CκHAnδκ−1n.M_N \le CN\sqrt{n}, \qquad A_n\delta^\kappa M_N \le C_\kappa H A_n\delta^{\kappa-1}\sqrt{n}.

Proof of Thm. 4. The decoder bound is the same as under LSI. With nn as in (47) and the parameter choices of App. § 13, the implementation and decoder errors are each at most ε/4\varepsilon/4, so Props. 8 and 10 bound the padded output error by ε\varepsilon, and (48) gives a query count of the form (5). Applying (34) with a=0a=0 proves the original-space guarantee.

Constants and Gaussian initialization under PI

Functional-inequality constants and smoothness

Lemma 18. If ∇V\nabla V is β\beta-Lipschitz and π∝e−V\pi\propto e^{-V} satisfies α\alpha-PI, then α≤β\alpha\le\beta.

Proof. Fix a unit vector e∈Rde\in\mathbb{R}^d, let X∼πX\sim\pi, and write m=E⟨e,X⟩m=\mathbb{E}\langle e,X\rangle.

Since ∇e−V=−∇Ve−V\nabla e^{-V}=-\nabla V e^{-V}, every C1C^1 function g:Rd→Rg:\mathbb{R}^d\to\mathbb{R} such that gg and ∇g\nabla g grow at most linearly satisfies

E⟨e,∇g(X)⟩=E[g(X)⟨e,∇V(X)⟩],(39)\mathbb{E}\langle e,\nabla g(X)\rangle=\mathbb{E}[g(X)\langle e,\nabla V(X)\rangle], \tag*{(39)}

by applying the divergence theorem to the function ge−Veg e^{-V}e.

Taking g≡1g\equiv1 in (39) gives E⟨e,∇V(X)⟩=0\mathbb{E}\langle e,\nabla V(X)\rangle=0. Taking g(x)=⟨e,x⟩g(x)=\langle e,x\rangle gives E[⟨e,X⟩⟨e,∇V(X)⟩]=∥e∥2=1\mathbb{E}[\langle e,X\rangle\langle e,\nabla V(X)\rangle]=\lVert e\rVert^2=1; subtracting mE⟨e,∇V(X)⟩=0m\mathbb{E}\langle e,\nabla V(X)\rangle=0 yields

E[(⟨e,X⟩−m)⟨e,∇V(X)⟩]=1.\mathbb{E}[(\langle e,X\rangle-m)\langle e,\nabla V(X)\rangle]=1.

Taking g(x)=⟨e,∇V(x)⟩g(x)=\langle e,\nabla V(x)\rangle and using ∇2V⪯βId\nabla^2V\preceq\beta I_d gives

E[⟨e,∇V(X)⟩2]=E⟨e,∇2V(X)e⟩≤β.\mathbb{E}[\langle e,\nabla V(X)\rangle^2]=\mathbb{E}\langle e,\nabla^2V(X)e\rangle\le\beta.

By the Cauchy–Schwarz inequality,

1=(E[(⟨e,X⟩−m)⟨e,∇V(X)⟩])2≤Var⁡⟨e,X⟩E[⟨e,∇V(X)⟩2]≤βVar⁡⟨e,X⟩⟹Var⁡⟨e,X⟩≥1/β.1=\big(\mathbb{E}[(\langle e,X\rangle-m)\langle e,\nabla V(X)\rangle]\big)^2\le\operatorname{Var}\langle e,X\rangle\mathbb{E}[\langle e,\nabla V(X)\rangle^2]\le\beta\operatorname{Var}\langle e,X\rangle\Longrightarrow\operatorname{Var}\langle e,X\rangle\ge1/\beta.

On the other hand, applying (PI) to f(x)=⟨e,x⟩f(x)=\langle e,x\rangle gives Var⁡⟨e,X⟩≤1/α\operatorname{Var}\langle e,X\rangle\le1/\alpha. Combining the two bounds completes the proof.

Gaussian initialization near a global minimizer

Proposition 19 (Gaussian divergence near a global minimizer). Suppose π\pi satisfies α\alpha-PI and a global minimizer x∗x_\ast of VV exists. For a point x0x_0 and a known A0≥V(x0)−V(x∗)A_0 \ge V(x_0)-V(x_\ast), let

q0=N(x0,(2β)−1Id),G0=∥∇V(x0)∥2/β.q_0 = \mathcal{N}\left(x_0,(2\beta)^{-1}I_d\right), \qquad G_0 = \lVert\nabla V(x_0)\rVert^2/\beta.

Then

D2(q0∥π)≤D∞(q0∥π)≤A0+G0/2+d2log⁡(2eκ)≤2A0+d2log⁡(2eκ).(40)D_2(q_0\Vert\pi) \le D_\infty(q_0\Vert\pi) \le A_0 + G_0/2 + \frac{d}{2}\log(2e\kappa) \le2A_0 + \frac{d}{2}\log(2e\kappa). \tag*{(40)}

In particular, at x0=x∗x_0=x_\ast the first two terms vanish.

Proof. For this proof, write ZV=∫Rde−V(x) dxZ_V=\int_{\mathbb{R}^d}e^{-V(x)}\,\mathrm{d}x. First, PI implies Cov⁡πX⪯α−1Id\operatorname{Cov}_{\pi}X \preceq\alpha^{-1}I_d. One can justify finite second moments before applying PI to a coordinate as follows. Truncate a coordinate centered at a median to [−R,R][-R,R]. The truncation is 1-Lipschitz and retains zero as a median, so its variance is at most α−1\alpha^{-1} and the square of its mean is at most twice that variance. Fatou’s lemma gives a finite second moment about the median. Applying PI to truncations of arbitrary linear functionals and passing to the limit gives the covariance bound. Smoothness then gives Eπ∣V∣<∞\mathbb{E}_{\pi}|V|<\infty.

The Gaussian maximum-entropy bound, or nonnegativity of KL relative to a Gaussian with covariance α−1Id\alpha^{-1}I_d, implies

h(π)≤d2log⁡2πeα.h(\pi) \le\frac{d}{2}\log\frac{2\pi e}{\alpha}.

Since h(π)=log⁡ZV+EπVh(\pi)=\log Z_V+\mathbb{E}_{\pi}V and EπV≥V(x∗)\mathbb{E}_{\pi}V\ge V(x_\ast),

log⁡ZV+V(x∗)≤d2log⁡2πeα.(41)\log Z_V+V(x_\ast)\le\frac{d}{2}\log\frac{2\pi e}{\alpha}. \tag*{(41)}

For u=x−x0u=x-x_0, the smoothness upper bound for VV gives

log⁡q0(x)π(x)≤log⁡ZV+V(x0)+d2log⁡βπ+∇V(x0)⋅u−β2∥u∥2\log\frac{q_0(x)}{\pi(x)}\le\log Z_V+V(x_0)+\frac{d}{2}\log\frac{\beta}{\pi}+\nabla V(x_0)\cdot u-\frac{\beta}{2}\lVert u\rVert^2
≤A0+G02+d2log⁡(2eκ).\le A_0+\frac{G_0}{2}+\frac{d}{2}\log(2e\kappa).

Here D∞(q0∥π)=log⁡ess sup⁡(q0/π)D_\infty(q_0\Vert\pi)=\log\operatorname*{ess\,sup}(q_0/\pi). Taking the essential supremum proves the first upper bound. Finally, the descent lemma evaluated at x0−∇V(x0)/βx_0-\nabla V(x_0)/\beta gives G0/2≤V(x0)−V(x∗)≤A0G_0/2\le V(x_0)-V(x_\ast)\le A_0. □

The remote-mass construction

Define

U(t)={38+34t2−18t4,∣t∣≤1,∣t∣,∣t∣≥1,ϕ(x)=(x+x2/2)e−x2,U(t)= \begin{cases} \frac{3}{8}+\frac{3}{4}t^2-\frac{1}{8}t^4, & |t|\le1,\\ |t|, & |t|\ge1, \end{cases} \qquad \phi(x)=(x+x^2/2)e^{-x^2},

and, for R≥2R\ge2, set

VR(x)=U(x−R)−R+ϕ(x),πR(x)∝e−VR(x).(42)V_R(x)=U(x-R)-R+\phi(x), \qquad\pi_R(x)\propto e^{-V_R(x)}. \tag*{(42)}

Lemma 20 (Uniform geometry and identical local responses). The potentials VRV_R are normalizable, C2C^2, and 2020-smooth. They satisfy

VR(0)=0,VR′(0)=0,VR′′(0)=1.V_R(0)=0,\qquad V_R'(0)=0,\qquad V_R''(0)=1.

Their Gibbs laws have PI constant at least α0=(4e19/8)−1\alpha_0=(4e^{19/8})^{-1}, independently of RR. For A≤RA\le R,

πR((−∞,A])≤12e19/8eA−R.(43)\pi_R((-\infty,A])\le\frac{1}{2}e^{19/8}e^{A-R}. \tag*{(43)}

For every x≤R−1x\le R-1, the value-and-gradient oracle returns

VR(x)=−x+ϕ(x),VR′(x)=−1+ϕ′(x),(44)V_R(x)=-x+\phi(x),\qquad V_R'(x)=-1+\phi'(x), \tag*{(44)}

independently of RR.

Proof. The polynomial branch of UU matches ∣t∣|t| in value and in its first two derivatives at ±1\pm1. It satisfies 0≤U−∣⋅∣≤3/80\le U-|\cdot|\le3/8 and 0≤U′′≤3/20\le U''\le3/2. Also ϕ(0)=0\phi(0)=0, ϕ′(0)=ϕ′′(0)=1\phi'(0)=\phi''(0)=1, ∥ϕ∥∞<1\|\phi\|_\infty<1, and

ϕ′′(x)=(1−6x−5x2+4x3+2x4)e−x2.\phi''(x)=(1-6x-5x^2+4x^3+2x^4)e^{-x^2}.

Since sup⁡x∣x∣je−x2≤1\sup_x |x|^j e^{-x^2}\le1 for j=0,…,4j=0,\ldots,4, we have ∥ϕ′′∥∞≤18\|\phi''\|_\infty\le18. These facts prove the smoothness, normalizability, and origin claims.

The centered Laplace density ℓ(x)=e−∣x∣/2\ell(x)=e^{-|x|/2} has PI constant 1/41/4. Indeed, for g(0)=0g(0)=0, integration by parts on a half-line gives

∫0∞g(x)2e−x dx=2∫0∞g(x)g′(x)e−x dx≤2(∫0∞g(x)2e−x dx)1/2(∫0∞g′(x)2e−x dx)1/2.\int_0^\infty g(x)^2e^{-x}\,dx=2\int_0^\infty g(x)g'(x)e^{-x}\,dx\le2\left(\int_0^\infty g(x)^2e^{-x}\,dx\right)^{1/2}\left(\int_0^\infty g'(x)^2e^{-x}\,dx\right)^{1/2}.

Apply the resulting factor-four inequality to g=f−f(0)g=f-f(0) on both half-lines, and use Var⁡ℓf≤Eℓ(f−f(0))2\operatorname{Var}_{\ell}f\le\mathbb{E}_{\ell}(f-f(0))^2. Bounded smooth functions are justified by cutoff approximation.

Relative to the Laplace density translated by RR, the potential perturbation is

bR(x)=U(x−R)−∣x−R∣+ϕ(x),osc⁡bR≤19/8.b_R(x)=U(x-R)-|x-R|+\phi(x),\qquad\operatorname{osc}b_R\le19/8.

If a density ratio lies between mm and MM, comparison of the variance using its infimum over constants and comparison of the Dirichlet form worsen the PI constant by at most M/mM/m. Here M/m≤e19/8M/m\le e^{19/8}, giving PI constant α0\alpha_0. The same density comparison and the translated Laplace left tail give (43). When x≤R−1x\le R-1, U(x−R)=R−xU(x-R)=R-x, proving (44).

Proof of the lower bound

Proof. First work in dimension one. Suppose a total oracle algorithm has a uniform deterministic query cap qq and the asserted accuracy on the family in Lemma 20, with common supplied bounds β=20\beta=20, α=α0\alpha=\alpha_0, and reference point zero.

Run its decision rules against the common response function V∞(x)=−x+ϕ(x)V_\infty(x)=-x+\phi(x). This is a device for generating transcripts, not a normalizable target. Every finite transcript is consistent with some admissible VRV_R, by choosing RR beyond all query locations in that transcript. Thus the rules produce a finite next query or an output, and they cannot make a (q+1)(q+1)st query: such a finite prefix would also occur for an admissible target and violate the uniform cap. Totality on admissible inputs likewise rules out nontermination between queries along a realizable finite prefix.

For a random seed, the at most qq query locations and the final output are finitely many finite real random variables. Choose a deterministic AA such that, with probability at least 0.99, all are at most AA. For R>A+1R>A+1, couple the two runs with the same seed. On that event all oracle replies and the final output agree with the common-response run. The algorithm’s output under VRV_R therefore lies in (−∞,A](-\infty,A] with probability at least 0.99. Increase RR until (43) is at most 0.01. Its TV error is at least 0.98, a contradiction.

For fixed d≥2d\ge2, use

V~R(x)=VR(x1)+12∑i=2dxi2.\widetilde{V}_R(x)=V_R(x_1)+\frac{1}{2}\sum_{i=2}^{d}x_i^2.

Tensorization preserves the common PI lower bound, smoothness remains at most 20, and the Hessian at the origin is IdI_d. Apply the same transcript argument to the first coordinate of each query and output.

Parameter selection and deterministic query accounting

The local-sampler parameters are fixed before the target dimension and accuracy are supplied. A convenient explicit recipe is

γLSI=min⁡{1/8,ν/4},γPI=min⁡{1/8,ν/12},K=⌊2+4/γ⌋+1.\gamma_{\mathrm{LSI}}=\min\{1/8,\nu/4\},\qquad\gamma_{\mathrm{PI}}=\min\{1/8,\nu/12\},\qquad K=\lfloor2+4/\gamma\rfloor+1.

In either regime take ω\omega as in (45) below. A fixed integer threshold n∗(ν)n_*(\nu) dominates the threshold in Prop. 5, ensures n≥2n\ge2 and δ≤1/2\delta\le1/2, and absorbs the fixed-order logarithmic factors. Its size is not quantitatively bounded here. We verify below that the choices have strict margins for both error and cost.

LSI parameter bounds

Write Eouter=AnδKMNE_{\mathrm{outer}}=A_n\delta^{K}M_N, and let EdescentE_{\mathrm{descent}} and EbaseE_{\mathrm{base}} denote the two decoder contributions bounded in Appendix § 8.

Fix ν>0\nu>0. Choose 0<γ<1/40<\gamma<1/4 with 2γ<ν2\gamma<\nu, choose an integer K>2+4/γK>2+4/\gamma, and set, for example,

ω=11000(K+2).(45)\omega=\frac{1}{1000(K+2)}. \tag*{(45)}

The constraint in (7) holds, and γ(K−1)>4\gamma(K-1)>4, ω<1\omega<1, and γ(1+ω)<ν\gamma(1+\omega)<\nu. Using κ≤n\kappa\le n in (33),

Eouter≤CAn(log⁡n)n5/2−γ(K−1)=o(n−1).E_{\mathrm{outer}}\le CA_n(\log n)n^{5/2-\gamma(K-1)}=o(n^{-1}).

Also Edescent≤CAn(log⁡n)n1/2−γK=o(n−1)E_{\mathrm{descent}}\le CA_n(\log n)n^{1/2-\gamma K}=o(n^{-1}) and Ebase≤Cn−7/2−γ=o(n−1)E_{\mathrm{base}}\le Cn^{-7/2-\gamma}=o(n^{-1}). The polylogarithmic factors have constants depending only on the fixed local-sampler parameters. Hence a single threshold n∗(ν)n_*(\nu) makes each of these three errors at most 1/(4n)1/(4n) for all n≥n∗(ν)n\ge n_*(\nu). Now take

n=max⁡{d,n∗(ν),⌈κ⌉,⌈ε−1⌉,⌈G0⌉}.(46)n = \max\{d, n_*(\nu), \lceil\kappa\rceil, \lceil\varepsilon^{-1}\rceil, \lceil G_0\rceil\}. \tag*{(46)}

Then 1/n≤ε1/n \le\varepsilon, and Prop. 8 proves the accuracy claim. By (18) and (32),

Q≤1+Cκpolylog⁡(n)nγ(1+ω)≤Cνκnν.Q \le1 + C_\kappa\operatorname{polylog}(n)n^{\gamma(1+\omega)} \le C_\nu\kappa n^\nu.

The second inequality absorbs both the initial query and the logarithmic factor by increasing CνC_\nu, using κnν≥1\kappa n^\nu\ge1. The dimension choice satisfies n≤Cν(d+κ+ε−1+G0)n \le C_\nu(d+\kappa+\varepsilon^{-1}+G_0), proving (4) after projection and inverse rescaling. All loop counts depend only on known parameters after the first reference query. The query cap of NoisySample is uniform in all subsequently generated centers, so the resulting query bound is deterministic. □\square

PI parameter bounds

Fix ν>0\nu> 0, choose 0<γ<1/40 < \gamma< 1/4 with 6γ<ν6\gamma< \nu, choose K>2+4/γK > 2 + 4/\gamma, and choose ω\omega by (45). Let

n=max⁡{d,n∗(ν),⌈κ(B+1)2⌉,⌈ε−1⌉}.(47)n = \max\{d, n_*(\nu), \lceil\kappa(B+1)^2\rceil, \lceil\varepsilon^{-1}\rceil\}. \tag*{(47)}

where the threshold is enlarged below as needed. Then κ≤n\kappa\le n, B≤nB \le\sqrt{n}, and H≤CnH \le Cn. Thus

Eouter≤CAn5/2−γ(K−1)=o(n−1).E_{\mathrm{outer}} \le C A n^{5/2-\gamma(K-1)} = o(n^{-1}).

The decoder errors are the same as in the LSI proof and are also o(n−1)o(n^{-1}). A fixed threshold makes each at most 1/(4n)≤ε/41/(4n) \le\varepsilon/4, proving accuracy by Prop. 8.

By (18),

Q−Qinit≤CκHpolylog⁡(n)nγ(1+ω)≤CνκHnν/3.(48)Q-Q_{\mathrm{init}} \le C_\kappa H\operatorname{polylog}(n)n^{\gamma(1+\omega)} \le C_\nu\kappa Hn^{\nu/3}. \tag*{(48)}

since 3γ(1+ω)<6γ<ν3\gamma(1+\omega) < 6\gamma< \nu. Put T=d+κ+B+ε−1T=d+\kappa+B+\varepsilon^{-1}. Because κ(B+1)2≤4T3\kappa(B+1)^2 \le4T^3 and the other padding terms are also at most CνT3C_\nu T^3, we have n≤CνT3n \le C_\nu T^3. Substitution into (48) proves (5). As in the LSI case, every invocation is uniformly capped and every loop length is predetermined from supplied parameters. □\square

References

  1. [1][AC24] Jason M. Altschuler and Sinho Chewi. Faster high-accuracy log-concave sampling via algorithmic warm starts. J. ACM, 71(3), June 2024.
  2. [2][BGL14] Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and geometry of Markov diffusion operators. Grundlehren der mathematischen Wissenschaften. Springer Cham, 2014.DOI
  3. [3][CCBJ18] Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett, and Michael I. Jordan. Under-damped Langevin MCMC: A non-asymptotic analysis. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 300–323. PMLR, 06–09 Jul 2018.arxiv.org/abs/1707.03663
  4. [4][CCLZ26a] Fan Chen, Sinho Chewi, Jianfeng Lu, and Matthew S Zhang. Accelerated high-accuracy sampling from a warm start via the proximal bouncy particle sampler. arXiv preprint arXiv:2609.06905, 2026.arxiv.org/abs/2609.06905
  5. [5][CCLZ26b] Fan Chen, Sinho Chewi, Jianfeng Lu, and Matthew S Zhang. High-accuracy simulation of Picard HMC, part I: Gaussian cloud correction. arXiv preprint arXiv:2609.38710, 2026.arxiv.org/abs/2609.38710
  6. [6][CCSW22] Yongxin Chen, Sinho Chewi, Adil Salim, and Andre Wibisono. Improved analysis for a proximal algorithm for sampling. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 2984–3014. PMLR, 02–05 Jul 2022.arxiv.org/abs/2202.06386
  7. [7][CEL+22] Sinho Chewi, Murat A Erdogdu, Mufan Li, Ruoqi Shen, and Shunshi Zhang. Analysis of Langevin Monte Carlo from Poincaré to log-Sobolev. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1–2. PMLR, 02–05 Jul 2022.arxiv.org/abs/2112.12662
  8. [8][Che22] Sinho Chewi. Log-concave sampling. Book draft available at https://chewisinho.github.io, 2022.
  9. [10]Sivakanth Gopi, Yin Tat Lee, and Daogao Liu. Private convex optimization via exponential mechanism. In Proceedings of the Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1948–1989, 2022.arxiv.org/abs/2203.00263
  10. [11]Jiaming Liang and Yongxin Chen. A proximal algorithm for sampling. Transactions on Machine Learning Research, 2023.arxiv.org/abs/2202.13975
  11. [12]R. Latała and K. Oleszkiewicz. Between sobolev and poincaré, pages 147–168. Springer Berlin Heidelberg, Berlin, Heidelberg, 2000.DOI
  12. [13]Yin Tat Lee, Ruoqi Shen, and Kevin Tian. Structured logconcave sampling with a restricted Gaussian oracle. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 2993–3050. PMLR, 15–19 Aug 2021.arxiv.org/abs/2010.03106
  13. [14]OpenAI. Subpolynomial query complexity for well-conditioned log-concave sampling. OpenAI Math Release preprint OAI:Subpolynomial-query-complexity-for-well-conditioned-log-concave-sampling-September-26-2026, 2026.hub.valency.io/works/W_jgeneua4
  14. [15]F. Otto and C. Villani. Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality. Journal of Functional Analysis, 173(2):361–400, 2000.DOI
  15. [16]Ruoqi Shen and Yin Tat Lee. The randomized midpoint method for log-concave sampling. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.arxiv.org/abs/1909.05503
  16. [17]Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.arxiv.org/abs/1903.08568
  17. [18]Bo Yuan, Wei Guo, and Yongxin Chen. Reflected proximal dynamics for accelerated high-accuracy log-concave sampling. arXiv preprint arXiv:2610.16248, 2026.arxiv.org/abs/2610.16248

Paper details

vlnc:W_8g82mdg3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents