Splitting method improves sampling accuracy for stochastic simulations
A Splitting Method for SDE Terminal-Law Estimation
Machine Learning
Summary
Sometimes, we want to create random examples from complex systems that change over time with randomness. Usually, these examples are made by simulating many independent paths, which can be slow and use a lot of computing power. The authors studied a new way to generate these examples by splitting simulation paths into a tree structure, which reuses parts of the paths to be more efficient. They carefully examined the accuracy and found their method improves how closely the samples match the true outcome, saving computational work. Their approach worked well even on complex image data.
What this means in practice
- •For machine learning engineers: Generate more accurate samples from diffusion models using fewer computations to improve training and inference efficiency.
- •For quantitative analysts: Improve accuracy in estimating final probability distributions from stochastic simulations for financial risk modeling with limited computational budget.
Authors
Rushil Gupta, Sandeep Juneja
Abstract
In many settings involving stochastic differential equations, including in diffusion based generative AI, our aim is to accurately generate samples from a terminal distribution. Typically, this is done by generating i.i.d. samples of diffusion paths. Given a fixed simulation budget, a reasonable way to gain efficiency may be to instead generate a tree of paths through appropriately split partial paths. This suggests improved performance, but one worries about the injected dependence. In this paper, we study this issue comprehensively. With Kolmogorov-Smirnov distance as a measure of accuracy, we identify the limiting errors of the associated empirical distributions as the simulation budget increases to infinity. We characterize a splitting strategy motivated by a corresponding asymptotic optimization problem. The theoretical results bring out the elegant underlying structure in the problem. Practical implementation involves two phases, an initial estimation phase and a final inference phase. Overall, we observe a 10-25% improvement in mean error over i.i.d. samples in many settings. In an exploratory CIFAR-10 study, our method reduces the maximum mean discrepancy by 8-13%.