Family 139Theoretical computer scienceLeanNot yet digested

Subpolynomial query complexity for log-concave sampling

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_\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.

Manuscripts in this family · 1

Subpolynomial query complexity for well-conditioned log-concave sampling

Sep 26, 2026·article.pdfLean

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.

Full abstract

PDF on GitHub LaTeX source