[论文] Provably adaptive sampling with uniform and remasking discrete diffusi...

论文概要

研究领域: ML
作者: Daniil Dmitriev, Zhihan Huang, Yuting Wei
发布时间: 2025-08-26
arXiv: 2508.17627

中文摘要

离散扩散模型通过并行更新为自回归生成提供了一种有前景的替代方案，但其采样效率强烈依赖于前向过程和采样器的选择。对于均匀前向过程，现有标准\(\tau\)-leaping采样器的下界随环境维度\(d\)线性缩放，引发了一个问题：这种依赖是否是前向过程固有的。本文给出了否定答案。我们考虑基于leave-one-out去噪器的一阶采样器，用于均匀和remasking过程，其坐标更新可以并行执行。在这两种情况下，采样器可以在采样过程中纠正去噪错误，这在多个坐标同时更新时变得必要。主要结果建立了自适应采样保证：在对数因子内，\(N = O(\mathrm{DTC}(X_0) / \varepsilon)\)个离散化步骤足以达到采样误差\(O(\varepsilon_{\mathrm{score}}+\varepsilon)\)，其中\(\varepsilon_{\mathrm{score}}\)是分数估计误差。因此，采样复杂度由目标分布的内在依赖结构（由其双总相关性\(\mathrm{DTC}(X_0)\)度量）控制，而非直接由环境维度\(d\)控制。

原文摘要

Discrete diffusion models offer a promising alternative to autoregressive generation by enabling parallel updates, but their sampling efficiency can depend strongly on the choice of the forward process and the sampler. For the uniform forward process, existing lower bounds for the standard \(\tau\)-leaping sampler scale linearly with the ambient dimension \(d\), raising the question of whether this dependence is intrinsic to the forward process. We answer this question in the negative. We consider a first-order sampler based on the leave-one-out denoiser for uniform and remasking processes whose coordinate updates can be performed in parallel. In both cases, the sampler can correct denoising mistakes during the sampling process, which becomes necessary when many coordinates are updated togethe...

自动采集于 2026-08-26

#论文 #arXiv #ML #小凯