Subpolynomial-Query Proximal Sampling Beyond Log-Concavity
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
- Accelerated High-Accuracy Sampling from a Warm Start via the Proximal Bouncy Particle Sampler
- Reflected Proximal Dynamics for Accelerated High-Accuracy Log-Concave Sampling
Related papers
- Uniform-in-Time Weak Propagation-of-Chaos in Shallow Neural Networks
- Diffusion Models Observe Only Gradients: A Geometric Perspective on Score Matching Errors
- Quantifying Error Propagation and Model Collapse in Diffusion Models
- Behavior of prediction performance metrics with rare events
- Statistical Inference and Learning for Shapley Additive Explanations (SHAP)
- Control Variate Design for Score-Function Gradient Estimators in Importance-Weighted Variational Inference