The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling
Abstract
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.
Related
- When Fresh Information Is Not Enough: Age-of-Actuation-Optimal Scheduling for Energy-Harvesting Actuators
- Oblique Projection Networks (OPN) Reference guide - variants, code, tests, complexity, and the application scope of oblique projections
- The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity
- Mutual Information Optimal Density Control of Linear Systems and Generalized Schrödinger Bridges with Reference Refinement
- The optimal information complexity of VC learning
BibTeX
@misc{wainwright2026information,
title = {{The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling}},
author = {Martin J. Wainwright},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.28949},
eprint = {2608.28949},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.28949},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling
AU - Martin J. Wainwright
PY - 2026
DA - 2026/08/28
PB - arXiv
DO - 10.48550/arxiv.2608.28949
UR - https://arxiv.org/abs/2608.28949
AB - 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.
ER -