Faster Diffusion-based Sampling with Randomized Midpoints: Sequential and Parallel
<|reference_start|>Faster Diffusion-based Sampling with Randomized Midpoints: Sequential and Parallel: In recent years, there has been a surge of interest in proving discretization bounds for diffusion models. These works show that for essentially any data distribution, one can approximately sample in polynomial time given a sufficiently accurate estimate of its score functions at different noise levels. In this work, we propose a new discretization scheme for diffusion models inspired by Shen and Lee's randomized midpoint method for log-concave sampling~\cite{ShenL19}. We prove that this approach achieves the best known dimension dependence for sampling from arbitrary smooth distributions in total variation distance ($\widetilde O(d^{5/12})$ compared to $\widetilde O(\sqrt{d})$ from prior work). We also show that our algorithm can be parallelized to run in only $\widetilde O(\log^2 d)$ parallel rounds, constituting the first provable guarantees for parallel sampling with diffusion models.   As a byproduct of our methods, for the well-studied problem of log-concave sampling in total variation distance, we give an algorithm and simple analysis achieving dimension dependence $\widetilde O(d^{5/12})$ compared to $\widetilde O(\sqrt{d})$ from prior work.<|reference_end|>
@article{gupta2024faster,
    title={Faster Diffusion Sampling with Randomized Midpoints: Sequential and
  Parallel},
    author={Shivam Gupta, Linda Cai, Sitan Chen},
    journal={arXiv preprint arXiv:2406.00924},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.00924},
    primaryClass={cs.LG cs.DS math.ST stat.ML stat.TH}
}