Subpolynomial-Query Proximal Sampling Beyond Log-Concavity
Abstract
We study the gradient query complexity of sampling from a density π(x)∝e−V(x) on ℝ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 ε using at most Cνκ(d+κ+ε−1+|∇ V(x0)|2/β)ν queries, where κ=β/α and x0 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.
Related
- Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities
- Query-Efficient Rejection Sampling for Parallel Masked Diffusion
- Proximal Policy Optimization for Amortized Discrete Sampling
- Accelerated High-Accuracy Sampling from a Warm Start via the Proximal Bouncy Particle Sampler
- Enhanced convergence guarantees of score-based generative models in 𝒲2-distance beyond log-concavity
BibTeX
@misc{guo2026subpolynomialquery,
title = {{Subpolynomial-Query Proximal Sampling Beyond Log-Concavity}},
author = {Wei Guo and Bo Yuan and Ye He and Jiaming Liang and Molei Tao and Yongxin Chen},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03442},
eprint = {2611.03442},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03442},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Subpolynomial-Query Proximal Sampling Beyond Log-Concavity
AU - Wei Guo
AU - Bo Yuan
AU - Ye He
AU - Jiaming Liang
AU - Molei Tao
AU - Yongxin Chen
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03442
UR - https://arxiv.org/abs/2611.03442
AB - We study the gradient query complexity of sampling from a density π(x)∝e^−V(x) on ℝ^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 ε using at most C_νκ(d+κ+ε^−1+|∇ 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.
ER -