Solving non-linear Kolmogorov equations in large dimensions by using deep learning: a numerical comparison of discretization schemes

Nicolas Macris, Raffaele Marino

TL;DR

This paper explores how different numerical discretization schemes for stochastic differential equations impact the accuracy of deep learning models trained to solve high-dimensional non-linear Kolmogorov equations. They find that higher-order schemes, like Milstein, can significantly improve accuracy without increasing computational cost, offering a more robust deep learning approach for these complex problems.

What Problem Does This Paper Address?

High-dimensional partial differential equations (PDEs), specifically non-linear Kolmogorov equations, are crucial for modeling phenomena in finance, physics, and engineering. However, traditional numerical methods struggle with the "curse of dimensionality," becoming computationally intractable as the number of dimensions increases. A recent breakthrough by Han and Jentzen proposed using deep learning to approximate solutions to these equations, leveraging the connection between Kolmogorov equations and forward-backward stochastic differential equations (FBSDEs). This deep learning approach trains a neural network on samples from the underlying stochastic process, achieving polynomial complexity in high dimensions. This paper investigates a key component of this deep learning method: the discretization scheme used for the stochastic differential equations. The authors aim to understand if using more sophisticated discretization schemes can lead to better accuracy without sacrificing the computational efficiency that makes the deep learning approach so attractive.

Methods

The core of the paper lies in comparing three different discretization schemes for the stochastic differential equations (SDEs) that underpin the Kolmogorov equations:

  • Euler-Maruyama (EM): This is the simplest and most commonly used first-order scheme, also used in the original deep learning method [1].
  • Milstein Scheme: A second-order scheme that includes higher-order terms from the Taylor expansion of the SDE. This is a more accurate scheme than EM.
  • Leimkuhler-Matthews (LM) Scheme: A first-order scheme designed for molecular sampling, which involves a non-Markovian (colored noise) process.

For each discretization scheme, the authors construct a corresponding deep neural network architecture. These networks are trained to approximate the solution of the backward Kolmogorov equation by minimizing a quadratic loss function based on the terminal condition and the discretized FBSDE. The key innovation here is adapting the network architecture to accommodate the specific terms arising from each discretization scheme.

Datasets

The paper does not introduce new datasets. Instead, it uses benchmarked examples from existing literature and well-known equations for evaluation:

  • Black-Scholes equation: A prominent example from financial mathematics.
  • Allen-Cahn equation: A reaction-diffusion equation used in physics for pattern formation.
  • An exactly solvable non-linear diffusion equation: Used to analyze the scaling of computational complexity with dimension.
  • Hamilton-Jacobi-Bellman (HJB) equation: Used in optimal control theory.

The "datasets" for training are generated stochastic trajectories sampled from the underlying SDEs. The number of these trajectories and their initial points are varied to test computational complexity and accuracy.

Key Insights and Ideas

  • Discretization Matters: The choice of discretization scheme for the underlying SDEs significantly impacts the accuracy of the deep learning solution for Kolmogorov equations.
  • Higher-Order Schemes Pay Off: The Milstein scheme, a second-order method, consistently provides improved accuracy compared to the simpler Euler-Maruyama scheme, often without increasing computational complexity. This suggests that capturing more of the SDE's dynamics leads to a better neural network approximation.
  • LM Scheme Limitations: The Leimkuhler-Matthews scheme, while useful for sampling, did not perform as well as EM or Milstein for the problems studied. This might be due to its specific nature or the increased memory requirements for finer time steps.
  • Curse of Dimensionality Mitigation: The paper reinforces that the deep learning approach, regardless of the discretization scheme, generally avoids the curse of dimensionality, with training complexity scaling polynomially with dimension.
  • Network Architecture Adaptation: The authors demonstrate that the deep learning architecture can be effectively adapted to incorporate the specific terms arising from different discretization schemes, allowing for a unified framework.

Key Results

  • Improved Accuracy with Milstein: For the Black-Scholes, Allen-Cahn, and HJB equations, the Milstein scheme-based networks achieved higher accuracy than the Euler-Maruyama scheme, often matching or exceeding benchmark values from multilevel Picard methods. For instance, in the Black-Scholes example, the Milstein scheme achieved a value of 57.276 ± 0.012, agreeing well with Picard's method.
  • LM Scheme Underperformance: The Leimkuhler-Matthews scheme generally showed poorer performance, sometimes overestimating solutions, as seen in the Allen-Cahn and HJB examples.
  • Computational Complexity: The study confirms that the computational complexity scales polynomially with the dimension for all schemes, and importantly, the Milstein scheme did not introduce a higher computational order compared to Euler-Maruyama.
  • Scaling with Dimension: For an exactly solvable non-linear diffusion equation, the number of training trajectories required to achieve a given error was shown to scale polynomially with dimension (e.g., P = O(d^1.78) for EM).

Limitations and Future Work

  • LM Scheme Performance: The paper notes that the Leimkuhler-Matthews scheme's underperformance might be related to the increased number of sub-networks needed for smaller time steps, leading to prohibitive memory requirements. Further investigation into optimizing this scheme or its application is suggested.
  • Rigorous Analysis: The authors acknowledge that rigorous analysis of why deep learning overcomes the curse of dimensionality for non-linear equations is still an open problem.
  • Further Discretizations: The paper suggests exploring even higher-order discretizations and other algorithmic improvements proposed in the literature.
  • Non-linear Setting Analysis: The authors highlight the need for extending the rigorous analysis of deep learning representation power to the non-linear setting, as current analyses are primarily for linear equations.

Summary updated

Abstract

Non-linear partial differential Kolmogorov equations are successfully used to describe a wide range of time dependent phenomena, in natural sciences, engineering or even finance. For example, in physical systems, the Allen-Cahn equation describes pattern formation associated to phase transitions. In finance, instead, the Black-Scholes equation describes the evolution of the price of derivative investment instruments. Such modern applications often require to solve these equations in high-dimensional regimes in which classical approaches are ineffective. Recently, an interesting new approach based on deep learning has been introduced by E, Han, and Jentzen [1][2]. The main idea is to construct a deep network which is trained from the samples of discrete stochastic differential equations underlying Kolmogorov's equation. The network is able to approximate, numerically at least, the solutions of the Kolmogorov equation with polynomial complexity in whole spatial domains. In this contribution we study variants of the deep networks by using different discretizations schemes of the stochastic differential equation. We compare the performance of the associated networks, on benchmarked examples, and show that, for some discretization schemes, improvements in the accuracy are possible without affecting the observed computational complexity.
BibTeX
@article{macris2020solving,
  author = {Nicolas Macris and Raffaele Marino},
  title = {{Solving non-linear Kolmogorov equations in large dimensions by using deep learning: a numerical comparison of discretization schemes}},
  journal = {J. Sci. Comput.},
  year = {2020},
  url = {https://openreview.net/forum?id=2btkv4FFybM},
}
Figure