Linear Convergence of Diffusion Models Under the Manifold Hypothesis

2024/10/11 by Potaptchik, Peter, Azangulov, Iskander, Deligiannidis, George · 7 citations
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2410.09046

Abstract

Score-matching generative models have proven successful at sampling from complex high-dimensional data distributions. In many applications, this distribution is believed to concentrate on a much lower d-dimensional manifold embedded into D-dimensional space; this is known as the manifold hypothesis. The current best-known convergence guarantees are either linear in D or polynomial (superlinear) in d. The latter exploits a novel integration scheme for the backward SDE. We take the best of both worlds and show that the number of steps diffusion models require in order to converge in Kullback-Leibler~(KL) divergence is linear (up to logarithmic terms) in the intrinsic dimension d. Moreover, we show that this linear dependency is sharp.

Cited by

• Dimension-free error estimate for diffusion model and optimal scheduling
• Sublinear iterations can suffice even for DDPMs
• Denoising growth complexity: Data geometry and certified schedules for diffusion sampling
• Diffusion Models and the Manifold Hypothesis: Log-Domain Smoothing is Geometry Adaptive
• Optimal estimation of a factorizable density using diffusion models with ReLU neural networks
• MAD: Manifold Attracted Diffusion
• Diffusion Generative Models Meet Compressed Sensing, with Applications to Imaging and Finance

Related

• Convergence of Diffusion Models Under the Manifold Hypothesis in High-Dimensions
• Convergence of denoising diffusion models under the manifold hypothesis
• KL Convergence Guarantees for Score diffusion models under minimal data assumptions
• Diffusion Models and the Manifold Hypothesis: Log-Domain Smoothing is Geometry Adaptive
• Manifolds, Random Matrices and Spectral Gaps: The geometric phases of generative diffusion