Log-concave sampling: a zero dimension exponent for exact oracle queries

← All digests

Family 139 · Theoretical computer science
Importance 2/5 · Provisional editorial rating
Sources consulted 2026-10-09

1. The question

Suppose a probability density is known only through a function and its gradient. How many evaluations are needed to draw a sample approximately from that density?

For a potential $V:\mathbb R^d\to\mathbb R$, the target density is proportional to $e^{-V(x)}$. A convex potential has one broad basin rather than many separated wells, making sampling more approachable. Yet common numerical schemes still need a number of gradient evaluations that grows as a positive power of dimension.

Is that dependence intrinsic to the information obtained from the oracle, or partly a consequence of how the algorithm processes it?

This manuscript claims that, for a fixed well-conditioned class with a known minimizer, every positive power of dimension can be beaten in exact first-order query complexity. More precisely, for every fixed $\varepsilon>0$, at most $C_\varepsilon d^\varepsilon$ queries suffice for a fixed total-variation accuracy. A logarithmic lower bound remains.

The distinction from running time is decisive. Computation between queries is unrestricted, exact real-valued responses are available, and no arithmetic or bit-cost bound is supplied. The theorem concerns the number of contacts with the unknown potential.

2. Background and essential definitions

Assume $V$ is twice continuously differentiable and normalized by $V(0)=0$ and $\nabla V(0)=0$. The origin is therefore a known minimizer. Its Hessian satisfies

$$I_d\preceq\nabla^2V(x)\preceq2I_d \qquad\text{for every }x\in\mathbb R^d.$$

The matrix inequality means that every directional curvature lies between one and two. This combines strong convexity, which prevents flat directions, with smoothness, which limits curvature. The condition number is at most two.

The target Gibbs law is

$$\pi_V(dx)=Z_V^{-1}e^{-V(x)}\,dx, \qquad Z_V=\int_{\mathbb R^d}e^{-V(x)}\,dx.$$

The unknown normalizing constant makes the density integrate to one. A first-order query at $x$ returns both $V(x)$ and the entire gradient vector $\nabla V(x)$, exactly. One query therefore contains $d$ real gradient coordinates; query count is not coordinate-operation count.

The distance requirement is total variation at most $1/10$. Total variation is the largest difference in probabilities assigned to the same measurable event by two laws. It controls all events, not just expectations of smooth functions.

Let $Q(d)$ be the smallest worst-execution query budget sufficient for every potential in the class. Algorithms may choose later queries adaptively from earlier replies and use private randomness. Their only information about $V$ comes from oracle replies.

The optimal dimension exponent is the limiting upper growth rate of $\log Q(d)/\log d$. Exponent zero permits growth slower than every fixed positive power. It does not necessarily mean constant or polylogarithmic query complexity.

3. Development history and previous partial results

Langevin sampling connects gradients with stochastic dynamics whose equilibrium is the target distribution. Nonasymptotic analyses by Dalalyan and Durmus–Moulines quantify how discretization and finite running time affect sampling accuracy. Underdamped dynamics and randomized midpoint methods improve dimension dependence under appropriate assumptions.

Accuracy metrics matter in these comparisons. A Wasserstein bound controls transportation cost, while total variation controls all measurable events. A rate in one metric cannot be silently assigned to another without a conversion theorem and its parameter losses.

The source cites recent methods with roughly $d^{1/3}$ query dependence at fixed conditioning and total-variation accuracy. Chen and coauthors’ smoothed Picard HMC improves the relevant fixed-accuracy exponent to $1/6$ through a relative-entropy guarantee. Its expected query bound can be capped with a controlled additional error to obtain a fixed worst-run budget at the accuracy used here.

The manuscript also discusses a subsequent Gaussian-cloud correction preprint, which improves a different high-accuracy tradeoff while retaining polylogarithmic dependence on inverse accuracy. This is not the same objective as fixing accuracy and driving the dimension exponent to zero.

High-order Hamiltonian methods already exploit additional smoothness or structure. The new claim instead keeps only the stated $C^2$ regularity and two-sided Hessian bounds. Higher derivatives arise after Gaussian smoothing, and the challenge is to implement the resulting conditional means through finitely many queries to the original gradient.

For lower bounds, Chewi and coauthors developed rotationally invariant Gaussian constructions and already obtained logarithmic dimension dependence in a related fixed-parameter setting. The new paper adapts that strategy to its exact spectral interval and accuracy threshold rather than presenting the general lower-bound method as new.

4. What the new manuscripts claim

For every fixed $\varepsilon>0$, there is a constant $C_\varepsilon$ such that

$$Q(d)\le C_\varepsilon d^\varepsilon \qquad(d\ge2).$$

The algorithm makes at most this many exact first-order queries on every execution. Its output law is within total variation $1/10$ of $\pi_V$ for every potential satisfying the stated assumptions.

The approximation orders and constants may depend on $\varepsilon$. This family of guarantees does not provide one explicit polylogarithmic bound, and it does not supply a uniform small constant as $\varepsilon$ tends to zero.

The manuscript also states that there are absolute $c>0,d_0$ with

$$Q(d)\ge c\log d \qquad(d\ge d_0),$$

even for arbitrary randomized adaptive algorithms with unrestricted computation between queries. The lower bound already holds for centered Gaussian targets whose potentials have the form $V(x)=x^{\mathsf T}Ax/2$, with $I_d\preceq A\preceq2I_d$.

Together the claims determine the optimal dimension exponent as zero, while leaving a gap in the finer growth rate between logarithmic and general subpolynomial behavior.

The oracle returns exact real values, and the model permits generation of random real variables. Algorithms may depend on dimension and must be measurable. There is no claim about the number of bit operations needed to represent queries, process answers, or write the sample to finite precision.

5. Why the advance matters

Provisional importance: 2/5. The result would sharply separate information requirements from the costs of familiar numerical sampling schemes in a specialized, well-conditioned oracle model. It says that a positive power of dimension is not forced by the number of exact gradient evaluations alone.

The known-minimizer and fixed-conditioning assumptions isolate discretization and information issues from the problem of first locating a useful region. The $C^2$ scope is also meaningful: the method does not assume a full collection of uniformly bounded higher derivatives of the original potential.

The rating is relative to the collection and reflects the model’s limits. Arbitrary computation and exact real arithmetic between queries can hide enormous practical cost. A subpolynomial count of whole-gradient queries is therefore narrower than a subpolynomial-time sampling algorithm.

The matching exponent classification remains valuable despite that limitation. It identifies where a positive dimension exponent can and cannot be justified by an oracle lower bound, and suggests which additional resource restrictions would be needed for stronger practical conclusions.

6. The main idea

Turn the target into nearly Gaussian conditional laws

Add a small Gaussian perturbation to a target sample. Conditional on the noisy observation $y$, the original sample has density proportional to

$$\exp\!\left(-V(x)-\frac{\|x-y\|^2}{2h}\right).$$

After rescaling around $y$, this is a standard Gaussian multiplied by a weak perturbation. Small $h$ reduces the perturbation’s curvature, making it a reusable auxiliary sampling problem.

This Gaussian conditional framework has established precedents. The new construction needs two related operations: a sample with added Gaussian noise and a conditional gradient mean with added Gaussian noise. The added noise is used as part of the recursive implementation, not merely tolerated as an uncontrolled output error.

Obtain high-order structure by smoothing

Gaussian conditioning makes conditional means smoother than the original $C^2$ potential. Their higher derivatives form tensors, which can be viewed as matrices by dividing their coordinate slots into two groups.

The manuscript bounds these matrices for every such division. This controls the contractions appearing in high-order flow approximations without paying an additional large power of dimension at each derivative. The relevant flows interpolate between Gaussian and target-like distributions and express their velocities through conditional gradient means.

A second stationary flow uses an auxiliary Gaussian momentum variable. Its displacement converts an integral of conditional means into a Gaussian centered at the desired mean. High-order quadrature then represents the needed operations as finite nested expressions in conditional means.

Implement noisy means with actual oracle calls

Writing a formula involving an exact conditional mean is not enough: that mean is itself unknown. The manuscript recursively replaces mean calls by procedures using only the original gradient oracle.

Its key mechanism is a translation property of random seeds. A shift in a conditional center can be compensated by a specified shift of Gaussian seeds while leaving the primitive query locations unchanged. Reducing the seed covariance then absorbs independent Gaussian uncertainty in the center.

The construction controls both the dependency depth of the finite expressions and the height of the routines evaluating their means. With approximation orders chosen for the desired $\varepsilon$, this yields the claimed arbitrarily small positive query exponent.

The final output must approximate the original target, not a Gaussian-blurred version. A further sequence of conditioning steps reduces the auxiliary variance, followed by a Gaussian approximation centered at the appropriate mode. This removal of noise is necessary for the total-variation conclusion.

Hide a Gaussian covariance from too few queries

For the lower bound, take a quadratic potential. A gradient query returns $Ax$, so sampling the target $N(0,A^{-1})$ is a matrix-vector information problem.

Randomly rotate a carefully selected spectrum inside $[1,2]$. With few adaptive queries, much of the rotation remains unexposed. A deferred-revelation argument places even an unrestricted randomized output within an enlarged random span generated by matrix powers and auxiliary Gaussian vectors.

A separating statistic behaves differently on that information-limited output and on a true target sample. The argument yields a logarithmic query obstruction. It is independent of the upper-bound construction and does not claim that every sampler must follow a particular iterative scheme.

7. Scope, limitations, and open questions

The minimizer is supplied and normalized to the origin. Finding it is not part of the query budget. The condition number is fixed at two, and the target accuracy is fixed at $1/10$; general dependence on conditioning and arbitrary accuracy is not determined by the headline theorem.

Exact gradients can carry much more information than noisy or finite-precision responses. The result does not directly cover stochastic gradients, limited precision, or a realistic bit-cost model.

Exponent zero leaves a quantitative gap. The upper bound does not establish $O((\log d)^C)$, while the lower bound rules out a bounded query count. Determining the finer optimal rate remains open in the manuscript.

Finally, high approximation orders and unrestricted inter-query computation can make the construction unsuitable for implementation. Turning the information-theoretic improvement into an efficient numerical sampler would require additional complexity and stability analysis. The digest reports the claimed smoothing, recursion, and lower-bound mechanisms without independently checking them.

8. Sources and further reading

The Langevin papers introduce finite-time sampling analysis; smoothed Picard HMC and Gaussian-cloud correction provide the immediate high-order context. Chewi and coauthors supply the Gaussian oracle lower-bound framework. The source manuscript below states the subpolynomial query theorem and its logarithmic obstruction in one precise model.

Source manuscripts

• M1. OpenAI, Subpolynomial query complexity for well-conditioned log-concave sampling (September 26, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.