VibeMathedMath problems solved with AI
Sign in

The dimension exponent of first-order query complexity for well-conditioned log-concave sampling

Let V∈C2(Rd)V\in C^2(\mathbb R^d) with V(0)=0V(0)=0, ∇V(0)=0\nabla V(0)=0 and Id⪯∇2V⪯2IdI_d\preceq\nabla^2V\preceq2I_d, and let πV∝e−V\pi_V\propto e^{-V}. An algorithm queries (V(x),∇V(x))(V(x),\nabla V(x)) adaptively and must output a sample within total variation ε\varepsilon of πV\pi_V. Chewi's book Log-Concave Sampling calls it a fundamental open question to determine, up to a universal constant, the minimum number of first-order queries needed uniformly over this class. Known upper bounds grew polynomially in dd (about d1/2d^{1/2} for Langevin-type methods, O~(d1/3)\widetilde O(d^{1/3}), then O~(d1/6)\widetilde O(d^{1/6}) expected queries), and the lower bounds of Chewi et al. were logarithmic. What is the query complexity, and in particular, is a positive power of dd necessary at fixed accuracy?

Result
Proved(see note)
Status
Partial result
AI contribution
AI-discovered
Method
Argument
Field
Sampling algorithms; oracle complexity
Posed by
Sinho Chewi, Log-Concave Sampling (book draft), preface: 'a fundamental open question about the complexity of log-concave sampling'
Year posed
—
Years open
—
Solved
2026-09-26
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
22 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: in the exact first-order oracle model with unrestricted computation between queries, for every ε>0\varepsilon>0 the worst-case query budget Q(d)Q(d) for TV error 1/101/10 satisfies Q(d)≤CεdεQ(d)\le C_\varepsilon d^{\varepsilon} for all d≥2d\ge2, on every execution; and Q(d)≥clog⁡dQ(d)\ge c\log d for arbitrary randomized adaptive algorithms. Hence the optimal dimension exponent is γ∗=0\gamma_*=0. Not shown: the growth rate of Q(d)Q(d) beyond the exponent (no polylogarithmic bound is claimed), dependence on the accuracy or condition number, or any running-time bound; the constants and approximation orders depend on ε\varepsilon.

What the AI did

The release README says every result was produced by an unreleased internal OpenAI model with a fixed procedure of roughly three hours of ChatGPT Pro thinking compute per result. This family is not among the README's exceptions (the Hodge conjecture for CM abelian varieties, and the Re(s) > 11/12 zero-free region, whose write-up was human-edited). The manuscripts are authored 'OpenAI' and name no human author. The family is a single manuscript dated September 26, 2026.

Verification

No independent mathematician has checked this yet. Checked here: the abstract, introduction and Theorem 1.1 were read against the question as stated in Chewi's book. The book asks for the complexity up to a universal constant at accuracy ε\varepsilon; the paper fixes TV accuracy 1/10 and determines only the dimension exponent, so this entry is partial. Lean: formalization.yaml lists ComparatorChallenges/LogConcaveQuery.json with declaration OAI.LogConcaveSampling.exact_source_main in OAI/Probability/LogConcave/Main.lean. The challenge statement was read: for admissible potentials (C2, V(0)=0, gradient zero at 0, Hessian between I and 2I), measurable randomized adaptive algorithms with a deterministic query budget, TV at most 1/10, it asserts queryComplexity(d) <= C d^eps for every eps>0, >= c log d eventually, and gammaStar = 0. That is the headline claim. Not rebuilt here. The paper states that computation between queries is unrestricted and no arithmetic or bit cost is bounded.

Sources

Changelog1 change

Discussion