提出几何度量DGC,统一解释扩散采样为何高效并设计可证明性能的采样方案。
Denoising growth complexity: Data geometry and certified schedules for diffusion sampling

- 用数据几何的DGC度量刻画扩散过程的复杂性
- 给出基于DGC的KL误差上界,支持优化步长调度
- 实现数据自适应的可证明性能采样,适用于高维数据
扩散采样中的两个核心挑战是:理论上理解其在高维空间中为何依然有效,以及实践中设计具有可证明性能保证的算法。本文揭示这两个问题通过「去噪增长复杂度」(DGC)紧密关联。DGC 是沿高斯热流对去噪均方误差导数进行时间加权积分的几何度量。我们证明,DGC 的增量可直接导出欧拉方案在随机创新表示下的 KL 误差上界,该上界沿路径局部控制:每一步由对应 DGC 增量及其相对步长决定。此结构使我们能推导出单块与多块(K-块)设置下优化步长策略的 KL 采样保证。DGC 具有自然的鞅结构,可用于开发完全数据认证的算法。它还可在协方差、率失真、度量熵和庞卡莱常数等信息论框架下获得上界,从而恢复并强化多种已有扩散采样保证,并得出新结果。在对数热时序下,精细划分极限由 DGC 密度平方根的积分主导;而单块调度依赖于其普通积分。这一对比精确刻画了利用数据几何带来的计算增益条件,包括对简单高斯混合模型实现对数到常数的分离。
原文摘要 · Abstract (English)
Two central challenges in diffusion-based sampling are the theoretical one of understanding their remarkable effectiveness even in high-dimensional settings, and the practical one of designing algorithms with certified performance guarantees. We show that these questions are intimately connected via the \emph{denoising growth complexity} ($\mathsf{DGC}$). It is a geometric measure defined by a log-time weighted integral of the derivative of the denoising mean-squared error along the Gaussian heat flow. We show how the $\mathsf{DGC}$ increments lead to a simple and explicit bound on the KL error of an Euler scheme applied to the stochastic innovations representation. The bound is local along the path: each step is controlled by the corresponding $\mathsf{DGC}$ increment and its relative stepsize. This structure allows us to derive KL sampling guarantees for optimized stepsize schedules, both in a simpler single-block setting and in a more refined $K$-block setting. The $\mathsf{DGC}$ function has a natural martingale structure, which we exploit to develop fully data-certified versions of these algorithms. It also admits information-theoretic upper bounds in terms of covariance, rate distortion, metric entropy, and the Poincar'e constant, thereby recovering and sharpening a range of existing diffusion-sampling guarantees, as well as giving new results. In log heat-time, the fine partition limit is governed by an integral involving the square root of the $\mathsf{DGC}$ density, whereas a single-block schedule depends on its ordinary integral. This comparison precisely characterizes when adaptation to data geometry yields substantial computational gains, including logarithmic-to-constant separations for simple Gaussian mixture models.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。