CS Paper Radar

Lower Bounds for Parallel Diffusion Sampling

Yiwen Kou, Yimeng Wang

cs.DS cs.AIcs.CCcs.LGstat.ML ·submitted 2026-10-06 22:09 UTC · v2
theoryhot direction

Abstract

Standard diffusion samplers generate samples through sequential evaluations of a learned score function, with each query depending on previous answers. Parallel samplers seek to accelerate this process by making multiple score queries simultaneously. We ask how many adaptive rounds are necessary when each round allows polynomially many queries. We establish the first polynomial lower bounds on the round complexity of diffusion sampling with approximate scores satisfying a mean-square accuracy guarantee. Specifically, we prove (1) a $\widetildeΩ(d^{1/3})$-round lower bound for sampling smooth, near-isotropic Gaussian mixtures in $\mathbb{R}^d$, and (2) a tight $Ω(d)$-round lower bound for uniform sampling from anisotropic axis-aligned boxes contained in the unit ball. Both bounds hold for arbitrary randomized algorithms making polynomially many queries per round at arbitrary locations and noise levels, with inverse-polynomial score error and constant total variation accuracy. Our near-isotropic construction follows the blockwise approach of earlier lower bounds for parallel matroid search and discrete sampling \cite{KUW85,AGR24}. We use independent coordinate blocks containing random codebooks with well-separated rates and construct approximate score oracles whose responses in each block depend on consistency tests in earlier blocks. Together, the rate separation and these tests ensure that each round reveals information about at most one additional block with high probability.

Closest papers

Nearest neighbours by meaning across the whole index.

Sharp Lower Bounds for Parallel Log-Concave Sampling

cs.DS math.PR ·2026-11-11 ·Evan Dogariu
theory similarity 0.69
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

Randomization Beyond Deterministic Adaptivity in Parallel Sampling

cs.IT ·2026-10-02 ·Da Li, Bo Jin, Xiaopeng Wei
similarity 0.67
Abstract · 20 pages

Parallel samplers, including masked diffusion models, generate several coordinates per round from conditional marginals, and their accuracy depends on which coordinates are revealed together. A schedule can be improved in two natural ways: adaptively, by choosing later batches from the values already generated, or by randomization, by drawing the schedule at random. We show that randomization is strictly more powerful. For every $r \geq 1$ we construct a full-support distribution on $9r$ binary coordinates such that every deterministic three-round sampler, even with value-dependent batches and arbitrary product kernels, has forward Kullback-Leibler divergence at least $γr - \log 4$ with $γ\approx 0.0966$, whereas drawing one of four fixed schedules with two fair bits drives the divergence below $18 r β^r$ with $β\approx 0.966$. Both samplers query conditionals of the same target. The separation holds for every fixed number of rounds $T \geq 2$, a strict advantage survives perturbations of the target and errors in the conditional predictor, and exact rational arithmetic certifies the gap at nine coordinates, where trained neural predictors preserve it. The mechanism is a hidden mixture: each schedule preserves the dependence pattern of one component, while no deterministic first batch can serve them all.

0.47

Provably adaptive sampling with uniform and remasking discrete diffusion models

cs.LG cs.ITmath.STstat.ML ·2026-08-24 ·Daniil Dmitriev, Zhihan Huang, Yuting Wei
similarity 0.63
Abstract · 37 pages, 4 figures

Discrete diffusion models offer a promising alternative to autoregressive generation by enabling parallel updates, but their sampling efficiency can depend strongly on the choice of the forward process and the sampler. For the uniform forward process, existing lower bounds for the standard $τ$-leaping sampler scale linearly with the ambient dimension $d$, raising the question of whether this dependence is intrinsic to the forward process. We answer this question in the negative. We consider a first-order sampler based on the leave-one-out denoiser for uniform and remasking processes whose coordinate updates can be performed in parallel. In both cases, the sampler can correct denoising mistakes during the sampling process, which becomes necessary when many coordinates are updated together. Our main result establishes an adaptive sampling guarantee: up to logarithmic factors, $N = O(\mathrm{DTC}(X_0) / \varepsilon)$ discretization steps suffice to achieve sampling error $O(\varepsilon_{\mathrm{score}}+\varepsilon)$, where $\varepsilon_{\mathrm{score}}$ is the error in score estimation. Thus, the sampling complexity is governed by the intrinsic dependence structure of the target distribution, as measured by its dual total correlation $\mathrm{DTC}(X_0)$, rather than directly by the ambient dimension $d$. Our analysis proceeds through a Bayes-optimal auxiliary sampler that separates discretization error from score-estimation error. We also derive an exact information-theoretic representation of the discretization error in terms of the mutual information between different coordinates of the forward process at different times. This representation applies to general forward processes and, in the uniform and remasking cases, can be controlled by $\mathrm{DTC}(X_0)$. Numerical experiments on structured synthetic distributions illustrate the predicted dimension-adaptive behavior.

0.60

Polytope Sampling at the Speed of Isoperimetry

cs.DS math.OCmath.PR ·2026-10-16 ·Anming Gu, Bobby Shi, Kevin Tian, Hubert Yang
similarity 0.63
Abstract · 58 pages

We give faster algorithms for sampling from the uniform distribution over a polytope. Our main result is an algorithm that, when applied to a polytope with $m$ constraints in $n$ dimensions, uses $m \cdot \mathrm{poly}\log(\frac m δ)$ iterations, each running in time $O(mn^{ω- 1})$, to return a sample within total variation distance $δ$ to the uniform distribution. When $m =O(n)$ and $δ= \mathrm{poly}(\frac 1 n)$, our runtime improves upon all prior works by an $Ω(n^{2/3})$ factor. Our sampler is based on the recent \emph{functional stochastic localization} framework of [GST26], and achieves an iteration count nearly matching the Poincaré constant of the uniform distribution with respect to the logarithmic barrier.

0.33

On Complexity of Gaussian Sampling

cs.CC stat.CO ·2026-10-14 ·Huanjian Zhou, Taiji Suzuki
theory similarity 0.63
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

Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization

cs.LG stat.ML ·2026-10-14 ·Haowei Wang, Yilin Zheng
theoryhot direction similarity 0.62
Abstract

Efficient global optimization aims to identify a global optimum of an expensive black-box function within a limited evaluation budget $N$. We investigate the convergence rates of Gaussian process Thompson sampling (GP-TS) under noiseless observations, assuming a fixed objective function in a reproducing kernel Hilbert space (RKHS). For Matérn kernels with smoothness parameter $ν$ in dimension $d$, we establish a worst-case expected simple-regret upper bound of $O(N^{-ν/d}\sqrt{\log N})$ for both discrete GP-TS on sufficiently fine grids and its continuous counterpart. For the continuous implementation, we develop a nested-grid argument to control posterior sample paths over the entire domain. We further establish matching lower bounds of $Ω(N^{-5/2}\sqrt{\log N})$ for both implementations under a fixed one-dimensional Matérn-$5/2$ kernel, demonstrating that the logarithmic penalty is intrinsic to standard GP-TS in this setting. Motivated by this limitation, we propose Gaussian Process Capped Thompson Sampling (GP-CTS), which caps posterior sample paths using a valid RKHS norm upper bound while preserving optimism. This modification successfully eliminates the logarithmic penalty and achieves the minimax-optimal rate $Θ(N^{-ν/d})$ for both discrete and continuous implementations.

0.28

Subpolynomial-Query Proximal Sampling Beyond Log-Concavity

cs.CC stat.MLcs.LGmath.ST ·2026-11-02 ·Wei Guo, Bo Yuan, Ye He, Jiaming Liang, Molei Tao +1 more
theory similarity 0.62
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.

0.17

Sample-Optimal Estimation of the Fréchet Inception Distance

cs.LG cs.CVcs.DSmath.ST+1 ·2026-10-05 ·Ziyun Chen, Jerry Li, Kevin Tian, Yusong Zhu
code/datahot direction similarity 0.61
Abstract · Our code is available at https://github.com/zys996/sample-optimal-fid-estimation

The Fréchet Inception Distance (FID) is widely used to evaluate generative models, but its empirical plug-in estimator suffers from finite-sample bias [BSAG18, CF20]. We study the sample complexity $n$ of estimating FID to error $ε$ between $d$-dimensional Gaussians with bounded mean distance and covariances, when one distribution is known. Our contributions are threefold. (1) We establish tight finite-sample $Θ(\frac{d^2}{n})$ bias and $Θ(\frac{d}{n} + \frac {d^2} {n^2})$ variance bounds for the empirical plug-in estimator, establishing a $\gtrsim d^2$ sample complexity. (2) To debias the empirical plug-in estimator, we generalize the ${\rm FID}_\infty$ estimator of [CF20] to extrapolation methods of arbitrary order $k$. We further prove tight bias and variance bounds of $Θ(\frac{d^{k + 2}}{n^{k + 1}})$ and $Θ(\frac d n + \frac{d^2}{n^2})$ for any order-$k$ extrapolation under our framework. (3) We introduce Relative Taylor Debiasing (RTD), a new, computationally efficient FID estimation algorithm using debiasing techniques inspired by U-statistics. We show that RTD achieves an $O(\frac d {ε^2})$ sample complexity, and prove that this is optimal. We provide a complementary empirical evaluation of our new estimators. Our experiments on synthetic Gaussians validate the predicted residual bias and support the tightness of our bounds. On ImageNet with Inception embeddings, RTD achieves the lowest mean estimation error at the standard 50K sample budget, while our second-order variance-aware extrapolation estimator (VALE$_2$) uses only 10K samples to achieve accuracy comparable to FID$_\infty$ at 50K samples.

0.46