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.
