Browse › Theoretical computer science › 139 Subpolynomial query complexity for log-concave sampling
Subpolynomial query complexity for well-conditioned log-concave sampling
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
For every fixed ε > 0, we give a sampling algorithm using at most $C_\varepsilon d^\varepsilon$ exact first-order queries on every execution for C2 potentials on ℝd with a known minimizer and Hessian between Id 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.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI math release, Lean scope note 139: Subpolynomial query complexity for log-concave sampling (lean/docs/139.md, 2026-10-06). The release's scope note states that the formalization covers the upper bound $C_\varepsilon d^\varepsilon$, the eventual lower bound $c\log d$, and $\gamma_*=0$ for randomized adaptive measurable algorithms using exact value-and-gradient queries at total-variation error 1/10. The comparator statement is in
LogConcaveQuery.lean. [family-level] - OpenAI, OAI/Probability/LogConcave/Main.lean (openai/math repository, October 2026). This is the release's top-level Lean module for this paper. It contains
source_subpolynomial_upper,source_gammaStar_zeroandexact_source_main, the last combining the upper bound, the logarithmic lower bound and $\gamma_*=0$. - DakeBU, Protocol: assimilate OpenAI Math into Samplinglib (PR #314) (GitHub pull request, merged 2026-10-07). This independent Lean library pins the 2026-10-06 release snapshot and treats
OAI/Probability/LogConcaveas a full proof graph, separating reusable leaves from the "source-specific subpolynomial query-complexity route". No theorem has been ported yet.
Related prior literature mentioned by others
- Sinho Chewi, Log-Concave Sampling (book draft) (version of 2026-08-20). VibeMathed cites this book as the source of the question the paper answers. In Section 9.4 the book notes that Gaussian lower bounds are only logarithmic in $d$, "whereas all of the upper bounds for general log-concave sampling thus far incur polynomial dimension dependence".
Possibly relevant literature (found by the agent, not checked)
- Chewi, Gerber, Lu, Le Gouic, Rigollet, The query complexity of sampling from strongly log-concave distributions in one dimension (arXiv:2105.14163, 2021). This earlier work in the same first-order query model determines the $d=1$ complexity as a function of the condition number. It may give context for the paper's fixed-conditioning lower bound (Theorem 1.1, lower part).
- Altschuler, Chewi, Faster high-accuracy log-concave sampling via algorithmic warm starts (arXiv:2302.10249, 2023). This is an earlier polynomial-in-$d$ query bound ($\widetilde O(d^{1/2})$ for high accuracy) for strongly log-concave, log-smooth targets. It is relevant to the historical comparison of dimension exponents in Section 1.2.
- Braverman, Hazan, Simchowitz, Woodworth, The gradient complexity of linear regression (arXiv:1911.02212, 2019). This is the source of the Wishart-conditioning technique for matrix-vector query lower bounds, which Chewi's book credits in its Gaussian sampling lower bounds. It may be relevant to the rotational-invariance and block-Krylov reduction behind the paper's $c\log d$ lower bound.
Digests and expositions
- Latent Seminar, Subpolynomial queries for log-concave sampling (2026-10-07). This exposition explains the oracle model, Gaussian conditioning, recursive noisy-mean implementation, noise removal, and Gaussian lower-bound strategy, and states that it has not independently verified the complete proofs. [family-level]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 139
Independent sites; their content is not reviewed here.
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}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/139.md. The Lean statements have not been checked by people against the paper's claims.
Family 139: Subpolynomial query complexity for log-concave sampling
For C2 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.
This is the only paper in this family.