Source-linked AI summary
A proof that deep artificial neural networks overcome the curse of dimensionality in the numerical approximation of Kolmogorov partial differential equations with constant diffusion and nonlinear drift coefficients
Arnulf Jentzen, Diyora Salimova, Timo Welti
TL;DR
Rigorous evidence that DNNs overcome the curse of dimensionality in high-dimensional function approximation remains available only in a few special situations. This paper proves polynomial parameter growth for DNN approximation of solutions to Kolmogorov PDEs with constant diffusion and nonlinear drift, using deep networks constructed through repeated compositions.
Problem
Although many rigorous neural-network approximation results exist, only a few special situations rigorously justify DNN success in high-dimensional function approximation.
Source: §1 · p. 3Method
The paper constructs random DNNs using suitable Monte Carlo approximations and composition results, then establishes a realization with the desired approximation properties.
Source: §1 · p. 5Results
For the stated Kolmogorov PDE setting, the number of DNN parameters grows at most polynomially in dimension d and reciprocal approximation accuracy ε.
Source: §1 · p. 3Takeaways & Limitations
DNNs overcome the curse of dimensionality for numerical approximation of Kolmogorov PDEs with constant diffusion and nonlinear drift coefficients under the paper’s assumptions.
Source: §1 · p. 3The stated general-activation setup uses continuous coordinatewise activation functions.
Source: §6.1 · p. 39
Abstract
from arXiv · showhide
In recent years deep artificial neural networks (DNNs) have been successfully employed in numerical simulations for a multitude of computational problems including, for example, object and face recognition, natural language processing, fraud detection, computational advertisement, and numerical approximations of partial differential equations (PDEs). These numerical simulations indicate that DNNs seem to possess the fundamental flexibility to overcome the curse of dimensionality in the sense that the number of real parameters used to describe the DNN grows at most polynomially in both the reciprocal of the prescribed approximation accuracy $ \varepsilon > 0 $ and the dimension $ d \in \mathbb{N}$ of the function which the DNN aims to approximate in such computational problems. There is also a large number of rigorous mathematical approximation results for artificial neural networks in the scientific literature but there are only a few special situations where results in the literature can rigorously justify the success of DNNs in high-dimensional function approximation. The key contribution of this paper is to reveal that DNNs do overcome the curse of dimensionality in the numerical approximation of Kolmogorov PDEs with constant diffusion and nonlinear drift coefficients. We prove that the number of parameters used to describe the employed DNN grows at most polynomially in both the PDE dimension $ d \in \mathbb{N}$ and the reciprocal of the prescribed approximation accuracy $ \varepsilon > 0 $. A crucial ingredient in our proof is the fact that the artificial neural network used to approximate the solution of the PDE is indeed a deep artificial neural network with a large number of hidden layers.
1 Introduction
Although DNNs are used across computational fields, rigorous justification for their high-dimensional approximation success remains limited. This paper proves polynomial parameter growth for DNN approximations of Kolmogorov PDE solutions under stated conditions, using deep networks built through iterative compositions.
1 Introduction
- Theorem 1.1 gives DNN approximations with parameter counts growing at most polynomially in PDE dimension d and reciprocal accuracy ε for the stated Kolmogorov PDE setting.The paper identifies this result as overcoming the curse of dimensionality for constant diffusion and nonlinear drift coefficients.Source: §1 · p. 3
- The result assumes the initial-value and drift functions can themselves be approximated without the curse of dimensionality by DNNs.The theorem concerns at most polynomially growing viscosity solutions over a fixed time horizon.Source: §1 · pp. 3–4
- Iterative Euler-type discretizations for nonlinear-drift stochastic dynamics create repeated compositions and deep solution-approximating networks, even when coefficient networks have one hidden layer.The number of hidden layers increases as approximation accuracy decreases and PDE dimension increases.Source: §1 · p. 5
- The proof constructs a random DNN, shows it is close to the deterministic PDE solution, then establishes that a realization has the desired approximation properties.The paper describes construction and analysis of the random DNN as central parts of the proof.Source: §1 · p. 5
2.1 Markov-type estimates
- The Markov-type estimates support an abstract argument that good approximation by a random field yields a realization with suitable approximation properties.The paper applies this argument to a random DNN representing the PDE solution.Source: §2 · p. 6, §2.1 · p. 6, §2.2 · pp. 7–8
3 The Feynman-Kac formula revisited
The paper recalls a special case of the Feynman–Kac formula because its proof uses the link between deterministic Kolmogorov PDEs and SDE solutions. The recalled setup involves stochastic processes and a function associated with the PDE.
3 The Feynman-Kac formula revisited
- The recalled Feynman–Kac formula supplies the link between deterministic Kolmogorov PDEs and SDE solutions used in the random-DNN construction.The paper says the construction uses Monte Carlo approximations of PDE solutions based on this link.Source: §3 · p. 8
- The theorem’s setup includes a standard Brownian motion and unique stochastic processes with continuous sample paths satisfying an SDE.The excerpt identifies a locally Lipschitz coefficient in the setup.Source: §3 · pp. 8–9
- The recalled theorem also states existence of a unique function on [0,T] × R^d.This is part of the theorem’s stated setup.Source: §3 · p. 9
4 Stochastic differential equations (SDEs)
The section develops SDE estimates used to analyze a random DNN built from Euler–Maruyama discretizations of SDEs associated with the Kolmogorov PDEs. It combines a priori bounds with strong and weak error estimates.
4 Stochastic differential equations (SDEs)
- Euler–Maruyama discretizations of the associated SDEs underpin the random DNN construction, whose error analysis uses weak error estimates.Those weak estimates use strong error estimates, which in turn rely on a deterministic perturbation inequality.Source: §4 · p. 9
4.1 A priori bounds for SDEs
- Lemma 4.1 provides an a priori SDE estimate derived from Gronwall’s integral inequality.The section also uses this estimate in the proof of Proposition 4.6.Source: §4 · p. 9
4.2 A priori bounds for Brownian motions
- Lemma 4.2 supplies an a priori estimate for standard Brownian motions, derived from Itô’s formula.The main-result proof also employs this estimate.Source: §4 · p. 9
4.3 Strong perturbations of SDEs
- Strong Euler–Maruyama error estimates follow from a deterministic perturbation inequality and support the subsequent weak-error analysis.The perturbation inequality is Lemma 4.3, and the strong estimates are established in Proposition 4.4.Source: §4 · p. 9
4.4 Weak perturbations of SDEs
- Weak Euler–Maruyama error estimates are established in Lemma 4.5 and Proposition 4.6 using strong estimates and an a priori bound.The proof of Proposition 4.6 also employs Lemma 4.1.Source: §4 · p. 9
5 Deep artificial neural network (DNN) calculus
This section establishes DNN representation properties needed to construct a network approximating the PDE solution without the curse of dimensionality. Its calculus covers sums, compositions, and identity representations.
5.1 Sums of DNNs with the same architecture
- Linear combinations of realizations of DNNs with the same architecture can themselves be represented by a suitable DNN.Lemma 5.1 establishes this representation property.Source: §5 · p. 21, §5.1 · p. 22
5.2 Compositions of DNNs involving artificial identities
- Inserting a network representing the identity between two DNNs yields a composition network whose parameter count grows at most additively.The paper notes that direct composition may instead require a parameter count essentially equal to the product; Proposition 5.3 is tailored to the Euler-based construction.Source: §5 · p. 21
5.3 Representations of the d-dimensional identities
- For rectifier activation, the d-dimensional identity has a flat DNN representation with one hidden layer of 2d neurons.This representation supplies the identity network needed for the composition results.Source: §5 · p. 21
6 DNN approximations for partial differential equations (PDEs)
This section develops DNN approximation results for Kolmogorov PDE solutions with nonlinear drift and constant diffusion, progressing from general activation functions to rectified networks and the unit-cube setting. It concludes by deriving Corollary 6.4 from Theorem 6.3 under the stated parameter choices and condition (204).
6.2 Rectified DNN approximations
- Theorem 6.3 establishes that rectified DNNs can approximate solutions of second-order Kolmogorov PDEs with nonlinear drift and constant diffusion without the curse of dimensionality.The proof applies Corollary 6.2 to the rectifier activation function.Source: §6 · p. 30, §6.2 · p. 40
6.1 DNN approximations with general activation functions
- For general activation functions, Proposition 6.1 bounds terminal-time Lp approximation error by ε for p ≥ 2, while Corollary 6.2 extends the result to every p > 0.The approximation is measured with respect to a suitable sequence of probability measures ν_d.Source: §6 · pp. 30–31
6.3 Rectified DNN approximations on the d-dimensional unit cube
- Corollary 6.4 specializes the rectified-network result to ν_d equal to the uniform distribution on the d-dimensional unit cube [0, 1]^d.The paper states that its Theorem 1.1 follows directly from this corollary.Source: §6 · p. 31, §6.3 · p. 42
- Corollary 6.4’s items (i)–(ii) follow by specializing Theorem 6.3 and applying condition (204).The proof then concludes Corollary 6.4.Source: §6.3 · p. 42