DDPM采样效率可自适应数据内在维度，理论证明其迭代复杂度近似线性于低维结构。
Denoising diffusion probabilistic models are optimally adaptive to unknown low dimensionality
- 利用数据内在低维特性，证明DDPM迭代次数近似线性于内在维度k
- 在使用KL散度衡量分布差异时，该复杂度达到理论最优
- 适用于理解生成模型高效采样的数学机制，适合研究者参考
去噪扩散概率模型（DDPM）已成为生成人工智能中的主流生成模型。尽管已有严格的收敛保证，但其迭代复杂度通常与数据的环境维度成正比，导致理论过于保守，无法解释实际效率。这促使近期工作Li和Yan（2024a）研究DDPM如何通过自动利用数据的内在低维性实现采样加速。本文在此基础上进一步证明：在一类广泛的数据分布中，DDPM的迭代复杂度几乎随内在维度k线性增长，当使用KL散度衡量分布差异时，这一结果是理论上最优的。值得注意的是，本工作与独立并发研究Potaptchik等（2024）高度一致——后者在本文发布前两周已提出类似近乎线性-k的收敛保证。
原文摘要 · Abstract (English)
The denoising diffusion probabilistic model (DDPM) has emerged as a mainstream generative model in generative AI. While sharp convergence guarantees have been established for the DDPM, the iteration complexity is, in general, proportional to the ambient data dimension, resulting in overly conservative theory that fails to explain its practical efficiency. This has motivated the recent work Li and Yan (2024a) to investigate how the DDPM can achieve sampling speed-ups through automatic exploitation of intrinsic low dimensionality of data. We strengthen this line of work by demonstrating, in some sense, optimal adaptivity to unknown low dimensionality. For a broad class of data distributions with intrinsic dimension $k$, we prove that the iteration complexity of the DDPM scales nearly linearly with $k$, which is optimal when using KL divergence to measure distributional discrepancy. Notably, our work is closely aligned with the independent concurrent work Potaptchik et al. (2024) -- posted two weeks prior to ours -- in establishing nearly linear-$k$ convergence guarantees for the DDPM.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。