查询扩散采样的下界

扩散模型通过迭代查询学习的分数估计来生成样本。快速增长的文献关注通过最小化评分评估的数量来加速采样，但这种加速的信息论限制仍不清楚。在这项工作中，我们建立了扩散采样的第一个分数查询下界。我们证明，对于$d$维分布，如果能够以多项式精度$\varepsilon=d^{-O(1)}$（在任何$L^p$意义上）获得分数估计，任何采样算法都需要$\widetildeΩ(\sqrt{d})$自适应分数查询。特别是，我们的证明表明，在任何多项式总查询预算内，成功的采样需要搜索 $\widetildeΩ(\sqrt{d})$ 不同的噪声水平，这为为什么在实践中需要多尺度噪声计划提供了正式的解释。