CS Paper Radar

Subpolynomial-Query Proximal Sampling Beyond Log-Concavity

Wei Guo, Bo Yuan, Ye He, Jiaming Liang, Molei Tao, Yongxin Chen

cs.CC stat.MLcs.LGmath.ST ·submitted 2026-11-02 16:55 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions

cs.LG math.STmath.PR ·2026-09-11 ·Weiming Ou, Xiao Wang
hot direction similarity 0.78
Abstract · Under Review

We establish the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in every fixed dimension $d\geq1$. For $μ$-strongly convex, $L$-smooth potentials with unknown minimizers $x_f^\star$ in the ball $\mathbb{B}(0,μ^{-1/2})$, and unbiased gradient oracles with variance at most $σ^2$, the minimax worst-case expected query complexity is $Θ\left(\log(1+κ)+\frac{σ^2}{μ\varepsilon}\right)$, jointly optimal for the condition number $κ:=L/μ$, variance $σ^2\ge 0$, and TV accuracy $0<\varepsilon\leq 1/10$. In the noiseless setting $σ=0$, this tight complexity $Θ\left(\log(1+κ)\right)$ is independent of $\varepsilon$. Moreover, a gradient-only sampler generates an exact sample with ${O}(\log(1+κ))$ worst-case expected queries. Without previous ball $\mathbb{B}(0,μ^{-1/2})$, exact sampling from any initial point $x_0$ can be implemented with expected cost ${O}\left(\log(1+κ)+\log(1+\sqrtμ\|x_0-x_f^\star\|)\right)$, without knowing the initial distance. We also show that dependence on initial distance is generally unavoidable.

0.25

Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities

cs.CC cs.DSmath.STstat.ML ·2026-11-04 ·Huanjian Zhou, Taiji Suzuki
theory similarity 0.77
Abstract

We study the query complexity of sampling from smooth distributions on $\mathbb R^d$ using first-order oracles. For $d$-dimensional strongly log-concave targets with condition number $κ=2$, we prove that any randomized sampler requires $\exp({Ω(\log^{1/3} d)})$ queries even from a constant warm start. This rules out polylogarithmic dimension dependence and strictly separates strongly log-concave sampling from Gaussian sampling. For targets with $L$-smooth potentials satisfying an $α$-log-Sobolev inequality with $κ= L/α$, we prove an $Ω(κ)$ query lower bound for $d\gtrsim\log^2κ$. This shows that log-Sobolev sampling is strictly harder than strongly log-concave sampling. Our proofs construct instance-dependent tests that target samples typically pass but outputs of algorithms making few queries typically fail. For strongly log-concave targets, we embed a sequence of hidden Gaussian into high-degree tensor polynomial with smooth gates, forcing any algorithm to uncover the layers sequentially. The log-Sobolev construction hides a constant fraction of the target mass in angular caps while controlling the log-Sobolev constant via delicate estimates.

0.06

Accelerated High-Accuracy Sampling from a Warm Start via the Proximal Bouncy Particle Sampler

cs.DS math.STcs.LGmath.PR+1 ·2026-09-07 ·Fan Chen, Sinho Chewi, Jianfeng Lu, Matthew S Zhang
highly cited similarity 0.72
Abstract

We study the problem of sampling from $μ(\mathrm{d}x)\propto e^{-V(x)}\,\mathrm{d}x$ on $\mathbb{R}^d$, where $V$ is $α$-strongly convex and $β$-smooth, and write $κ:=β/α$. We design and analyze the Proximal Bouncy Particle Sampler (Proximal BPS), a new sampler that combines ideas from the proximal sampler and the bouncy particle sampler. From a warm start initialization with $ O(1) $ Rényi divergence w.r.t. $μ$, Proximal BPS returns a sample whose law is $\varepsilon$-close to $μ$ in total variation distance using $\widetilde O(\sqrtκ\,d^{1/4} \,\mathrm{polylog}(1/\varepsilon))$ gradient queries in expectation.

0.57

Penalized Nonreversible Langevin for Constrained Sampling

cs.LG stat.MLmath.PR ·2026-09-21 ·Pervez Ali, Weihao Dong, Xiaoyu Wang
similarity 0.71
Abstract · 68 pages, 8 figures

We propose penalized nonreversible Langevin algorithms for sampling from $π(x)\propto e^{-f(x)}\mathbf 1_{\mathcal C}(x)$, where $\mathcal C\subset\mathbb R^d$ is a compact convex set. The algorithms combine a squared distance penalty with constant or compatible state dependent skew symmetric perturbations that preserve the penalized Gibbs distribution. For smooth, possibly nonconvex $f$, we derive nonasymptotic total variation bounds for the full gradient algorithm under a log Sobolev inequality. When unbiased stochastic gradients are available, we establish $2$-Wasserstein bounds under global contraction and Lipschitz conditions on the full drift in an adapted quadratic metric. For a fixed penalty parameter, the error relative to the penalized Gibbs distribution decays exponentially to an $\mathcal{O}(\sqrtη)$ neighborhood, where $η$ is the stepsize. We also bound the discrepancy between the penalized Gibbs distribution and the constrained target. In a two dimensional quadratic model, we establish nonreversible acceleration by tuning the skew perturbation to the curvature imbalance induced by penalization. With the target accuracy and smaller curvature fixed and initial Wasserstein distances uniformly bounded, tuning the skew perturbation improves the sufficient Euler iteration bound from linear to logarithmic in the curvature ratio. Numerical experiments evaluate the algorithms on constrained Bayesian regression, classification, neural networks, and truncated sampling, and examine the acceleration mechanism in a stochastic quadratic model.

0.17

Near-Linear Accuracy Bounds for Moreau--Yosida Unadjusted Langevin Sampling

cs.LG ·2026-09-30 ·Yuchen Xin, Zhihua Zhang
similarity 0.71
Abstract

We establish near-linear accuracy bounds for the classical Moreau--Yosida unadjusted Langevin algorithm (MYULA). The target is $π\propto e^{-f-g}$, where $f\in C^2(\mathbb{R}^d)$ is $m$-strongly convex with Lipschitz gradient and $g$ is convex and globally Lipschitz. Under an explicit parameter-dependent step-size condition, we bound the invariant-measure bias relative to the Moreau-smoothed target by $\widetilde O(h)$, with only logarithmic dependence on the inverse smoothing parameter in the error coefficient. Combining this estimate with the Moreau approximation bias and Wasserstein contraction gives $\widetilde O(\varepsilon^{-1})$ iterations to make the $N$th-iterate law $μ_N$ satisfy $\sqrt m\,W_2(μ_N,π)\le\varepsilon$, for fixed model parameters and initialization. We bound the stationary error directly, without assuming third derivatives or a Lipschitz Hessian. Each iteration uses one gradient evaluation and one exact proximal evaluation. The key idea in our analysis is to convert a second-order stationary residual into a Wasserstein bound using a Poisson-based estimate.

0.07

Sharp Lower Bounds for Parallel Log-Concave Sampling

cs.DS math.PR ·2026-11-11 ·Evan Dogariu
theory similarity 0.71
Abstract

How many rounds of parallel queries are needed to sample from a smooth, strongly log-concave distribution on $\mathbb{R}^d$? For every fixed condition number $κ\in (1, \infty)$, we prove that any sampler making polynomially many queries per round requires $Ω_κ(\log d)$ rounds to achieve constant total variation error in the worst case. The lower bound holds even if queries return derivatives of all orders. Together with the first-order parallel Picard algorithm of \cite{zhou2025parallel}, this establishes a depth complexity of $Θ_κ(\log d)$ for parallel log-concave sampling with $\operatorname{poly}(d)$ width. We then study centered Gaussian targets to understand how much width is needed at a given depth. From \cite{chewi2023query,zhou2026complexitygaussiansampling}, it is known that either one round of width $d$ or $\mathcal{O}(\sqrtκ \log d)$ rounds of constant width suffice for first-order Gaussian sampling. At fixed $κ$ we characterize the depth-width tradeoff interpolating between these regimes: when using $ \lceil c \log d\rceil$ rounds, if $0 < c < c_\star(κ)$ then the optimal width at constant TV error is $\widetildeΘ(d^{1-c/c_\star(κ)})$, while if $c \geq c_\star(κ)$ then it is $Θ_κ(1)$. Here, $c_\star(κ)$ is an explicit constant with $c_\star(κ) \sim \sqrtκ / 8$ as $κ\to \infty$.

0.05

Quantum Speedups for Log-Concave Sampling from Local Structure

cs.DS quant-ph ·2026-08-14 ·Chenghua Liu, Qisheng Wang, Zhengfeng Ji
similarity 0.70
Abstract

For a convex function $f \colon \mathbb{R}^d \to \mathbb{R}$, the problem of sampling from a distribution proportional to $e^{-f(x)}$ is called log-concave sampling. In many practical scenarios, the function $f(x)$ turns out to admit a local decomposition $f(x) = \sum_{a=1}^R ψ_a(x_{S_a})$. In this paper, we consider log-concave sampling using local queries, i.e., evaluation and gradient queries to each clause $ψ_a(\cdot)$, which can be computationally much cheaper than the queries to $f(x)$ itself. We show that if each coordinate appears in only a small number of clauses, there is a quantum algorithm for strongly log-concave sampling using $\widetilde{O}(\sqrtκd)$ local queries, where $κ$ is the condition number. This improves the prior best classical result $\widetilde{O}(κd)$ due to Ascolani, Lavenant, and Zanella (Ann. Probab. 2026) and the quantum result $\widetilde{O}(\sqrtκ d^2)$ implied by Childs et al. (NeurIPS 2022). Our quantum sampler applies to a broad class of locally structured models from statistical computing and machine learning, with representative examples including Gaussian Markov random fields, finite-element latent Gaussian models, and sparse generalized linear models. These results demonstrate that local structure is not merely an implementation detail, but a quantum algorithmic resource for high-dimensional sampling.

0.04

On Complexity of Gaussian Sampling

cs.CC stat.CO ·2026-10-14 ·Huanjian Zhou, Taiji Suzuki
theory similarity 0.70
Abstract · 36 pages

We study the number of exact matrix-vector queries needed to sample a centered $d$-dimensional Gaussian with condition number at most $κ$ to total variation error $\varepsilon$. The best known algorithm uses $O(\min\{d,\sqrtκ\log(\frac{d}{\varepsilon})\})$ queries, while the known lower bounds do not grow as $\varepsilon\to0$ and match this bound only for $κ\le d^{1/5-δ}$ at constant accuracy. We introduce a construction based on a hidden determinant sign and prove a lower bound of $Ω\!\left(\min\left\{d,\sqrtκ\log\left(1+\frac{d}{\sqrtκ\,\varepsilon}\right)\right\}\right)$ uniformly for all $d\ge1$, $κ\ge4$, and $0<\varepsilon\le\tfrac{1}{16}$. This bound matches the known upper bound up to constant factors whenever $κ\le d^{2-δ}$ for fixed $δ\in(0,2)$, or $\varepsilon\le d^{-c}$ for fixed $c>0$. We also extend a recent fixed-spectrum construction with a hidden eigenbasis from $κ=2$ to $2\leκ\le d^{1-δ}$, for any fixed $δ\in(0,1)$. This gives an $Ω_δ(\sqrtκ\log d)$ lower bound at constant accuracy that holds even when the spectrum of the precision matrix is known to the algorithm.

0.13