On the Parallel Complexity of Multilevel Monte Carlo in Stochastic Gradient Descent
This addresses a practical bottleneck for researchers and practitioners using MLMC in SGD on parallel platforms like GPUs, offering an incremental improvement.
The paper tackled the poor parallel scaling of Multilevel Monte Carlo (MLMC) in stochastic gradient descent (SGD) on GPUs by proposing a delayed MLMC gradient estimator that recycles gradients from earlier steps, reducing average parallel complexity per iteration at the cost of a slightly worse convergence rate, as demonstrated in deep hedging experiments.
In the stochastic gradient descent (SGD) for sequential simulations such as the neural stochastic differential equations, the Multilevel Monte Carlo (MLMC) method is known to offer better theoretical computational complexity compared to the naive Monte Carlo approach. However, in practice, MLMC scales poorly on massively parallel computing platforms such as modern GPUs, because of its large parallel complexity which is equivalent to that of the naive Monte Carlo method. To cope with this issue, we propose the delayed MLMC gradient estimator that drastically reduces the parallel complexity of MLMC by recycling previously computed gradient components from earlier steps of SGD. The proposed estimator provably reduces the average parallel complexity per iteration at the cost of a slightly worse per-iteration convergence rate. In our numerical experiments, we use an example of deep hedging to demonstrate the superior parallel complexity of our method compared to the standard MLMC in SGD.