Sampling with almost no queries?

0:00Sampling by queries

Statistics and physics often need random samples from a density of the form e^(−V). Here V is a smooth bowl in d dimensions, whose curvature is pinned between one and two in every direction, with its lowest point at the origin. An algorithm may ask an oracle for V and its gradient at any point it likes, and computing in between is free; the cost is the number of questions. The goal is a sample whose distribution is within total variation one tenth of the target. The simplest method is rejection: propose a standard Gaussian point and accept it with the right probability. In our test potential, the acceptance rate falls like 0.74^d: about one in twenty at ten dimensions, and about one in 10 trillion at a hundred. Methods based on Langevin dynamics do far better, but small errors add up across dimensions: in our check, a Gaussian whose curvature is off by one percent is at total variation about 0.09 in a thousand dimensions, and 0.73 in a hundred thousand. The paper cites analyses of the unadjusted Langevin algorithm by Dalalyan and by Durmus and Moulines, and recent results with about d^(1/3) queries at this fixed conditioning and accuracy, by Altschuler, Chewi and Zhang, and by Chen, Chewi, Rakhlin and Zhang. The smallest exponent it cites is one sixth, counting expected queries, from smoothed Picard Hamiltonian Monte Carlo by Chen, Chewi, Lu and Zhang. In the other direction, results of Chewi and coauthors already gave growth at least like log d, at a suitable fixed accuracy. Is any positive power of the dimension really necessary?

1:44The claim

Result 139 is a single OpenAI preprint, 55 pages, dated September 26. It claims no: for every positive exponent ε, there is a constant C such that C times d^ε queries suffice, on every run, not just on average, for every such potential in every dimension. So the best exponent of d is zero. Here ε is an exponent, not an accuracy: the accuracy stays at one tenth. The count still grows, though: the paper also proves a lower bound of a constant times log d, even for quadratic potentials, following a strategy of Chewi and coauthors, whose results already give logarithmic growth. The fine print matters. Only queries are counted: the paper bounds no arithmetic, and says the construction aims at oracle complexity rather than practical running time. The upper bound’s constants are not given, and by our reading they are astronomical: one depth bound in the proof is already about 87,000 when ε is 1/5. The curvature window and the accuracy are fixed, and with the constant in the paper’s proof, the lower bound rules out even one-query algorithms only beyond about 2 trillion dimensions. The main theorem, upper and lower bounds together, is formalized in Lean: 326 files, about 64,000 lines, with no sorry.

3:11How the proof goes

The proof adds noise, then conditions. If X has the target law and you add Gaussian noise of variance h, then X, given the noisy point, has a density that is a Gaussian times a gentle correction: in rescaled units, the correction bends by at most two h. Alternating the two moves gives a chain that keeps the target fixed, and it needs about one over h steps. The paper sets h to d to the minus a small power, and these steps account for essentially all of the growth with d. In our one-dimensional run, noise 1/2 reached total variation 1/1000 in 5 steps, 1/10 in 19, and 1/50 in 89: smaller noise makes each step easier, but needs more of them. The catch is that each conditional sample must be far more accurate than one over the number of steps, using almost no queries. For that inner problem, a Gaussian is carried into the target by a flow, and the flow’s velocity is a conditional average of gradients: the same kind of problem one level down. So the algorithm is recursive. Integrating the flow to high order needs high derivatives, and naive bounds would lose a power of d at every differentiation. The paper instead bounds each derivative tensor under every split of its slots into two groups, so repeated integration by parts costs only polylogarithmic factors, plus one square root of d at the end. Picard iteration then gives finite formulas of fixed depth, and accuracy is raised by raising the interpolation order, which changes only constants. That is why every positive exponent is within reach. Nested calls need exact centers they cannot know. The paper’s trick: run the inner call at a noisy center, but shrink its random seeds by exactly the right amount, and the result has exactly the law of a call at the true center. Then steps that halve the remaining variance remove the auxiliary noise, and a final Gaussian, centered at the peak of the last conditional law, finishes. The lower bound hides a random rotation inside a quadratic potential. With q queries, an algorithm’s output lies in a Krylov space built from a few Gaussian directions. A statistic stays small everywhere on that space, but true samples show a clear bias in it while q is below a constant times log d. In our simulation at a million dimensions, the matching statistic still told true samples apart, narrowly, from everything one query can produce, but not from two.

5:40Where it stands

The preprint is not peer reviewed, and the posted version has not been revised. Its main theorem, the upper bound, the lower bound and the zero exponent, is formalized in Lean; we did not build it or run the comparator. The paper is not among those OSVerify reviewed, and we have seen no expert review. If it holds, for well-conditioned log-concave sampling with a known minimizer, the number of queries need not grow like any power of the dimension: it lies between a constant times log d and a constant times d^ε, for every ε. It says nothing about running time, and by our reading the constants are far from practical.