Theoretical computer science · Result 139

Subpolynomial query complexity for log-concave sampling

1 paperLean

For C² potentials with a supplied minimizer and \(I\preceq\nabla^2V\preceq2I\), proves that sampling within total variation 1/10 requires only \(C_\varepsilon d^\varepsilon\) exact value-and-gradient queries for every fixed ε > 0. The bound holds on every run, with unrestricted computation between queries. A logarithmic lower bound also holds, so the optimal power-law exponent in this oracle model is zero.

Watch

▶Introduction: the problem and why it mattersin preparation

▶The presented solutionin preparation

Papers 1

Subpolynomial query complexity for well-conditioned log-concave sampling

OpenAI · September 26, 2026

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

Read PDF Download Source

Cite

@misc{OAI:Subpolynomial-query-complexity-for-well-conditioned-log-concave-sampling-September-26-2026,
  author = {{OpenAI}},
  title = {{Subpolynomial query complexity for well-conditioned log-concave sampling}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Subpolynomial-query-complexity-for-well-conditioned-log-concave-sampling-September-26-2026/article.pdf}{OAI:Subpolynomial-query-complexity-for-well-conditioned-log-concave-sampling-September-26-2026}},
  year = {2026}
}

What was formalized in Lean

The following describes the scope of the Lean formalization related to the following accompanying paper(s):

Subpolynomial query complexity for well-conditioned log-concave sampling

Scope

The formalized result determines the dimension exponent of exact value-and-gradient query complexity for well-conditioned log-concave sampling. For potentials with \(V(0)=0\), \(\nabla V(0)=0\), and \(I\le\nabla^2V\le2I\), the least worst-case query budget achieving total-variation error at most \(1/10\) is at most \(C_\varepsilon d^\varepsilon\) for every \(\varepsilon>0\), and at least \(c\log d\) eventually. Hence the infimal polynomial exponent is zero. Algorithms may be measurable, randomized, and adaptive; arithmetic and bit costs are not bounded.

Comparator links

Result	Comparator statement
Subpolynomial query complexity for log-concave sampling	LogConcaveQuery.lean

Scope note on GitHub →