Subpolynomial query complexity for log-concave sampling
OpenAI research collection · 1 manuscript · Source checked 2026-10-19
OpenAI's result summary
For C^(2) potentials with a supplied minimizer and I\preceq\nabla^2V\preceq2I, proves that sampling within total variation 1/10 requires only C_ε d^ε 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.
Read the manuscripts
Short excerpts below come from OpenAI's abstracts. The full abstract and original PDF preserve the paper's precise scope.
MANUSCRIPT 01
Subpolynomial query complexity for well-conditioned log-concave sampling
For every fixed ε > 0, we give a sampling algorithm using at most C_ε d^ε exact first-order queries on every execution for C^(2) 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…
Full source abstract
For every fixed ε > 0, we give a sampling algorithm using at most C_ε d^ε exact first-order queries on every execution for C^(2) 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.
This PDF is listed in OpenAI's formalization catalogue. See the scope and dependencies before interpreting coverage.
New mathematical reasoning could help AI tackle harder scientific and computational problems. How reliably these skills transfer beyond mathematics will determine how much they contribute to general intelligence.