Score Approximation for Diffusion Models on Arbitrary Low-Dimensional Structures

Problem Statement
The theoretical foundations of score-based diffusion models have largely relied on restrictive assumptions regarding the underlying data distribution, specifically requiring Lipschitz continuous densities or smooth manifold supports. However, real-world perceptual data (such as images) often exhibit singularities, sharp boundaries, and disjoint clusters where densities are discontinuous or gradients are ill-behaved. Existing complexity bounds for approximating the score function $\nabla \log p_t(x)$ typically suffer from an exponential dependence on the ambient dimension $n$, or they fail to apply to distributions lacking smoothness. This gap raises a fundamental theoretical question: Can diffusion models theoretically succeed on arbitrary compact data distributions without assuming regularity or smoothness?

Methodology
The authors propose a universal score approximation framework that removes all continuity and smoothness assumptions. The core of their approach involves a novel discrete-mixture formulation and an analytics-heavy strategy focusing on the smoothing effects of Gaussian kernels.

1. Discrete-Mixture Formulation: The authors decompose the initial distribution $p_0$ into a finite mixture of sub-distributions $p_i$, each supported on a small ball $B(y_i, r)$. The true score function is approximated by replacing the integral over each sub-distribution with a point-mass evaluation at the local mean $\tilde{y}_i$. This transforms the score approximation problem into approximating a weighted sum of Gaussian kernels.
2. Divide-and-Conquer Error Analysis: To bound the discretization error, the authors partition the space into "near" and "far" groups relative to a query point $x$.
   • Near Group: For points close to the support, Taylor expansion of the Gaussian kernel around the local mean shows that the approximation error is small.
   • Far Group: For points far from the support, the Gaussian weight decays exponentially. The authors prove that even if the local approximation error is large in these regions, the contribution to the total error is negligible due to the rapid decay of the kernel.
3. Universal Regularity: A critical theoretical hurdle is ensuring that the "bad" points (where the approximation might fail) have negligible measure. The authors introduce a $C_1, C_2, r$-regularity condition and prove a "Universal Regularity" theorem: for any compactly supported distribution, the set of points that are not regular has arbitrarily small measure. This ensures the approximation holds almost everywhere.
4. Neural Network Implementation: The discrete mixture formula is shown to be implementable by a ReLU network. The authors construct a network that approximates the necessary operations (squaring, exponentiation, division, and Softmax) with controlled error, ensuring the output remains within the convex hull of the support.

Key Contributions

• Universal Score Approximation Theorem: The paper establishes the first theorem proving that the score function for any distribution with compact support (characterized by an upper Minkowski dimension $d$) can be approximated by a ReLU network. This removes the need for Lipschitz, Hölder, or Sobolev smoothness assumptions.
• Complexity Bounds: The authors prove that the network complexity (parameter size) grows polynomially with the ambient dimension $n$ and exponentially only with the intrinsic dimension $d$. Specifically, the size scales roughly as $O(n^3 d/4 (1/\epsilon)^{d/2})$. This breaks the "curse of ambient dimensionality" that plagues existing theories.
• Relaxed Regularity Conditions: By introducing the concept of universal regularity, the work demonstrates that the "bad sets" where approximation fails are of negligible measure for any compact distribution, including fractal-like measures (e.g., Cantor measures) that lack probability density functions.

Results
The main result (Theorem 1) states that for a distribution $p_0$ with compact support of diameter $R$ and upper Minkowski dimension $d$, the true score function $\nabla \log p_t(x)$ can be approximated by a data-prediction formulation $\nabla \log p_{t,appr}(x) = s_\theta(x, t) - x/t$ such that the mean squared error is bounded by $7\epsilon^2$ for all $t \in [t_0, T]$.

• The approximating network $s_\theta$ has a depth of $O(\log \omega \log \log \omega)$ and a width of $O(C_K r^{-d} (n \log \omega + \log^2 \omega))$, where $\omega$ depends polynomially on $n$ and $1/\epsilon$.
• The error bound holds globally, with the approximation error bounded by $R/t$ for out-of-distribution points, which is integrable over the small probability region.

Significance
The paper claims to provide a rigorous theoretical justification for the empirical success of diffusion models on irregular, non-smooth data structures. By proving that accurate score estimation is possible for arbitrary compact distributions without smoothness assumptions, the work bridges the gap between theoretical guarantees and real-world data characteristics (such as pixel clipping and singularities). The authors note that their divide-and-conquer tactics and regularity results can be adapted to bound higher-order derivatives (like the Hessian), potentially aiding future theoretical work on diffusion models that currently rely on boundedness assumptions for these terms. The work positions itself as a foundational step, expanding the scope of score approximation theory from smooth manifolds to the general class of compactly supported distributions.