Subpolynomial query complexity for log-concave sampling

Sampling from a gently curved bowl needs no fixed power of the dimension in queries.

1 paper September 26, 2026 Explained by AI

Sampling means drawing random points that favour the low parts of a bowl-shaped function. An algorithm learns the bowl only by asking for its height and slope at chosen points. This paper proves the number of questions can grow slower than any power of the dimension (Lean proof listed). It also proves that the count must still grow at least like the logarithm of the dimension.

First step

2017

Dalalyan; Durmus and Moulines, nonasymptotic Langevin bounds

Significance

Major

It settles the dimension exponent for this query model at zero, where the best earlier bound was about d^(1/6).

Trust

Formal proof listed

Field

Theoretical computer science

1 paper

Best power of dimension d in the query count

Year	Who	Value
2026	Altschuler, Chewi and Zhang	0.3333
2026	Chen, Chewi, Lu and Zhang	0.1667
2026	This paper	0

Lower is better. Log factors and constants are ignored. The 2026 value 0 means any positive power works.

The explanation

Start with a bowl on a line, the curve V(x) = x²/2. Give each point x a weight of e to the power −V(x). Low points of the bowl get the most weight. Drawing random points in proportion to that weight is called sampling. For this bowl the result is the standard bell curve. A steeper bowl, V(x) = x², gives a narrower bell. Its spread is about 0.71 instead of 1.

The paper allows any bowl whose curvature stays between those two, at every point and in every directionSource 1. Curvature is how fast the slope changes. The bowl may live in d dimensions, not just on a line. Its lowest point is at zero, and the algorithm is told so. The target is called the Gibbs law of V. A sample counts as good if its distribution is within 1/10 of the target in total variation. Total variation is the largest gap in probability the two give to any single event. The two bells above are about 0.166 apart by that measure. So the tolerance of 1/10 is tighter than the gap between the two extreme bowls.

The algorithm cannot see the bowl. It learns only by asking questions, called queries. Each query names a point and gets back the exact height and slope there. The slope in many dimensions is called the gradient. Between queries the algorithm may compute as much as it likes, for free. The cost is the number of queries, and the limit must hold on every run, not just on average. The question is how fast that count must grow with d.

Classical samplers follow a random walk downhill in small steps, a method called Langevin dynamics. Their step error grows with dimension. In 2017, Dalalyan, and separately Durmus and Moulines, gave explicit error bounds for this method. In 2026, an analysis by Altschuler, Chewi and Zhang implied about d^(1/3) queries in this setting. A September 2026 preprint by Chen, Chewi, Lu and Zhang lowered it to about d^(1/6) on average. These rates ignore slowly growing log factors. The open question was whether some positive power of d is needed at all.

This paper proves that none is (Lean proof listed). For every small positive number ε, some constant C_ε makes C_ε times d^ε queries enoughSource 2. Take d = 1,000,000. Then d^(1/3) is 100 and d^(1/6) is 10. With ε = 0.05, d^ε is about 2. The paper states no value for C_ε, and it may depend on εSource 3. So these figures show how the counts grow, not real query numbers. The paper aims at counting queries, not at practical running timeSource 4.

The paper also proves a floor. Some fixed constant c makes at least c times log d queries necessary, once d is largeSource 2. Earlier work by Chewi and coauthors (2024) already gave a floor like this. The paper follows its strategy for this exact setting. For d = 1,000,000, log d is about 13.8. The floor holds even for exactly quadratic bowlsSource 5. It also holds for any randomized algorithm that adapts its questionsSource 6. Together the two bounds pin the best power of d at exactly zero. They do not pin down the exact growth between log d and d^ε. The paper does not claim a count that grows like a power of log dSource 7.

The hard part was accuracy. Methods that take large, precise steps usually need many smooth derivatives of the bowl. Here the bowl is only promised to have bounded curvature. Like the earlier d^(1/6) work, the paper gets the missing smoothness by blurring the bowl with a little Gaussian noiseSource 8. Each blurred quantity is an average that itself needs sampling, so calls nest inside calls. The paper shows how to run these nested, noisy calls exactly with finitely many real queriesSource 9. It then removes the added noise by further conditioning, so the final sample is for the original bowlSource 10.

How sure is this? A computer proof checker called Lean has checked a formal version of the main theorem. It covers both the d^ε upper bound and the log d lower bound, so the best exponent is zero. In that statement, algorithms may be randomized and adaptive, and their arithmetic cost is not limited. No specialist review of the paper has been published.

What it doesn't show. This does not give a practical fast sampler, since it counts queries only and the constants are not stated.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Major within its query model. Lean has checked the main theorem. The result counts queries, not running time, gives no size for its constants, and has no published specialist review.

Words used

Sampling: Drawing random points so that likely points come up more often, in a set proportion.
Gibbs law: The distribution that gives each point a weight of e to the power minus the bowl's height.
Log-concave: A distribution built this way from a bowl that curves upward everywhere.
Query: One question to the bowl, returning its exact height and slope at a chosen point.
Gradient: The slope of a function in many dimensions, pointing uphill.
Total variation: The largest gap in probability two distributions give to any single event.
Langevin dynamics: A random walk that drifts downhill, used by classical samplers.

The original paper

Subpolynomial query complexity for well-conditioned log-concave sampling (PDF, opens in a new tab)
September 26, 2026 Formal proof listed

Lean notes

All quoted lines (10)

For $d\ge2$ , let $\mathcal V_d$ consist of the functions $V\in C^2(\R^d)$ satisfying $V(0)=0,\qquad \nabla V(0)=0,\qquad I_d\preceq\nabla^2V(x)\preceq2I_d \quad\text{for every }x\in\R^d.$
Subpolynomial query complexity for well-conditioned log-concave sampling Back to text
There are also absolute constants $c>0$ and $d_0$ such that $Q(d)\ge c\log d\qquad(d\ge d_0).$
Subpolynomial query complexity for well-conditioned log-concave sampling Back to text
The constants and the algorithmic approximation orders may depend on $\varepsilon$ .
Subpolynomial query complexity for well-conditioned log-concave sampling Back to text
The construction uses approximation orders that can depend on the desired exponent and is aimed at oracle complexity rather than practical running time.
Subpolynomial query complexity for well-conditioned log-concave sampling Back to text
The lower bound already holds for centered Gaussian targets, whose minimizer is known.
Subpolynomial query complexity for well-conditioned log-concave sampling Back to text
The lower bound applies to arbitrary randomized adaptive first-order algorithms. In particular, $\gamma_*=0$ .
Subpolynomial query complexity for well-conditioned log-concave sampling Back to text
Together they determine the exponent but not the finer growth rate of $Q(d)$ . In particular, the upper bound does not assert a polylogarithmic query count.
Subpolynomial query complexity for well-conditioned log-concave sampling Back to text
All high derivatives come from Gaussian conditioning; the original potential still needs only the $C^2$ regularity in (…).
Subpolynomial query complexity for well-conditioned log-concave sampling Back to text
The obstacle here is to obtain high-order accuracy under those bounds while implementing every conditional mean with finitely many first-order queries.
Subpolynomial query complexity for well-conditioned log-concave sampling Back to text
We first implement this conditional operation with an added Gaussian, then remove that noise by further conditioning.
Subpolynomial query complexity for well-conditioned log-concave sampling Back to text