The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling

• URL: http://arxiv.org/abs/2608.28949v1
• Date: Fri, 28 Aug 2026 23:38:39 GMT
• Title: The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling
• Abstract summary: We study a class of product-reference diffusion algorithms for sampling from a discrete distribution.<n>We show that their sampling performance can be characterized using a path-based measure of data geometry.
• Score: 14.877292137182422
• License: http://creativecommons.org/licenses/by/4.0/
• 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 papers

• The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity [14.877292137182422]
  We study masking diffusion for discrete sampling and introduce a path-resolved measure of data geometry called the emphunmasking growth complexity (textsfUGCxspace)<n>Its local increments directly control Kullback--Leibler (KL) discretization error, yielding a unified analysis of Bernoulli-subset and fixed-cardinality unmasking schemes.
  arXiv  Detail & Related papers  (2026-08-13T17:40:17Z)
• Multi-kernel spectral clustering: Entrywise eigenvector perturbation bounds and exact recovery [5.506184984859199]
  Kernel spectral clustering with a single bandwidth can be inadequate for data exhibiting multiple characteristic pairwise-distance scales.<n>We address this issue through a multi- kernel formulation that aggregates kernels with different bandwidths.<n>We develop a rigorous theoretical analysis of the resulting method under a general high-dimensional, multi-scale mixture model.
  arXiv  Detail & Related papers  (2026-08-09T13:34:27Z)
• Denoising growth complexity: Data geometry and certified schedules for diffusion sampling [14.877292137182422]
  We show how the $mathsfDGC$ increments lead to a simple and explicit bound on the KL error of an Euler scheme applied to the innovations representation.<n>We derive KL sampling guarantees for optimized stepsize schedules, both in a simpler single-block setting and in a more refined $K$-block setting.
  arXiv  Detail & Related papers  (2026-07-28T21:26:16Z)
• Rethinking Heterogeneous LLM Merging: A Weighted Model Averaging Perspective [41.30735431552607]
  heterogeneous fusion methods typically introduce adapters, learned latent spaces, routing, or feature alignment.<n>We revisit this counterintuitive question through training-free dimensional adaptation followed by ratio-controlled ratios.<n>Results show that simple parameter averaging, when paired with lightweight dimensional adaptation and carefully controlled ratios, is a surprisingly strong baseline for heterogeneous merging.
  arXiv  Detail & Related papers  (2026-07-20T14:58:53Z)
• Influence-Guided Symbolic Regression: Scientific Discovery via LLM-Driven Equation Search with Granular Feedback [56.69850045068714]
  We introduce textitInfluence-Guided Regression (IGSR), a method that frames equation discovery as an iterative two-step process.<n>We demonstrate IGSRs effectiveness on a diverse suite of benchmarks, including LLM-SRBench, pharmacological PKPD models, an epidemiological simulation, and real-world genomic data.
  arXiv  Detail & Related papers  (2026-05-27T23:48:01Z)
• SEED: Targeted Data Selection by Weighted Independent Set [76.68391670109433]
  We develop a robust and scalable data selection pipeline dubbed SEED.<n>SEED consistently outperforms state-of-the-art methods on instruction tuning, visual instruction tuning, and semantic segmentation.
  arXiv  Detail & Related papers  (2026-05-15T07:26:54Z)
• Gradient-Based Feature Learning under Structured Data [57.76552698981579]
  In the anisotropic setting, the commonly used spherical gradient dynamics may fail to recover the true direction. We show that appropriate weight normalization that is reminiscent of batch normalization can alleviate this issue. In particular, under the spiked model with a suitably large spike, the sample complexity of gradient-based training can be made independent of the information exponent.
  arXiv  Detail & Related papers  (2023-09-07T16:55:50Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
  We study the properties of ensembled clustered inference algorithms which combine spatially constrained clustering, statistical inference, and ensembling to aggregate several clustered inference solutions. We show that ensembled clustered inference algorithms control the $delta$-FWER under standard assumptions for $delta$ equal to the largest cluster diameter.
  arXiv  Detail & Related papers  (2021-06-04T16:37:19Z)
• EiGLasso for Scalable Sparse Kronecker-Sum Inverse Covariance Estimation [1.370633147306388]
  We introduce EiGLasso, a highly scalable method for sparse Kronecker-sum inverse covariance estimation. We show that EiGLasso achieves two to three orders-of-magnitude speed-up compared to the existing methods.
  arXiv  Detail & Related papers  (2021-05-20T16:22:50Z)
• GANs with Variational Entropy Regularizers: Applications in Mitigating the Mode-Collapse Issue [95.23775347605923]
  Building on the success of deep learning, Generative Adversarial Networks (GANs) provide a modern approach to learn a probability distribution from observed samples. GANs often suffer from the mode collapse issue where the generator fails to capture all existing modes of the input distribution. We take an information-theoretic approach and maximize a variational lower bound on the entropy of the generated samples to increase their diversity.
  arXiv  Detail & Related papers  (2020-09-24T19:34:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.