首次证明扩散采样所需查询次数下界，揭示多尺度噪声的必要性。
Query Lower Bounds for Diffusion Sampling
- 基于信息论，推导出高维扩散采样最低查询次数
- 在多项式精度下，需至少约√d次自适应查询
- 解释为何实际中必须使用多尺度噪声调度
扩散模型通过迭代查询学习到的梯度估计生成样本。尽管加速采样、减少梯度评估次数的研究日益增多，但此类加速的信息论极限仍不清晰。本文首次建立了扩散采样中梯度查询的下界。我们证明：对于d维分布，在任意L^p意义下梯度估计具有多项式精度ε = d^{-O(1)}时，任何采样算法都至少需要˜Ω(√d)次自适应梯度查询。特别地，我们的证明表明，任何采样器必须在˜Ω(√d)个不同的噪声级别上搜索，为实践中多尺度噪声调度的必要性提供了形式化解释。
原文摘要 · Abstract (English)
Diffusion models generate samples by iteratively querying learned score estimates. A rapidly growing literature focuses on accelerating sampling by minimizing the number of score evaluations, yet the information-theoretic limits of such acceleration remain unclear. In this work, we establish the first score query lower bounds for diffusion sampling. We prove that for $d$-dimensional distributions, given access to score estimates with polynomial accuracy $\varepsilon=d^{-O(1)}$ (in any $L^p$ sense), any sampling algorithm requires $\widetildeΩ(\sqrt{d})$ adaptive score queries. In particular, our proof shows that any sampler must search over $\widetildeΩ(\sqrt{d})$ distinct noise levels, providing a formal explanation for why multiscale noise schedules are necessary in practice.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。