The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity

• URL: http://arxiv.org/abs/2608.13520v1
• Date: Thu, 13 Aug 2026 17:40:17 GMT
• Title: The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity
• Abstract summary: 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.
• Score: 14.877292137182422
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling [14.877292137182422]
  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.
  arXiv  Detail & Related papers  (2026-08-28T23:38:39Z)
• 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)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Smoothed Score Queries and the Complexity of Sampling [17.319855487817257]
  We study the query complexity of sampling from high-dimensional Gaussian distributions using gradient information.<n>$ smoothed-score queries for total variation error (_rm TV) improve the condition-number dependence from (sqrt) to logarithmic.<n>We also study finite-bit gradient oracles.
  arXiv  Detail & Related papers  (2026-05-26T23:38:20Z)
• Adaptation to Intrinsic Dependence in Diffusion Language Models [5.185131234265025]
  Diffusion language models (DLMs) have emerged as a promising alternative to autoregressive (AR) approaches.<n>We introduce a distribution-agnostic unmasking schedule for DLMs that adapts to the (unknown) dependence structure of the target data distribution.<n>Our results significantly improve upon prior convergence theories and yield substantial sampling acceleration for low-complexity distributions.
  arXiv  Detail & Related papers  (2026-02-23T18:41:34Z)
• Analysis of Hessian Scaling for Local and Global Costs in Variational Quantum Algorithm [0.42970700836450487]
  We quantify the entrywise resolvability of the Hessian for Variational Quantum Algorithms.<n>We show two distinct scaling regimes that govern the sample complexity required to resolve Hessian entries against shot noise.
  arXiv  Detail & Related papers  (2026-01-31T15:49:23Z)
• Optimal Transportation and Alignment Between Gaussian Measures [80.4634530260329]
  Optimal transport (OT) and Gromov-Wasserstein (GW) alignment provide interpretable geometric frameworks for datasets.<n>Because these frameworks are computationally expensive, large-scale applications often rely on closed-form solutions for Gaussian distributions under quadratic cost.<n>This work provides a comprehensive treatment of Gaussian, quadratic cost OT and inner product GW (IGW) alignment, closing several gaps in the literature to broaden applicability.
  arXiv  Detail & Related papers  (2025-12-03T09:01:48Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Generalization Bounds for Stochastic Gradient Descent via Localized $\varepsilon$-Covers [16.618918548497223]
  We propose a new covering technique localized for the trajectories of SGD. This localization provides an algorithm-specific clustering measured by the bounds number. We derive these results in various contexts and improve the known state-of-the-art label rates.
  arXiv  Detail & Related papers  (2022-09-19T12:11:07Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
  arXiv  Detail & Related papers  (2022-07-18T12:03:26Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  One of the most widely used methods for solving large-scale optimization problems is distributed asynchronous gradient descent (DASGD) We show that DASGD converges to a global optimal implementation model under same delay assumptions.
  arXiv  Detail & Related papers  (2021-07-06T21:59:49Z)
• 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)

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.