arXiv：cs.LG· Yiwen Kou, Yimeng Wang·· 4 小时前AI 评分46
并行扩散采样首个多项式轮数下界：平滑高斯混合需 Ω̃(d^{1/3}) 轮，各向异性盒采样需 Ω(d) 轮
Lower Bounds for Parallel Diffusion Sampling
AI 导读
研究者为近似分数下的扩散采样建立了首个多项式并行轮数下界：在 R^d 中采样平滑近各向同性高斯混合需 Ω̃(d^{1/3}) 轮，从单位球内各向异性轴对齐盒中均匀采样需 Ω(d) 轮，后者对该盒族是紧的。两个下界对任意随机算法成立，即使每轮可在任意位置和噪声水平做多项式次查询，只要分数误差为多项式倒数、总变差精度为常数。
正文
Abstract:Standard diffusion samplers generate samples through repeated evaluations of a learned score function. Parallel sampling methods seek to accelerate generation by trading additional evaluations for fewer sequential rounds. This raises the question of how much sequential dependence is unavoidable, even when many score queries can be made simultaneously.
We establish the first polynomial parallel-round lower bounds for diffusion sampling with approximate scores. Specifically, we prove (1) a $\widetilde{\Omega}(d^{1/3})$-round lower bound for sampling smooth, near-isotropic Gaussian mixtures in $R^d$, and (2) an $\Omega(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. The linear bound is tight for our box family. Our constructions use fixed approximate score oracles that enforce sequential access to hidden information while satisfying the accuracy guarantee at every noise level.
| Subjects: | Data Structures and Algorithms (cs.DS); Artificial Intelligence (cs.AI); Computational Complexity (cs.CC); Machine Learning (cs.LG); Machine Learning (stat.ML) |
| Cite as: | arXiv:2610.09166 [cs.DS] |
| (or arXiv:2610.09166v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2610.09166 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Yiwen Kou [view email]
[v1]
Tue, 6 Oct 2026 22:09:42 UTC (191 KB)
来源：arXiv：cs.LG · arxiv.org