证明某些易采样的分布仍难用去噪扩散采样，因漂移函数不可计算。
Computational bottlenecks for denoising diffusions
- 基于信息-计算鸿沟假设，分析扩散过程的漂移学习瓶颈
- 多项式时间漂移可逼近最优值但样本分布仍与目标相距甚远
- 揭示扩散模型在理论上的计算极限，适合研究生成模型基础的学者
去噪扩散通过构建一个随机过程 $({oldsymbol x}_t:t/ge 0)$ 在 $\mathbb{R}^d$ 中采样概率分布 $μ$，使得初始状态 ${\boldsymbol x}_0$ 易于采样，而大时间 $T$ 下的 $\boldsymbol x_T$ 分布近似 $μ$。该过程的漂移函数 $\boldsymbol m: \mathbb{R}^d \times \mathbb{R} \to \mathbb{R}^d$ 通过最小化得分匹配目标学习得到。我们提供证据表明，并非所有可有效采样的分布 $μ$ 都能通过扩散方法有效采样。研究一个采样容易但扩散漂移不可计算的分布 $μ$，在统计估计的信息-计算鸿沟主流假设下，存在漂移函数可超多项式逼近最优（在多项式时间漂移中），但生成样本的分布与目标分布相去甚远。
原文摘要 · Abstract (English)
Denoising diffusions sample from a probability distribution $μ$ in $\mathbb{R}^d$ by constructing a stochastic process $({\hat{\boldsymbol x}}_t:t\ge 0)$ in $\mathbb{R}^d$ such that ${\hat{\boldsymbol x}}_0$ is easy to sample, but the distribution of $\hat{\boldsymbol x}_T$ at large $T$ approximates $μ$. The drift ${\boldsymbol m}:\mathbb{R}^d\times\mathbb{R}\to\mathbb{R}^d$ of this diffusion process is learned my minimizing a score-matching objective. Is every probability distribution $μ$, for which sampling is tractable, also amenable to sampling via diffusions? We provide evidence to the contrary by studying a probability distribution $μ$ for which sampling is easy, but the drift of the diffusion process is intractable -- under a popular conjecture on information-computation gaps in statistical estimation. We show that there exist drifts that are superpolynomially close to the optimum value (among polynomial time drifts) and yet yield samples with distribution that is very far from the target one.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。