Search papers, labs, and topics across Lattice.
This paper establishes a universal score approximation theorem for score-based diffusion models that operates on any distribution supported on compact sets of upper Minkowski dimension \(d\), addressing limitations of previous complexity bounds that relied on restrictive assumptions. By employing a novel discrete-mixture formulation, the authors demonstrate that the score function can be approximated using a ReLU network with complexity that only grows exponentially with \(d\), effectively mitigating the challenges posed by high ambient dimensionality. The findings reveal that diffusion models can effectively adapt to complex, irregular data structures, enhancing their performance in real-world generative tasks.
Score-based diffusion models can now handle complex, irregular data structures without succumbing to the exponential curse of dimensionality.
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.
