Diffusion sampling avoids condition number limits in high dimensions
Diffusion Removes Langevin's Conditioning Dependence: A Sharp Gaussian Analysis
Machine Learning
Summary
Sampling from complex data is often slowed down by certain technical challenges related to data shape. The authors show that diffusion models can get around these problems by using time-varying adjustments, unlike traditional methods. They prove this using clean mathematical models based on Gaussian shapes, explaining why diffusion methods need fewer steps to sample well. However, when it comes to learning from noisy data, diffusion doesn't have an advantage over classical techniques.
What this means in practice
- •For machine learning engineers: Optimize sampling methods for high-dimensional Gaussian-like data to reduce time and improve efficiency in probabilistic modeling tasks.
- •For statistical software developers: Design improved sampling algorithms that avoid condition number-related slowdowns when generating synthetic data or performing Bayesian inference.
A theory result. No direct application yet.
Authors
Adam Perbost, Francis Bach, Pierre Marion
Abstract
Despite their empirical success, why diffusion models overcome the bottlenecks of classical score-based samplers remains unclear. In this work, we leverage Gaussian distributions to isolate this phenomenon. We establish 2-Wasserstein convergence bounds for optimized hyperparameters, showing that diffusion processes achieve a sampling error of $O(\sqrt{dλ_{\max}}\log N/N)$, where $d$ is the dimension, $N$ the number of sampling steps, and $λ_{\max}$ the largest eigenvalue of the target covariance matrix. Unadjusted and underdamped Langevin dynamics suffer from an additional $\sqrtκ$ factor, where $κ$ is the condition number. These rates follow from spectral bounds which are sharp: we confirm them via matching first-order asymptotics as $N\rightarrow\infty$. Our analysis provides a rigorous characterization, in the Gaussian setting, of how time-dependent score trajectories remove condition-number dependence during sampling. By contrast, in the learning phase, we show that estimating the unnoised score by gradient descent leads to essentially the same estimator as estimating a noisy score, which suggests that the benefits of noising do not come from the learning phase.