{"id":"openai-math/Subpolynomial-query-complexity-for-well-conditioned-log-concave-sampling","pdf":"https://github.com/openai/math/blob/main/preprints/Subpolynomial-query-complexity-for-well-conditioned-log-concave-sampling-September-26-2026/article.pdf","url":"https://github.com/openai/math/tree/main/preprints/Subpolynomial-query-complexity-for-well-conditioned-log-concave-sampling-September-26-2026","tags":["sampling","log-concave","query-complexity","optimization"],"score":0,"title":"Subpolynomial query complexity for well-conditioned log-concave sampling","domain":"Theoretical computer science","family":"139","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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 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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-26","reactions":{},"formalized":true,"family_title":"Subpolynomial query complexity for log-concave sampling"}