Parametric Complexity Bounds for Approximating PDEs with Neural Networks
Authors: Tanya Marwah
Zachary Chase Lipton
Andrej Risteski
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: PDE
Partial Differential Equations
Deep Learning Theory
Universal Approximation

Abstract: Recent experiments have shown that deep networks can approximate solutions to high-dimensional PDEs, seemingly escaping the curse of dimensionality. However, questions regarding the theoretical basis for such approximations, including the required network size remain open. In this paper, we investigate the representational power of neural networks for approximating solutions to linear elliptic PDEs with Dirichlet boundary conditions. We prove that when a PDE's coefficients are representable by small neural networks, the parameters required to approximate its solution scale polynomially with the input dimension $d$ and proportionally to the parameter counts of the coefficient networks. To this end, we develop a proof technique that simulates gradient descent (in an appropriate Hilbert space) by growing a neural network architecture whose iterates each participate as sub-networks in their (slightly larger) successors, and converge to the solution of the PDE.

Parametric Complexity Bounds for Approximating PDEs with Neural Networks
Tanya Marwah, Zachary C. Lipton, Andrej Risteski Machine Learning Department, Cameeie Mellon University (tmarwah, zlipton, (alstesk)@andrees cmu. edu
Abstract
Recent experiments have shown that deep networks can approximate solutions nigh-dimensional PDEs, seemingly escaping the curse of dimensionality. However, questions regarding the theoretical basis for such approximations, including the required network size remain open. In this paper, we investigate the representational power of neural networks for approximating solutions to linear elliptic PDEs with Dirichlet boundary conditions. We prove that when a PDE's coefficients are representable by small neural networks, the parameters required to approximate its solution scale polynomially with the input dimension d and proportionally to the parameter counts of the coefficient networks. To this end, we develop a proof technique that simulates gradient descent (in appropriate Hilbert space) by growing a neural network architecture whose iterates each participate as sub- networks in their (slightly larger) successors, and converge to the solution of the PDE. We bound the size of the solution showing a polynomial dependence on d and dependence on the volume of the domain.
Introduction
partial differential equation (PDE) relates a multivariate function defined over some domain to its partial derivatives. Typically, one's goal is solve for the (unknown) function, often subject to additional constraints, such as the function's value on the boundary of the domain. PDEs are ubiquitous in both the natural and social sciences, where they model such diverse processes as heat diffusion [7, 32], fluid dynamics [2, 39], and financial markets [6, 10]. Because most PDEs of interest lack closed-form solutions, computational approximation methods remain vital and an active field of research [1]. For low-dimensional functions, dominant approaches include the finite differences and finite element methods [26]. which discretize the domain. After partitioning the domain into a mesh, these methods solve for the function value at the vertices of the mesh. However, these techniques scale exponentially with the input dimension, rendering them unsuitable for high-dimensional problems.
Following breakthroughs in deep learning for approximating high-dimensional functions in such diverse domains as computer vision [21, 33] and natural language processing [3, 9, 40), burgeoning line of research leverages neural networks to approximate solutions to PDEs. This line of work has produced promising empirical results for common PDEs such the
and Black-Scholes equations [17, 16, 37J. Because they do not explicitly discretize the domain, and given their empirical success on digeeiimmesional problems. these methods appear not to suffer the curse of dimensionality. However, these methods are not well understood theoretically, leaving open questions about when they are applicable, what their performance depends on, and just how many parameters are required to approximate the solution to given PDE.
Over the past three years, several theoretical works have investigated questions of representational power under various assumptions. Exploring variety settings, [22), [16], and [19), proved that the number of parameters required approximate solution PDE exhibits less than exponential
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

dependence on the input dimension for some special parabolic PDEs that admit straightforward analysis. [15] consider elliptic PDEs with Dirichlet boundary conditions. However, their rate depends on the volume of the domain, and thus can have an implicit exponential dependence on dimension (e.g., consider a hypercube with side length greater than one).
In this paper, we focus on linear elliptic PDEs with Dirichlet boundary conditions, which are prevalent in science and engineering (e.g., the Laplace and Poisson equations). Notably, linear elliptic PDEs define the steady state of processes like heat diffusion and fluid dynamics. Our work asks:
Question. How many parameters suffice to approximate solutions to a linear elliptic PDE up to a specified level of precision using neural network?
We show that when the coefficients of the PDE are expressible as small neural networks (note that PDE coefficients are functions), the number of parameters required approximate the PDE's solution is proportional to the number of parameters required to express the coefficients. Furthermore, we show that the number of parameters depends polynomially on the dimension and does not depend upon the volume of the domain.
2 Overview of Results
To begin, we formally define linear elliptic PDEs.
Definition (Linear Elliptic PDE [11]). Linear elliptic PDEs with Dirichlet boundary condition can be expressed in the following form: { (Ta) (x) = (-div (AVu) + cu) (x) = f(x), Vx E Ω
u(x) 0, Vr E an,
where Q TRd a bounded open set with a boundary 00. Further, for all a E Q, A: > Rdxd s.I. A(x) > O, and e S2 R2 s.I. c(x) 0.
matrix-valued function, funcittiioonnntion
We refer to A and c as the coefficients of the PDE. The divergence form in Definition is one two canonical ways define linear elliptic PDE [11] and is convenient for several technical reasons (see Section 4). The Dirichlet boundary condition states that the solution takes constant value (here 0) the boundary an
Our goal is to express the number of parameters required to approximate the solution of a PDE in terms of those required to approximate its coefficients A and Our key result shows:
Theorem (Informal). If the coefficients A, e and the function f are approximable by neural networks with at most N parameters, the solution u" the PDE in Definition is approximable by a neural network with O (d=s((t)) parameters.
This result, formally expressed in Section 5, may help to explain the practical efficacy of neural networks in approximating solutions to high-dimensional PDEs with boundary conditions [37, 27]. To establish this result, we develop constructive proof technique that simulates gradient descent (in an appropriate Hilbert space) through the very architecture of a neural network. Each iterate, given by a neural network, is subsumed into the (slightly larger) network representing the subsequent iterate. The key to our analysis is to bound both (i) the growth network size across consecutive iterates; and (ii) the total number of iterates required.
Organization of the paper We introduce the required notation along with some mathematical preliminaries on PDEs in Section 4. The problem setting and formal statement of the main result are provided in Section Finally, we provide the proof of the main result in Section
Prior Work
Among the first papers leverage neural networks approximate solutions to PDEs with boundary conditions are [23], [24], and [29]. However, these methods discretize the input space and thus are not
'erre, diy denotes the divergence operator. Given vector tield F' _ Rd. div(F) V

---

suitable for high-dimensiona input spaces, More recently, mesh-free neural network approaches have been proposed for nigh-dimensional PDEs [17, 34, 35], achieving impressive empirical results in various applications. [37] design a loss function that penalizes failure to satisfy the PDE, training their network on minibatches sampled uniformly from the input domain. They also provide a universal approximation result, showing that for sufficiently regularized PDEs, there exists a multilayer network that approximates its solution. However, they do not comment on the complexity of the neural network or how it scales with the input dimension. [20] also prove universal approximation power, albeit with networks of size exponential in the input dimension. Recently, [16, 19] provided better-than- exponential dependence
the input dimension for some special parabolic PDEs, for which the simulating a PDE solver by a neural network is straightforward.
Several recent works [5, 22, 28, 27] show (experimentally) that a single neural network can solve for an entire family of PDEs. They approximate the map from a PDE's parameters to its solution, potentially avoiding the trouble of retraining for every set of coefficients. Among these, only [22] provides theoretical grounding. However, they assume the existence of a finite low-dimensional space with basis functions that approximate this parametric map-and it is unclear when this would obtain. Our work proves the existence of such maps, under the assumption that the family of PDEs has coefficients described by neural networks with a fixed architecture (Section 7).
In the work most closely related to ours, [15] provides approximation rates polynomial in the input dimension for the Poisson equation (a special kind of linear elliptic PDE) with Dirichlet boundary conditions. They introduce equation that can be used to solve a Poisson equation with Dirichlet boundary conditions (see, e.g. [31]'s Theorem 9.13). The rates provided in [15] depend on the volume of the domain, and thus depend, implicitly, exponentially on the input dimension d. Our result considers the boundary condition for the PDE and is independent the volume of the domain. Further, we note that our results are defined for a more general linear elliptic PDE, of which the Poisson equation is a special case.
mall--on-the-pheee algorithm. which simulates stochastic differential
4 Notation and Definitions
We now introduce several key concepts from PDEs and some notation. For any open set Ω C IRd, we denote its boundary by OQ and denote its closure by Q == Ω U an. By (Q)), we denote the space of real-valued continuous functions defined over the domain Ω. Furthermore, for k E N, a function belongs C* (92) if all partial derivatives 0 g exist and are continuous for any multi-index a, such (S2) for all i E N. Next, define several that |a| < k. Finally, a function g E C (52) if g C*(
relevant function spaces:
Definition 2. For any E (Oc),, (G) (g:9 E C* (Q), supp(g) C
Definition 3. For domain Ω2 the function space T.2( consists of all functions g : S IR, S.I.
(|llا oo where (19]]22(0) (Ja ( This function space is equipped with the inner product
(g, = - g(x)h(o)dd.
Definition 4. For domain Ω and function g Ω > R. the function space [.P( is defined analogously, where [[g]] (x) inf 0: (g(x)) S for almost all x E 22).
Definition 5. For a domain Ω and m E N. we define the Hilbert space H Hm) as
( = {g: R 0e e L2(1),, Va s.t. |a| S m}
Furthermore, HT (S2) is equipped with the inner product, (g, h) mm)())) Ealsm Sa (n(d")) (0))))))) and the corresponding norm
1
[1)1)=(()) =
Σ
110 g|0d o
|a|| Sm
Definition 6. The closure of C (22 in (²t((() is denoted by H (S)).
3

---

Informally, HO is the set of functions belonging to H (S2) H²
that can be approximated by
sequence of functions on CD (St). This also implies that a function g H. (92), then g(x) for all x E an. This space (particularly with m 1) is often useful when analyzing elliptic PDFs with Dirichlet boundary conditions.
Definition 7 (Weak Solution). Given the PDE in Definition I, if E (2)). then function u Ω + solves the PDE in a weak sense if E Ho (9t) and for all E HQ) we have
J (AVu Ve + cuv) dx fudr
The left hand side of (1) is also equal to (Lu, (2(()) for all u, E Hg (see Lemma 6), whereas, following the definition of the (2)) norm, the right side is simply (f. v) (9)) Having introduced these preliminaries, now introduce some important facts about linear PDEs that feature prominently in our analysis.
Proposition 1. For the PDE in Definition 1, if E (22) the following hold:
1. The solution to Equation (1) exists and is unique.
2. The weak solution is also the unique solution of the following minimization problem:
1 (L o) (f 10
u argmin J(D) argmin (9)
WE (E))
This proposition is standard (we include a proof in the Appendix, Section A. for completeness) and states that there exists a unique solution to the PDE (referred to as u²), which is also the solution we get from the variational formulation in (2). In this work, we introduce a sequence of functions that minimizes the loss the variational formulation.
Definition 8 (Eigenvalues and Eigenfunctions, [11]). Given operator L. the tuples (A, p) where X E I and yi E Hd (S2) are (eigenvalue, eigenfinction) pairs that satisfy Lip = Xip, for all E Ω Since & E H. (92), we know that ylaan 0. The eigenvalue can be written
(Lu, u) u)
A = inf NEX.
(3)
{u E ( (u, 12 =0 Vj fl.... ,i}} and 0 < A I >2 S ... Furthermore, we define by 4g the span of the first eigenfunctions of L, iee. & span span Pk.)
where X; span ppanny91........................
We note that since the operator self-adjoint and elliptic (in particular, I.-1 is compact), the eigenvalues are real and countable. Moreover, the eigenfunctions form an orthonormal basis of H. (12) (see [11], Section 6.5).
5
Main Result
Before stating our results, we provide the formal assumptions on the PDEs of interest:
Assumptions:
(i) Smoothness:
We assume that the coefficient Ω - Rdxd is symmetric ma- trix valued function, i.e., A (a:j(z)) and (x)(r) E I (12 is three times differ- entiable for all i,j E [d]. Furthermore, the function e [.P) twice differen- tiable and c(x) 2 > 0 for all E Ω We define a constant C = (2d² 1) max maxaa]a|gs max,, [|0a (=)()), maxa:aals2 ( Further, the func- tion f (22 is infinitely differentiable and we assume there exists function Sapan E $5. such that for any multi-index a, |000 8x Sapan (2 S (span-
(ii) Ellipticity: There exist constants M 2 m > 0 such that, for all x E Ω and 5 E Rgd
m <
( S 2

---

(iii) Neural network approximability: There exist neural networks A and ē with Na, e N parameters, respectively, that approximate the functions A and c, i... ||A (0) S EA and ||c - (0)) I cc. for small c, 2 O. We assume that for all E ( the operator L defined as,
div-di((AVu) ču.
is elliptic with (A,, 1:),=111111)))))00)0 (eigenvalue, eigenfunction) pairs. We also assume that there exists a neural network fun C with N E N parameters such that for any multi-index o,, [|00 - da fnn [L)(()) S Cnn- By Σ, we denote the set of all (infinitely differentiable) activation functions used by networks Á, č, and fun By E', we denote the set that contains all the n-th order derivatives of the activation functions in Σ, Vn E No
Intuitively, ellipticity of L in a linear PDE Lu f is analogous to positive definiteness of matrix Q E Rd in a linear equation Qz = k, where 2; k E R
In (iii), we assume that the coefficients A and and the function f can be approximated by neural networks. While this true for any smooth functions given sufficiently large NA, No. N2, our results are most interesting when these quantities are small (e.g. subexponential in the input dimension d). For many PDEs used in practice, approximating the coefficients using small neural networks is straightforward. For example, in heat diffusion (whose equilibrium is defined by linear elliptic PDE) A(x) defines the conductivity the material at point æ. the conductivity is constant, then the coefficients can be written as neural networks with O(1) parameters.
Intuitively, our assumption (iii) that there exists an fspan in H. (S2) that lies in the span of the low- lying k eigenfunctions of the operator L can be thought of as a smoothness condition on f. For instance, if L = - (the Laplacian operator), the Dirichlet form satisfies (Lu,u)_300 [|
Twll
Tw
so eigenfunctions corresponding to higher eigenvalues tend to exhibit higher degree of spikiness. The reader can also think of the eigenfunctions corresponding to larger as Fourier basis functions corresponding to higher frequencies.
Finally, in (i) and (iii), while the requirement that the function pairs fmn) and (f+ fspan) are close not only in their values, but their derivatives as well is a matter of analytical convenience, our key results do not necessarily depend on this precise assumption. Alternatively, we could replace this assumption with similar (but incomparable) conditions: e.g., we can also assume closeness of the values and a rapid decay of the L2 norms of the derivatives. We require control over the derivatives because our method's s gradient descent iterations involve repeatedly applying the operator to wwhhc results in progressively higher derivatives.
We can now formally state our main result:
Theorem (Main Theorem). Consider a linear elliptic PDE satisfying Assumptions (i)- and let ut E (Q) denote its unique solution. If there exists neural network uo (92) with No parameters, such that I|u* - uollz2(0)) I R. for some R < oc, then for every e > 0, there exists a neural network u. with size
O (d (No+Na) + N.) + T(N, + NN))
such that ||u- - uel uell I e è where,
8 223/211.f|12600
23/28 (l Espan + Enn +
²:= Espan
- ul (max
X1
7-6
7 8
and K Seth, 17 Autho
T = - log( (R/( and min min(m/ca&Sle) and a is multi- index.
Xx-3."
Furthermore, the activation functions used in u, belong to the set Σ E' U {p} where p(y) = y² for all y E the square activation fnnivaatiofunctttio function.
This theorem shows that given an initial neural network uo E H. (12) containing No parameters, we can recover neural network that is close to the unique solution u². The number parameters in u, depend on how close the initial estimate uo is to the solution u', and No. This results in trade-off, where better approximations may require more parameters, compared to a poorer approximation with fewer parameters.
5

---

Note that can be taken arbitrarily close to O, while is "bias" error term that does not go to O. The first three terms in the expression for result from bounding the difference between the solutions to the equations Lu = f and Lu = Jspan. whereas the third term is due to difference between f and fun and the fact that our proof involves simulating the gradient descent updates with neural networks.
The term T- = O
Log(R/e) comes from the fact that we are simulating T steps of a gradient log(s)
descent-like procedure on strongly convex loss with condition number to reach an e-approximate optimum. The parameters 0 and Å can be thought of as the effective Lipschitz and strong-con croveiccn constants of the loss. Finally, to give sense of what R looks like, we show in Corollary 2 (see
Section B in the Appendix) that if uo is initialized to he identically zero then R [1
A
We make few remarks about the theorem statement:
Remark 1. While we state our convergence results in (S2) norm, our proof works for the H2((S) norm as well. This is because in the space defined by the top-k eigenfunctions of the operator L. (S2) and Hig (St) norm are equivalent (shown in Proposition 2). Further, note that even though we have assumed that u E Ho (52) is the unique solution of (1) from the boundary regularity condition, we have that u² E (92) (see [11], Theorem 4 in Chapter 6). This ensures that the solution u" is twice differentiable as well.
Remark 2. To gel a sense of the scale of X and Ass when L = - (the Laplacian operator), the [|
eigenvalue A (n( T| 22(0) Ep' where Cp is the Poincaré constant (see Theorem in Appendix). For geometrically well-behaved sets Q2 (e.g. convex sets with strongly convex boundary. like a sphere), Cp is even innppiiiionnndeeeeeen. Further from the Weyl's law operator ([11), Section 6.5) we have
4/2
(2x)a
lim k-+00
vol(D))((d)
where (d) is the volume of a unit ball in d dimensions. So, if vol(S)) 2 1/a(d), A grows as O(k2/d), which constant so long as log k & d.
Remark 3. The choice of activation functions (in particular, the requirement that E only contains differentiable functions) is for mathematical convenience. Namely, by standard results from approx- imation theory [41, 4] one can approximate a neural network with one choice of nonlinearity via a (comparably sized) neural network with another choice of nonlinearity (under mild assumptions) by incurring diimenioon-independen increase in size. Thus, if the coefficients are approximable by a neural network with a non-differentiable activation function, they can also approximated by a slightly larger network with a differentiable activation over any compact domain. Similarly, the activations on the network resulting from Theorem I can be replaced by different activation the expense of slight blowup in size. Details are included in Appendix C.4.
6 Proof of Main Result
First, we provide some intuition behind the proof, via an analogy between a uniformly elliptic operator and a positive definite matrix in linear algebra. We can think of finding the solution to the equation Lu = f for an elliptic L as analogous to finding the solution to the linear system of equations Qx = k. where Q is a d x d positive definite matrix, and x and k are d-dimensional vectors. One way to solve such a linear system is by minimizing the strongly convex function ||Qr - bl[2 using gradient descent. Since the objective is strongly convex, after O(log(1/e)) gradient steps, we reach an e-optimal point in an // sense.
Our proof uses similar strategy. First, we show that for the operator L. we can define a sequence of functions that converge to an e-optimal function approximation (in this case in the L22( norm) after (1/) steps similar to the rate of convergence for strongly convex functions. Next, we induetively show that each iterate in the sequence can be approximated by a small neural network. More precisely, we show that given a bound on the size of the t-th iterate u4, we can, in turn, upper bound the size of the (I + 1)-th iterate u,41 because the update transforming u, to we-1 can be simulated by a small neural network (Lemma 4). These iterations look roughly like (Lemma 7) which bounds the We-1 +- 44 - TT(Tu, - f). and we use a "hackpropagation" lemma lemma
size of the derivative of a neural network.

---

6.1 Defining a Convergent Sequence
The rough idea is to perform gradient descent in (22) [30, 12, 13], and define convergent sequence whose iterates converge to u" in (S2 norm (and following Remark 1, in H. (S2) as well). However, there are two obstacles to defining the iterates as simply Ut+1 t- Ur L,, f), (1) is unbounded-so the standard way of choosing a step size for gradient descent (roughly the ratio of the minimum and maximum eigenvalues of L) would imply choosing a step size 0, and (2) does not necessarily preserve the boundary conditions, so if we start with ue H. (9), it may be that Lut f does not even lie in Hj (52).
We resolve both issues by restricting the updates to the span of the first & eigenfunctions of L. More concretely, shown in Lemma if a function in &g, then the function Lu will also lie in 4 We also show that within the span of the first k eigenfunctions, I. is bounded (with maximum eigenvalue A and can therefore be viewed an operator from 4 4x. Further, we use Sapan instead of in our updates, which now have the form U++1 f n Lu, fspan). Since fapan belongs to Qx. for u, 4x the next iterate 1r+1 will now remain in @x. Continuing the matrix analogy, we can choose the usual step size of AithE' Precisely, we show:
Lemma 1. Let L be an elliptic operator. Then, for all 4g it holds:
1. Lo E Ex
2. Ar]|v|lza(0) & (Lv, L2(0) S {m
3. ( |x xx 1) I
A x (1ll
The proof of this lemma provided in Section C.I.
Further, note that we will use a slight variant of the updates and instead set u++1 + U4 -- fspan) as the iterates of the convergent sequence. Here, the operator (defined in (4)) has the neural network approximations of and c as its coefficients, and fapan is function that lics in span of the first eigenfunctions of L (denoted by 4x). such that Ilfa fapau (.2))) is small (for an exact statement, see Lemma 11 in the Appendix). Section 6.2, we will see that updates defined thusly will be more convenient to simulate via neural network.
The sequence defined far satisfies important properties. First, the convergence point of the sequence and u², the solution to the original PDE, are not too far from each other. Concretely:
Lemma 2. Assume that Sppa is the solution to the PDE Las = Sspan. where Ispan ( IR. and Japan E $z. Given Assumptions (i)-(iii), we have |I= Üspan (( 6, such that =
1 ppm [[)) where 7 Ax AE11 and 5 min min[m/ea.///])
Expan A1 7-8
The proof for Lemma 2 is provided in the Appendix (Section D.I). Each of the three terms in the final error captures different sources of perturbation: the first term comes from approximating by fapani the second term comes from applying Davis-Kahan [8] to bound the "misalignment" between the eigenspaces h and & (hence, the appearance of the eigengap between the k and (k: + 1 1)-st eigenvalue of T. 11= the third term a type of "relative" error bounding the difference between the solutions to the PDEs Lu fspan and Lu Jspan
The second property of the sequence of functions is that they converge exponentially fast. The rate is characterized in the following lemma:
Lemma 3 (Convergence of gradient descent in L2), Let Vapan denote the unique solution the PDE i. = Fspan where Japan E h and the operator L. satisfies the conditions in Lemma 1. Then for any E (92) such that ug E Er we define the sequence
U441 f- u, dι Av
(Lu, Japan) E E)
(5)
7

---

where for all t E N, ue E (Q). Then for any 2 O we have |ur - 0h Span (112 S after T iterations where,
|lu0 - "iipanlee20
log
T
Aet
log
The proof for Lemma 3 is similar to the analysis of the convergence time of gradient descent for strongly convex losses and can be found in Section C.2 of the Appendix. Finally, combining the results from Lemma 2 and Lemma via triangle inequality, we have:
||u" urll (. S I|u"
الpan 1.2(9)) + || ur (I)(
and the first term on the RHS subsumes the first three summands of é defined in Theorem 1.
6.2 Approximating iterates by neural networks
In Lemma 3, show that there exists sequence of functions (5) which converge fast function close to u*. The next step in the proof is to approximate the itcrates by neural networks.
The main idea is as follows. Suppose first the iterates u++1 4e ry( fspau) are such that Sapan is exactly representable as neural network. Then, the iterate U4+1 can be written terms of three operations performed ue, and taking derivatives, multiplication and addition. Moreover, g is representable as a neural network with N parameters, the coordinates the vector V can be represented by neural network with O(N) parameters. This is classic result (Lemma 7), essentially following from the backpropagation algorithm. Finally, addition or multiplication of two functions representable neural networks with sizes Ni, N2 be represented neural networks with size O(Ni + N2) (see Lemma 8).
Using these facts, approximation U++1, denoted by u,+1, in terms of the number of parameters in ú, (which is the neural network approximation to uz). Formally, we have:
write down recurrence upper bounding the size of neural network
Lemma (Recursion Lemma). Given the Assumptions (i)-(iii), consider the update equation
úz41 + ūt
[Lu - Sun
(6)
at step t, ât Rd + R neural network with No parameters, then the function ú is neural network with ON No) +N+ + N2 No) parameters.
Proof. Expand the update uz+1 f- ūr
[Lū - Smn) as follows:
u+t1 f- ún 17
Σ +,==
+
Σ i=1
0,ā,s 0fūe oūg Sun
Using Lemma 7, 0.y Li dzú, and d, can be represented by neural network with O(N)), O(N)
and ((N,) parameters, respectively. Further, 0,ā,,0,u and 0,y å can be represented by neural
network with O(Na + N₂) parameters, and čü; can be represented by network with O(N, + No) parameters, from Lemma Hence ü++1 can represented in O + N₂) + Ny + N N parameters. Note that, throughout the entire proofs O hides independent constants.
L
Combining the results of Lemma and Lemma 4, we can get a recurrence for the number of parameters required to represent the neural network uz:
N < d - d2 N
N + N No L'd - - NA T(N,) N.).
Unfolding this recurrence, we get NT < E No
#-1
Hence, the total number of parameters required for a neural network to approximate a solution to a PDE of the form in Definition!
[gg Span
[1ug-uu Ripan 12
log
0
d
(No + NA)= +
(N, + No)
log π.

---

Finally, we have to deal with the fact that fapan is not exactly neural network, but only approximately so. The error due this discrepancy can be characterized through the following lemma:
Lemma 5 (Error using Sna). Consider the update equation in (6), where Jan is neural network
with N.. Then the neural network dn approximates the function us such that llue - Celle2(0)) I Con
(t) where tun is
o ( (maxx(1 Espan
22/28 (1 ))
Enn
7
where 8 min (m/mm
Ax A111 and a is a multi-index.
The main strategy to prove this lemma involves tracking the "residual" non non-neural-networf part of the iterates. Precisely, we can write the update Me+1 = (7( Tue (fun +r), for a "residual" function r= Saaann fnn- If We was exactly neural network, the first part of the update, can be written as a neural network as in Lemma 4, and yrr can be treated as an error. Thus, in order bound the error for using Sun instead of fapan: we maintain decomposition of uz into a neural network part, and residual part, and inductively bound the total residual part. Given the recurrent structure of our updates, at each iteration t, there will be an accumulation of the earlier f - 1 applications of the operator L, that results an increasing number of higher order derivatives r to be bounded at each step. This is why we require that Sna is close to f not only in the L2 sense but also in terms of their higher order derivatives.
nıLL, - fmn)
7 Applications to Learning Operators
number of recent works attempt simultaneously approximate the solutions for an entire family of PDFs by learning parametric map that takes as inputs (some representation of) the coefficients of PDE and returns solution [5, 28, 27]. For example, given a set of observations that {az, u, " where each aj denotes coefficient of PDE with corresponding solution uj. they learn neural network G' such that for all j. új = G(a Our parametric results provide useful insights for why simultaneously solving an entire family of PDEs with single neural network G is possible in the case of linear elliptic PDEs.
Consider the case where the coefficients a, in the family of PDEs are given by neural networks with a fixed architecture, but where each instance of a PDE is characterized by a different setting of the weights in the models representing the coefficients. Lemma 4 shows that each iteration of our sequence (5) constructs a new network containing both the current solution and the coefficient networks as subnetworks. We can view our approximation as not merely approximating the solution to single PDE but to every PDE in the family, by treating the coefficient networks as placeholder architectures whose weights are provided as inputs. Thus, our construction provides parametric map between the coefficients of an elliptic PDE in this family and its solution.
8 Conclusion and Future Work
We derive parametric complexity bounds for neural network approximations for solving linear elliptic PDEs with Dirichlet boundary conditions, whenever the coefficients can be approximated by are neural networks with finite parameter counts. By simulating gradient descent in function spaces using neural networks, we construct a neural network that approximates the solution of PDE. We show that the number of parameters in the neural network depends on the parameters required to represent the coeffcients and has (cly(d) dependence on the dimension of the input space, therefore avoiding the curse of dimensionality.
An immediate open question is related to the tightening our results: our current error bound is sensitive to the neural network approximation lying close 4 which could be alleviated by relaxing (by adding some kind of "regularity" assumptions) the dependence of our analysis on the first k eigenfunctions. Further, the dependencies in the exponent of on and & in parametric bound may also be improvable. Finally, the idea of simulating derive a pnaeseentaiionthhorette result broadly applicable, and may be fertile ground for further work, both theoretically and empirically, as it suggest particular kind of weight tying.
iterative algorithm by neural network to

---

Acknowledgement
This paper is based upon work funded and supported by the Department of Defense under contract FA8702-15-D-0002
References
[1] W. F. Ames. Numerical methods for partial differential equations. Academic press, 2014.
[2] J. D. Anderson and J. Wendt. Computational fluid dynamics, volume 206. Springer, 1995.
[3] D. Bahdanau, K. Cho, and Y. Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv: 1409.0433. 2014.
[4] A. Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Trunsuctions on Information theory, 39(3):930-945, 1993.
[5] K. Bhattacharya, B. Hosseini, N. B. Kovachki, and A. M. Stuart. Model reduction and neural networks for parametric pdes. arXiv preprint arXiv:2005.03/ 2020.
[6] Black and M. Scholes. The pricing of options and corporate liabilities. Journal of political economy, 81 (3):63377654, 1973.
[7] Crank and P. Nicolson. A practical method for numerical evaluation of solutions partial dif- ferential equations of the heat-conduction type. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 43, pages 50-67. Cambridge University Press, 1947.
[8] C. Davis and W. M. Kahan. The rotation of eigenvectors by perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):1-46, 1970.
[9] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 04805, 2018
[10] M. Ehrhardt and R. E. Mickens. A fast, stable and accurate numerical method for the black- scholes equation of american options. International Journal of Theoretical and Applied Finance, 1 (105))471-501, 2008
[11] L. C. Evans. Partial Differential Equations. graduate studies in mathematics. american mathematical society, 1998. ISBN 9780821807729,
[12] I. Faragó and J. Karátson. The gradient-fintte element method for elliptic problems. Computers Mathematics with Applications, 1043--90004115,,,, 2001.
[13] I. Faragó and J. Karátson. Numerical solution of nonlinear elliptic problems via preconditioning operators: Theory and applications, volume 11. Nova Publishers, 2002.
[14] D. Gilbarg and N. S. Trudinger. Elliptic partial differential equations of second order. 2001.
[15] Grohs and L. Hermmann Deep neural network approximation for high dimensional elliptic pdes with boundary conditions. arXiv preprint 20Xi::2007.05884 2020.
[16] Grohs, Hornung, A. Jentzen, and P. Von Wurstemberger. A proof that artificial neural networks overcome the curse of dimensionality in the numerical approximation of black-scholes partial differential equations. arXiv preprint arXiv:
/ 022202262,... 2018.
[17] J. Han, A. Jentzen, and F. Weinan. Solving high-dimensional partial differential equations using deep learning. Proceedings of the National Academy of Sciences, 115(34):500-8855 2018.
[18] K. Hornik, M. Stinchcombe, and H. White. Universal approximation of an unknown mapping and its derivatives using multilayer feedforward networks. Neural networks, 3(5):551-564 1990.
10

---

[19] A. Jentzen, D. Salimova, and T. Welti. A proof that deep artificial neural networks overcome the curse of dimensionality in the numerical upproximation of kolmogorov partial differential equa- tions with constant diffusion and nonlinear drift coefficients. arXiv preprint arXiv: (KKv:/809.07322 2018.
[20] Y. Khoo, J. Lu, and L.. Ying. Solving parametric pde problems with artificial neural networks. arXiv preprint arXiv: 03351, 2017.
[21] A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25, pages 1097-1105. Curran Associates, Inc., 2012.
[22] G. Kutyniok, Petersen, M. Raslan, and R. Schneider. theoretical analysis of deep neural networks and parametric pdes. arXiv preprint arXiv:1904.0033: 2019.
[23] I. Lagaris, Likas, and D. Fotiadis. Artificial neural networks for solving ordinary and partial differential equations. IEEE transactions on neural networks, 9(5):987-1000, 1998.
[24] I. E. Lagaris, A. C. Likas, and D. G. Papageorgiou. Neural-network methods for boundary value problems with irregular boundaries. IEEE Transactions on Neural Networks, 1165):041-1049, 2000.
[25] P. D. Lax and A. N. Milgram. Parabolic equations, volume 33 of annals of mathematics studies, 1954.
[26] R. LeVeque. Finite difference methods for ordinary and partial differential equations: steady-state and time-dependent problems. SIAM, 2007.
[27] Z. Li, N. Kovachki, K. Azizzadenesheli. B. Liu, K. Bhattacharya, A. Stuart, and A. Anand- kumar. Fourier neural operator for parametric partial differential equations. arXiv preprint arXiv:2010.08895. 2020.
[28] Z. Li, N. Kovachki, K. Azizzadenesheli, B. Liu, K. Bhattacharya, A. Stuart, and A. Anandku- mar. Neural operator: Graph kernel network for partial differential equations. arXiv preprint arXiv:2003.0348. 2020.
[29] A. Malek and R. S. Beidokhti. Numerical solution for high order differential equations using hybrid neural oettork-optimiizatio method. Applied Mathematics and Computation, 183(1): 260-271, 2006.
[30] Neuberger. Sobolev gradients and differential equations. Springer Science & Business Media, 2009.
[31] B. Oksendal. Stochastic differential equations: introduction with applications. Springer Science & Business Media, 2013.
[32] M. N. Özişik, H. R. Orlande, M. Colaço, and R. M. Cotta. Finite difference methods in heat transfer. CRC press, 2017.
[33] A. Radford, I., Metz, and S. Chintala. Unsupervised representation learning with deep convolu- tional generative adversarial networks. arXiv preprint 1rXiv:1511.06433 2015.
[34] M. Raissi, Perdikaris, and G. E. Karniadakis. Physics informed deep learning (part i): Data- driven solutions of nonlinear partial differential equations. arXiv preprint arXiv:1711.10561. 2017.
[35] M. Raissi, P. Perdikaris, and G. E. Karniadakis. Physics-ing Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. Journal of Computational Physics, 378:686-707, 2019.
[36] D. Rumelhart, G. E. Hinton, and R. J. Williams. Learning representations by paok-propggating errors. nature, 323(6088):533-52) 1986.

---

[37] J. Sirigmano and K. Spiliopoullos. Dgm: A deep learning algorithm for solving partial differential equations. Journal of computational physics, 375:1339- 2018.
[38] M. Telgarsky. Neural networks and rational functions. arXiv preprint arXiv: 03301, 2017.
[39] R. Temam. Navier-Stokes equations: theory and numerical analysis, volume 343, American Mathematical Soc., 2001.
[40] A. Vaswani, N. Shazeer, N. Parmar, Uszkoreit, L., Jones, A. N. Gomez, I.. Kaiser, and
I. Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998-6008, 2017.
[41] D. Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you's 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "Iha_QbtVXl", "reviewer": "Reviewer_gsRU", "summary": "The paper proved an $\\epsilon$ approximation theory showing that the neural network approximation for linear elliptical PDEs is bounded by the number of NN parameters required for approximating the PDE coefficients as well as the dimension of the domain. The proof is mainly based on an operator theoretic point of view and the bounds are obtained by approximating gradient descent using neural networks. The results also provide insights into the recent success of using NN to approximate high dimensional as well as parametric PDEs. ", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper provides a rigorous proof for an $\\epsilon$ upper-bound for the approximation error. The paper provides important insights on the success of the NN approximation of high-dimensional/parametric PDEs. I enjoyed reading the paper and believe that it will be of interest to the NeurIPS audience. I therefore recommend a clear accept. \n\nBelow are some issues/questions that I have: \n(1)   Section 4 provides a list of well-known definition/theorem in functional analysis. While I appreciate the author's effort of including these in the main section, they should at least provide the references for the definitions/theories as they are not the authors' work.  \n(2)   The proof is mainly based on the fact that the gradient descent algorithm can be approximated by an NN. I wondering in practice, will this hold true? In other words, how tight are these bounds? Given the fact that the paper mainly concerns linear elliptic PDEs one should be able to easily check the scaling proposed in the main theorem. \n (3)  The paper mainly concerns the PDE coefficient $a(x)$ and the source term $f(x)$. How would the main conclusion change when the boundary condition is non-trivial? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "EXI3mEW9qzs", "reviewer": "Reviewer_WhbH", "summary": "The authors attempt to bound a neural network's complexity that approximates a solution to a self-adjoint elliptic PDE. The paper lacks mathematical rigor on the PDE theory side: the most important one is that their gradient descent step doesn't make sense from a functional analysis point-of-view (see main review). The authors need to compare the complexity of their neural network to the bound obtained by combining standard PDE regularity theory (see Evan's Section 6.3) with the complexity of neural networks for approximating smooth functions. Since the main theorem doesn't take into account the smoothness of the boundary of \\Omega, I suspect that the latter gives much stronger bounds for many practical domains. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Definition 1 is for self-adjoint elliptic PDEs, not general elliptic PDEs. \n\nThe domain \\Omega is assumed to be a bounded open set with a boundary. However, to define H_0^1(\\Omega), the domain must have a bounded trace operator. The usual assumption is that the domain has a Lipschitz boundary. \n\nThe smoothness of the boundary of the domain *greatly* affects the smoothness of the PDE solution. The paper gives the impression that \"if an elliptic PDE's coefficients and forcing term are easy to approximate by a neural network, then so is the PDE's solution.\" However, this is forgetting about the important role of the smoothness of the domain's boundary. Consider Poisson's equation on the unit square [0,1]^2 with zero Dirichlet conditions with forcing term f = 1. The coefficients of Poisson's equation and forcing term are trivial to represent by a neural network. However, the solution has logarithmic singularities at the four corners of the domain. In contrast, consider Poisson's equation on the unit disk with zero Dirichlet conditions with forcing term f = 1. Then, the solution is polynomial: u(x,y) = (x^2+y^2 - 1)/4. The main theorem ignores the smoothness of the boundary of \\Omega and without that I suspect that one can do better by combining standard PDE regularity theory (see Evan's Section 6.3) with the complexity of neural networks for approximating smooth functions.  \n\nUnfortunately, the gradient descent step in (5) seems to assume that L can be applied to functions in strong form. In strong form, the elliptic PDE operator L takes derivatives so it reduces the regularity of the gradient descent iterates. One cannot take two steps of the gradient descent iteration, as the second iterate may not be twice weakly differentiable. For the gradient step to make sense, the authors need to assume that the initial guess is infinity differentiable.  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some limitations are discussed. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "DwvmzTZpVSy", "reviewer": "Reviewer_rCSp", "summary": "This paper aims to establish neural network representation results for solutions to elliptic PDEs. The main result states that such solutions can be approximated without curse of dimensionality. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The approximation of high dimensional PDEs is a very relevant topic and neural networks are undoubtedly a very promising tool for this problem. There is already a significant body of research confirming that neural networks do not suffer from the curse of dimensionality. However, the approach of these previous works is different from the auhor's approach. In the present paper\n\n1.  the solution of an elliptic PDE is formulated as stationary limit of a parabolic flow that can be discretized yielding a sequence of functions, obtained form iteratively applying a suitable differential operator, that converges exponentially to the PDE solution. \n2. it is \"shown\" that applying one iteration step does not have a tangible negative impact on the approximability of a function by neural networks.\n3. together with the exponential convergence of the iteration, the approximation result follows. \n\n\n\nPoints 1. and 3. are certainly well known. Unfortunately, 2. is not correct. The authors state a Lemma (Lemma 7 in their paper) that claims that the derivative of a neural network is also a neural network of comparable size. This is wrong. The hat function is a small ReLU network, its derivative is discontinuous and therefore cannot be represented as a ReLU network. The second derivative is a linear combination of Dirac distributions - not even a function anymore. \n\n\n------\nAfter discussing with the authors I am now confident in the correctness of the claimed result. The issue has been that the authors use a highly unusual definition of neural networks which allows to choose at every node a different activation function from a countable set of activation functions. This set of activation functions consists of all derivatives of a given C^\\infty function, as well as the square function. This casts some doubt regarding the relevance of this result because it is clearly impossible to train such networks. The result is thus purely theoretical, even much more than \"usual\" neural network approximation results. \n\nOverall, given these considerations I am raising my score to 5. \n\n------\nAfter more discussions, the authors could also address the concern related to the unusual choice of activation function. \n\nI thank the authors for putting so such effort into this clarifying process and raise my score to 7. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Everything ok in this respect", "review_text": "", "extra_scores": {"ethical_concerns": "Everything ok in this respect", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "0nrR8P926vu", "reviewer": "Reviewer_PQMY", "summary": "The authors show that the solution of a linear elliptic PDE (with boundary condition) can be represented with a neural network, whose number of parameters is at most polynomial in the input dimension d, under the assumption that the coefficients of the PDE are given by NNs with poly(d) parameters.\n\nThis is achieved by first showing that gradient descent with a particular choice of stepsize, provides a sequence in $L_2$, that converges to the solution of the PDE. Then the iterates of the sequence are approximated by NNs in a recursive manner, and counting the number of parameters that are added at each iteration.\n\nIn essence, the result aims to help the understanding of how learning a solution of a high-dimensional PDE from samples might be computationally feasible using parametrized families of functions, like NNs.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The **originality** of this work hinges on its differences with the reference [14], which proves a similar result. Unfortunately I am not familiar with that paper. In this work, the authors only present a brief comparison to [14] claiming that \"their rate depends on the volume of the domain, and thus can have an exponential dependence on the dimension\", which would set them apart as they find mild conditions for the soution to require poly(d) parameters. After a quick glance at [14], indeed their results depend on the volume of the domain, but I believe it would be a good Idea to discuss reference [14] in depth, in the prior work section. In any case, reference [14] appears to provide a less general result that focuses on the Poisson equation, and the method of proof is vastly different.\n\nThe main issue I have found is regarding the **clarity**. The main result **Theorem 1** has an unspecified parameter $\\gamma$ that does not even appear in the paper up to that point. This makes it extremely hard to have a clear grasp of the implications of the theorem, because if $\\gamma \\to \\delta^+$ then $\\tilde{\\epsilon} \\to \\infty$ and the bound presented becomes vacuous. After some effort, it appears that the definition of $\\gamma$ appears for the first time in **Lemma 2**, 2 pages after **Theorem 1**! All parameters involved in **Theorem 1** should have a clear definition at the moment it is stated.\n\nMoreover, if $\\gamma$ is in fact like in **Lemma 2**, It is a quantity related to the operator $L$ and the results only make sense, I believe, if $\\gamma > \\delta$. So in fact there is a hidden assumption that is not disclosed nor discussed. Can it happen that $\\delta = \\gamma$, for example? why not? does it matter? This should be discussed and explained by the authors.\n\nAnother point that is not **clear** is what particular property of neural networks are used in the proofs. I have to disclose that I did not delve into the details of the supplementary material, but in the main text I think there are no particular properties of neural networks that are used to obtain the results. Everything is stated in number of parameters needed to approximate a function. Do the results hold for other classes of parametric functions like say, linear over features, products of polynomials, etc? It seems like the arguments using the gradient descent sequence and backpropagation should also work. If there are no particular properties of neural networks that are used in the proofs then It seems like it is just a term that is being thrown in without need. After briefly checking the supplementary It seems that only Lemma 8,9 talk about NNs but they just seem like general properties of automatic differentiation (that should apply to other classes of parametric functions) (Lemma 8) or allowing to take the square of the function (Lemma 9) which leads to the mostly artificial assumption that the quadratic activation function should be allowed in Theorem 1 (Line 186).\n\nFinally regarding **clarity**, the term *small neural network* is used throughout but the meaninig of *small* is not actually clear until later in the paper. It would be better if this can be clarified as early as possible otherwise the meaning of some claims in the abstract/introduction are too vague.\n\nThe synthetic assumption of a quadratic activation function being allowed in the neural network in Theorem 1 has practical implications that are not clear. Does it mean that when solving a PDE using a NN one should put the quadratic activation in some neurons? in all? try all combinations? The theorem, of course, only talks about existence of a solution and practical implications seem to be out of the scope of this work. Nevertheless this is an interesting point to discuss.\n\nThe **quality** of the work would be better if the previously mentioned issues are clarified/improved. Other than that, the paper is overall well written and the authors show expertise in the topics discussed.\n\nThe theoretical results seem **significant** as the apparent absence of the curse of dimensionality for NNs solutions to PDEs is not understood. However, I find it hard to see practical impacts of the work, other than my observation that using some quadratic activations might improve performance. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": " addressing potential negative societal impact is not relevant to this work. The authors do not discuss the limitations of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Recently, neural networks (NN) have had great success in approximating solutions of partial differential equations (PDEs). One key observation is that the NN approach to PDEs do not seem to suffer from the curse-of-dimensionality. Hence, it is important to understand the strengths and limitations of this approach.

The authors take on a particular class of PDEs (i.e., linear elliptic PDEs with Dirichlet boundary conditions) and provide a theoretical characterization of how many parameters are needed to approximate their solutions within a desired accuracy. They identify "small" networks suffice where the number of parameters depend polynomially on the dimension and linearly on the number of parameters required to express the PDE. The theoretical analysis is non-trivial and the paper provides a great path moving forward in the PDE research vein. 

While the initial scores of the work were below the threshold, the rebuttal was effective in clarifying the concerns of the reviewers, in particular mooting a counter-example proposed by a reviewer, confusions on the applications of the gradient operators (due to the final activations, and the way in which the NNs are constructed by authors (i.e., growing network in each iteration). As a result, the scores improved uniformly and I thank both the authors and the reviewers for their efforts.  


Decision: Accept (Spotlight)