A proof that rectified deep neural networks overcome the curse of dimensionality in the numerical approximation of semilinear heat equations

Introduction

Deep neural networks (DNNs) have revolutionized a number of computational problems; see, e.g., the references in Grohs et al. [GHJvW18]. In 2017 deep learning-based approximation algorithms for certain parabolic partial differential equations (PDEs) have been proposed in Han et al. [EHJ17, HJE18] and based on these works there is now a series of deep learning-based numerical approximation algorithms for a large class of different kinds of PDEs in the scientific literature; see, e.g., [BBG+18, BEJ17, BCJ18, EY18, EGJS18, FTT17, GHJvW18, Hen17, KLY17, Mis18, NM18, Rai18, SS17]. There is empirical evidence that deep learning-based methods work exceptionally well for approximating solutions of high-dimensional PDEs and that these do not suffer from the curse of dimensionality; see, e.g., the simulations in [EHJ17, HJE18, BEJ17, BBG+18]. There exist, however, only few theoretical results which prove that DNN approximations of solutions of PDEs do not suffer from the curse of dimensionality: The recent articles [GHJvW18, BGJ18, JSW18, EGJS18] prove rigorously that DNN approximations overcome the curse of dimensionality in the numerical approximation of solutions of certain linear PDEs.

The remainder of this article is organized as follows. In Section 2 we provide auxiliary results on multilevel Picard approximations ensuring that these approximations are stable against perturbations in the nonlinearity $f$ and the terminal condition $g$ of the PDE 1. In Section 3 we show that multilevel Picard approximations can be represented by DNNs and we provide bounds for the number of parameters of the representing DNN. We use the results of Section 2 and Section 3 to prove the main result LABEL:n18 in LABEL:sec:main_result.

A stability result for full history recursive multilevel Picard (MLP) approximations

2 An a priori estimate for solutions of partial differential equations (PDEs)

The integral transformation theorem, (8), and the triangle inequality show for all $t\in[0,T]$ that

Next, Jensen’s inequality, Fubini’s theorem, (11), the fact that $\mathbf{W}$ has independent and stationary increments, and (4) demonstrate that for all $t\in[0,T]$ it holds that

Furthermore, Jensen’s inequality, Fubini’s theorem, (11), the fact that $\mathbf{W}$ has independent and stationary increments, the triangle inequality, (3), and (4) demonstrate for all $t\in[0,T]$ that

Combining this with (12) and (13) implies that for all $t\in[0,T]$ it holds that

Next, [HJK+18, Corollary 3.11] shows that

This, Gronwall’s integral inequality, and (15) establish for all $t\in[0,T]$ that

The proof of Lemma 2.2 is thus completed. ∎

3 A stability result for solutions of PDEs

This, (22), and the triangle inequality yield that

4 A stability result for MLP approximations

This, the triangle inequality, (26), the fact that $B\leq B^{q}+1$, the assumption that $q\geq 2$, and Jensen’s inequality show that

The proof of Corollary 2.4 is thus completed. ∎

Deep neural network representations for MLP approximations

The main result of this section, Lemma 3.10 below, shows that multilevel Picard aproximations can be well represented by DNNs. The central tools for the proof of Lemma 3.10 are Lemmas 3.8 and 3.9 which show that DNNs are stable under compositions and summations. We formulate Lemmas 3.8 and 3.9 in terms of the operators defined in (34) below, whose properties are studied in Lemmas 3.3, 3.4, and 3.5.

The set $\mathbf{N}$ can be viewed as the set of all artificial neural networks. For each network $\Phi\in\mathbf{N}$ the function $\mathcal{R}(\Phi)$ is the function represented by $\Phi$ and the vector $\mathcal{D}(\Phi)$ describes the layer dimensions of $\Phi$.

2 Properties of operations associated to deep neural networks

Assume Setting 3.1 and let $\alpha,\beta,\gamma\in\mathbf{D}$. Then it holds that $(\alpha\odot\beta)\odot\gamma=\alpha\odot(\beta\odot\gamma)$.

The definition of $\odot$ in (33) then shows that

The proof of Lemma 3.3 is thus completed. ∎

it holds that $(\alpha\operatorname*{\boxplus}\beta)\operatorname*{\boxplus}\gamma=\alpha\operatorname*{\boxplus}(\beta\operatorname*{\boxplus}\gamma)$.

The proof of Lemma 3.4 is thus completed. ∎

The following result, Lemma 3.6, is a variant of [JSW18, Lemma 5.4].

Note that (41) and the definition of $\mathcal{D}$ (see (31)) imply that $\mathcal{D}(\phi)=\mathfrak{n}_{H+2}$. Furthermore, (41), (42), and an induction argument show that

The definition of $\mathcal{R}$ (see (32)) hence ensures that

The definition of $\mathcal{R}$ (see (32)) hence shows that

This and the fact that $y_{0}$ was arbitrary prove that $\mathcal{R}(\phi)=\lambda((\mathcal{R}(\Psi))(\cdot+b)+a)$. This and the fact that $\mathcal{D}(\phi)=\mathcal{D}(\Psi)$ imply that $\lambda\left((\mathcal{R}(\Psi))(\cdot+b)+a\right)\in\mathcal{R}(\{\Phi\in\mathbf{N}\colon\mathcal{D}(\Phi)=\mathcal{D}(\Psi)\})$. The proof of Lemma 3.7 is thus completed. ∎

The following result, Lemma 3.9, essentially generalizes [JSW18, Lemma 5.1] to the case where the DNNs have different hidden layer dimensions.

The proof of Lemma 3.9 is thus completed. ∎

3 Deep neural network representations for MLP approximations

it holds for all $t_{1},t_{2}\in[0,T]$, $\theta_{1},\theta_{2}\in\Theta$ that

it holds for all $t\in[0,T]$, $\theta\in\Theta$ that

it holds for all $t\in[0,T]$, $\theta\in\Theta$ that

Furthermore, Lemma 3.6 (with $H=(n+1)\left(\dim\!\left(\mathcal{D}(\Phi_{f})\right)-1\right)-1$ in the notation of Lemma 3.6) ensures that

Next, (83) (with $l=n$) and Lemma 3.8 (with

in the notation of Lemma 3.8) prove for all $\eta,\theta\in\Theta$, $t\in[0,T]$ that

Furthermore, the definition of $\odot$ in (33) and the fact that

This shows, roughly speaking, that the functions in (80), (90), and (88) can be represented by networks with the same depth (i.e. number of layers): $(n+1)(\dim\!\left(\mathcal{D}(\Phi_{f})\right)-1)+\dim\!\left(\mathcal{D}\left(\Phi_{g}\right)\right)$. Hence, Lemma 3.9