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

Technical Summary: Denoising Growth Complexity and Certified Diffusion Sampling

Problem Statement
Diffusion-based sampling methods have demonstrated remarkable effectiveness in generating high-dimensional data, yet two central challenges remain: (1) theoretically understanding why these methods succeed where generic worst-case complexity bounds suggest failure, and (2) practically designing algorithms with certified performance guarantees. The paper addresses the need to explain diffusion sampling performance through a measure tied to data geometry and to exploit such a measure to design and certify practical sampling schemes.

Methodology
The authors analyze diffusion samplers based on the Gaussian heat flow, specifically focusing on a variant of the standard Euler discretization applied to a stochastic innovations (SI) representation of the reverse-time process. The core of their methodology is the introduction and analysis of a new geometric measure called Denoising Growth Complexity (DGC).

• The DGC Function: Defined as a log-time weighted integral of the derivative of the denoising mean-squared error (MSE) along the heat path. If $h(t)$ denotes the MSE at time $t$, the DGC $H(a, b)$ over an interval $[a, b]$ is given by:
  $$H(a, b) := \frac{1}{2} \int_a^b \frac{h'(t)}{t} dt$$
• Stochastic Innovations Representation: The analysis utilizes a transformation to stochastic localization (SL) or innovations space, where the reverse process is viewed as a forward SDE driven by a Brownian motion and the optimal denoiser. This allows for a cleaner derivation of the Euler discretization error.
• Local Error Analysis: The paper establishes that the KL discretization error for a single step of the Euler scheme is locally controlled by the DGC increment over that step and the relative stepsize. This local bound is then aggregated over the entire path.

Key Contributions

1. Main Theoretical Guarantee (Theorem 1):
   The paper provides an explicit upper bound on the KL divergence between the target distribution and the output of the SI-Euler scheme. The bound is a sum of local terms, each controlled by the DGC increment $H(t_{j+1}, t_j)$ and the stepsize ratio $(t_j/t_{j+1} - 1)$.
   $$D_{KL}(P_\delta \| Q_\delta) \leq \sum_{j=0}^{N-1} \left( \frac{t_j}{t_{j+1}} - 1 \right) H(t_{j+1}, t_j) + D_{KL}(P_T \| Q_T)$$
   This result recovers and sharpens existing dimension-dependent and dimension-independent guarantees without requiring complex analysis (the proof is noted to be under three pages of elementary analysis).

2. Data-Certified Algorithms:
   Leveraging the martingale structure of the denoising functions along the heat path, the authors develop a method to estimate DGC increments from data samples.

   • They introduce a "denoising increment" $D(s, t)$ which can be estimated via Monte Carlo.
   • A "sandwich relation" is proven: $D(s, t)/t \leq 2H(s, t) \leq D(s, t)/s$.
   • This allows for the construction of fully data-certified stepsize schedules. The algorithm can estimate the required number of iterations to achieve a target accuracy $\epsilon$ with high probability, using only samples from the target distribution (or a hold-out set) without needing to know the true score function.

3. Single-Block vs. Multi-Block Schedules:

   • Single-Block: A geometric schedule with a constant multiplier $\rho$ over the entire path yields a complexity bound proportional to $H(\delta, T) \log(T/\delta)$.
   • Multi-Block (K-Block): By partitioning the path into $K$ blocks and assigning optimal geometric multipliers to each, the complexity is governed by the DGC-based partition complexity $C_{DGC}(P) = (\sum \sqrt{S_k H_k})^2$, where $S_k$ is the log-time length of block $k$.
   • Fine Partition Limit: As $K \to \infty$, the complexity converges to a quantity involving the integral of the square root of the log-time DGC density, $q(r) = h'(\delta e^r)$. Specifically, the limit depends on $(\int \sqrt{q(r)} dr)^2$, whereas the single-block scheme depends on $\int q(r) dr$.

4. Information-Theoretic Connections:
   The DGC is shown to have equivalent representations in terms of mutual information and rate-distortion theory. This connects the sampling complexity to:

   • Covariance structure (recovering linear dimension scaling).
   • Metric entropy and intrinsic dimension (recovering linear scaling with intrinsic dimension).
   • Shannon rate-distortion functions.
   • The Poincaré constant (yielding logarithmic dependence on the condition number).

Results and Specific Findings

• Dimension Scaling: The single-block scheme recovers linear dependence on the ambient dimension $d$ without logarithmic overhead via a covariance-based bound.
• Gaussian Mixture Models (GMMs): For simple GMMs, the paper demonstrates a separation between single-block and multi-block complexities. In specific hierarchical GMMs, the multi-block approach can reduce the complexity from logarithmic in the separation ratio ($\log(R^2/\delta)$) to constant or iterated logarithmic scales, depending on the number of blocks $K$.
• Poincaré Constant: For distributions satisfying a Poincaré inequality, the iteration complexity is shown to depend logarithmically on the Poincaré constant, improving upon previous results that relied on stronger log-concavity assumptions.
• Data-Certification: The paper provides a concrete procedure (Proposition 1) to estimate the DGC function from data with high-probability confidence intervals, enabling the selection of iteration budgets that guarantee $\epsilon$-accuracy in KL divergence.

Significance and Claims
The paper claims to provide affirmative answers to two fundamental questions:

1. Explanation: The performance of diffusion sampling can be explained and quantified by the DGC, a geometric measure tied to the data distribution's evolution under the heat flow.
2. Certification: This geometric measure can be exploited to design sampling schemes with rigorous, data-dependent performance guarantees.

The authors emphasize that their approach unifies and sharpens a wide range of existing results (covering dimension scaling, intrinsic dimension, manifold structures, and mixture models) under a single, simple theoretical framework. A key novelty is the ability to adapt stepsize schedules to the specific geometry of the data (via the DGC profile) to achieve computational gains, particularly in multi-block settings where the "spread" of the DGC density allows for significant reductions in iteration complexity compared to uniform or single-block schedules. The work bridges the gap between theoretical complexity analysis and practical, certified algorithm design.