Breaking the Curse of Dimensionality: Diffusion Models Efficiently Learn Low-Dimensional Distributions

Summary

The paper develops a mathematical framework explaining how diffusion models learn low-dimensional data distributions from a finite number of training samples without the curse of dimensionality. It models data as a mixture of low-rank Gaussians and shows that the diffusion training objective is equivalent to subspace clustering over the training samples, so sample complexity scales linearly with intrinsic dimension rather than exponentially with ambient dimension. Experiments on synthetic and real image datasets show phase transitions in generalization.