High-accuracy sampling for diffusion models and log-concave distributions

Abstract

We present algorithms for diffusion model sampling which obtain $\hat{I}´$-error in $\mathrm{polylog}(1/\hat{I}´)$ steps, given access to $\tilde{O}(\hat{I}´)$-accurate score estimates in $L^2$. This is an exponential improvement over all previous results. Specifically, under minimal data assumptions, the complexity is $\tilde{O}(d_{\star }\mathrm{polylog}(1/\hat{I}´))$ where $d_{\star }$ is the intrinsic dimension of the data. Further, under a non-uniform $L$-Lipschitz condition, the complexity reduces to $\tilde{O}(L\mathrm{polylog}(1/\hat{I}´))$. Our approach also yields the first $\mathrm{polylog}(1/\hat{I}´)$ complexity sampler for general log-concave distributions using only gradient evaluations.