Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

This 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.

In 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.
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.

The 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.

Moreover, 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.

Another 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).

Finally 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.

The 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.

The **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.

The 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. 
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_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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. 
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. 

Below are some issues/questions that I have: 
(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.  
(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. 
 (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? 
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
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

1.  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. 
2. it is "shown" that applying one iteration step does not have a tangible negative impact on the approximability of a function by neural networks.
3. together with the exponential convergence of the iteration, the approximation result follows. 



Points 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. 


------
After 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. 

Overall, given these considerations I am raising my score to 5. 

------
After more discussions, the authors could also address the concern related to the unusual choice of activation function. 

I thank the authors for putting so such effort into this clarifying process and raise my score to 7. 
limitations_and_societal_impact: Everything ok in this respect
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
main_review: Definition 1 is for self-adjoint elliptic PDEs, not general elliptic PDEs. 

The 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. 

The 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.  

Unfortunately, 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.  

limitations_and_societal_impact: Some limitations are discussed.
review_title: null

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)