Subpolynomial query complexity for log-concave sampling

1 · The essentials

The task is to generate a random point whose distribution closely matches a specified target in a space with many coordinates. The target is described by a smooth function, and the algorithm can ask for its exact value and slope at chosen points. The result assumes that a point where the function is smallest is supplied, and that its curvature stays between two fixed bounds. Under these conditions, the number of requests grows more slowly than any fixed positive power of the number of coordinates. This request limit holds on every run, not just on average, and the output meets a fixed standard of closeness to the target. The main result has a Lean formalization. The guarantee concerns requests for information, not total running time: computation between requests is unrestricted.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine exploring a smooth bowl-shaped landscape while paying only for calls to a service that reports the height and slope at a chosen spot. You are given the bottom of the bowl, and the result limits how many calls you need to choose a random location with the required distribution—but places no limit on how much work you do between calls.

Why it matters

The result separates the information needed for sampling from the computation needed to process that information. In this exact-query model, under the stated assumptions, no positive power of dimension is necessary to bound the query count. A logarithmic lower bound shown in the manuscript also indicates that the required information cannot remain bounded independently of dimension.

2 · Going further

The precise problem is sampling from a target Gibbs law described by a potential $V$ on $R^{d}$ . The potential must be $C^{2}$ , a minimizer must be supplied, and its Hessian must satisfy $I_{d} ⪯ \nabla^{2} V ⪯ 2 I_{d}$ . An exact first-order query returns the value and gradient of $V$ at a selected point. The required output accuracy is total-variation distance at most $1/10$ from the target law.

For every fixed $ε > 0$ , the main result gives an algorithm making at most $C_{ε} d^{ε}$ queries on every execution. Here the constant is indexed by $ε$ ; the statement does not give a dimension-independent query bound. Computation between queries is unrestricted, so this is an information-access guarantee rather than a running-time guarantee.

The manuscript also shows an $Ω (lo g d)$ lower bound for arbitrary randomized adaptive algorithms. Together, the bounds determine the optimal power-law exponent in dimension to be zero, without determining an exact query rate. The supplied abstract states the algorithmic guarantee and lower bound but does not describe the construction or the argument behind them. Only one manuscript is supplied, so no companion-manuscript relationship can be described from this source.

Useful notions

Probability distributions and random sampling
Gradients and second derivatives
Dimension and asymptotic growth
Algorithms that request information at chosen points

What was known before / what is new

Before

The source places the problem in the setting of well-conditioned log-concave sampling with exact value-and-gradient access. It does not state earlier query bounds or provide a historical account, so no comparison with a prior best result is available from the supplied text.

New

The main contribution is the every-execution bound $C_{ε} d^{ε}$ for each fixed $ε > 0$ , with total-variation error at most $1/10$ under the specified assumptions. The manuscript also shows a logarithmic lower bound for arbitrary randomized adaptive algorithms. These statements identify the optimal dimension exponent as zero.

Limits and assumptions

The guarantee requires a twice continuously differentiable potential, a supplied minimizer, and the curvature bounds $I_{d} ⪯ \nabla^{2} V ⪯ 2 I_{d}$ . Queries return exact values and gradients, and computation between queries is unrestricted; the statement therefore supplies no total running-time bound or guarantee for inexact queries. The main sampling result has a Lean formalization, but the supplied text does not separately specify formalization coverage for the lower bound. The stated upper and lower bounds leave the exact query rate undetermined, and the source does not identify further open problems.

Mini glossary

Potential: The function describing the target Gibbs law and accessed through value-and-gradient queries.
Hessian: The matrix of second derivatives that expresses the potential's curvature.
Query complexity: The number of requests an algorithm makes for information about the potential.
Total-variation distance: A measure of discrepancy between probability distributions, used here to specify sampling accuracy.
Subpolynomial bound: A bound of the form $C_{ε} d^{ε}$ for every fixed positive $ε$ .
Adaptive algorithm: An algorithm whose later queries can depend on the information returned by earlier queries.

Keywords : Log-concave sampling · Query complexity · Subpolynomial growth

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

For C² potentials with a supplied minimizer and $I ⪯ \nabla^{2} V ⪯ 2 I$ , proves that sampling within total variation 1/10 requires only $C_{ε} d^{ε}$ 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.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/139.md

Manuscripts in this family

★

Subpolynomial query complexity for well-conditioned log-concave sampling

26/09/2026

Verified by Lean

For every fixed ε > 0, we give a sampling algorithm using at most $C_{ε} d^{ε}$ exact first-order queries on every execution for C² potentials on ℝ^d with a known minimizer and Hessian between I_d and $2 I_{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 $Ω (lo g d)$ query lower bound for arbitrary randomized adaptive algorithms, determining the optimal dimension exponent to be zero.

PDF GitHub folder Lean formalization