betaFeedback

WorksMathematics

Subpolynomial query complexity for well-conditioned log-concave sampling

Abstract

For every fixed ε>0\varepsilon>0, we give a sampling algorithm using at most CεdεC_\varepsilon d^\varepsilon exact first-order queries on every execution for C2C^2 potentials on Rd\mathbb R ^d with a known minimizer and Hessian between IdI_d and 2Id2I_d. The output has total-variation distance at most 1/101/10 from the target Gibbs law. Computation between queries is unrestricted. We also prove an Ω(log⁡d)\Omega(\log d) query lower bound for arbitrary randomized adaptive algorithms, determining the optimal dimension exponent to be zero.

Introduction

How many evaluations of a potential and its gradient are needed to sample its Gibbs distribution? Even when the potential is uniformly strongly convex and smooth, familiar discretizations incur an error that grows with dimension. The question is particularly sharp when conditioning and accuracy are held fixed: is a positive power of the dimension intrinsically necessary, or is it a feature of the sampling algorithms used?

We answer this question in the exact first-order oracle model with unrestricted real computation between queries. The optimal dimension exponent is zero. The construction uses approximation orders that can depend on the desired exponent and is aimed at oracle complexity rather than practical running time.

Model and result

For d≥2d \ge2, let Vd\mathcal{V}_d consist of the functions V∈C2(Rd)V \in C^2(\mathbb{R}^d) satisfying

V(0)=0,∇V(0)=0,Id⪯∇2V(x)⪯2Idfor every x∈Rd.(1.1)V(0) = 0,\qquad\nabla V(0) = 0,\qquad I_d \preceq\nabla^2 V(x) \preceq2I_d\quad\text{for every }x \in\mathbb{R}^d.\tag{1.1}

The target law is

πV(dx)=ZV−1e−V(x) dx,ZV=∫Rde−V(x) dx.\pi_V(dx) = Z_V^{-1}e^{-V(x)}\,dx,\qquad Z_V = \int_{\mathbb{R}^d} e^{-V(x)}\,dx.

An exact first-order query at xx returns (V(x),∇V(x))(V(x), \nabla V(x)). Queries may be adaptive. Random real variables may be generated, and computation between queries is unrestricted. An algorithm may depend on dd, but its only information about VV is through the oracle responses. All algorithms are measurable.

Write ∥μ−η∥TV=sup⁡B∣μ(B)−η(B)∣\|\mu-\eta\|_{\mathrm{TV}} = \sup_B |\mu(B)-\eta(B)|. Let Q(d)Q(d) be the smallest integer qq for which an algorithm makes at most qq queries on every execution and returns XX satisfying ∥L(X)−πV∥TV≤1/10\|\mathcal{L}(X)-\pi_V\|_{\mathrm{TV}} \le1/10 for every V∈VdV \in\mathcal{V}_d. Thus the budget is not merely an expectation. Define the optimal dimension exponent by

γ∗=inf⁡{γ≥0:Q(d)≤dγ+o(1)}=lim sup⁡d→∞log⁡Q(d)log⁡d.\gamma_* = \inf\{\gamma\ge0 : Q(d) \le d^{\gamma+o(1)}\} = \limsup_{d \to\infty} \frac{\log Q(d)}{\log d}.

Theorem 1.1. In the oracle model above, for every ε>0\varepsilon> 0 there is Cε<∞C_\varepsilon< \infty such that

Q(d)≤Cεdε(d≥2).Q(d) \le C_\varepsilon d^\varepsilon\qquad(d \ge2).

There are also absolute constants c>0c > 0 and d0d_0 such that

Q(d)≥clog⁡d(d≥d0).Q(d) \ge c \log d \qquad(d \ge d_0).

The lower bound applies to arbitrary randomized adaptive first-order algorithms. In particular, γ∗=0\gamma_* = 0.

The upper assertion is proved in Theorem 8.5 and the lower assertion in Theorem 9.1. Together they determine the exponent but not the finer growth rate of Q(d)Q(d). In particular, the upper bound does not assert a polylogarithmic query count. The constants and the algorithmic approximation orders may depend on ε\varepsilon. No arithmetic or bit-complexity bound is imposed or deduced.

Historical context

Sampling by discretizing Langevin or Hamiltonian dynamics turns functional inequalities and smoothness into algorithmic bounds, but it also introduces a dimension-dependent discretization problem. Nonasymptotic analyses of the unadjusted Langevin algorithm were developed by Dalalyan [15] and Durmus and Moulines [16]; Cheng et al. [12] analyzed the underdamped method under strong convexity and smoothness. Randomized midpoint discretization further improved the quadratic-Wasserstein guarantees [22]. Wasserstein and total-variation guarantees must be distinguished in comparing these results. The shifted-composition analysis of Altschuler et al. [3], Theorem 5.6 gives a relative-entropy guarantee that yields a O~(d1/3)\widetilde{O}(d^{1/3}) query bound at fixed conditioning and total-variation accuracy. Another gradient-only route, based on rejection sampling on diffusion path space, was developed by Chen et al. [10], Theorem 3.2(ii); its stated query-tail bound also gives O~(d1/3)\widetilde{O}(d^{1/3}) in this fixed-parameter setting.

High-order integration and polynomial collocation already reduce the dimensional dependence of Hamiltonian Monte Carlo under stronger regularity or structural assumptions [18, 21]. In particular, their high-order results use assumptions beyond the two-sided Hessian bounds in (1.1). The obstacle here is to obtain high-order accuracy under those bounds while implementing every conditional mean with finitely many first-order queries.

More recently, Chen et al. [9], Theorem 7.1(i) obtain a O~(d1/6)\widetilde{O}(d^{1/6}) expected-gradient-query bound at fixed relative-entropy accuracy and fixed conditioning. Their theorem applies with the supplied minimizer in our model, and Pinsker’s inequality gives the same dimension exponent at fixed total-variation accuracy. The expected budget can also be capped at a constant multiple of its uniform bound, using a fixed fallback on overflow, without changing that exponent.1 Their separate high-accuracy total-variation result combines this construction with the proximal bouncy-particle sampler [6] and has a d1/4d^{1/4} term, while its dependence on inverse accuracy is polylogarithmic [9], Theorem 1.3. A subsequent preprint of September 30, 2026 by Chen et al. [7], Theorem 1.1 improves the high-accuracy dimension dependence to O~(d1/5)\widetilde O(d^{1/5}) expected gradient queries at fixed conditioning, while retaining polylogarithmic dependence on inverse total-variation accuracy. Its Gaussian-cloud representation propagates unevaluated Picard iterates using likelihood corrections.

The smoothed Picard work is also a close methodological precedent: it develops Gaussian smoothing of C2C^2 potentials, conditional cumulant estimates for derivatives of the smoothed potential, and high-order Picard approximation, including arbitrary Picard depth when exact smoothed gradients are available. Here we prove the all-split tensor estimates needed by our construction and implement recursively nested noisy conditional means with finitely many queries to the original gradient. This finite implementation, together with the subsequent removal of the auxiliary noise, gives every fixed positive query exponent in Theorem 1.1.

The Gaussian conditional-sampling framework used below was developed by Lee et al. [19]; see also the functional-inequality analysis of Chen et al. [11]. Its main operation adds a Gaussian quadratic to the potential and samples the resulting restricted conditional law. We retain that framework and give the contraction argument used here, while implementing its conditional operation by the recursive construction above.

For lower bounds, Chewi et al. [13] developed a systematic first-order query-complexity treatment of log-concave sampling. Their Gaussian lower bounds use rotational invariance to reduce arbitrary adaptive algorithms to block-Krylov information. Their results already give logarithmic dimension dependence for well-conditioned Gaussian sampling at a suitable fixed total-variation accuracy. Our lower-bound proof follows that strategy, with an explicit spectrum in [1,2][1,2] and a separating statistic. We give the full argument for total-variation threshold 1/101/10, including unrestricted randomized outputs.

Proof strategy and principal ingredients

The auxiliary problem comes from conditioning a target sample after a small Gaussian perturbation. Fix h>0h > 0. If X∼πVX \sim\pi_V and GG is an independent standard Gaussian, the conditional density of XX given X+hG=yX+\sqrt{h}G=y is proportional to

exp⁡(−V(x′)−∣x′−y∣22h).\exp\left(-V(x')-\frac{\lvert x'-y\rvert^2}{2h}\right).

Writing x′=y+hzx'=y+\sqrt{h}z gives the potential ∣z∣2/2+Fy(z)\lvert z\rvert^2/2+F_y(z), where Fy(z)=V(y+hz)F_y(z)=V(y+\sqrt{h}z) and Lip⁡(∇Fy)≤2h\operatorname{Lip}(\nabla F_y)\le2h. Thus a small hh makes the perturbation weak, using one original gradient query for each evaluation of ∇Fy\nabla F_y. We first implement this conditional operation with an added Gaussian, then remove that noise by further conditioning.

To make the conditional operation reusable, we work with a C2C^2 perturbation F:Rd→RF:\mathbb{R}^d\to\mathbb{R}, a center x∈Rdx\in\mathbb{R}^d, a scale 0<r≤10<r\le1, and the near-quadratic law

ν(dz)∝e−∣z∣2/2−F(x+rz) dz.\nu(dz)\propto e^{-\lvert z\rvert^2/2-F(x+rz)}\,dz.

where the gradient of FF has small Lipschitz constant. We construct two procedures: a sample from ν\nu with an added Gaussian, and the mean Eν∇F(x+rZ)\mathbb{E}_{\nu}\nabla F(x+rZ) with an added Gaussian. The noise is not merely an error allowance. It is used to make recursive evaluation possible.

Gaussian transport. For independent Z∼νZ\sim\nu and standard Gaussian NN, consider Yρ=ρZ+1−ρ2NY_\rho=\rho Z+\sqrt{1-\rho^2}N. The velocity of its marginal-law transport is a conditional gradient mean, hence another instance of the same auxiliary mean problem. This conditional-velocity construction belongs to the probability-flow and stochastic-interpolant viewpoint [2, 23].

Dimension-controlled high derivatives. High-order approximation is useful only if each further derivative does not introduce another power of the dimension. Derivatives of a Gaussian conditional mean form tensors with many coordinate slots. We bound each tensor as a matrix under every division of those slots into two nonempty groups. These bounds let us estimate the contractions arising along the flow by matrix composition. Repeated integration by parts then incurs only polylogarithmic dimension losses, followed by one d\sqrt{d} cost at the final vector output. The first step builds on classical Appell polynomials and higher-order Poincaré estimates [1, 4, 17]; we prove the all-split cumulant and subsequent divergence estimates needed here. All high derivatives come from Gaussian conditioning; the original potential still needs only the C2C^2 regularity in (1.1).

Stationary centering. To produce a noisy mean, we next couple one of the smoothed marginal laws above to a Gaussian momentum law while preserving their product. Its invariance uses a skew-matrix drift, as in Ma et al. [20], Section 2.1. Our transport-derived matrix makes the momentum displacement convert a path integral of gradient means into a Gaussian centered at the desired mean. The derivative estimates control high-order quadrature of both the probability transport and this stationary flow.

Noisy recursive evaluation. Fixed-depth polynomial and Picard computations represent the transports and centering flow as finite expressions in exact conditional means. The difficulty is to implement nested mean evaluations without knowing their exact centers. Our recursive procedure has a pathwise translation property: shifting a center can be compensated by a specified shift of its Gaussian random seeds, leaving every primitive query unchanged. A deterministic covariance reduction of those seeds then absorbs independent Gaussian noise in the center. This converts a noisy-center call into the correct known-center law. There are two distinct depths: the dependency depth of a finite expression in means, and the height of the routines called to evaluate those means. We bound both before choosing the quadrature mesh. Each routine is assigned a requested error and a bound on the size of its perturbation. The update rules for these parameters make the routine recursion finite and allow its query exponent to be arbitrarily small. This seed transformation is an exact finite-dimensional identity, not an appeal to an approximate sampling oracle.

Return to the original target. A Gaussian proximal chain uses the near-quadratic procedure to sample πV\pi_V with a small added Gaussian. Repeated conditioning halves the remaining variance and reduces the conditional problem to an almost Gaussian law. A mode-centered Gaussian completes the descent. This final step is necessary because the requested accuracy is for the unnoised target in total variation.

Section 2 states the auxiliary sampling guarantee and the elementary comparison facts. Sections 3 and 4 prove the derivative estimates. Sections 5 and 6 construct and discretize the two flows. Section 7 implements the resulting expressions with actual gradient calls. Section 8 proves the sampling upper bound, and Section 9 gives the independent lower bound.

The near-quadratic sampling problem

The conditional density in the introduction is a Gaussian multiplied by a factor with a small Hessian. We now formulate the sampling problem for that larger class of perturbations. The center will be arbitrary: later calls must work at centers supplied by earlier random computations, without a bound on the gradient there. We state the required uniform guarantee first, then prove the comparison and smoothing facts used throughout its construction.

Notation and the auxiliary theorem

Vectors have Euclidean norm, and matrices have its induced operator norm unless otherwise indicated. For a random vector or tensor, ∥X∥2=(E∣X∣2)1/2\lVert X\rVert_2 = (\mathbb{E}|X|^2)^{1/2}, with the chosen pointwise norm; the notation ∥X∥F,2\lVert X\rVert_{\mathrm{F},2} specifies the Frobenius norm. The distance W2W_2 is quadratic Wasserstein distance on Euclidean space. Total variation is ∥μ−η∥TV=sup⁡B∣μ(B)−η(B)∣\lVert\mu-\eta\rVert_{\mathrm{TV}} = \sup_B |\mu(B)-\eta(B)|. All probability laws and oracle procedures are measurable.

Fix 0<e<10<e<1, and put δ=d−e\delta=d^{-e}. Let F:Rd→RF:\mathbb{R}^d\to\mathbb{R} be C2C^2, with gradient g=∇Fg=\nabla F of Lipschitz constant at most the declared bound λ=δ\lambda=\delta. Values of FF need not be available. For x∈Rdx\in\mathbb{R}^d and 0<r≤10<r\le1, define

νx,r(dz)=exp⁡(−∣z∣2/2−F(x+rz)) dz∫Rdexp⁡(−∣v∣2/2−F(x+rv)) dv,f(z)=g(x+rz),u=Eνx,rf.(2.1)\nu_{x,r}(dz)=\frac{\exp(-|z|^2/2-F(x+rz))\,dz}{\int_{\mathbb{R}^d}\exp(-|v|^2/2-F(x+rv))\,dv},\qquad f(z)=g(x+rz),\qquad u=\mathbb{E}_{\nu_{x,r}}f.\tag{2.1}

We often write ν=νx,r\nu=\nu_{x,r}, and use

L=λr,l=λr2=rL,D(x)=d+∣g(x)∣.(2.2)L=\lambda r,\qquad l=\lambda r^2=rL,\qquad D(x)=\sqrt{d}+|g(x)|.\tag{2.2}

Here xx is the actual input center; it need not be a minimizer of FF. The positive number λ\lambda is a declared upper bound, so the notation also covers affine or constant FF. The full potential in (2.1) has Hessian between (1−l)I(1-l)I and (1+l)I(1+l)I. Since l≤δ<1l\le\delta<1 for d≥2d\ge2, the normalizing integral is finite, even when FF is not convex. For the quantitative construction we take dd large enough that l≤1/2l\le1/2.

Throughout the construction, polylog⁡(d)\operatorname{polylog}(d) denotes a factor bounded by C(1+log⁡d)CC(1+\log d)^C. Its constants may depend on the fixed parameters ee, accuracy orders, and other fixed orders introduced below, but never on FF, xx, rr, or the oracle responses. Different occurrences may have different constants. Every sufficiently-large-dimension threshold has the same uniformity.

Theorem 2.1 (Noisy near-quadratic sampling). Fix 0<e<10<e<1, an integer K0≥2K_0\ge2, and t>0t>0 satisfying

40(K0+2)t<14.(2.3)40(K_0+2)t<\frac{1}{4}.\tag{2.3}

There are constants and a dimension threshold depending only on ee, K0K_0, tt with the following property. For every integer dd above that threshold, put δ=d−e\delta=d^{-e}. One measurable randomized oracle procedure works for every F∈C2(Rd)F\in C^2(\mathbb{R}^d) with Lip⁡(∇F)≤δ\operatorname{Lip}(\nabla F)\le\delta, every x∈Rdx\in\mathbb{R}^d, and every 0<r≤10<r\le1. Given evaluation access to g=∇Fg=\nabla F, it uses at most polylog⁡(d)δ−t\operatorname{polylog}(d)\delta^{-t} evaluations of gg on every execution and returns

X=Xpre+12G,X=X_{\mathrm{pre}}+\frac{1}{2}G,

References

  1. [1]Adamczak and Paweł Wolff. Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order. Probability Theory and Related Fields, 162:531–586, 2015. doi: 10.1007/s00440-014-0579-3. URL https://arxiv.org/abs/1304.1826v1. Statement numbering cited from arXiv:1304.1826v1.
  2. [2]Michael S. Albergo, Nicholas M. Boffi, and Eric Vanden-Eijnden. Stochastic interpolants: A unifying framework for flows and diffusions. Journal of Machine Learning Research, 26(209): 1–80, 2025. URL https://jmlr.org/papers/v26/23-1605.html. Equation numbering cited from arXiv:2303.08797v4.arxiv.org/abs/2303.08797
  3. [3]Jason M. Altschuler, Sinho Chewi, and Matthew S. Zhang. Shifted composition IV: Toward ballistic acceleration for log-concave sampling. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, pages 1739–1750. Association for Computing Machinery, 2026. doi: 10.1145/3798129.3800881. URL https://arxiv.org/abs/2506.23062v3. Full version: arXiv:2506.23062v3.
  4. [4]Michael Anshelevich. Appell polynomials and their relatives. International Mathematics Research Notices, 2004(65):3469–3531, 2004. doi: 10.1155/S107379280413345X. URL https://arxiv.org/abs/math/0311043v3. Preprint version: arXiv:math/0311043v3.
  5. [5]Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and Geometry of Markov Diffusion Operators, volume 348 of Grundlehren der mathematischen Wissenschaften. Springer, Cham, 2014. doi: 10.1007/978-3-319-00227-9.DOI
  6. [6]Fan Chen, Sinho Chewi, Jianfeng Lu, and Matthew S. Zhang. Accelerated high-accuracy sampling from a warm start via the proximal bouncy particle sampler, 2026. URL https://arxiv.org/abs/2609.06905v1. Version 1, September 7, 2026.
  7. [7]Fan Chen, Sinho Chewi, Jianfeng Lu, and Matthew S. Zhang. High-accuracy simulation of Picard HMC, part I: Gaussian cloud correction, 2026. URL https://arxiv.org/abs/2609.38710v1. Version 1, September 30, 2026.
  8. [8]Fan Chen, Sinho Chewi, Jianfeng Lu, and Matthew S. Zhang. Sharp Gaussian divergence and Bernstein–Markov inequalities, 2026. URL https://arxiv.org/abs/2609.32851v1. Version 1, September 26, 2026.
  9. [9]Fan Chen, Sinho Chewi, Jianfeng Lu, and Matthew S. Zhang. Smoothed Picard Hamiltonian Monte Carlo, 2026. URL https://arxiv.org/abs/2609.06906v1. Version 1, September 7, 2026.
  10. [10]Fan Chen, Sinho Chewi, Alexander Rakhlin, and Matthew S. Zhang. Exact simulation of diffusions and improved algorithms for log-concave sampling, 2026. URL https://arxiv.org/abs/2608.05022v1. Version 1, August 5, 2026.
  11. [11]Yongxin Chen, Sinho Chewi, Adil Salim, and Andre Wibisono. Improved analysis for a proximal algorithm for sampling. In Proceedings of the 35th Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 2984–3014, 2022. URL https://proceedings.mlr.press/v178/chen22c.html.arxiv.org/abs/2202.06386
  12. [12]Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett, and Michael I. Jordan. Underdamped Langevin MCMC: A non-asymptotic analysis. In Proceedings of the 31st Conference on Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 300–323, 2018. URL https://proceedings.mlr.press/v75/cheng18a.html.
  13. [13]Sinho Chewi, Jaume de Dios Pont, Jerry Li, Chen Lu, and Shyam Narayanan. Query lower bounds for log-concave sampling. Journal of the ACM, 71(4):29:1–29:42, 2024. doi: 10.1145/3673651. URL https://arxiv.org/abs/2304.02599v2. First circulated in 2023; theorem numbering cited from arXiv:2304.02599v2.
  14. [14]Thomas A. Courtade, Max Fathi, and Ashwin Pananjady. Existence of Stein kernels under a spectral gap, and discrepancy bounds. Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 55(2):777–790, 2019. doi: 10.1214/18-AIHP898. URL https://arxiv.org/abs/1703.07707v2.
  15. [15]Arnak S. Dalalyan. Theoretical guarantees for approximate sampling from smooth and log-concave densities. Journal of the Royal Statistical Society: Series B, 79(3):651–676, 2017. doi: 10.1111/rssb.12183. URL https://arxiv.org/abs/1412.7392.
  16. [16]Alain Durmus and Eric Moulines. Nonasymptotic convergence analysis for the unadjusted Langevin algorithm. The Annals of Applied Probability, 27(3):1551–1587, 2017. doi: 10.1214/16-AAP1238. URL https://arxiv.org/abs/1507.05021.
  17. [17]Pravesh K. Kothari and Jacob Steinhardt. Better agnostic clustering via relaxed tensor norms, 2017. URL https://arxiv.org/abs/1711.07465v1. Version 1, November 20, 2017.
  18. [18]Yin Tat Lee, Zhao Song, and Santosh S. Vempala. Algorithmic theory of ODEs and sampling from well-conditioned logconcave densities, 2018. URL https://arxiv.org/abs/1812.06243v1. Version 1, December 15, 2018.
  19. [19]Yin Tat Lee, Ruoqi Shen, and Kevin Tian. Structured logconcave sampling with a restricted Gaussian oracle. In Proceedings of the 34th Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 2993–3050, 2021. URL https://arxiv.org/abs/2010.03106v4. Revised version: arXiv:2010.03106v4.
  20. [20]Yi-An Ma, Tianqi Chen, and Emily B. Fox. A complete recipe for stochastic gradient MCMC. In Advances in Neural Information Processing Systems, volume 28, 2015. URL https://proceedings.neurips.cc/paper/2015/hash/9a4400501febb2a95e79248486a5f6d3-Abstract.html.
  21. [21]Oren Mangoubi and Aaron Smith. Rapid mixing of Hamiltonian Monte Carlo on strongly log-concave distributions, 2017. URL https://arxiv.org/abs/1708.07114v1. Version 1, August 23, 2017.
  22. [22]Ruoqi Shen and Yin Tat Lee. The randomized midpoint method for log-concave sampling. In Advances in Neural Information Processing Systems, volume 32, 2019. URL https://proceedings.neurips.cc/paper/2019/hash/eb86d510361fc23b59f18c1bc9802cc6-Abstract.html.arxiv.org/abs/1909.05503
  23. [23]Yang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, 2021. URL https://arxiv.org/abs/2011.13456v2.

Paper details

vlnc:W_jgeneua4
Version
v1 · latest
Published
License
LicenseRef-OpenAI-public
Usage

views · 7

downloads · 0

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

  • Mathematics

unreleased internal OpenAI model

View statement
Looking for related papers…
Contents