Denoising growth complexity: Data geometry and certified schedules for diffusion sampling

技术摘要：去噪增长复杂度与认证扩散采样

问题陈述
基于扩散的采样方法在生成高维数据方面展现了卓越的有效性，然而两个核心挑战仍然存在：(1) 在通用最坏情况复杂度界限暗示其会失败的情况下，从理论上理解这些方法为何成功；(2) 实际设计具有认证性能保证的算法。本文旨在通过一种与数据几何相关的度量来解释扩散采样的性能，并利用该度量来设计并认证实用的采样方案。

方法论
作者分析了基于高斯热流（Gaussian heat flow）的扩散采样器，特别关注于应用于随机创新（stochastic innovations, SI）表示下的逆向过程的标准欧拉离散化变体。其方法论的核心是引入并分析了一种新的几何度量，称为去噪增长复杂度（Denoising Growth Complexity, DGC）。

• DGC 函数： 定义为沿热路径的去噪均方误差（MSE）导数的对数时间加权积分。若 $h(t)$ 表示时间 $t$ 处的 MSE，则区间 $[a, b]$ 上的 DGC $H(a, b)$ 为：
  $$H(a, b) := \frac{1}{2} \int_a^b \frac{h'(t)}{t} dt$$
• 随机创新表示： 分析利用了向随机定位（stochastic localization, SL）或创新空间的转换，在该空间中，逆向过程被视为由布朗运动和最优去噪器驱动的前向 SDE。这使得推导欧拉离散化误差的过程更加清晰。
• 局部误差分析： 本文确立了欧拉方案单步的 KL 离散化误差受该步的 DGC 增量及相对步长的控制。随后，该局部界限在整个路径上进行聚合。

主要贡献

1. 主要理论保证（定理 1）：
   本文提供了目标分布与 SI-Euler 方案输出之间的 KL 散度显式上界。该界限是局部项之和，每一项都受 DGC 增量 $H(t_{j+1}, t_j)$ 和步长比率 $(t_j/t_{j+1} - 1)$ 的控制。
   $$D_{KL}(P_\delta \| Q_\delta) \leq \sum_{j=0}^{N-1} \left( \frac{t_j}{t_{j+1}} - 1 \right) H(t_{j+1}, t_j) + D_{KL}(P_T \| Q_T)$$
   该结果恢复并强化了现有的维度相关和维度无关的保证，且无需复杂的分析（证明过程被指出仅需三页左右的基础分析）。

2. 数据认证算法：
   利用去噪函数沿热路径的鞅结构（martingale structure），作者开发了一种从数据样本中估计 DGC 增量的方法。

   • 他们引入了一个“去噪增量” $D(s, t)$，可以通过蒙特卡洛方法进行估计。
   • 证明了一个“夹逼关系”：$D(s, t)/t \leq 2H(s, t) \leq D(s, t)/s$。
   • 这使得构建完全数据认证的步长调度成为可能。该算法可以估计实现目标精度所需的迭代次数，且能以高概率实现，仅需使用来自目标分布（或留出集）的样本，而无需了解真实的得分函数（score function）。

3. 单块（Single-Block）与多块（Multi-Block）调度：

   • 单块： 在整个路径上采用常数乘子 $\rho$ 的几何调度，其复杂度界限与 $H(\delta, T) \log(T/\delta)$ 成正比。
   • 多块（K-Block）： 通过将路径划分为 $K$ 个块并为每个块分配最优几何乘子，其复杂度由基于 DGC 的划分复杂度 $C_{DGC}(P) = (\sum \sqrt{S_k H_k})^2$ 控制，其中 $S_k$ 是第 $k$ 个块的对数时间长度。
   • 细分极限： 当 $K \to \infty$ 时，复杂度收敛于一个涉及对数时间 DGC 密度 $q(r) = h'(\delta e^r)$ 平方根积分的量。具体而言，该极限取决于 $(\int \sqrt{q(r)} dr)^2$，而单块方案则取决于 $\int q(r) dr$。

4. 信息论联系：
   DGC 被证明在互信息和率失真理论方面具有等价表示。这建立了采样复杂度与以下各项的联系：

   • 协方差结构（恢复线性维度缩放）。
   • 度量熵和内在维度（恢复与内在维度的线性缩放）。
   • 香农率失真函数。
   • 庞卡莱常数（yielding 对条件数呈对数依赖关系）。

结果与具体发现

• 维度缩放： 单块方案通过基于协方差的界限，恢复了对环境维度 $d$ 的线性依赖关系，且没有对数开销。
• 高斯混合模型（GMMs）： 对于简单的 GMM，本文展示了单块与多块复杂度之间的分离。在特定的层次化 GMM 中，多块方法可以将复杂度从关于分离比率的对数级（$\log(R^2/\delta)$）降低到常数级或迭代对数级，具体取决于块的数量 $K$。
• 庞卡莱常数： 对于满足庞卡莱不等式的分布，迭代复杂度被证明对庞卡莱常数呈对数依赖，这优于以往依赖于更强对数凹性假设的结果。
• 数据认证： 本文提供了一个具体的程序（命题 1），能够以高概率置信区间从数据中估计 DGC 函数，从而实现选择能保证 $\epsilon$-精度 KL 散度的迭代预算。

意义与主张
本文声称为两个基本问题提供了肯定的回答：

1. 解释： 扩散采样的性能可以通过 DGC 来解释和量化，DGC 是一个与数据分布在热流下演化的几何度量。
2. 认证： 这种几何度量可以被用来设计具有严格的、数据依赖的性能保证的采样方案。

作者强调，我们的方法在单一、简单的理论框架下统一并强化了广泛的现有结果（涵盖维度缩放、内在维度、流形结构和混合模型）。一个关键的新颖之处在于，能够通过适应数据的特定几何特性（通过 DGC 剖面）来设计步长调度，从而在多块设置中获得计算增益，特别是当 DGC 密度的“分布”允许相比于均匀或单块调度实现显著的迭代复杂度降低时。这项工作填补了理论复杂度分析与实用的、认证算法设计之间的鸿沟。