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

ABSTRACT

We present algorithms for diffusion model sampling which obtain δ-error in polylog(1/δ) steps, given access to eO(δ)-accurate score estimates in L2. This is an exponential improvement over all previous results. Specifically, under minimal data assumptions, the complexity is eO(d polylog(1/δ)) where d is the dimension of the data; under a non-uniform L-Lipschitz condition, the complexity is eO(sqrt(dL) polylog(1/δ)). Our approach also yields the first polylog(1/δ) complexity sampler for general log-concave distributions using only gradient evaluations.