Nearly $d$-Linear Convergence Bounds for Diffusion Models via Stochastic Localization
This provides improved theoretical guarantees for diffusion models, addressing a bottleneck in sampling efficiency for machine learning applications, though it is incremental as it refines existing methods.
The paper tackles the problem of slow convergence rates in diffusion models for high-dimensional data sampling, achieving a bound that is nearly linear in data dimension with only finite second moment assumptions, specifically requiring at most O(d log^2(1/δ)/ε^2) steps to approximate distributions within ε^2 KL divergence.
Denoising diffusions are a powerful method to generate approximate samples from high-dimensional data distributions. Recent results provide polynomial bounds on their convergence rate, assuming $L^2$-accurate scores. Until now, the tightest bounds were either superlinear in the data dimension or required strong smoothness assumptions. We provide the first convergence bounds which are linear in the data dimension (up to logarithmic factors) assuming only finite second moments of the data distribution. We show that diffusion models require at most $\tilde O(\frac{d \log^2(1/δ)}{\varepsilon^2})$ steps to approximate an arbitrary distribution on $\mathbb{R}^d$ corrupted with Gaussian noise of variance $δ$ to within $\varepsilon^2$ in KL divergence. Our proof extends the Girsanov-based methods of previous works. We introduce a refined treatment of the error from discretizing the reverse SDE inspired by stochastic localization.