ICLR 2026 学习理论扩散模型扩散采样信息-计算 gap 分数匹配计算下界稀疏低秩矩阵

Computational Bottlenecks for Denoising Diffusions¶

会议: ICLR 2026
OpenReview: https://openreview.net/forum?id=rAjHUNXybH
代码: 无
领域: 学习理论 / 扩散模型
关键词: 扩散采样、信息-计算 gap、分数匹配、计算下界、稀疏低秩矩阵

一句话总结¶

本文证明：只要一个分布 $\mu$ 对应的去噪问题存在"信息-计算 gap"，那么哪怕从 $\mu$ 直接采样很容易，用去噪扩散采样也必然失败——既存在分数匹配近优却采样完全跑偏的漂移，所有 Lipschitz 的多项式时间近优漂移也都会失败，并用稀疏低秩矩阵这个玩具例子给出了理论与数值上的双重佐证。

研究背景与动机¶

领域现状：去噪扩散（diffusion sampling, DS）已经是生成式 AI 的核心范式。要从目标分布 $\mu$ 采样，DS 构造一个随机过程 $(\hat x_t)$，让大时刻 $T$ 的 $\hat x_T$ 近似服从 $\mu$。它把"采样"这个难题归约成"逼近一个漂移函数 $m(y,t)$"，而这个漂移恰好就是高斯噪声下的贝叶斯最优去噪器 $m(y,t)=\mathbb{E}\{x\mid tx+\sqrt{t}\,g=y\}$，通过最小化分数匹配（score-matching）目标来学。这里时间 $t$ 可以解读成去噪问题的信噪比（SNR）。

现有痛点：绝大多数 DS 的理论文献关心的是"有限样本 $N$"或"非零步长 $\Delta$"带来的采样质量下降。但还有一个更本质、却被回避的限制：$\hat m$ 必须是多项式时间可计算的。这个约束即使在拥有 $\mu$ 全部信息（$N=\infty$）时也存在——它纯粹是计算上的。

核心矛盾：统计估计领域早就发现存在"信息-计算 gap"：某些问题里，最优估计器能达到很小的误差，但所有多项式时间算法都被一道墙挡住、达不到这个误差（在 P$\neq$NP 类的猜想下严格成立）。既然 DS 的漂移就是去噪器，一个自然的猜想是：去噪有 gap $\Rightarrow$ DS 失败。Koehler & Vuong (2024) 非正式地提过这点，但严格来说这句话是错的：如果从 $\mu$ 采样容易，完全可以构造一个漂移让它在 $t\ge t_0$ 时直接吐出一个固定样本 $x\sim\mu$，这样扩散采样是对的——只不过这个漂移离最优去噪器非常远（本文 Proposition 2.1 给出了形式化的反例）。所以"gap $\Rightarrow$ DS 失败"远没有看上去那么显然。

本文目标：把上面这个被多篇物理 / 贝叶斯统计文献观察到、但从没被严格证明过的现象补全——在什么意义下"去噪有 gap"会真正导致"DS 失败"？

切入角度：不去纠结某个具体漂移，而是直接刻画"分数匹配近优"这个学习目标本身的盲区：是不是存在分数匹配几乎最优、采样却烂到极致的漂移？最优的那个漂移会不会反而采样很好？

核心 idea：把 DS 的失败严格归因于"用多项式时间函数逼近贝叶斯最优去噪器"这一计算要求——只要去噪问题有信息-计算 gap，分数匹配这条路就找不到能正确采样的漂移。

方法详解¶

整体框架¶

本文是一篇理论论文，主体是一组关于"扩散采样何时必然失败"的不可能性定理。整条逻辑链是：先把 DS 改写成一个去噪（denoising）问题——漂移 $m(y,t)$ 就是从 $y_t=tx+W_t$ 估计 $x$ 的贝叶斯最优估计器，$t$ 是 SNR；然后引入一个算法阈值 $t_{\mathrm{alg}}$，假设在它以下所有多项式时间去噪器都好不过常数估计器、在它以上存在可靠的多项式时间检测；在这两条假设下推出两类失败结论，再补一个反向归约把整个"估计 $\leftrightarrow$ 采样"的等价性闭环。

具体而言，结论分三块：(1) 定理 1 / 推论 3.2——存在分数匹配近优（在多项式时间算法里近最优，且差距是超多项式小）却采样完全错误的漂移；(2) 定理 3 / 推论 5.1——再加一个 Lipschitz 条件，所有多项式时间的分数匹配近优漂移都采样错误，堵住"最优漂移也许采样好"的漏洞；(3) 定理 2 / 定理 5——反向归约：若能多项式时间精确 DS，则也能多项式时间近贝叶斯最优地估计 $x$，其逆否命题正是"有 gap $\Rightarrow$ 无法多项式时间正确 DS"。全文用稀疏低秩矩阵 $\mu_{n,k}$ 作为贯穿例子来实例化这些定理，并配一个 GNN 去噪器的数值实验佐证。

这套结论不依赖具体的网络结构或训练算法，而是关于"分数匹配这个目标 + 多项式时间这个约束"的内在缺陷——本质上是一个计算复杂性结论，而非优化或泛化结论。

关键设计¶

1. 核心视角：把"扩散能不能采样"翻译成"去噪有没有计算 gap"

扩散过程满足 $y_t = tx + W_t$（$W_t$ 为布朗运动），理想漂移 $m(y,t)=\mathbb{E}\{x\mid y_t=y\}$ 正是从高斯观测 $y_t\sim\mathcal{N}(tx, tI_d)$ 估计 $x$ 的 MSE 最优解，所以学漂移等价于做去噪、$t$ 充当 SNR。在此基础上，本文采用统计估计里的信息-计算 gap 定义：存在常数 $\mathrm{gap}(t)>0$，使得对所有多项式时间算法 $\hat m$、当 $d$ 足够大时 $$\mathbb{E}\big[\|\hat m(y_t)-x\|^2\big]\ \ge\ \inf_\phi \mathbb{E}\big[\|\phi(y_t)-x\|^2\big]+\mathrm{gap}(t).$$ 这个视角的价值在于：它把"扩散采样失败"这个看似动力学的问题，钉死在一个纯粹的计算复杂性事实上。但要让"gap $\Rightarrow$ 失败"成立并不平凡——Proposition 2.1 构造了一个反例：丢掉分数匹配近优性（M2）后，可以有多项式时间漂移让 $\mathbb{E}[\|\hat m(y_t,t)-x\|^2]=2(1-o(1))$（分数匹配很差）却 $W_1(\hat m(\hat y_{\ell\Delta},\ell\Delta), x)=0$（采样完美）。这说明：失败不是采样本身做不到，而是"沿着分数匹配去找漂移"这条路被 gap 堵死了，必须把"分数匹配近优"这个条件牢牢钉进结论里。

2. 定理 1：构造分数匹配近优、采样却完全跑偏的漂移

这是第一类不可能性。给定任意一个多项式时间漂移 $\hat m_0$，本文显式构造另一个多项式时间漂移 $\hat m$，让它的分数匹配值和 $\hat m_0$ 几乎一模一样、采样却"错到不能再错"。构造依赖两条假设：假设 1（阈值以下小范数）——在 $t<t_{\mathrm{alg}}$ 时，任何"好"的多项式时间漂移范数都很小（因为在 gap 区里它好不过常数估计器 $\mathbb{E}[x]\approx 0$，最优做法就是把输出收缩到接近零）；假设 2（阈值以上检测可靠）——存在多项式时间的二元检验 $\phi$，能可靠区分含信号的 $y_t=tx+W_t$ 与纯噪声 $\mathcal{N}(a,tI_d)$。构造方式是给 $\hat m_0$ 套上门控：$t\le(1-\gamma)t_{\mathrm{alg}}$ 时取 $\hat m_0(y,t)\mathbf{1}_{\|\hat m_0(y,t)\|\le\varepsilon}$，$t\ge(1+\delta)t_{\mathrm{alg}}$ 时取 $\hat m_0(y,t)\phi(y,t)$。

它为什么能两头讨好？在真实耦合 $(x,y_t)$ 上，门控几乎不改变 $\hat m_0$ 的取值，所以分数匹配差距被压到超多项式小：$\int_0^\infty \mathbb{E}[\|\hat m(y_t,t)-\hat m_0(y_t,t)\|^2]\,dt = O(\eta_1\vee\eta_2)$（推论 3.2 里是 $O(n^{-D})$，对任意 $D$ 成立，即 M2）。但 DS 真正跑的是自生成过程 $\hat y_t$，它从噪声起步、靠漂移自己往上爬：阈值以下的小范数截断让信号根本立不起来，等 $t$ 爬到 $t_{\mathrm{alg}}$ 时轨迹里压根没有信号可放大，检验 $\phi$ 一直把它判成噪声并门控掉。结果生成样本死死卡在 $0/\mathbb{E}[x]$ 附近，导致 $W_1(\hat m(\hat y_t,t),x)\ge\alpha-o_d(1)$（即 $W_1$ 拉满，M3）。

3. 定理 3：堵住 Lipschitz 漏洞，外加混合分布技巧

定理 1 只说"存在"坏的近优漂移，没排除"最优的那个漂移也许采样很好"。定理 3 把这个后路也堵上：只要漂移 $\hat m(\cdot,t)$ 在 $t\ge(1+\delta)t_{\mathrm{alg}}$ 上是 $C/t$-Lipschitz 的（取 $C/t$ 是因为输入 $y_t=tx+W_t$ 里两个 $t$ 因子相消），任何分数匹配近优的多项式时间漂移都采样错误，下界仍是 $W_1\ge\alpha-o(1)$。这个条件很自然——层数有界、权重算子范数受控的神经网络就在这一类里，所以它不是数学上的边角料。

为让"在纯噪声上小"这条技术条件（定理 3 的条件 2：$\Delta\sum_t\mathbb{E}[\|\hat m(W_t,t)\|^2]=o(1)$）成立，本文引入一个混合分布技巧：$\bar\mu_{n,k}=\tfrac12\delta_0+\tfrac12\mu^0_{n,k}$，即一半概率让 $x=0$、一半概率取中心化后的稀疏秩一矩阵。这样 MSE 自然分解成 $$\mathbb{E}_{x\sim\bar\mu_{n,k}}[\|\hat m(y_t,t)-x\|^2]=\tfrac12\mathbb{E}_{x\sim\mu^0_{n,k}}[\|\hat m(y_t,t)-x\|^2]+\tfrac12\mathbb{E}[\|\hat m(W_t,t)\|^2],$$ 要把第一项压小（拟合信号）就必须把第二项压小（在纯噪声上趋零），从而强制出"纯噪声上趋零"的性质。代价是误差基准从 1 变成 $1/2$（最优常数去噪器在混合分布上误差就是 $1/2$），所以推论 5.1 的下界是 $W_1\ge\tfrac12-o_n(1)$。

4. 定理 2：从扩散采样反向归约到去噪，闭合等价关系

前面是"去噪难 $\Rightarrow$ 采样难"，定理 2 补上反方向：如果能多项式时间、足够精确地做 DS（即离散插值轨迹与理想轨迹的 KL 散度 $D_{\mathrm{KL}}(\bar P^{T,\Delta}_{\hat y}\|P^T_y)\le\varepsilon$），那就能构造出一个随机算法 $\hat m_+$ 把后验期望估出来：$\mathbb{E}[\|\hat m_+(y)-m(y)\|^2]\le 2\bar\varepsilon+2N^{-1}$。它的逆否命题正好是"信息-计算 gap 存在 $\Rightarrow$ 无法多项式时间正确 DS"，与前面的不可能性结论方向一致，把"高效估计"和"高效扩散采样"两件事钉成等价。这意味着：凡是去噪侧已知有 gap 的问题，扩散这条路天然没有出路。

一个完整示例¶

用贯穿全文的稀疏低秩矩阵 $\mu_{n,k}$ 把抽象阈值落地。令 $u\sim\mathrm{Unif}(B_{n,k})$ 是只有 $k$ 个非零、取值 $\pm 1/\sqrt{k}$ 的单位向量，目标分布是 $x=uu^T$（$d=n^2$）。直接采样平凡：随手抽一个满足稀疏约束的 $u$、令 $x=uu^T$ 即可。但对应的去噪问题（从 $y_t=tx+W_t$ 里恢复 $uu^T$，本质是子矩阵定位 / 稀疏 PCA）有一道墙：贝叶斯阈值 $t_{\mathrm{Bayes}}=2k\log(n/k)$，算法阈值在中等稀疏区 $\sqrt n\ll k\ll n$ 时 $t_{\mathrm{alg}}=n/2$、在极稀疏区 $k\ll\sqrt n$ 时 $t_{\mathrm{alg}}=k^2\log(n/k^2)$。在 $t_{\mathrm{Bayes}}\ll t\ll n$ 这段区间里，最优估计器能准确恢复 $x$，但（在广为接受的 Conjecture 3.1 下）没有多项式时间算法能做到。把这个 gap 喂进定理 1 / 定理 3，就得到结论：哪怕采样本身一秒钟搞定，沿分数匹配训出来的多项式时间扩散一定采不对——它会把样本统统塞到接近 $0$ 的地方。这同一套定理还能套用到张量 PCA、随机线性码解码、低秩+噪声后验、随机约束满足问题等一系列同样有 gap 的分布上。

实验关键数据¶

主实验¶

数值实验用来佐证理论预言的失败模式，设定 $n=350$、$k=20$（落在中等稀疏区，$t_{\mathrm{alg}}=n/2$）。对比三种多项式时间去噪器：谱+投影（Algorithm 2）、用 25 步幂迭代近似特征向量再投影、以及学出来的图神经网络（GNN，因 25 步幂迭代可被 25 层 GNN 逼近，故 (b) 是 GNN 的基线）。

去噪器	$t<t_{\mathrm{alg}}$ 行为	$t>t_{\mathrm{alg}}$ 行为	是否越过阈值墙
谱算法 + 投影（Alg. 2）	MSE 居高	表现尚可	否
幂迭代 25 步 + 投影	MSE 居高	表现尚可	否
学习的 GNN 去噪器	MSE 居高（最低但仍卡墙）	表现最好	否

三者都在 $t_{\mathrm{alg}}=n/2$ 处撞墙：阈值以上表现都不错，但没有一个能越过 $t_{\mathrm{alg}}$ 这道屏障——验证了理论预言 1（学到的去噪器在 $t<(1-\delta)t_{\mathrm{alg}}$ 时 MSE 接近 $1/2$、在 $t>(1+\delta)t_{\mathrm{alg}}$ 时接近 $0$）。值得注意的是 GNN 确实优于谱算法及其幂迭代近似，但优势再大也跨不过计算墙。

采样分布¶

量	观测	理论预言
生成样本的 Frobenius 范数	直方图集中在接近 $0$（约 $0.006\text{–}0.014$）	应集中在 $0$（预言 2）
扩散样本与目标的 $W_1$ 下界	$\ge 0.48$（用 $\\|\cdot\\|_F$ 作 1-Lipschitz 检验函数读出）	$0.50$（渐近预言）

GNN 去噪器生成的样本范数贴近 $0$，与"样本被塞到原点附近"的预言吻合；实测 $W_1\ge 0.48$ 与理论渐近值 $0.50$ 几乎一致。

关键发现¶

失败的根因不是模型容量或训练不足——GNN 在阈值以上学得很好、阈值以下也是三者里最好的，但所有方法都被同一道 $t_{\mathrm{alg}}$ 墙挡住，这正是计算下界的指纹。
失败模式是"塌缩到原点"：生成样本范数趋零，意味着扩散根本没建立起信号结构，与定理 1/3 里"漂移在低 SNR 段被压成小范数、信号立不起来"的机制对得上。

亮点与洞察¶

把"扩散采样失败"严格钉在"信息-计算 gap"上，是把生成模型的可行性和统计估计的计算下界打通的一座桥——以前这是一句被反复观察却从没被证明的"民间智慧"，本文给了它形式化的骨架。
对"分数匹配近优却采样错"和"反例：分数匹配很差却采样对"（Proposition 2.1）的对照特别有启发：它说明问题不出在采样能力，而出在"用分数匹配当指南针"——当好漂移和坏漂移的分数匹配值只差超多项式小量时，这个目标根本分辨不出谁好谁坏。这提示：在有 gap 的分布上，最小化分数匹配也许压根不是找到好漂移的正确途径。
Lipschitz 条件这个落点很务实：它不是为了数学方便强加的，而是恰好覆盖了"层数有界、权重范数受控"的真实神经网络，让"所有 Lipschitz 优化器都失败"这个结论真正咬住实践。
混合分布 $\tfrac12\delta_0+\tfrac12\mu^0$ 这个小技巧很巧：它通过 MSE 的可分解性，把"在纯噪声上趋零"从一条难验证的技术条件变成训练目标自动强制的副产物。
一个可迁移的判据：拿到一个新分布想用扩散采样前，先问"它的去噪问题有没有计算 gap"——只要有，就该警惕扩散会塌缩，宁可换其他采样路径（如先采隐变量 $u$ 再算 $uu^T$）。

局限与展望¶

结论是条件性的：依赖信息-计算 gap 的猜想（如 Conjecture 3.1），而这类猜想本身是 P$\neq$NP 式的、目前无法无条件证明——这是该领域的固有限制，作者也坦承"条件性是迄今无法避免的"。
定理 3 只排除了 Lipschitz 的多项式时间近优漂移，原则上仍可能存在非 Lipschitz 的近优漂移采样得很好。不过作者论证：即便存在，由于它和坏漂移的分数匹配值只差超多项式小量，分数匹配也找不到它，所以实践意义有限。
假设 1、假设 2 的形式并不直接就是 gap 定义 (7)，作者只是论证"对一大类问题它们不蕴含 gap 就不成立"，但"假设 $\Leftrightarrow$ gap"的严格等价被留作未来工作。
实例化目前主要做到了稀疏低秩矩阵（外加张量 PCA、随机线性码等几个直接套用的例子）；贝叶斯后验、随机约束满足这类例子需要额外技术处理，本文只点到、留待后续。
数值实验规模偏小（$n=350$、GNN 只在约 3% 的全部可能输出上训练），主要起佐证而非压力测试作用。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次把扩散采样的失败严格归约到信息-计算 gap，并修正了此前非正式断言的错误。
实验充分度: ⭐⭐⭐⭐ 数值实验干净地佐证了两条理论预言，但规模偏小、本质是说明性而非系统评测。
写作质量: ⭐⭐⭐⭐ 逻辑链清晰、对反例与限定条件交代诚实，但定理与假设密度高、对非该领域读者门槛不低。
价值: ⭐⭐⭐⭐⭐ 给"何时不该用扩散采样"提供了原理性判据，对生成模型理论与实践都有指导意义。

量	观测	理论预言
生成样本的 Frobenius 范数	直方图集中在接近 \(0\)（约 \(0.006\text{–}0.014\)）	应集中在 \(0\)（预言 2）
扩散样本与目标的 \(W_1\) 下界	\(\ge 0.48\)（用 \(\\|\cdot\\|_F\) 作 1-Lipschitz 检验函数读出）	\(0.50\)（渐近预言）