Deep neural network approximation for high-dimensional elliptic PDEs with boundary conditions

Introduction

The approximation of solutions to partial differential equations (PDEs) in high dimensions by classical algorithms such as finite difference or finite element methods is burdened by the so called curse of dimension. This means that the computational cost to achieve a certain accuracy depends exponentially on the dimension of the domain with respect to the reciprocal of the accuracy as base. This is for example improved in the case of so called sparse tensor discretizations. There the logarithm of the reciprocal of the accuracy is the base, but the dependence with respect to the dimension is still exponential . This curse of dimension does not appear in Monte Carlo methods, which are stochastic methods and converge in the root mean squared sense. These methods are however typically restricted to evaluating the solution of a given PDE at a single point rather than the full computational domain. The approximation of solutions to PDEs in high dimensions on the full computational domain hence remains a challenging problem.

Deep neural networks (DNNs) emerge as an approximation architecture with application in various areas of function approximation theory, which are in many cases as good as the established state of the art method, cf. . They are also used in the context of uncertainty quantification to approximate mappings that result in parametrized physical systems, where each realization is computationally expensive and treated as an offline cost, cf. . The weights of DNNs are usually obtained by approximately solving an optimization problem with a given loss functional defined with computed training data, see for example .

In particular we establish the first result on the approximation of solutions to PDEs with boundary conditions without curse of dimension using DNNs. More precisely, we consider the Poisson equation

We explicitly establish the required DNN approximation property for $x\mapsto{\rm dist}(x,\partial D)$ for $D$ a cube or a Euclidean ball. On the way to this result we derive a novel DNN approximation for the square root function at a spectral rate that may be of independent interest, see Lemma A.1. There has been another approach to approximate the Euclidean norm by DNNs based on the observation that the Euclidean norm is a rotation symmetric function, cf. .

Theorem 4.1 is similar in spirit to other existing works where Monte Carlo methods have been used to show existence of the DNN weights, cf. . The approaches and techniques in the presented manuscript differ significantly for the reason that the behavior of the solution near the boundary needs to be taken into account, which complicates the analysis.

The structure of the manuscript is as follows. In Section 2, we briefly recapitulate basic facts on on DNNs. In Section 3, we introduce the walk-on-the-sphere algorithm and prove basic properties. It serves as a tool in Section 4, where we show the existence of DNNs that approximate the solution to certain elliptic PDEs with boundary conditions.

Neural networks

The following lemma is [35, Proposition 3].

The following two lemmas are versions of [7, Lemmas II.5 and II.7].

Throughout this manuscript, we will construct ReLU DNNs mostly by composition and addition of already existing ReLU DNNs. The asserted upper bounds in later parts of the manuscript on the size of certain DNNs then result by Lemmas 2.2 and 2.3.

Basics on the walk-on-the-sphere algorithm

In this work we consider the following elliptic PDE with Dirichlet boundary conditions,

Furthermore, for any $\varepsilon\in(0,1)$ define the subdomain $D_{\varepsilon}$ of $D$ by

This is explicitly [30, Proposition 3.1.8]. ∎

We recall the fact that for a one dimensional Brownian motion starting at zero, the expected time such that it leaves the interval $[a,b]$ for $a<0<b$ is equal to $|ab|$, see [30, Proposition 2.2.20]. Thus the claimed estimate follows. ∎

The following result is also implied by [27, Theorems 9.13 and 9.17]. We give a proof to establish some techniques to be used throughout this section.

We will first establish a formula of the type asserted in this proposition in the interior of $D$ and then extend it to also incorporate the boundary.

The assumed convexity of the domain $D$ implies that all boundary points are regular in the sense of ; for details see [11, pp. 25, 27]. In conjunction with [11, Theorem 4.3], it follows that the solution $u$ to (2) exists and is unique. More precisely by [11, Lemma 4.2], $u$ is twice continuously differentiable in $D$.

Let $\varepsilon>0$ be arbitrary. Recall $D_{\varepsilon}:=\{x\in D:{\rm dist}(x,\partial D)>\varepsilon\}$. Suppose that $\varepsilon$ is sufficiently small such that $D_{\varepsilon}$ is not empty. By Ito’s formula (see for example [31, Theorem 17.8]), for every $x\in D_{\varepsilon}$

We seek to study the limit $\varepsilon\to 0$. The solution $u$ is Lipschitz continuous on the closure $\overline{D}$ with Lipschitz constant $L_{u}>0$, which may be concluded by [5, Theorem 1.4]. There, the statement of [5, Theorem 1.4] is applied to $v=u-g$ with right hand side $f-\Delta g$. The Lipschitz continuity of $u$ yields

cf. [24, Corollary 2.46 and Theorem 2.48], we obtain by Lemma 3.2

We define the discrete processes $\bar{X}_{k}$, $k\geq 0$, and $r_{k}$, $k\geq 1$, which also tacitly depend on an initial starting point $x\in D$. Let $\bar{X}_{0}=x$ and

The process $\bar{X}_{k}$, $k\geq 0$, is related to $X_{t}$, $t\geq 0$ as follows. Define $\bar{r}_{1}:={\rm dist}(x,\partial D)$ and $\tau_{1}:=\tau_{B(x,r_{1})}$. For every $k\geq 2$,

Note that $r_{k}$ and $\bar{r}_{k}$ have the same distribution, $k\geq 1$. Define

Let the assumptions of Proposition 3.3 be satisfied. There holds that

The strong Markov property of the Brownian motion yields

The assertion follows by inserting the previous equality into (11) with $x^{\prime}=\bar{X}_{k-1}$ and $r=r_{k}$ and Proposition 3.3 using that $\bar{X}_{k-1}$ and $X_{\mathcal{I}(k-1)}$ have the same distribution. ∎

Note that the functional $v\mapsto K_{1}(v)$ denotes the solution to the Poisson equation with homogeneous Dirichlet boundary conditions on the unit ball evaluated at the origin. An explicit formula for $K_{1}$ is a classical result by Boggio , see also . Specifically by [8, Lemma 2.27] for $d\geq 3$,

For every $\varepsilon>0$, let us define the random index $N(\varepsilon)$ by

As a consequence of Lemma 3.4 and its proof, see (11),

The first assertion (13) follows by Lemma 3.2. To show the second assertion (14), we may apply Ito’s lemma (see for example [31, Theorem 17.8]), which implies

The statement of the following lemma is in principle known. We provide a proof for the convenience of the reader.

We recall that for $x\in D$ such that ${\rm dist}(x,\partial D)<\varepsilon$, $N(\varepsilon)=1$. Thus, by the Markov property and Lemma 3.1, for every $k\geq 1$,

Since $\{t>0:W_{t}\notin B(0,{\rm diam}(D))\}\subset\{t>0:x+W_{t}\notin D\}$ for every $x\in D$ (using convexity of $D$), it holds that $\sup_{x\in D}\tau_{D}\leq\inf\{t>0:W_{t}\notin B(0,{\rm diam}(D))\}$. By Lemma 3.1,

which concludes the proof of this lemma. ∎

Approximation by deep neural networks without curse of dimension

Recall that we aim to approximate solutions to the prototypical elliptic PDE

by DNNs with ReLU activation function. The basics on stochastic sampling methods introduced in Section 3 shall serve as tools in the proofs of this section. The following theorem constitutes our main result.

Let the assumptions of Proposition 3.3 be satisfied. Suppose that for every $\delta,\delta_{f},\delta_{g}\in(0,1)$, there exist ReLU DNNs $\phi_{{\rm dist},\delta}$, $\phi_{f,\delta_{f}}$, and $\phi_{g,\delta_{g}}$ such that

and ${\rm size}(\phi_{{\rm dist},\delta})=\mathcal{O}(d^{a}\lceil\log(\delta^{-1})\rceil^{b})$, ${\rm size}(\phi_{f,\delta_{f}})=\mathcal{O}(d^{a}\delta_{f}^{-b})$, and ${\rm size}(\phi_{g,\delta_{g}})=\mathcal{O}(d^{a}\delta_{g}^{-b})$ for some $a,b\in(1,\infty)$ which do not depend on $d$. Let additionally $f$ and $g$ be Lipschitz continuous on $\overline{D}$. For every $\bar{\delta}\in(0,1)$, there exists a ReLU DNN $\phi_{u,\bar{\delta}}$ such that

with ${\rm size}(\phi_{u,\bar{\delta}})=\mathcal{O}(d^{a}\bar{\delta}^{-14-6b}(1+|D|^{14+6b}))$. The tacit constants in the Landau symbols depend on $\|f\|_{L^{\infty}(D)}$, $\|\Delta g\|_{L^{\infty}(D)}$, $\|g\|_{L^{\infty}(D)}$, the Lipschitz constants of $f$ and $g$, and on ${\rm diam}(D)$.

The proof of Theorem 4.1 will be postponed to the end of this section after two intermediate propositions have been proven.

Suppose that $g\in C^{2}(\overline{D})$, $x\mapsto{\rm dist}(x,\partial D)$ can be realized by a ReLU DNN $\phi_{\rm dist}$, and for any $\delta_{g}\in(0,1)$ there exists a ReLU DNN $\phi_{g,\delta_{g}}$ such that

For every $\bar{\delta}\in(0,1)$, there exists a ReLU DNN $\phi_{1,\bar{\delta}}$ such that

Furthermore, there exist $M=\lceil c\bar{\delta}^{-2}(1+|D|)\rceil$, $\bar{N}_{i}$, $i=1,\ldots,M$, and unit vectors $Y_{i,k}$, $k=1,\ldots,\bar{N}_{i}$, $i=1,\ldots,M$, such that for every $x\in D$,

The accuracy $\delta_{g}$ of the ReLU DNN $\phi_{g,\delta_{g}}$ satisfies $\delta_{g}=c^{\prime}\bar{\delta}/(1+\sqrt{|D|})$. The numbers $\bar{N}_{i}$, $i=1,\ldots,M$, satisfy that

The constants $c,c^{\prime},C>0$ only depend on $\|\Delta g\|_{L^{\infty}(D)}$ and on ${\rm diam}(D)$.

Let $\varepsilon\in(0,1)$ and $\delta_{g}\in(0,1)$ be arbitrary such that $D_{\varepsilon}$ is not empty, which will be determined in the following. Define the random variable $\bar{N}(\varepsilon):=\sup_{x\in D}N(\varepsilon)$. By Proposition 3.5,

The assumed approximability of $g$ by the ReLU DNN $\phi_{g,\delta_{g}}$ results in

where $((\bar{X}_{k})^{(i)}_{k\geq 0},\bar{N}^{(i)}(\varepsilon))$, $i=1,\ldots,M$, are mutually independent and have the same distribution as $((\bar{X}_{k})_{k\geq 0},\bar{N}(\varepsilon))$. Recall that $\bar{X}_{0}=x$, $x\in D$. It is well-known that that for any square integrable $\varphi$

Thus, by (19), (20), (22), and by Lemma 3.6

In conjunction with the previous estimate, the Jensen inequality and Lemma 3.6, imply

Then, the elementary estimate that $\sqrt{\sum_{i=1}^{M}c_{i}}\leq\sum_{i=1}^{M}\sqrt{c_{i}}$ for any positive numbers $c_{i}$, $i=1,\ldots,M$, implies

We choose the parameters $\delta_{g}=\varepsilon$ and $M=\lceil\varepsilon^{-2}\rceil$. The assertion (18) follows by inserting the expression for ${\rm error}^{2}_{M,\varepsilon,\delta_{g}}$ from (23) into the previous estimate. Define the ReLU DNN $\phi_{1,\bar{\delta}}$ by its realization

Then, as a consequence of (24) there exists a constant $C^{\prime}>0$, which only depends on $\|\Delta g\|_{L^{\infty}(D)}$, $\|g\|_{L^{\infty}(D)}$, and on ${\rm diam}(D)$ such that

We choose $\varepsilon=\bar{\delta}/(C^{\prime}(1+\sqrt{|D|}))$, which proves the assertion of this proposition. ∎

Let $d\geq 3$. Suppose that $f$ is Lipschitz continuous on $\overline{D}$, $x\mapsto{\rm dist}(x,\partial D)$ can be realized by a ReLU DNN $\phi_{\rm dist}$, and for any $\delta_{f}>0$ there exists a ReLU DNN $\phi_{f,\delta_{f}}$ such that

For every $\bar{\delta}\in(0,1)$, there exists a ReLU DNN $\phi_{2,\bar{\delta}}$ such that

Furthermore, there exist $M_{1}=M_{2}=\lceil c\bar{\delta}^{-2}(1+|D|^{2})\rceil$, $\bar{N}_{i}$, unit vectors $Y_{i,k}$, and elements of the unit ball $y_{i,j,k}$, $i=1,\ldots,M_{1}$,$k=1,\ldots,\bar{N}_{i}$, $i=1,\ldots,M_{2}$ such that for every $x\in D$,

The constants $c,c^{\prime},c^{\prime\prime},C>0$ depend only on $\|f\|_{L^{\infty}(D)}$ and on ${\rm diam}(D)$.

Let $\varepsilon\in(0,1)$ and $\delta_{f}\in(0,1)$ be arbitrary and sufficiently small. The value of these two numbers will be chosen at a later stage in the following proof. The effect of the approximation of the right hand side $f$ by $\phi_{f,\delta_{f}}$ is estimated by Lemma 3.1, i.e.,

where the domain $D$ may be embedded into a ball with radius ${\rm diam}(D)/2$ in order to apply Lemma 3.1.

Define the random number $\bar{N}(\varepsilon)=\sup_{x\in D}N(\varepsilon)$. By Proposition 3.5,

where we inserted the relation $|\partial B(0,1)|=d|B(0,1)|$ and the value for the volume of the unit $d$-ball, i.e., $|B(0,1)|=\pi^{d/2}/\Gamma(1+d/2)$. Note that $|\partial B(0,1)|$ denotes the measure of the $d-1$ dimensional unit sphere. Thus,

The Monte Carlo estimators $E_{M_{1}}(\cdot)$ and $E_{M_{2}}(\cdot)$ are independent and also independent from the sequence of random directions $Y_{k}$, $k\geq 1$, introduced in (6).

We estimate by (28) that for every $x\in D$,

where we used the indenpendence of $E_{M_{2}}(\cdot)$ from $Y_{k}$, $k\geq 1$. Furthermore, by (5) and Lemma 3.1 for every $x\in D$,

where we recall that $r_{k}$ depends on $x$ via $r_{k}={\rm dist}(\bar{X}_{k-1},\partial D)$, $k\geq 1$, and $\bar{X}_{k}$ has the same distribution as $X_{\mathcal{I}(k)}$, $k\geq 0$. Thus,

We combine the estimates (30), (31), and (32), which results in

where the latter estimate follows with the Jensen inequality and the elementary estimate that $\sqrt{\sum_{i=1}^{M_{1}}c_{i}}\leq\sum_{i=1}^{M_{1}}\sqrt{c_{i}}$ for any positive numbers $c_{i}$, $i=1,\ldots,M_{1}$, see the derivation of (25).

Let us define the DNN $\phi_{2,\bar{\delta}}$ by its realization, i.e., for every $x\in D$

In this proof, we also include the approximation of the distance function to the boundary by a ReLU DNN $\phi_{{\rm dist},\delta}$, where $\delta>0$ is still to be chosen. We may restrict ourselves to the case $d\geq 3$. For $d=1,2$, the statement follows by [35, Theorem 1], since the solution $u$ is Lipschitz continuous on $\overline{D}$ as observed in the proof of Proposition 3.3 and may be extended Lipschitz-continuously to a suitable box that is a superset of $D$. For every $x\in D$, we define the process $\widetilde{X}_{k}$, $k\geq 0$, by

The assumed accuracy of the ReLU DNN $\phi_{{\rm dist},\delta}$ implies

where we used that the distance function is Lipschitz continuous with Lipschitz constant equal to one. Thus, for every $x\in D$,

By Proposition 4.2, for every $\delta_{1}>0$ the function $\phi_{1,\delta_{1}}$ satisfies that

Also according to Proposition 4.2, $\phi_{1,\delta_{1}}$ depends on weight parameters $M=\lceil c\delta_{1}^{-2}(1+\sqrt{|D|})\rceil$, $\bar{N}_{i,1}$, $i=1,\ldots,M$, and unit vectors $Y_{i,k}$, $k=1,\ldots,\bar{N}_{i,1}$ $i=1,\ldots,M$. However, $\phi_{1,\delta_{1}}$ does not constitute a ReLU DNN here, since the assumption on the distance function in Proposition 4.2 is weakened in the theorem to be proved here. Define the ReLU DNN $\phi^{1}_{u,\bar{\delta}}$ by its realization

where $L_{g}$ denotes the Lipschitz constant of $g$. By the triangle inequality and the estimates (38) and (39)

We equilibrate the error contributions by the choices $\delta_{g}=\delta_{1}$ and $\delta=2^{-CM^{2}(M+|D|)}\delta_{1}$, where $C>0$ is the constant from (18). Thus,

where $L_{f}$ denotes the Lipschitz constant of $f$. By Proposition 4.3, for every $\delta_{2}$ the function $\phi_{2,\delta_{2}}$ satisfies that

Also according to Proposition 4.3, $\phi_{2,\delta_{2}}$ depends on weight parameters $M_{1}=M_{2}=\lceil c\delta_{2}^{-2}(1+|D|^{2})\rceil$, $\bar{N}_{i,2}$, unit vectors $Y_{i,k}$, and elements of the unit ball $y_{i,j,k}$, $i=1,\ldots,M_{1}$,$k=1,\ldots,\bar{N}_{i,2}$ $j=1,\ldots,M_{2}$ However, $\phi_{2,\delta_{2}}$ does not constitute a ReLU DNN here, since the assumption on the distance function in Proposition 4.3 is weakened in the theorem to be proved here. Recall $r_{k}={\rm dist}(\bar{X}_{k-1},\partial D)$ and $\bar{X}_{k-1}=\bar{X}_{k-1}(x,Y_{i,1},\ldots,Y_{i,k-1})$. The estimates (41) and (42) imply for $k=1,\ldots,\bar{N}_{i,2}$, $i=1,\ldots,M_{1}$

Define the ReLU DNN $\phi^{2}_{u,\bar{\delta}}$ by its realization

By the triangle inequality, (43), and (44)

We define the ReLU DNN $\phi_{u,\bar{\delta}}$ by

and chose the remaining two parameter $\delta_{1}$ and $\delta_{2}$ such that $\delta_{1}=\bar{\delta}/(2+6\sqrt{|D|})$ and $\delta_{2}=\bar{\delta}/(2+2C^{\prime}\sqrt{|D|})$. Thus, by the estimates (40) and (45)

where $C_{1},C_{2},C_{3},C_{4}$ are generic constants. The size of the ReLU DNN $\phi^{1}_{u,\bar{\delta}}$ will be asymptotically dominated by the size of the ReLU DNN $\phi^{2}_{u,\bar{\delta}}$. ∎

Thus, we choose $\delta_{1}=\delta/2$ and $\delta_{2}=\delta^{2}/(2d)^{2}$, which implies that $\phi_{{\rm dist},\delta}$ has accuracy $\delta$ and ${\rm size}(\phi_{{\rm dist},\delta})=\mathcal{O}(d\lceil\log(\delta_{2}^{-1})\rceil+\lceil\log(\delta_{1}^{-1})\rceil^{2})=\mathcal{O}(d[\lceil\log(\delta^{-1}\rceil^{2})+\log(d)])$, see Lemma A.1 and [35, Proposition 2]. Since here $|D|=\mathcal{O}(1)$, Theorem 4.1 holds without the curse of dimension.

Conclusions

Appendix A Neural network approximation of the square root

In this appendix we provide a constructive DNN approximation to the square root function that converges at a spectral rate. We use this result to establish spectral DNN approximability of the distance function of Euclidean balls but the result may be of independent interest.

For every $\bar{\delta}\in(0,1)$, there exists a ReLU DNN $\phi_{\sqrt{},\bar{\delta}}$ such that

with ${\rm size}(\phi_{\sqrt{},\bar{\delta}})=\mathcal{O}(\lceil\log(\bar{\delta}^{-1})\rceil^{2})$.

Thus, for every $x\in$, $s_{n}\to\sqrt{x}$ as $n\to\infty$. However, this convergence is not uniform with respect to $x\in$. For that reason, we introduce a shift by $\delta^{2}$ for some $\delta\in(0,1)$. Specifically, we set for every $x\in$,

The condition ${(1-\delta^{2})^{2^{n}}}/{2\delta^{2}}\leq\delta$ is satisfied if $2^{n}\geq[\log(1/2)+3\log(\delta^{-1})]\delta^{-2}$, where we used the fact that $\log(1/(1-\delta^{2}))\geq\delta^{2}/(1-\delta^{2})\geq\delta^{2}$. Since $|\sqrt{x}-\sqrt{x+\delta^{2}}|\leq\delta$ for any $x\in$,

The following fact, which follows by an elementary application of the fundamental theorem of calculus,

where $\bar{\varepsilon}=9N\varepsilon/2$. Indeed, by (52) for $n=2,\ldots,N$,

Another tool is the following estimate for any $a,b,c>1$,

where $k=\lceil\log(a)/\log(b)\rceil$ and we used the transformation $z=b^{y}$. The estimate of this integral implies

where we used that $\log(1+x)>x/2$ for every $x\in[0,1/2]$ (assuming $\delta\in(0,\sqrt{1/3}]$). Thus,

In conclusion, combining with (51) we have estimated that

for $\geq(\log[\log(1/2)+3\log(\delta^{-1})]+2\log(\delta^{-1}))/2$.

The choice $\varepsilon\leq\bar{\delta}/2(\delta/4)^{7}/C$ implies that

References