Subpolynomial-Query Proximal Sampling Beyond Log-Concavity

arXiv:2611.03442 · stat.ML, cs.CC, cs.LG, math.ST, stat.TH · Submitted 2026-11-02 · Read on arXiv

stat.ML, cs.CC, cs.LG, math.ST, stat.TH

Submitted: 2026-11-02

Updated: 2026-11-02

License: http://creativecommons.org/licenses/by/4.0/

The gist: We study the gradient query complexity of sampling from a density π(x) proportional to e-V(x) on R d, where V has a β-Lipschitz gradient but need not be convex.

Terminology

Abstract

We study the gradient query complexity of sampling from a density π(x) proportional to e-V(x) on R d, where V has a β-Lipschitz gradient but need not be convex. Our approach uses the proximal sampler, which alternates Gaussian perturbation with sampling a position conditional on the noisy observation. We implement its observation chain using the high-order noisy conditional sampler of [OpenAI 2026], obtaining improved dimension dependence under functional inequalities. If π satisfies a log-Sobolev inequality (LSI) with constant α, then for every fixed ν>0, there is a finite constant C ν depending only on ν such that the algorithm returns a sample within total-variation distance epsilon using at most C νκ(d+κ+ epsilon-1+| grad V(x 0)| 2/β) ν queries, where κ=β/α and x 0 is an arbitrary reference point for initialization. The analysis controls center-dependent local errors along exact proximal histories and removes the final observation noise by conditional decoding. Under a Poincaré inequality (PI), we obtain a corresponding guarantee from a warm start with a known bound on its Rényi divergence. An oracle lower bound shows that a stationary point alone, which suffices under LSI, is insufficient under PI.

Sources

Related papers