Microsoft Research

Convergence Analysis for Fast High-Order ODE Solvers in Diffusion Probabilistic Models

Score-based generative models have revolutionized high-dimensional sampling through forward diffusion and reverse processes. While stochastic DDPM samplers benefit from mature polynomial convergence theory, deterministic probability flow ODEs (underlying efficient DDIM-style samplers) offer superior speed through high-order Runge-Kutta integrators but have lagged in rigorous analysis of the combined effects of score approximation error and discretization error. In our two works, we establish convergence guarantees for p-th order Runge-Kutta integrators with maximum step size $H_{max}$ under $L^2$ score matching error $\varepsilon_{score} ^2$. Using the method of characteristic lines, Gagliardo-Nirenberg interpolation, and interpolation of the discrete solution, we bound the total variation distance between the target and generated distributions. Both works yield the iteration complexity $O(d^{1+1/p} \varepsilon^{-1/p})$ to achieve TV accuracy $\varepsilon$. The first work considers the continuous-in-time score function and score error for the Ornstein-Uhlenbeck process and requires the approximate score $s_t$ to be $C^p$ in the spatial variable to obtain the TV bound $O(d^{3/4} \varepsilon_{score}^{1/2} + d \cdot (d H_{max})^p)$. The second work advances to the practical discrete-in-time score matching setting with arbitrary variance schedules and non-uniform steps. It relaxes the regularity requirement to only $C^2$ on $s_t$ while proving the TV bound $O(d^{7/4} \varepsilon_{score}^{1/2} + d \cdot (d H_{\max})^p)$. Numerical experiments on benchmark datasets confirm the theoretical rates and verify that the trained score functions $s_t$ satisfy the $C^2$ assumption in practice. These results provide a solid theoretical foundation for designing fast, high-order deterministic diffusion samplers while quantifying the interplay between score matching error and time discretization error. Speaker bio: Zhengjiang Lin is a C.L.E. Moore Instructor in the Department of Mathematics at MIT. He is interested in calculus of variations, elliptic PDEs, and differential geometry – including their interactions with each other, and some applications of these tools to problems from probability and machine learning theory. He obtained his PhD in Mathematics at the Courant Institute of Mathematical Sciences at NYU. Find seminar details and upcoming talks: https://www.microsoft.com/en-us/research/event/microsoft-research-new-england-generative-modeling-sampling-seminar/