Score Approximation for Diffusion Models on Arbitrary Low-Dimensional Structures
Provides theoretical justification for diffusion models' effectiveness on real-world perceptual data with singularities and sharp boundaries, addressing a key gap in existing theory.
The paper proves that score functions for any distribution on a compact set with upper Minkowski dimension d can be approximated by a ReLU network with complexity exponential only in d, breaking the curse of ambient dimensionality. This shows diffusion models adapt to irregular data structures.
The remarkable success of score-based diffusion models has spurred significant efforts to establish their theoretical foundations. However, existing complexity bounds for score approximation rely heavily on restrictive assumptions like Lipschitz continuous densities or smooth manifold supports, which are routinely violated by the singularities, sharp boundaries, and disjoint clusters inherent to real-world perceptual data. This work establishes a universal score approximation theorem that works for any distribution supported on any compact set of upper Minkowski dimension $d$. Using a novel discrete-mixture formulation, we prove that the score function can be approximated with a ReLU network whose complexity grows exponentially only with $d$, thus breaking the exponential curse of ambient dimensionality. Combined with existing theories on accurately solving the backward diffusion SDE for arbitrary compact distributions, our work shows that diffusion models readily adapt to irregular, non-smooth data structures, explaining their competence in real-world generative tasks.