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