提出新几何度量,实现离散扩散采样最优调度。
The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity
- 引入未掩码增长复杂度,量化数据几何对采样误差的影响。
- 基于样本估计该度量,构建保证误差的最优采样器。
- 适配数据结构可提升效率,尤其在高维场景下显著优于固定调度。
我们研究离散采样的掩码扩散过程,提出一种路径解析的数据几何度量——未掩码增长复杂度(UGC)。其局部增量直接控制KL离散化误差,统一分析伯努利子集与固定基数去掩码方案。在对数揭示几率坐标下,该结构可导出单块与多块最优调度,并量化计算资源随数据几何自适应的收益。关键发现是:通过耦合揭示轨迹的KL增量,可从样本中估计UGC增量。这带来具有保证的最优采样器,在高概率下实现指定KL误差,且迭代复杂度仅比理想情况差常数倍。路径坍缩后得到总UGC质量,与经典多元依赖度量及先前离散扩散分析中的复杂度度量相关。在细划分极限下,平方根UGC密度的平方积分决定了最优欧拉离散化误差的主导项。实例显示,相比粗调度,高维下可获得显著改进,即使使用常数个自适应块也能实现˜Ω(√d)级别的提升。
原文摘要 · Abstract (English)
We study masking diffusion for discrete sampling and introduce a path-resolved measure of data geometry called the \emph{unmasking growth complexity} ({\textsf{UGC}\xspace}). Its local increments directly control Kullback--Leibler (KL) discretization error, yielding a unified analysis of Bernoulli-subset and fixed-cardinality unmasking schemes. In log-reveal-odds coordinates, this structure yields optimized single-block and multi-block schedules, and quantifies the gains from adapting computational effort to data geometry. Crucially, we show how {\textsf{UGC}\xspace} increments can be estimated from samples via KL increments along coupled reveal trajectories. This leads to \emph{certified-optimal} samplers that achieve a prescribed KL error with high probability and iteration complexity within a constant factor of the corresponding oracle procedure. Collapsing the \ugc path yields the aggregate {\textsf{UGC}\xspace} mass, which connects to classical multivariate dependence measures and complexity measures from previous analyses of discrete diffusion. In the fine-partition limit, the squared integral of the square-root {\textsf{UGC}\xspace} density determines the sharp leading-order optimal Euler discretization error. Examples exhibit substantial dimension-dependent gains over coarse schedules, including $\widetildeΩ(\sqrt{d})$ improvements achievable with a constant number of adaptively placed blocks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。