并行扩散采样的下界

arXiv:2610.09166v1 公告类型：交叉收录 摘要：标准扩散采样器通过反复计算学习得到的得分函数来生成样本。并行采样方法力求以增加计算次数为代价，减少串行轮数，从而加速生成。这引出了一个问题：即使可以同时进行大量得分查询，仍有多少串行依赖是不可避免的？我们首次建立了使用近似得分进行扩散采样所需并行轮数的多项式下界。具体而言，我们证明了：(1) 对 $R^d$ 中光滑、近各向同性的高斯混合分布进行采样，需要 $\widetilde{\Omega}(d^{1/3})$ 轮；(2) 从包含于单位球内的各向异性轴对齐盒中进行均匀采样，需要 $\Omega(d)$ 轮。这两个下界均适用于任意随机化算法，允许其在每轮中于任意位置和噪声水平进行多项式次查询，且得分误差为多项式倒数量级、总变差误差为常数量级。对于我们构造的盒族，线性下界是紧的。我们的构造使用固定的近似得分预言机，在每个噪声水平都满足精度保证的同时，强制算法按顺序访问隐藏信息。