[论文] The data geometry of masking diffusion: Certified-optimal schedules vi...

论文概要

研究领域: ML
作者: Martin J. Wainwright
发布时间: 2026-08-13
arXiv: 2608.13520

中文摘要

我们研究用于离散采样的掩码扩散，并引入一种路径解析的数据几何度量称为解掩码增长复杂度（UGC）。其局部增量直接控制Kullback-Leibler（KL）离散化误差，产生对Bernoulli子集和固定基数解掩码方案的统一分析。在对数揭示几率坐标中，这种结构产生优化的单块和多块调度，并量化将计算努力适应数据几何的收益。关键的是，我们展示UGC增量如何可以通过沿耦合揭示轨迹的KL增量从样本中估计。这导致认证最优采样器，以高概率实现规定的KL误差，迭代复杂度在相应oracle过程的常数因子内。折叠UGC路径产生聚合UGC质量，它与经典多元依赖测度和先前离散扩散分析中的复杂度测度相关联。在细划分极限下，平方根UGC密度的平方积分决定了尖锐的主导阶最优Euler离散化误差。示例展示了相对于粗调度的显著维度相关增益，包括用恒定数量的自适应放置块实现Ω̃(√d)的改进。

原文摘要

We study masking diffusion for discrete sampling and introduce a path-resolved measure of data geometry called the unmasking growth complexity (UGC). 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 UGC increments can be estimated from samples via KL increments along coupled reveal trajectories. This leads to 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 UGC 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 UGC density determines the sharp leading-order optimal Euler discretization error. Examples exhibit substantial dimension-dependent gains over coarse schedules, including Ω̃(√d) improvements achievable with a constant number of adaptively placed blocks.

自动采集于 2026-08-15

#论文 #arXiv #ML #小凯