WorksMathematics
Subpolynomial-Query Proximal Sampling Beyond Log-Concavity
Abstract
We study the gradient query complexity of sampling from a density on , where 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 , there is a finite constant depending only on such that the algorithm returns a sample within total-variation distance using at most queries, where and 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 on 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 potentials with a known minimizer and , sampling to total-variation accuracy requires at most exact first-order queries for every fixed , 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 dimension dependence for rejection-based proximal sampling [FYC23] and, more recently, 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 , the conditional potential has Hessian bounded below by 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 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 , we obtain the following guarantees with a finite constant depending only on . 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 using
gradient queries for every fixed \kappa = \beta/\alpha$, where is the smoothness constant and is the LSI constant. The algorithm starts from at any supplied point , whose quality enters through .
Under PI and smoothness assumptions, suppose an initial sample from can be generated using at most gradient queries, with a known bound , . For every fixed , we obtain a sampler with total-variation error at most using at most
gradient queries (Thm. 4), where and 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.

Figure 1. Structure of Alg. 1. The padded target has dimension . After the observation updates and final conditional sampling, we discard the appended coordinates and undo the rescaling to obtain .
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 on with , where is possibly non-convex but has a -Lipschitz gradient, so that . The complexity of our algorithms is quantified through the number of gradient queries , and potential values are not required for the algorithms.
Notations and definitions. For a random variable , denotes its distribution, and for a measurable map , for . For probability densities and on , the total-variation distance is , the Kullback–Leibler (KL) divergence is , the divergence is , and the Rényi divergence of order two is . Pinsker’s inequality gives , and Jensen’s inequality gives . We write for a positive constant whose value may change from line to line. It never depends on , , , , or the initialization; when it depends on the fixed parameters of NoisySample (Prop. 5), we mention it explicitly.
The proximal sampler
The proximal sampler [13, 6] augments with an auxiliary variable under the joint density , where is the step size. Its -marginal is , and its conditional distributions are
An exact draw from is called a restricted Gaussian oracle (RGO) draw. The proximal sampler is the Gibbs chain that draws and then . It preserves for every , so the position chain has stationary law , and the observation chain has stationary law . Since , every is strongly log-concave when , even if 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 for . We say that satisfies an -logarithmic Sobolev inequality (LSI) or an -Poincaré inequality (PI) if, respectively, the following inequalities hold for all smooth :
(LSI)
(PI)
Note that -strongly log-concave targets satisfy -LSI, and -LSI implies -PI [2].
Unlike strong log-concavity, both inequalities are stable under bounded perturbations of [2], so they allow saddle points and multiple local minima (see the example at the end of § 4). A larger means the distribution is better concentrated and typically implies faster mixing, and plays the role of a condition number as in the strongly log-concave case. Valid constants always satisfy (Lem. 18), so .
Proposition 2 (Convergence of the ideal proximal sampler). Fix and run (1) with exact conditional draws. Let and assume the relevant initial divergence below is finite. For every integer ,
The same respective upper bounds hold for the divergences of the observation law from .
Proof. The position bounds follow from [6], Thms. 3 and 4. Applying the same Gaussian convolution kernel to and contracts both divergences by data-processing inequalities, giving the observation bounds.
These bounds require neither global convexity nor for the ideal chain, and they furthermore imply geometric convergence in TV with factor . With a step size of order , about 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 satisfies -LSI. For every fixed , there is a finite such that the following holds. Let be any point provided as an input to the algorithm, and set . For every , Alg. 1 returns a sample whose law satisfies using at most
gradient queries.
Theorem 4 (Finite-Rényi-start sampling under PI). Suppose satisfies -PI. For every fixed , there is a finite such that the following holds. Assume an initial sample can be generated using only gradient access to , with deterministic query cost at most , and a known satisfies . For every , Alg. 1 returns a sample whose law satisfies using at most
gradient queries.
Interpretation. Both theorems run Alg. 1 and differ only in its initialization. Under LSI, is an arbitrary input point; the cost of finding it is not counted, and its quality enters only through , which vanishes at any stationary point, including a saddle point. Under PI, the initial sampler and the bound are inputs, and the cost of the initial sample is charged to the total. The prefactor reflects the roughly iterations needed by the exact proximal sampler (Prop. 2), and all other parameters enter through a power that can be taken arbitrarily small, with the algorithm and depending on . Thus, for fixed , , and or , 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 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 , the next observation is , where and are independent. Writing , we have , where follows
Thus, updating the observation requires a sample of . The additional Gaussian noise smooths the distribution of . 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 , center , and scale , define
With , , , and , this is the law of above after the transformation of the RGO target . Given , , and access to , the algorithm NoisySample approximates for independent and without exact sample of . 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 , an approximation order , and a query-overhead exponent such that
There are a constant and a dimension threshold, both depending only on , and a bound , with the following property. For every above the threshold, , , , and , the algorithm NoisySample uses at most gradient queries to and satisfies
The constants are uniform in .
This guarantee follows from [14 Thm. 2.1]. We suppress the fixed parameters in the notation NoisySample.
Normalization and Gaussian padding
We now construct the padded target described at the beginning of this section. Let under LSI and under PI. For , define the forward and output maps
and the padded potential and target
Then , the potential is 1-smooth with LSI or PI constant , and each gradient of costs one gradient of (Lem. 12). In these coordinates the step size becomes .
Proximal chain on the padded target. The two conditionals of (1), for and step size , are the kernels
For a law , write , similarly for , and compose kernels from left to right by convention. The observation chain then has kernel . With , we have
i.e., the observation chain is stationary at , and a position drawn given a stationary observation is an exact sample of , the step the decoder in § 3.4 approximates. Let and be the positions and observations of the exact chain, so that .
Implementing one observation step
Let . By the argument at the beginning of this section, is the law of for independent and . The implemented kernel replaces by the output of NoisySample:
The gradient is -Lipschitz, and in Alg. 1 we have and above the threshold of Prop. 5. Since TV is unchanged by the common affine map , (8) with , , and gives
The final decoder
After steps the observation chain is close to , not . A position sample requires one draw from at , that is, with , but NoisySample only returns the noisy variable . The decoder closes this gap with the following identity.
Lemma 6 (Variance halving [14]). Let and be independent, and set . Then
Equivalently, given one noisy observation , the variable has the law of for the same family with center and scale . 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 , the decoder runs as follows.
Set , , and . For , draw and set and .
Now , so is close to a Gaussian with identity covariance centered at its mode, which is the fixed point of . Approximate the mode by fixed-point steps,
Draw a fresh and return
Write for the kernel . With exact draws in place of NoisySample and of the final Gaussian approximation, Lem. 6 shows that exactly. For an approximate implementation, we quantify the error and query complexity in the following proposition.
Proposition 7 (Decoder accuracy). For every smooth normalizable as in Lem. 13, the decoder satisfies
Its deterministic query cost is at most $JA_n\delta^{-\omega}+m.
Algorithm 1 Subpolynomial-Query Proximal sampling
Require: Normalized and padded potential on ; initial position ; step size ; number of iterations ; original dimension ; shift and scale .
Observation updates
Draw and set .
for do
Define .
.
.
end for
Sample a position conditioned on
Define .
Set , , and .
for do
.
.
.
end for
Approximate the remaining conditional by a Gaussian
Set and .
for do
. ▷ Approximate the conditional mode
end for
Draw a fresh .
.
Return to the original coordinates
.
return .
The proof is in App. § 8. Its global input is the stationary score identity . It does not require global convexity or proximity to a minimizer.
The outer algorithm Alg. 1 assembles the pieces of this section: padding, implemented observation steps, and the decoder. The dimension and the number of steps are explicit functions of the inputs; they involve a fixed threshold depending only on (App. § 13).
Query accounting. All random draws in Alg. 1 are independent, and , , 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 . Taking 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 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 and , which concern the exact chain.
Proposition 8 (From exact histories to implemented samples). Let be the exact observation laws and the implemented one. Suppose (11) holds, , and . Define
Then
Moreover, the number of gradient queries made after initialization satisfies the deterministic bound
Proof. For , let be the law after exact steps followed by implemented steps, so that and . The laws and differ only in step , which starts from , and TV does not increase under the common remaining kernel by the data-processing inequality. By the triangle inequality, summing over and using (11), we have
Applying the same decoder kernel to , , and and using the triangle inequality,
which gives (17). There are calls to NoisySample and 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 and the score budget , which averages the gradient under the exact laws 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 and 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 ; since it never increases, Talagrand’s transport inequality also bounds the gradient moments in (Lem. 15).
Proposition 9 (Exact-chain inputs under LSI). Let , , and , and let be as in (32). For the exact chain started from ,
Substituting these bounds into Prop. 8, the implementation error is at most and the algorithm makes at most queries. Choosing small makes the query exponent less than , and choosing large relative to then makes the implementation and decoder errors at most each. We detail the explicit choices in App. § 13. Mapping the output back with gives Thm. 3. Full proof can be found in App. § 9. Note that the initial divergence can be of order , but it enters only logarithmically.
A non-log-concave example. The potential is 3-smooth, has a negative Hessian eigenvalue at zero, and has LSI constant at least by bounded perturbation (App. § 8.§ 6). Since , Thm. 3 applies with and . As is a constant, it gives gradient queries for every fixed . For fixed accuracy, this improves the dimension dependence of the bound in [FYC23] and the bound in [5], whose condition 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 and of Prop. 8, but two ingredients change. First, PI does not bound the divergence of a simple Gaussian start, so the initial law and its bound are inputs. Under PI the exact chain contracts (Prop. 2), and allows as large as , so the number of steps grows linearly in 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 of (Lem. 17). A first moment is all that requires. The result is as follows:
Proposition 10 (Exact-chain inputs under PI). Let , , and , let be as in (38), and set . For the exact chain started from ,
Substituting these bounds into Prop. 8, the implementation error is at most , and the algorithm makes at most queries. The parameters are then chosen as under LSI (App. § 13), and mapping the output back with gives Thm. 4; App. § 10 contains the full proof.
Initialization under PI
Thm. 4 takes the initial law and its bound as inputs. What information about suffices to construct them? We now demonstrate that a global minimizer does, but an arbitrary stationary point does not.
A global minimizer suffices. If is a global minimizer of , the Gaussian satisfies (see Prop. 19, which also covers approximate minimizers). Thm. 4 thus applies with and , which gives gradient queries for every fixed at fixed and . The extra factor of compared with LSI comes from , which enters the bound linearly.
A stationary point does not. Under LSI, any point works, and its quality is measured by . Under PI, no such guarantee is possible, even when is a strict local minimum.
Theorem 11 (No uniform bound from an arbitrary stationary point). For fixed , there is no finite query bound depending only on , , , and that guarantees TV error 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 .
The proof uses a one-dimensional family of targets , sketched in Figure 2. Each is a smoothed Laplace distribution centered at a remote point , 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 are uniformly smooth and satisfy PI with a common constant. The key property is that, to the left of , the potential and its gradient are the same for every . An algorithm with a fixed query budget, started at the origin, therefore receives the same answers for every sufficiently large , so its queries and output stay in a bounded region that does not depend on . Taking large, the output misses the mass of . Appending Gaussian coordinates extends the example to any . App. § 12 gives the construction and the argument for randomized adaptive algorithms.

Figure 2. Schematic potential behind Thm. 11, not to scale. Every has a strict local minimum at the reference point , but most of the mass of lies near the remote location . Oracle answers in the shaded region are the same for every , so an algorithm with a fixed query budget cannot locate the mass when 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 , and it is unknown whether an arbitrarily small dimension exponent can be combined with polylogarithmic dependence on . Under PI, it would be useful to find initializations that need less information than a global minimizer, or that have a smaller divergence bound , 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 . 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 expected gradient queries, with polylogarithmic inverse-accuracy dependence, for smooth strongly log-concave targets from an 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 expected gradient queries with polylogarithmic inverse-accuracy dependence, assuming . Our bounds permit any fixed positive dimension exponent, have deterministic query caps, and charge arbitrary , 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 and , consider the interpolation , , and define
Completing the square shows that this is another conditional mean of the same type, at a smaller scale:
The deterministic probability flow
satisfies . This is equality of marginal laws: the interpolating process does not itself solve the deterministic flow equation. In particular, stopping at and rescaling by gives the law of . Gaussian conditioning makes the velocity smooth even though 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 above, the conditional density gives
by integration by parts. Since the derivative of the interpolation is , its conditional expectation given is . 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 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
for a prescribed and independent standard Gaussian , 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
where is the requested Gaussian noise standard deviation, distinct from the proximal step size and the initial density . With independent standard Gaussian vectors, this approximates 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 .
Absorbing a noisy center. Suppose a seeded mean algorithm , with vector-valued seed slots, has the deterministic translation identity
and preserves every physical gradient-query location in that identity. Here is fixed, , and . Put
For independent standard Gaussian seed slots and a standard Gaussian vector , the call has exactly the law of . Indeed, the translation identity rewrites its seed array at center as , with the tensor identity suppressed. This array is centered Gaussian with slot covariance
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 be the Wasserstein-2 distance, the infimum of over couplings of and . The noisy local sampler reserves independent Gaussian noise until all queries are complete. More precisely, the output has the form , where is independent of and all queries, and
For any two laws with finite second moments and any , a coupling and the Gaussian shift bound give
Apply this with and the pre-reserve laws in (23). Adding the independent reserve raises the Gaussian covariance from to , yielding the TV guarantee.
Normalization and Gaussian padding
Lemma 12 (Coordinate and oracle accounting). Let , , , be as in (9) to (10), with . Then is -Lipschitz, and -LSI (respectively PI) for implies -LSI (respectively PI) for . For any law on , set . Its KL and divergences from equal those of from . Moreover, and
for every law on . One gradient query to costs one gradient query to .
Proof. The normalized Hessian is , and the padding block is the identity. A change of variables in either functional inequality gives constant for . Since , tensorization with the standard Gaussian retains this constant. Under the invertible map , density ratios are carried along unchanged. Adding the same independent Gaussian to both laws leaves their KL and integrals unchanged as well. Projection and inverse rescaling give , and data processing gives the TV bound. Finally, at ,
so the gradient of follows from a single gradient query at .
Stationary score control
Lemma 13 (Stationary score identity). If has -Lipschitz gradient and is integrable, then
Proof. Choose smooth compactly supported cutoffs tending pointwise to one, with and . Integration by parts gives
Since , Young’s inequality gives . 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 and , if and is an independent standard Gaussian, then
If is the mode of , then
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 with and independent standard Gaussian . By Lem. 13 and Lipschitz continuity,
Exact-history moments. Define a separate exact process by , , and
These are exact draws, not calls to NoisySample. Put , where expectation includes and the exact history. Initially . Conditional on , (25) applies directly:
The exact center update, , and the triangle inequality imply
Both and are bounded by absolute constants, so iteration gives uniformly in .
Implementation error. Let be the output law, averaged over , obtained with the first observations exact and the remaining observations implemented by NoisySample. Every hybrid uses the same terminal Gaussian rule (13) to (14). Thus , while has an entirely exact observation history. Consecutive hybrids share the exact prefix . Conditional on this prefix, (8) bounds the differing observation; all subsequent computation is a common Markov kernel. Hence
Summing yields
No moment bound for the implemented histories is used.
Terminal approximation. Under the exact history, let be the mode of and let denote the fixed-point iterate at that center. The mode satisfies . This map is -contractive, where , so
By (26), the Gaussian shift inequality, and , the averaged error in replacing this last conditional by the terminal Gaussian is at most
The last inequality uses and . Conditional affine reconstruction contracts TV. With an exact terminal draw, repeated use of (12) reconstructs , whose average under is . Thus , and the triangle inequality proves (15). The cost is calls to NoisySample and gradient iterations.
The bounded-perturbation example
The LSI comparison used in § 4 follows from
The integrand is nonnegative. If and is standard Gaussian, its LSI gives . For the perturbation , . Its Hessian eigenvalues lie between and , proving the example’s other claims. Direct Gaussian rejection uses acceptance ; this additional structure explains why the example is not a complexity-separation witness.
Proofs for the LSI analysis
Throughout, has LSI constant (Lem. 12), and since , we have .
Lemma 14 (Gaussian initial entropy). For ,
Proof. For , the relative score is . Since is 1-Lipschitz,
so . Apply (LSI), with constant , to . Then and , so
The last expectation is finite, so is an admissible test function; alternatively, apply (LSI) to truncations and pass to the limit. □
The same argument without padding () shows that the initialization in the original coordinates satisfies .
Lemma 15 (Gradient moments from relative entropy). If , then
If , is independent, and with , then
Proof. Since satisfies LSI with constant , it satisfies Talagrand’s transport inequality [15]
Couple to . Since is 1-Lipschitz,
Taking the infimum over couplings, the first term is at most by Lem. 13, and the second is at most by (31). For , the same argument gives
□
Proof of Prop. 9. Set . Since , Lem. 14 gives . By Prop. 2, applied to with LSI constant and step size ,
Choose
where the inequality uses and . Then . Since and , data processing and Pinsker’s inequality give . For the score budget, every has divergence at most , and is the law of with . Hence Lem. 15 gives , and by Cauchy–Schwarz each summand of is at most . Therefore
□
Proof of Thm. 3. By (18), , and (32), the algorithm makes at most queries after computing . With as in (46) and the parameter choices of App. § 13, the implementation error (33) and the decoder error (15) are each at most , so Props. 8 and 9 bound the padded output error by , and the query count is of the form (4). Finally, for the law returned by Alg. 1, Lem. 12 transfers the error back to the original target:
Proofs for the PI analysis
Throughout, has PI constant (Lem. 12).
Lemma 16 (A PI exponential-moment bound). If satisfies -PI and is integrable and -Lipschitz, then
Proof. For bounded , write . Applying PI to gives
Set and iterate the corresponding logarithmic inequality at . After subtracting the centered linear term,
The omitted limiting centered term is zero because is bounded. The second inequality uses for . Apply this result to Lipschitz truncations of . Their means converge by integrability, and Fatou’s lemma gives the claim. Weak-gradient approximation justifies the test functions when is only Lipschitz.
Lemma 17 (PI change of measure for the score). If , then
For and with independent
Proof. The function is -Lipschitz and by Lem. 13. The entropy variational inequality and Lem. 16, with , give
Use nonnegative truncations of first if its integrability under has not yet been established. This proves (36). The Gaussian observation adds at most by Lipschitz continuity.
Proof of Prop. 10. By Lem. 12, normalizing the initialization and appending independent Gaussian coordinates preserves its divergence, so and . By Prop. 2, applied to with PI constant and step size , together with data processing under ,
Choose
Then , and gives . For the score budget, is the law of with , and . Hence Lem. 17 gives , and therefore
Proof of Thm. 4. The decoder bound is the same as under LSI. With as in (47) and the parameter choices of App. § 13, the implementation and decoder errors are each at most , so Props. 8 and 10 bound the padded output error by , and (48) gives a query count of the form (5). Applying (34) with proves the original-space guarantee.
Constants and Gaussian initialization under PI
Functional-inequality constants and smoothness
Lemma 18. If is -Lipschitz and satisfies -PI, then .
Proof. Fix a unit vector , let , and write .
Since , every function such that and grow at most linearly satisfies
by applying the divergence theorem to the function .
Taking in (39) gives . Taking gives ; subtracting yields
Taking and using gives
By the Cauchy–Schwarz inequality,
On the other hand, applying (PI) to gives . Combining the two bounds completes the proof.
Gaussian initialization near a global minimizer
Proposition 19 (Gaussian divergence near a global minimizer). Suppose satisfies -PI and a global minimizer of exists. For a point and a known , let
Then
In particular, at the first two terms vanish.
Proof. For this proof, write . First, PI implies . One can justify finite second moments before applying PI to a coordinate as follows. Truncate a coordinate centered at a median to . The truncation is 1-Lipschitz and retains zero as a median, so its variance is at most 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 .
The Gaussian maximum-entropy bound, or nonnegativity of KL relative to a Gaussian with covariance , implies
Since and ,
For , the smoothness upper bound for gives
Here . Taking the essential supremum proves the first upper bound. Finally, the descent lemma evaluated at gives . □
The remote-mass construction
Define
and, for , set
Lemma 20 (Uniform geometry and identical local responses). The potentials are normalizable, , and -smooth. They satisfy
Their Gibbs laws have PI constant at least , independently of . For ,
For every , the value-and-gradient oracle returns
independently of .
Proof. The polynomial branch of matches in value and in its first two derivatives at . It satisfies and . Also , , , and
Since for , we have . These facts prove the smoothness, normalizability, and origin claims.
The centered Laplace density has PI constant . Indeed, for , integration by parts on a half-line gives
Apply the resulting factor-four inequality to on both half-lines, and use . Bounded smooth functions are justified by cutoff approximation.
Relative to the Laplace density translated by , the potential perturbation is
If a density ratio lies between and , comparison of the variance using its infimum over constants and comparison of the Dirichlet form worsen the PI constant by at most . Here , giving PI constant . The same density comparison and the translated Laplace left tail give (43). When , , proving (44).
Proof of the lower bound
Proof. First work in dimension one. Suppose a total oracle algorithm has a uniform deterministic query cap and the asserted accuracy on the family in Lemma 20, with common supplied bounds , , and reference point zero.
Run its decision rules against the common response function . This is a device for generating transcripts, not a normalizable target. Every finite transcript is consistent with some admissible , by choosing beyond all query locations in that transcript. Thus the rules produce a finite next query or an output, and they cannot make a 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 query locations and the final output are finitely many finite real random variables. Choose a deterministic such that, with probability at least 0.99, all are at most . For , 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 therefore lies in with probability at least 0.99. Increase until (43) is at most 0.01. Its TV error is at least 0.98, a contradiction.
For fixed , use
Tensorization preserves the common PI lower bound, smoothness remains at most 20, and the Hessian at the origin is . 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
In either regime take as in (45) below. A fixed integer threshold dominates the threshold in Prop. 5, ensures and , 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 , and let and denote the two decoder contributions bounded in Appendix § 8.
Fix . Choose with , choose an integer , and set, for example,
The constraint in (7) holds, and , , and . Using in (33),
Also and . The polylogarithmic factors have constants depending only on the fixed local-sampler parameters. Hence a single threshold makes each of these three errors at most for all . Now take
Then , and Prop. 8 proves the accuracy claim. By (18) and (32),
The second inequality absorbs both the initial query and the logarithmic factor by increasing , using . The dimension choice satisfies , 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.
PI parameter bounds
Fix , choose with , choose , and choose by (45). Let
where the threshold is enlarged below as needed. Then , , and . Thus
The decoder errors are the same as in the LSI proof and are also . A fixed threshold makes each at most , proving accuracy by Prop. 8.
By (18),
since . Put . Because and the other padding terms are also at most , we have . Substitution into (48) proves (5). As in the LSI case, every invocation is uniformly capped and every loop length is predetermined from supplied parameters.
References
- [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][BGL14] Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and geometry of Markov diffusion operators. Grundlehren der mathematischen Wissenschaften. Springer Cham, 2014.DOI
- [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][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][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][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][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][Che22] Sinho Chewi. Log-concave sampling. Book draft available at https://chewisinho.github.io, 2022.
- [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
- [11]Jiaming Liang and Yongxin Chen. A proximal algorithm for sampling. Transactions on Machine Learning Research, 2023.arxiv.org/abs/2202.13975
- [12]R. Latała and K. Oleszkiewicz. Between sobolev and poincaré, pages 147–168. Springer Berlin Heidelberg, Berlin, Heidelberg, 2000.DOI
- [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
- [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
- [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
- [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
- [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
- [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