提出新几何度量,揭示离散扩散采样中的复杂性与最优调度关系。
The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling
- 用交互增长复杂度衡量采样路径的几何特性,刻画采样性能。
- 步长优化可降低迭代复杂度,细网格下结果精确。
- 适用于多变量依赖分析,适合研究采样效率与分布结构者。
我们研究一类用于从离散分布中采样的乘积参考扩散算法。发现其采样性能可通过一种基于路径的几何度量——交互增长复杂度(IGC)来表征。双变量IGC核能精确表示KL离散化误差及一个简单的一步上界。单变量IGC密度可用于分析步长选择对获得ε-准确样本所需迭代复杂度的影响。在对数平方可靠性奇数等距步长下,采样性能取决于总IGC质量;而优化步长选择则使复杂度依赖于平方根泛函。在细网格极限下,两种表征均趋于精确。我们还允许一般乘积参考分布,发现参考分布可显著改变IGC分布和采样复杂度;特别是远离均匀分布和数据边缘的参考分布可带来维度相关的改进。此外,总IGC质量可由总相关性和对偶总相关性界定,从而将路径几何与经典多元依赖度量相连接。
原文摘要 · Abstract (English)
We study a class of product-reference diffusion algorithms for sampling from a discrete distribution. We show that their sampling performance can be characterized using a path-based measure of data geometry that we call the interaction growth complexity (IGC). We show that a bivariate IGC kernel gives an exact representation of both the KL discretization error and a simple one-step upper bound. The simpler univariate IGC density can be used to study the effect of stepsize choices on the iteration complexity required to obtain $ε$-accurate samples in KL divergence. Samplers that traverse the path with equi-spaced steps in log-squared-reliability-odds have performance that depends on the aggregate IGC mass, whereas refined choices of stepsizes have a lower complexity depending on a square-root functional. In the fine-grid limit, both of these characterizations become sharp. We also allow general product reference distributions and show that the reference law can substantially reshape the IGC profile and the resulting sampling complexity; in particular, references far from both the uniform and the data marginals can yield dimension-dependent improvements. Finally, the aggregate IGC mass admits bounds in terms of total correlation and dual total correlation, thereby connecting the pathwise geometry to classical measures of multivariate dependence.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。