High-accuracy and dimension-free sampling with diffusions

Diffusion models have shown remarkable empirical success in sampling from rich multi-modal distributions. Their inference relies on numerically solving a certain differential equation. This differential equation cannot be solved in closed form, and its resolution via discretization typically requires many small iterations to produce *high-quality* samples. More precisely, prior works have shown that the iteration complexity of discretization methods for diffusion models scales polynomially in the ambient dimension and the inverse accuracy $1/\varepsilon$. In this work, we propose a new solver for diffusion models relying on a subtle interplay between low-degree approximation and the collocation method, and we prove that its iteration complexity scales *polylogarithmically* in $1/\varepsilon$, yielding the first "high-accuracy" guarantee for a diffusion-based sampler that only uses (approximate) access to the scores of the data distribution. In addition, our bound does not depend explicitly on the ambient dimension; more precisely, the dimension affects the complexity of our solver only through the *effective radius* of the support of the target distribution.

Modern AI image and video generators create content through a long sequence of small computational steps. The more steps they take, the more time and energy are required to generate an image or video. We introduce a generation algorithm that requires far fewer steps. In particular, we prove that the number of steps needed is, to a first approximation, independent of the number of pixels in an image or the number of frames in a video. This could make AI generation significantly faster, particularly for high-resolution images and long videos.