Denoising growth complexity: Data geometry and certified schedules for diffusion sampling

• URL: http://arxiv.org/abs/2607.26285v1
• Date: Tue, 28 Jul 2026 21:26:16 GMT
• Title: Denoising growth complexity: Data geometry and certified schedules for diffusion sampling
• Abstract summary: 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.
• Score: 14.877292137182422
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Two central challenges in diffusion-based sampling are the theoretical one of understanding their remarkable effectiveness even in high-dimensional settings, and the practical one of designing algorithms with certified performance guarantees. We show that these questions are intimately connected via the \emph{denoising growth complexity} ($\mathsf{DGC}$). It is a geometric measure defined by a log-time weighted integral of the derivative of the denoising mean-squared error along the Gaussian heat flow. We show how the $\mathsf{DGC}$ increments lead to a simple and explicit bound on the KL error of an Euler scheme applied to the stochastic innovations representation. The bound is local along the path: each step is controlled by the corresponding $\mathsf{DGC}$ increment and its relative stepsize. This structure allows us to derive KL sampling guarantees for optimized stepsize schedules, both in a simpler single-block setting and in a more refined $K$-block setting. The $\mathsf{DGC}$ function has a natural martingale structure, which we exploit to develop fully data-certified versions of these algorithms. It also admits information-theoretic upper bounds in terms of covariance, rate distortion, metric entropy, and the Poincar'e constant, thereby recovering and sharpening a range of existing diffusion-sampling guarantees, as well as giving new results. In log heat-time, the fine partition limit is governed by an integral involving the square root of the $\mathsf{DGC}$ density, whereas a single-block schedule depends on its ordinary integral. This comparison precisely characterizes when adaptation to data geometry yields substantial computational gains, including logarithmic-to-constant separations for simple Gaussian mixture models.

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)
• Scalable Lindblad Noise Learning via Stochastic Tensor-Network Simulation [48.887627688666974]
  Learning dissipation rates in large-scale open quantum systems is a major obstacle for near-term quantum technologies.<n>Here, we propose a scalable noise-learning framework for Lindblad dissipation rates that combines a simulation method, the Jump Method (TJM)<n>We demonstrate the approach on two noise models in the Ising model, in which independent dissipation rates are learned for each site up to $N_mathrmsite=16$.<n>This combination of scalable numerics and rigorous theoretical guarantees positions TJM-based noise learning as a practical foundation for characterizing dissipation in large quantum devices.
  arXiv  Detail & Related papers  (2026-08-25T15:07:11Z)
• 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)
• 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)
• Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees [9.180350432640912]
  We study the sampling efficiency of score-based discrete diffusion models under a continuous-time Markov chain (CTMC) formulation.<n>For uniform discrete diffusion, we show that the $$-leaping algorithm achieves an complexity of order $tilde O(d/varepsilon)$.<n>For masking discrete diffusion, we introduce a modified $$-leaping sampler whose convergence rate is governed by an intrinsic information-theoretic quantity.
  arXiv  Detail & Related papers  (2026-02-16T18:48:17Z)
• 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)
• Estimation of Toeplitz Covariance Matrices using Overparameterized Gradient Descent [1.7188280334580195]
  We revisit Toeplitz covariance estimation through the lens of simple descent (GD)<n>We show that when $K = P$, GD may converge to suboptimal solutions.<n>We propose an accelerated GD variant with separate learning rates for amplitudes and frequencies.
  arXiv  Detail & Related papers  (2025-11-03T14:07:53Z)
• 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)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  We consider monotone variational inequality (VI) problems in multi-GPU settings where multiple processors/workers/clients have access to local dual vectors. Extra-gradient, which is a de facto algorithm for monotone VI problems, has not been designed to be communication-efficient. We propose a quantized generalized extra-gradient (Q-GenX), which is an unbiased and adaptive compression method tailored to solve VIs.
  arXiv  Detail & Related papers  (2023-08-17T21:15:04Z)
• Compressed and distributed least-squares regression: convergence rates with applications to Federated Learning [11.870656106069447]
  We investigate the impact of compression on gradient algorithms for machine learning.<n>We highlight differences in terms of convergence rates between several unbiased compression operators.<n>We extend our results to the case of federated learning.
  arXiv  Detail & Related papers  (2023-08-02T18:02:00Z)
• Score-based Diffusion Models in Function Space [137.70916238028306]
  Diffusion models have recently emerged as a powerful framework for generative modeling.<n>This work introduces a mathematically rigorous framework called Denoising Diffusion Operators (DDOs) for training diffusion models in function space.<n>We show that the corresponding discretized algorithm generates accurate samples at a fixed cost independent of the data resolution.
  arXiv  Detail & Related papers  (2023-02-14T23:50:53Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  This paper analyzes the trajectories of gradient descent (SGD) We show that SGD avoids saddle points/manifolds with $1$ for strict step-size policies.
  arXiv  Detail & Related papers  (2020-06-19T14:11:26Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting. We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$. Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
  arXiv  Detail & Related papers  (2020-05-13T16:44:12Z)

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.