Improved sampling method with fewer queries for complex distributions
Subpolynomial-Query Proximal Sampling Beyond Log-Concavity
Computational ComplexityMachine Learning
Summary
This paper looks at ways to efficiently draw random samples from tricky probability distributions that are not easily handled by usual methods. The authors improve a sampling technique called the proximal sampler, which mixes random noise and conditional steps to get sample points. They show this approach requires fewer gradient checks (or queries) especially when the distribution satisfies certain mathematical conditions. The findings help clarify when starting points affect sampling quality and provide limits on what can be achieved with weaker assumptions.
What this means in practice
- •For machine learning engineers: Implement efficient sampling methods for complex, non-log-concave models reducing computational cost in probabilistic modeling pipelines.
- •For statistical simulation teams: Use improved proximal sampling algorithms to generate high-quality samples under weaker assumptions on the target distribution for robust simulation studies.
Authors
Wei Guo, Bo Yuan, Ye He, Jiaming Liang, Molei Tao, Yongxin Chen
Abstract
We study the gradient query complexity of sampling from a density $π(x)\propto\mathrm{e}^{-V(x)}$ on $\mathbb{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 $\varepsilon$ using at most $C_νκ(d+κ+\varepsilon^{-1}+\|\nabla 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.