# On the Parallel Complexity of Multilevel Monte Carlo in Stochastic Gradient Descent

arXiv: https://arxiv.org/abs/2310.02402 · HTML: https://mlsanity.com/paper/2310.02402/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 38 references that are in the map.
- First posted on arXiv 3 Oct 2023.

## Builds on (most cited first, 19 of 19)

- [Neural Ordinary Differential Equations](https://mlsanity.com/paper/1806.07366/) (2018)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Sigmoid-Weighted Linear Units for Neural Network Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/1702.03118/) (2017)
- [Neural Controlled Differential Equations for Irregular Time Series](https://mlsanity.com/paper/2005.08926/) (2020)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [On Neural Differential Equations](https://mlsanity.com/paper/2202.02435/) (2022)
- [Large-Scale Methods for Distributionally Robust Optimization](https://mlsanity.com/paper/2010.05893/) (2020)
- [Neural Stochastic Differential Equations: Deep Latent Gaussian Models in the Diffusion Limit](https://mlsanity.com/paper/1905.09883/) (2019)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Neural Jump Stochastic Differential Equations](https://mlsanity.com/paper/1905.10403/) (2019)
- [Deep Hedging](https://mlsanity.com/paper/1802.03042/) (2018)
- [Neural Stochastic PDEs: Resolution-Invariant Learning of Continuous Spatiotemporal Dynamics](https://mlsanity.com/paper/2110.10249/) (2021)
- [Neural Jump Ordinary Differential Equations: Consistent Continuous-Time Prediction and Filtering](https://mlsanity.com/paper/2006.04727/) (2020)
- [Latent State Marginalization as a Low-cost Approach for Improving Exploration](https://mlsanity.com/paper/2210.00999/) (2022)
- [Multilevel Bayesian Quadrature](https://mlsanity.com/paper/2210.08329/) (2022)
- [Bayesian Deep Learning with Multilevel Trace-class Neural Networks](https://mlsanity.com/paper/2203.12961/) (2022)
- [Multilevel Monte-Carlo for Solving POMDPs Online](https://mlsanity.com/paper/1907.09673/) (2019)
- [A Multilevel Reinforcement Learning Framework for PDE-based Control](https://mlsanity.com/paper/2210.08400/) (2022)

## Abstract (arXiv)

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.