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

This paper introduces a new algorithm called first-order rejection sampling (FORS) to achieve high-accuracy sampling for diffusion models and log-concave distributions. By utilizing only score estimates (the gradient of the log-density) rather than density evaluations, the researchers provide a method that converges exponentially fast, requiring only polylogarithmic steps relative to the target error. This represents an exponential improvement over previous sampling techniques that typically scaled polynomially. The authors demonstrate that their approach is robust under minimal data assumptions, with complexity primarily determined by the intrinsic dimension of the data. Furthermore, the framework successfully addresses the log-concave sampling problem, matching...