Authors: Gen Li, Changxiao Cai
Abstract: While score-based diffusion models have achieved exceptional sampling
quality, their sampling speeds are often limited by the high computational
burden of score function evaluations. Despite the recent remarkable empirical
advances in speeding up the score-based samplers, theoretical understanding of
acceleration techniques remains largely limited. To bridge this gap, we propose
a novel training-free acceleration scheme for stochastic samplers. Under
minimal assumptions — namely, $L^2$-accurate score estimates and a finite
second-moment condition on the target distribution — our accelerated sampler
provably achieves $\varepsilon$-accuracy in total variation within
$\widetilde{O}(d^{5/4}/\sqrt{\varepsilon})$ iterations, thereby significantly
improving upon the $\widetilde{O}(d/\varepsilon)$ iteration complexity of
standard score-based samplers. Notably, our convergence theory does not rely on
restrictive assumptions on the target distribution or higher-order score
estimation guarantees.
Source: http://arxiv.org/abs/2410.23285v1
