Polynomial Speedup in Diffusion Models with the Multilevel Euler-Maruyama Method

View PDF HTML (experimental)

Abstract:We introduce the Multilevel Euler-Maruyama (ML-EM) method compute solutions of SDEs and ODEs using a range of approximators $f^1,\dots,f^k$ to the drift $f$ with increasing accuracy and computational cost, only requiring a few evaluations of the most accurate $f^k$ and many evaluations of the less costly $f^1,\dots,f^{k-1}$. If the drift lies in the so-called Harder than Monte Carlo (HTMC) regime, i.e. it requires $\epsilon^{-\gamma}$ compute to be $\epsilon$-approximated for some $\gamma>2$, then ML-EM $\epsilon$-approximates the solution of the SDE with $\epsilon^{-\gamma}$ compute, improving over the traditional EM rate of $\epsilon^{-\gamma-1}$. In other terms it allows us to solve the SDE at the same cost as a single evaluation of the drift. In the context of diffusion models, the different levels $f^{1},\dots,f^{k}$ are obtained by training UNets of increasing sizes, and ML-EM allows us to perform sampling with the equivalent of a single evaluation of the largest UNet. Our numerical experiments confirm our theory: we obtain up to fourfold speedups for image generation on the CelebA dataset downscaled to 64x64, where we measure a $\gamma\approx2.5$. Given that this is a polynomial speedup, we expect even stronger speedups in practical applications which involve orders of magnitude larger networks.

Subjects:

Machine Learning (cs.LG); Numerical Analysis (math.NA); Machine Learning (stat.ML)

Cite as: arXiv:2603.24594 [cs.LG]

(or arXiv:2603.24594v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2603.24594

arXiv-issued DOI via DataCite (pending registration)

Submission history

From: Arthur Jacot [view email] [v1] Wed, 25 Mar 2026 17:59:45 UTC (828 KB)