Denoising Diffusion Probabilistic Models Are Optimally Adaptive to Unknown Low Dimensionality

The denoising diffusion probabilistic model (DDPM) has emerged as a mainstream generative model in generative artificial intelligence. Although sharp convergence guarantees have been established for the DDPM, the iteration complexity is, in general, proportional to the ambient data dimension, resulting in overly conservative theory that fails to explain its practical efficiency. This has motivated the recent work to investigate how the DDPM can achieve sampling speed-ups through automatic exploitation of intrinsic low dimensionality of data. We strengthen this line of work by demonstrating, in some sense, optimal adaptivity to unknown low dimensionality. For a broad class of data distributions, we prove that the iteration complexity of the DDPM scales nearly linearly with its intrinsic dimension, which is optimal when using the Kullback-Leibler divergence to measure distributional discrepancy. Funding: Y. Wei is supported in part by the National Science Foundation (NSF) [Grant CCF-2418156 and CAREER Award DMS-2143215]. Y. Chen is supported in part by the Alfred P. Sloan Research Fellowship, the Office of Naval Research [Grants N00014-22-1-2354 and N00014-25-1-2344], the NSF [Grants 2221009 and 2218773], the Wharton AI & Analytics Initiative [AI Research Fund], and the Amazon Research Award.