Source-linked AI summary
Algorithms for Solving High Dimensional PDEs: From Nonlinear Monte Carlo to Machine Learning
Weinan E, Jiequn Han, Arnulf Jentzen
TL;DR
The paper addresses how PDEs and related control or variational problems can be approximated in very high dimensions despite the curse of dimensionality. It reviews nonlinear Monte Carlo, deep-learning, and traditional variational formulations, emphasizing rigorous multilevel Picard results for nonlinear parabolic PDEs. These results show that MLP methods overcome the curse of dimensionality for broad classes of semilinear PDEs, while rigorous deep-learning guarantees remain unresolved.
Problem
High-dimensional PDE solvers face exponentially growing computational complexity, and rigorous evidence that deep-learning methods overcome this barrier remains unavailable.
Method
The paper reviews stochastic algorithms such as multilevel Picard and Deep BSDE methods, machine-learning approximation methods, and Ritz, Galerkin, and least-square formulations.
Results
MLP methods are proven to overcome the curse of dimensionality for semilinear PDEs with general time horizons, including nonlinear heat PDEs with α = 1 and β = 2 + δ for arbitrarily small δ.
Takeaways & Limitations
The results support complexity-based study of high-dimensional PDEs and their relevance to high-dimensional control theory and reinforcement learning.
Takeaways & Limitations
The Galerkin formulation is difficult to work with despite encouraging progress, and the exponent α remains unresolved for specific high-dimensional example classes.
Abstract
from arXiv · showhide
In recent years, tremendous progress has been made on numerical algorithms for solving partial differential equations (PDEs) in a very high dimension, using ideas from either nonlinear (multilevel) Monte Carlo or deep learning. They are potentially free of the curse of dimensionality for many different applications and have been proven to be so in the case of some nonlinear Monte Carlo methods for nonlinear parabolic PDEs. In this paper, we review these numerical and theoretical advances. In addition to algorithms based on stochastic reformulations of the original problem, such as the multilevel Picard iteration and the Deep BSDE method, we also discuss algorithms based on the more traditional Ritz, Galerkin, and least square formulations. We hope to demonstrate to the reader that studying PDEs as well as control and variational problems in very high dimensions might very well be among the most promising new directions in mathematics and scientific computing in the near future.
1 Introduction
High-dimensional PDEs are difficult because conventional methods suffer from the curse of dimensionality, while recent Monte Carlo and machine-learning approaches offer algebraic-scaling alternatives. The paper reviews these advances and highlights rigorous results for multilevel Picard methods on nonlinear parabolic PDEs.
- Motivation: High-dimensional PDE computation is difficult because traditional complexity grows exponentially with dimension, limiting finite-difference and finite-element methods to relatively low dimensions.Sparse grids may extend applicability to around 10 dimensions, but the paper seeks algorithms whose cost scales algebraically with dimension.
- Monte Carlo foundations: Grid-based quadrature rules suffer from the curse of dimensionality, whereas Monte Carlo achieves an O(1/√n) rate independent of dimension.Reducing the error to ε requires order ε^-2 samples.
- Multilevel Picard methods: MLP methods are recursive nonlinear Monte Carlo methods that achieve α = 1 and β = 2 + δ for arbitrarily small δ over a wide class of nonlinear parabolic equations.Their estimates provide dimension-independent complexity exponents in the paper’s approximation framework.
- Approaches reviewed: The paper reviews machine-learning approximation methods, including deep neural networks and stochastic-gradient-based optimization, alongside multilevel Picard approximation methods.The reviewed approaches include stochastic reformulations and traditional Ritz, Galerkin, and least-square formulations.
- Theory and open questions: Rigorous analyses establish that MLP methods overcome the curse of dimensionality for semilinear PDEs with general time horizons, while comparable rigorous results for deep-learning PDE methods remain unavailable.The paper identifies this as the only class of approximation methods with such a proof in the cited literature.
- Multilevel Picard methods: For semilinear heat PDEs, MLP methods can match the computational complexity of classical Monte Carlo for linear heat PDEs up to an arbitrarily small polynomial-order difference.The stated nonlinear result uses α = 1 and β = 2 + δ, compared with α = 1 and β = 2 in the linear case.
2 General remarks about algorithms for solving PDEs in high dimensions
The review surveys algorithms for high-dimensional PDEs, including stochastic reformulations, deep learning, and variational approaches, while highlighting their applications and current theoretical and practical limits.
- Approaches: The review covers algorithms for high-dimensional PDEs based on stochastic reformulations, deep learning, and variational formulations.The surveyed approaches include multilevel Picard, Deep BSDE, Ritz, Galerkin, and least-square methods.
- Stochastic reformulations: Monte Carlo evaluation via the Feynman-Kac formula can compute linear parabolic PDE solutions without suffering from the curse of dimensionality.The method expresses the PDE solution as an expectation over a diffusion process and evaluates it using Monte Carlo.
- Stochastic reformulations: Convex Hamilton-Jacobi equations admit Hopf-formula representations whose right-hand sides can be computed using optimization algorithms.The Hopf formula uses the Legendre transform of the Hamiltonian; Darbon and Osher developed an algorithm based on this approach.
- Applications: Neural-network methods have been applied to stochastic control, spin and electron Schrödinger equations, variational problems, parametric PDEs, stochastic games, and related systems.The review also notes applications involving restricted Boltzmann machines, permutation-symmetric ansätze, neural-network trial functions, and coupled PDE systems.
- Limitations: The review identifies important boundaries: neural-network algorithms for many-body Schrödinger equations remain at an early stage, and reinforcement learning is not covered.For variational problems, robust neural-network Galerkin formulations are described as problematic, whereas Ritz formulations are comparatively straightforward.
- Nonlinear parabolic PDEs: The multilevel Picard method was the first algorithmic class for general nonlinear parabolic PDEs with general time horizons in dimensions d ≥40 and has the most complete theory among these methods.The review states that this theory proves MLP overcomes the curse of dimensionality, while Deep BSDE was the first systematic deep-learning application to general high-dimensional PDEs.
3 The Deep BSDE method
The Deep BSDE method reformulates high-dimensional nonlinear parabolic PDEs through BSDEs and trains neural networks on time-discretized stochastic paths. The review reports benchmark results while noting that its theoretical analysis remains incomplete.
- The Deep BSDE method reformulates general nonlinear parabolic PDEs as stochastic optimization problems using BSDEs.
- Neural networks approximate the initial value function and gradient-related processes, with Euler discretization producing subnetworks at each time step.
- Training uses the terminal-condition mismatch as a loss, while simulated stochastic paths provide data on the fly and support SGD.
- LQG benchmark: 0.17% relative error was achieved for the 100-dimensional LQG benchmark in 330 seconds at λ = 1.
- Nonlinear Black-Scholes benchmark: 0.46% relative error was achieved for a 100-asset nonlinear Black-Scholes problem with default risk in 617 seconds.
- Theoretical analysis has established only the time-discretization step; function-class and adaptation analyses remain incomplete.
4 Control problems in high dimensions
High-dimensional optimal control is difficult primarily for closed-loop controls, whose value must be represented throughout the state space. The section contrasts this with open-loop control and discusses neural-network training-data strategies.
- Open-loop controls are defined only along an optimal path, so their independent-variable dimensionality is one and the curse is not a central issue.
- The curse of dimensionality arises for closed-loop controls because they must be specified as functions over the state space.
- Accurate closed-loop control requires solving the control problem for a large set of initial conditions rather than a single initial condition.
- A Gibbs distribution based on the value function is proposed as one choice for sampling initial states with relatively small values.
- Training-data generation can combine two-point boundary-value solves with neural-network value-function training, using warm starts and adaptive sampling to reduce difficulty.
5 Ritz, Galerkin, and least squares
Ritz, Galerkin, and least-squares formulations provide variational or weak-form routes for neural-network PDE solvers. The section describes Deep Ritz, least squares, and Galerkin approaches alongside their practical and theoretical limitations.
- Ritz uses a variational principle, Galerkin uses a weak form with trial and test functions, and least squares minimizes squared PDE residuals.
- Deep Ritz: Deep Ritz replaces the traditional trial-function space with neural networks, evaluates the functional by numerical quadrature, and solves the resulting optimization problem.
- Deep Ritz: High-dimensional Deep Ritz computation requires effective Monte Carlo integration, and its integral discretization interacts with neural-network trial-function discretization.
- Deep Ritz: Deep Ritz is presented on a corner-singularity example using 811 neural-network parameters and a finite-difference comparison with 1681 degrees of freedom.
- Deep Ritz limitations: Deep Ritz generally produces a nonconvex variational problem, lacks consistent convergence-rate conclusions, and complicates essential boundary conditions.
- Least squares and Galerkin: Least-squares formulations resemble Ritz optimization under a sampleable, non-degenerate probability distribution, while Galerkin formulations retain explicit test functions.
- Galerkin limitations: The Galerkin min-max formulation is difficult to work with, with challenges similar to those encountered in Wasserstein GANs.
6 Multilevel Picard approximation methods for nonlinear PDEs
Multilevel Picard (MLP) methods reformulate semilinear PDEs as stochastic fixed-point problems and recursively approximate their Picard iterations with full-history multilevel Monte Carlo. Under stated assumptions, their computational cost grows polynomially with dimension and nearly quadratically with inverse accuracy, with rigorous results extending beyond the basic theorem.
- Scope: MLP methods are analyzed here for semilinear heat PDEs with Lipschitz continuous nonlinearities and bounded initial values.Theorem 3 uses this restricted setting, although related analyses cover more general second-order operators.
- Complexity: Theorem 3 achieves L2 error at most ε with computational cost at most c d^c ε^-3, polynomial in dimension and cubic in reciprocal accuracy.The cost counts function evaluations and random-variable realizations used to compute the MLP approximation.
- Extensions: More general MLP results allow arbitrary spatial evaluation points, provide explicit constants and exponents, and can yield dimension-linear cost under bounded initial conditions.Most cited results also reduce the reciprocal-accuracy dependence from cubic to at most quadratic up to an arbitrarily small exponent increase.
- Extensions: MLP schemes overcome the curse of dimensionality for elliptic PDEs with Lipschitz nonlinearities as well as parabolic PDEs.The review also reports encouraging simulations for semilinear Black–Scholes, systems of semilinear PDEs, Allen–Cahn, and sine-Gordon equations.
- Method: The derivation first converts the PDE into a stochastic fixed-point equation, then applies Picard iterations and recursively approximates them with full-history multilevel Monte Carlo.The fixed-point solution corresponds to the PDE solution, while the resulting Monte Carlo approximation is nonlinear and recursive.
- Theory: The rapid, factorial convergence of fixed-point iterations combined with efficient multilevel sampling underpins proofs of curse-of-dimensionality avoidance for broad semilinear PDE classes.The review states that MLP methods are currently the only schemes with such proofs for semilinear PDEs with general time horizons.
7 Mathematical results for neural network approximations for PDEs
The review presents rigorous neural-network approximation results for certain high-dimensional semilinear heat PDEs, under polynomial-growth and approximability assumptions. These results establish polynomial dependence on dimension and inverse accuracy, while broader claims about trained deep-learning algorithms remain unresolved.
- Status: No complete rigorous analysis proves or disproves that a deep-learning-based PDE solver overcomes the curse of dimensionality.Existing mathematical results establish approximation capacity for deep neural networks, not the full algorithmic conjecture.
- Related results: For linear Black–Scholes PDEs, prior results prove neural networks with parameter counts polynomial in both dimension and reciprocal approximation accuracy.The review also notes extensions from linear PDEs to nonlinear heat PDEs with Lipschitz nonlinearities.
- Theorem 4: Theorem 4 shows that DNNs approximate solutions of Lipschitz-semilinear heat PDEs without curse-of-dimensionality dependence under specified regularity and initial-function assumptions.The theorem assumes the initial values themselves admit suitably efficient DNN approximations.
- Assumptions: The theorem’s assumptions require polynomial growth of the PDE solutions and polynomial-size DNN approximations of the initial value functions.The parameter bound P(g_d,ε) ≤ κ d^κ ε^-κ expresses polynomial dependence on dimension and inverse precision.
- Theorem 4: The approximating networks achieve L2 error at most ε at final time T on [0,1]^d, with parameter counts growing polynomially in d and ε^-1.More general results extend the spatial domain beyond the d-dimensional hypercube.
- Proof strategy: The proofs use probabilistic arguments: random neural networks are constructed on an artificial probability space, then a suitable deterministic realization is selected.A small L2 error for a random variable guarantees the existence of one realization with error no larger than that bound.
8 Conclusion
The reviewed methods create new possibilities for high-dimensional finance and control while motivating a complexity-based theory of high-dimensional PDEs. Reinforcement learning remains outside the review and its relation to these model-based approaches is unresolved.
- Applications: The methods have been proved effective in finance, including financial-derivative pricing and credit valuation adjustment.The review identifies control theory as another area likely to be strongly affected because it has long been hindered by dimensionality.
- Future directions: Efficient computation of very high-dimensional PDE solutions motivates studying solution complexity rather than relying primarily on low-dimensional regularity.The review asks whether this complexity can be quantified as a foundation for high-dimensional PDE theory.
- Open problems: Reinforcement learning is untouched, and the relative merits of its model-light approach versus the reviewed model-based methods remain unclear.The review connects reinforcement learning to Bellman equations for underlying Markov decision processes.