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

arXiv:2602.01338v1 Announce Type: cross
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,mathrm{polylog}(1/delta))$ where $d$ is the dimension of the data; under a non-uniform $L$-Lipschitz condition, the complexity is $widetilde O(sqrt{dL},mathrm{polylog}(1/delta))$; and if the data distribution has intrinsic dimension $d_star$, then the complexity reduces to $widetilde O(d_star,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.