Subpolynomial query complexity for log-concave sampling

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. (Lean)

Manuscript

Subpolynomial query complexity for well-conditioned log-concave sampling

September 26, 2026 · source · Lean formalization available · cite as \cite{OAI:Subpolynomial-query-complexity-for-well-conditioned-log-concave-sampling-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.

Result 139 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.