PaperlayerView exact revision on arXiv

Source-linked AI summary

Machine Learning for semi linear PDEs

Quentin Chan-Wai-Nam, Joseph Mikael, Xavier Warin

arXiv:1809.07609v2cs.LGmath.APstat.ML

TL;DR

High-dimensional PDE solvers face dimensionality barriers, motivating improved Deep BSDE architectures and a new deep-learning algorithm. The paper reports that the new method is competitive in accuracy with the improved Deep BSDE method, while demonstrating a conditional convergence result.

  • Problem

    Traditional deterministic methods for nonlinear PDEs suffer from the curse of dimensionality and are not expected to solve equations above dimensions 4 or 5.

    Source: §1 · p. 1

  • Method

    The paper improves Deep BSDE networks and develops a deep-learning algorithm for solving a fixed-point problem.

    Source: §3 · pp. 3–4, §3.3 · p. 5

  • Results

    The new algorithm is competitive in accuracy with the improved Deep BSDE algorithm, and its errors are reported to be of the same magnitude as the best Deep BSDE-based algorithms.

    Source: §1 · p. 2, §6 · p. 30

  • Takeaways & Limitations

    Under simplifying assumptions, the new algorithm’s loss can tend to zero, implying convergence to the true solution when the driver is independent of the gradient.

    Source: §1 · p. 2

    The new algorithm’s memory use grows with n_inner and d, though reported typical n_inner values of 4000 or 10000 fit in a standard computer’s memory.

    Source: §4.1 · p. 8, §6 · p. 30

Abstract

from arXiv · show

Recent machine learning algorithms dedicated to solving semi-linear PDEs are improved by using different neural network architectures and different parameterizations. These algorithms are compared to a new one that solves a fixed point problem by using deep learning techniques. This new algorithm appears to be competitive in terms of accuracy with the best existing algorithms.

1 Introduction

The paper targets high-dimensional semilinear PDEs, where deterministic methods face the curse of dimensionality and existing numerical approaches have practical limits. It improves Deep BSDE methods, introduces a deep-learning algorithm, compares them numerically, and studies conditions for convergence.

1 Introduction

  • Traditional deterministic PDE methods face the curse of dimensionality, while regression-based BSDE methods are described as practical only below dimensions 7 or 8.The cited regression methods can solve some nonlinear PDEs above dimension 4, but still face dimensionality limits.Source: §1 · p. 1
  • Branching methods for high-dimensional PDEs are limited to small maturities, small nonlinearities, and mainly polynomial nonlinearities in u and Du.The approach combines branching and time-step randomization with a Feynman–Kac representation, using Malliavin weights to estimate Du.Source: §1 · p. 1
  • Nesting Monte Carlo is more effective when the nonlinearity’s Lipschitz coefficients and problem maturity are not too high.Picard-iteration methods can solve some very high-dimensional PDEs, but tuning them can be difficult; a modified scheme has a polynomial-complexity result without numerical confirmation.Source: §1 · p. 2
  • Deep BSDE methods appear effective, but the cited work reports no result justifying their convergence, leaving their limitations difficult to establish.The paper therefore compares numerical performance and gives a conditional convergence demonstration for its new algorithm.Source: §1 · p. 2
  • The paper’s objectives are to improve Deep BSDE architectures and parameterizations, develop a new deep-learning algorithm, compare accuracy, and analyze convergence under simplifying assumptions.The convergence claim is conditional: when the driver is independent of the gradient, loss tending to zero implies convergence to the true solution.Source: §1 · p. 2

2 Existing Deep BSDE algorithms

Existing Deep BSDE algorithms discretize the associated forward process and BSDE, then train neural networks so the terminal solution matches the terminal condition. Their outputs and guarantees are tied to the chosen trajectories and discretization.

2 Existing Deep BSDE algorithms

  • Deep BSDE algorithms train neural networks by minimizing terminal-condition error after Euler-discretizing the forward process and associated BSDE.The terminal target is g(X_T), corresponding to u(T, X_T).Source: §2 · p. 2
  • The original architecture uses separate feed-forward networks at each time step, with no link between gradients estimated at successive times.The paper proposes adding global structure to encourage consistency between nearby time-step gradients.Source: §2 · pp. 2–3, Figure 1 · p. 3
  • Deep learning algorithms return Y_ti and Z_ti along simulated trajectories, but Deep BSDE variants do not return u(t,x) and Du(t,x) outside a given trajectory.The [Rai18] approach can evaluate arbitrary (t,x), but the authors say accuracy is not guaranteed for unseen times or trajectory combinations.Source: §2 · p. 3
  • The paper adopts the hard-constraint [HJW17] formulation, which its tests found converged faster overall and which permits recurrent schemes.The alternative [Rai18] formulation enforces Euler constraints softly in the loss.Source: §2 · p. 3

3 Different neural networks architectures

The paper explores neural-network architectures and parameterizations for DBSDE-based semi-linear PDE solvers, aiming to reduce parameter growth and improve optimization. It compares per-time-step networks with shared-parameter and LSTM-based designs.

3 Different neural networks architectures

  • Specific network structures are proposed to limit the growth of estimated weights as time discretization increases and potentially improve optimization by reducing numerical instabilities.The gradient networks approximate Du(ti, Xti) rather than σ⊤Du(ti, Xti), and the paper also investigates batch normalization, ELU activations, and residual connections.Source: §3 · pp. 3–4

3.1 Architectures building a different neural networks for each time step

  • Per-time-step DBSDE networks are modified by removing batch normalization from the final layer, replacing ReLU with ELU without batch normalization, or adding residual connections.The paper reports that omitting final-layer batch normalization improves final results over the original network.Source: §3.1 · p. 4, Figure 3 · p. 5

3.2 Architectures building one single neural network for all the time steps

  • Sharing one network across time is intended to reduce estimated weights and add regularity by encouraging gradients at nearby time steps to be close for a given state.The comparison is between N networks with d input features and one network with d + 1 features, including time.Source: §3.2 · p. 4

3.2.1 Sharing parameters through time

  • The Merged Deep BSDE uses a single network with time and state as inputs to estimate κ, and can also use Yt and g(Xt) as supplementary inputs.Batch normalization is not used because the distribution of X is likely non-stationary; when Yti is the network output, successive calls form a recurrent network. Shared-parameter variants add shortcut or residual connections.Source: §3.2.1 · p. 4, Figure 4 · p. 6

3.3 Adding a temporal structure with LSTM networks

  • LSTM-based designs use internal state to represent temporal dependencies that might compensate for Euler discretization error, which prevents the target g(XT) from being reached exactly.The compared designs include stacked LSTMs, supplementary Yt and g(Xt) inputs, a hybrid LSTM/fully connected network, and residual connections.Source: §3.3 · p. 5, Figure 5 · p. 6

4 Two new machine learning algorithms

The paper replaces time-discretized BSDE value estimation with two learning schemes that approximate the global solution function, and compares neural-network parameterizations for them. The schemes show promising numerical behavior, while their optimization and sampling costs and the conditions for theoretical convergence remain important qualifications.

4 Two new machine learning algorithms

  • The two algorithms estimate the global function u(t, x) rather than discrete-time BSDE values, though an Euler scheme may still be needed to simulate the forward process.Source: §4 · p. 7

4.1 A first scheme

  • The first scheme fits a neural-network pair (u, v) by minimizing a loss based on the operator T, approximated with Monte Carlo samples and Malliavin-weight gradient estimates.The operator maps a candidate pair to (ū, v̄); increasing inner samples reduces bias but increases computation and memory costs.Source: §4.1 · pp. 7–8

4.2 A second scheme

  • In the second scheme, automatic differentiation obtains Du from u, and adding a Du estimator to the loss can improve results.Source: §4.2 · pp. 8–9

4.3 Presentation of the networks used

  • The network comparison includes separate versus shared outputs for the first scheme and automatic-differentiation variants with different losses for the second.The figure labels these A, B, C, and C bis.; C bis uses loss (26).Source: §4.3 · pp. 9–10, Figure 7 · p. 10

4.4 Numerical and convergence consideration

  • Although slower than [H+17], the two new algorithms did not show its observed initialization-sensitive convergence failures in the numerical tests.The authors note that computation time cannot compete with [H+17] and describe the robustness difference as test-specific.Source: §4.4 · p. 10
  • Because training uses gradient descent on a non-convex problem, convergence to the solution is not proved and optimization may reach a local minimum.The authors say the method seems less prone to this issue than [H+17].Source: §4.4 · p. 10
  • Under the stated assumptions, the loss can be made arbitrarily small; when f is independent of Du and sufficiently Lipschitz in u, vanishing loss implies convergence to the continuous solution.Source: §4.4 · p. 11

5 Experiments & results on DBSDE algorithms

This section reports experiments comparing Deep BSDE network architectures and the paper’s fixed-point algorithm and variants across driver nonlinearities, maturity, time-step counts, equations, and computation time. It assesses their accuracy and error behavior, including the effects of architecture choice and post-processing.

5.1.1 Learning parameters

  • Suitable Deep BSDE network sizes are h = 2 hidden layers and w ≃d or 2d; deeper networks slow convergence without significant precision gains.The standard procedure uses batch size M = 300, initializes Y0 to E[g(XT)] when applicable, and starts Adam at η = 10^-2 with a learning-rate reduction when test loss plateaus.Source: §5.1.1 · p. 12, §5.1.2 · p. 13

5.2.1 Influence of the number of time steps

  • Merged and LSTM networks generally improve Deep BSDE results over other architectures; increasing time steps usually helps them but can harm or leave unchanged standard FC networks.On A.1.2 at d = 100, networks a., b., c., g., and i. fail to converge; residual LSTM j. and shortcut Merged e. perform noticeably better. On A.1.6 at d = 100, a., b., and c. perform worse than Merged and LSTM networks, while i. is unstable.Source: §5.2.1 · p. 14, Figure 8 · p. 15, Figure 9 · p. 16

5.2.2 Influence of the non-linearity in the driver

  • Merged networks outperform other architectures overall as driver nonlinearity increases, while the new architectures are generally more resilient than standard FC networks.On A.1.4, LSTMs show slightly higher errors at high r, and standard FC losses increase greatly; on A.1.7, FC b. and c. have lower initial-condition errors but greater integral errors than Merged and LSTM networks.Source: §5.2.2 · p. 18, Figure 11 · p. 19, Figure 12 · p. 20

5.2.3 Influence of the maturity

  • Errors tend to increase linearly with maturity T; at T ≥2.5, the standard training procedure produces instabilities, especially on A.1.4.Networks a. and g. fail to converge, while b. and c. perform slightly worse; the instability is less visible on A.1.7 except for h., and could be addressed by further hyperparameter tuning.Source: §5.2.3 · p. 21, Figure 13 · p. 21, Figure 14 · p. 22

5.2.4 Computation times

  • Merged and LSTM algorithms reach lower final losses in less computation time than other algorithms, with a computation-time advantage for Merged algorithms among the lowest-loss methods.The reported computation times for all algorithms remain approximately 1 hour; measurements used a NVIDIA Tesla K80 GPU and Intel Xeon E5-2680 v4 CPU, and depend on hardware and implementation.Source: Figure 15 · p. 23, §5.2.4 · p. 23

5.3 Numerical results: our new algorithm

  • The new algorithm approximates u and v with a neural network and solves a fixed-point problem; increasing ninner beyond several thousand or changing λ has little effect.It uses post-processing estimators with neval ≫ninner new particles; the standard values are ninner = 10000 and λ = 0.5, or λ = 1.0 when specified otherwise.Source: §5.3 · p. 24

5.3.1 Influence of neval and the post-processing step

  • Using post-processing estimators with neval ≫ninner improves accuracy, and larger neval improves it further; direct network outputs perform similarly to estimators using training samples.Pointwise evaluation can use neval = 1000000, while trajectory integral errors use neval = 100000 on 10 trajectories.Source: §5.3.1 · p. 24

5.3.2 Comparison of the new architectures

  • Algorithms A., C bis., and C. perform better overall on A.1.5; including a cost on Du yields lower errors on Y0 and Z, so C. is used in later comparisons.C bis. has little overall effect but slightly worsens trajectory precision, especially Z; computation times are comparable, with an advantage for B. High ninner in high dimensions can require large-memory CPU use and increase computation time.Source: §5.3.2 · p. 24

5.3.3 Influence of the non-linearity in the driver

  • As driver nonlinearity r increases, evaluation with larger neval lowers errors with diminishing gains; the new algorithm matches Deep BSDE on initial-condition precision and improves integral error.Final errors increase with r but remain acceptable.Source: §5.3.3 · p. 24, Figure 18 · p. 27

5.3.4 Influence of the maturity

  • As maturity T increases, initial-condition errors remain similar to Deep BSDE, Z0 error is slightly lower, integral errors are better overall, and all algorithms remain stable.The comparison uses N = 100 × T time steps for Deep BSDE and the same rule for the fixed-point algorithm’s integral errors.Source: §5.3.4 · pp. 25–26, Figure 19 · p. 28

5.3.5 Other examples

  • On other equations, the new algorithm shows comparable overall performance to Deep BSDE, with higher Y0 error than network f. and similar integral errors.The trajectory-error shape differs: Deep BSDE errors increase over time, while this trend is not apparent for the fixed-point algorithm.Source: §5.3.5 · p. 26, Table 7 · p. 29

6 Discussion

The new algorithm solves problems in the tested dimensional range with errors comparable to the best Deep BSDE algorithms, while avoiding time discretization. The discussion also reports robustness findings and flags ill-defined terminal-condition derivatives as problematic.

Discussion

  • In tests, no case had a small loss with an incorrect solution; the loss therefore appears to be a reasonably robust precision indicator.Most divergences were attributed to excessive learning rates, incorrect initialization, or vanishing or exploding gradients at very high time-step counts.Source: §6 · p. 30

Deep BSDE type algorithm

  • Merged or LSTM Deep BSDE networks improve precision and stability with fewer parameters, enabling more time steps and generic learning-rate strategies and batch sizes.Typical hidden-layer settings are two layers of size 2d; increasing non-linearity r and maturity T makes resolution harder, though solutions remain acceptable.Source: §6 · p. 30

Our new algorithm

  • d = 10 and d = 100 problems are solved in ∼1−10 hours, with errors of the same magnitude as the best Deep BSDE algorithms.The algorithm discretizes a conditional expectation operator rather than time, allowing u(t, x) evaluation for any t; memory grows with ninner and d.Source: §6 · p. 30

Special cases

  • Equations with ill-defined derivatives on the terminal condition remain problematic; for A.1.1, the authors say C. seems more correct, but further analysis is needed.The case has no analytical solution, and the tested Deep BSDE setup converged slowly with a final loss of ≃26.Source: §6 · p. 30
  • Y0 is 57.11 for f. and 57.37 for C.; Figure 21 reports final losses of 16.84 for f. and 3.87 for C., which are not comparable.Figure 21 compares Z-trajectory distributions using 1500 trajectories for f. and 10 for C., with neval = 100000.Source: Figure 21 · p. 30

A.1 Some test PDEs

The test-PDE appendix recalls the semilinear PDE notation and specifies the corresponding coefficients and functions for each example. For implementation, it uses a transformed driver for convenience and more direct formulations.

A.1 Some test PDEs

  • The appendix recalls the notation used for the semilinear PDEs.The following examples provide their corresponding µ, σ, f, and g.Source: §A.1 · p. 31
  • For implementation, the authors use ˜f(t, x, u(t, x), Du(t, x)) := f(t, x, u(t, x), σ⊤(t, x)Du(t, x)).This substitutes σ⊤Du for the gradient argument of f.Source: §A.1 · p. 31
  • Using ˜f is for convenience and allows a more direct formulation for some PDEs without influencing the results.Source: §A.1 · p. 31

A.1.1 A Black-Scholes equation with default risk

The Black-Scholes equation with default risk uses parameters from EHJ17 and HJW17 unless otherwise stated, and starts from the specified initial condition.

A.1.1 A Black-Scholes equation with default risk

  • Unless otherwise stated, the parameters are µ = 0.02, σ = 0.2, δ = 2/3, R = 0.02, γh = 0.2, γl = 0.02, vh = 50, and vl = 70.Source: §A.1.1 · p. 31
  • The initial condition is X0 = (100, · · · , 100).Source: §A.1.1 · p. 31
  • The SDE dynamic is computed using its closed formula.Source: §A.1.1 · p. 31

A.1.2 A Black-Scholes-Barenblatt equation

The Black-Scholes-Barenblatt equation uses the stated parameters from Rai18 unless otherwise stated, with the specified initial condition and a closed-form SDE dynamic.

A.1.2 A Black-Scholes-Barenblatt equation

A.1.3 A Hamilton-Jacobi-Bellman equation

The subsection specifies parameter and initial-state defaults and gives a Monte Carlo baseline setting at dimension 100.

A.1.3 A Hamilton-Jacobi-Bellman equation

  • The defaults are λ = 1.0 and X0 = (0, · · · , 0), with the settings attributed to [HJW17].Source: §A.1.3 · p. 31
  • The baseline is computed using 10 million Monte-Carlo realizations at d = 100.Source: §A.1.3 · p. 32

A.1.4 An oscillating example with a square non-linearity

The example specifies default parameters and an initial condition, and states that the min and max in f are intended to make f Lipschitz.

A.1.4 An oscillating example with a square non-linearity

  • The [War18b] example uses µ0 = 0.2, σ0 = 1.0, a = 0.5, r = 0.1 and X0 = (1.0, 0.5, 1.0, · · · ); min and max in f are intended to make f Lipschitz.Source: §A.1.4 · p. 32

A.1.5 A non-Lipschitz terminal condition

The appendix records settings for three examples and outlines proof steps for Propositions 4.6 and 4.7.

A.1.5 A non-Lipschitz terminal condition

  • The example uses α = 0.5 and X0 = (0, · · · , 0); its baseline uses 10 million Monte-Carlo realizations at d = 10.Source: §A.1.5 · p. 32

A.1.6 An oscillating example with Cox-Ingersoll-Ross propagation

  • For the [War18a] Cox-Ingersoll-Ross example, 2k̂m̂ > σ̂² is stated to ensure that X remains positive.The defaults include a = 0.1, α = 0.2, T = 1.0, k̂ = 0.1, m̂ = 0.3, σ̂ = 0.2, with X0 = (0.3, · · · , 0.3).Source: §A.1.6 · p. 33

A.1.7 An oscillating example with inverse non-linearity

  • The inverse-nonlinearity example specifies µ0 = 0.2, σ0 = 1.0, a = 0.5, r = 0.1 and X0 = (1.0, 0.5, 1.0, · · · ).Source: §A.1.7 · p. 33

A.2 Demonstration of Proposition 4.6

  • For Proposition 4.6, the proof invokes a Feynman-Kac relation and approximates u and Du with a pair whose stated error is at most ϵ.The Feynman-Kac relation is stated under Lipschitz f, bounded f and g, and the regularity of u; the approximation is given in (40).Source: §A.2 · p. 34

A.3 Demonstration of Proposition 4.7

  • For Proposition 4.7, the proof places each compact K within Ω0,x for sufficiently large n and uses bounds before taking K small enough to complete the proof.Source: §A.3 · p. 35

Related papers

Loading 1809.07609v2…