notesum.ai

Published at December 10

Parallel simulation for sampling under isoperimetry and score-based diffusion models

cs.DS

cs.DC

cs.LG

cs.NA

math.NA

Released Date: December 10, 2024

Authors: Huanjian Zhou¹, Masashi Sugiyama²

Aff.: ¹The University of Tokyo; ²RIKEN AIP

Arxiv: http://arxiv.org/pdf/2412.07435v1

Work dynamics	Measure	Iteration Complexity	Space Complexity
[53, Theorem 4] underdamped Langevin diffusion	$\mathsf{W}_{2}$	$\widetilde{\mathcal{O}}\left(\log^{2}\left(\frac{{d}}{\varepsilon^{2}}\right)\right)$	$\widetilde{\mathcal{O}}\left(\frac{d^{3/2}}{\varepsilon}\right)$
[61, Corollary 2] underdamped Langevin diffusion	$\mathsf{W}_{2}$	$\widetilde{\mathcal{O}}\left(\log^{2}\left(\frac{d}{\varepsilon^{2}}\right)\right)$	$\widetilde{\mathcal{O}}\left(\frac{d^{3/2}}{\varepsilon}\right)$
[1, Theorem 15] underdamped Langevin diffusion	$\mathsf{TV}$	$\widetilde{\mathcal{O}}\left(\log^{2}\left(\frac{d}{\varepsilon^{2}}\right)\right)$	$\widetilde{\mathcal{O}}\left(\frac{d^{3/2}}{\varepsilon}\right)$
[1, Theorem 13] overdamped Langevin diffusion	$\mathsf{KL}$	$\widetilde{\mathcal{O}}\left(\log^{2}\left(\frac{d}{\varepsilon^{2}}\right)\right)$	$\widetilde{\mathcal{O}}\left(\frac{d^{2}}{\varepsilon^{2}}\right)$
Theorem 4.2 overdamped Langevin diffusion	$\mathsf{KL}$	$\bm{\widetilde{\mathcal{O}}\left(\log\left(\frac{d}{\varepsilon^{2}}\right)% \right)}$	$\widetilde{\mathcal{O}}\left(\frac{d^{2}}{\varepsilon^{2}}\right)$