Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: The objective of this paper is to prove that the solution $u$ of a certain class of PDEs, of the form 
\begin{equation}\label{eq:PDE}
- \nabla\cdot (A \cdot \nabla u) + cu = f \mbox{ on } \mathbb{R}^d  
\end{equation}
for some matrices $A$, coefficient $c$ and right-hand side $f$ can be well-approximated by functions belonging to some Barron spaces, provided that $A$, $c$ and $f$ belong to some Barron spaces as well. The precise approximation results are stated 
in Theorems~2.9 and~2.10 of the manuscript. 

Such kinds of approximation result are very interesting since they can give some insight on how well the solutions of some high-dimensional PDEs can be approximated by neural networks-based numerical methods. Indeed, 
it is proved in earlier works that elements of these Barron spaces can be approximated in the $H^1$ norm by two-layer neural networks.  

The article is organized as follows: notation and assumptions on the data of the problem are introduced in Section~2.1. The definition of Barron spaces is recalled in Section~2.2, together with approximation results in the $H^1$ norm of elements of Barron spaces 
by two-layer neural networks (Theorem~2.5). The proofs of these results is postponed in Appendix~B. The main results of the paper concerning the approximation of the solution of PDE (\ref{eq:PDE}) by elements of a Barron space are stated in Theorem~2.9 and Theorem~2.10. 
The main idea of the proofs of these results is sketched in Section~3, together with the statement of useful auxiliary lemmas. The detailed proofs of these results are given in the Appendix. 
main_review: The article is very well written and the presented results are very interesting with regards to the theoretical questions that neural-networks based numerical methods for the resolution of high-dimensional PDEs are rising. The proofs of the results all seem 
correct to me although I did not check all the details. Hence, I am in favor of the publication of the present manuscript in NeurIPS, up to a few minor modifications highlighted below. 

\begin{itemize}
 \item p.4: Def.~2.2: precise the definition of $\overline{B}_R^d$ l. 153
 \item Theorem~2.5, p. 5, l. 184: In this theorem $g$ is assumed to belong to the space $\mathcal B_R^2(\Omega)$. However, in Proposition~2.4, it is stated that $\mathcal B_R^\infty(\Omega) = \mathcal B_R^p(\Omega) = \mathcal B_R^1(\Omega)$ for $1\leq p \leq \infty$. 
 The use of the exponent $2$ in Theorem~2.5 is then confusing. I suspect a typo and that the author(s) actually meant to assume that $g$ belongs to $\mathcal B_R^1(\Omega)$. Correct? Similar remark/question at l.205 of the same page (Assumptions~2.8) where 
 $l_{d,2}$ is defined as $\|\sigma''\|_{\mathcal B^2_{R_{d,2}}}$. Do the authors mean $l_{d,2}:= \|\sigma''\|_{\mathcal B^1_{R_{d,2}}}$?  Please check in the manuscript if other similar typos are present. 
 \item p.5, l. 200: Do the authors simply mean by ${\rm im}\sigma \neq \{0 \}$ the fact that $\sigma$ has to be non identically equal to $0$? I am unsure of the meaning of the ${\rm im}$ notation there. 
 \item Theorem~2.9, l.214, p. 6: Could the authors comment on the fact that the dimension $d$ has to be assumed greater than $3$ for the result to hold? Could the authors add a remark on the reason why wuch a result could not hold in lower dimension? 
\end{itemize}

limitations_and_societal_impact: No potential negative societal impact identified
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the neural network approximation of high-dimensional elliptic PDEs. Specifically, it shows that when the source term and the coefficient functions lie in a Barron space, the solution can be approximated by two-layer neural networks without the curse of dimensionality.  The Barron norm characterizes the approximability of functions by two-layer neural networks.  The primary technique is to represent the PDE solution as the fixed point of the preconditioned steepest descent iteration.  Then,  it shows that the iteration satisfies two properties: (1) The iteration converges to the fixed point exponentially fast; (2) Each iteration only amplifies the Barron norm by a small fact.  To guarantee the first property, the PDE must be strongly elliptic. To guarantee the second property, the Barron space must be closed under multiplication, which excludes the most commonly-used activation functions. 
main_review: ## Quality and clarity 
This paper is well-written, and I can follow the authors' ideas very smoothly.  I went through the proof and they seem correct to me, though there are many tiny (no essential) errors.

## Originality
The result of this paper is obtained from a novel combination of the Barron space theory of two-layer neural networks and the property of elliptic PDEs, in particular representing the PDE solution as the fixed point of the preconditioned steepest iteration.  The authors also develop some interesting extensions of Barron space to bounded smooth activation functions, which may be of independent interest. 
Given the previous work, the main result (Theorem 2.10) is not surprising to me.  However,  I believe that the rigorous proof is not straightforward, which can also be seen from this paper, which extensively exploits the structures of the two-layer neural nets and the strongly elliptic PDE.  Therefore, in my opinion, this work makes a decent contribution to understanding high-dimensional PDEs and the neural net approximation.  

## Limitations and questions
- Assumption 2.7 excludes all the commonly-used activation functions.  I understand that this assumption is needed to establish the closeness of Barron space under multiplication. But, can authors comment more on this point? For instance, is it essential or just a technical issue?

- The main result 2.10 seems to suggest that cosine activation gives rise to a much better rate. Does the cosine activation function work better in practice under the setting of the theorem? 


# Minor issues
- In Theorem 2.10, the upper bounds should depend on $m(\Omega)$  instead of $\sqrt{m(\Omega)}$.
- In line 232, the upper bound of $k$ at least has a factor $1/\varepsilon^2$, which comes from the Monte-Carlo discretization. 
- In Proposition A.1 and the proof, $R_f$ is not defined. 

limitations_and_societal_impact: See the main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper derives complexity estimates of the solutions of second-order linear elliptic PDEs in the Barron space. It proves the solution of the PDE is ε-close with respect to the H1 norm to a Barron function and the complexity depends polynomially on the dimension d. The theorem implies physics-informed neural networks can efficiently approximate the solution of second-order linear elliptic PDEs.
main_review: Compared to previous work, the paper focuses on deriving complexity estimates of the solution in the integral-representation-based Barron space. 

Pros:
(1) the paper uses the Barron spaces techniques to improve the previous theorem.
(2) the writing is clear.
(3) clean related works.

Cons:
(1) the improvement looks subtle compared to previous work, especially [30], which also proves complexity estimates for elliptic equations. (2) The relief of assumption from 2 layer activations to 1 layer seems not very significant.

I have to admit that I am not very confident to assess the theoretical contribution and proof techniques. But overall, I like this work. I would vote for the border of acceptance. 
limitations_and_societal_impact: The second-order linear elliptic equation are in general easy for conventional solvers. The higher dimension cases are not very common to my opinion. It will be very interesting if the work can be extended to nonlinear PDE so that it can be applied to equations such as Navier-Stokes.
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: This paper studies the representation of solutions of second order elliptic PDEs using two layer neural networks,
and gives sufficient conditions so that this can be done without curse of dimension (the number of units grows at 
most polynomially in the dimension).  Precise theorems to this effect are stated and proven. 
The mathematical framework includes the definition of a Barron space of functions (essentially, finite norm of the
final layer weights), many structural results about this function space, and an iterative solution scheme with its analysis.

main_review: In recent years there has been much interest in developing numerical methods which take advantage of machine
learning concepts and technology, including the use of feedforward neural networks (FFNs) to represent solutions of PDEs.
There is a fair amount of numerical evidence that FFNs mitigate the curse of dimension for high dimensional PDEs of
practical interest, such as the HJB equation and equations of mathematical finance.
The present work studies the representation of solutions of second order elliptic PDEs using two layer neural networks,
and gives sufficient conditions so that this can be done without curse of dimension, here meaning the number of units grows at 
most polynomially in the dimension.  
The arguments do not use special properties of the PDEs and thus are more general than most previous work.
Their main conceptual tool is the definition of a Barron space of functions -- essentially, functions with a two layer FNN representation of arbitrary width such that the final layer weights have finite norm.
This definition is inspired by 1993 work of Barron (ref. [2]) as developed in ref. [8].
The authors develop the idea systematically in order to implement an iterative solution scheme and its analysis,
thus proving their theorems 2.9 and 2.10 which are precise forms of the claims.

The authors adequately cite the main works in this area that I know of.
The previous work closest to theirs is Marwah et al ref. [30], which uses a very similar iterative scheme to get similar results. 
However ref. [30] does not define and systematize the function spaces involved as clearly.
I found the arguments in the present paper somewhat simpler and clearer, also they have some advantages (listed in "related works").   Also ref. [30] is not yet published and the preprint only appeared in March 2021, so the citation to it here seems adequate.
limitations_and_societal_impact: No apparent direct societal impact.
review_title: null

Meta-review: All the reviewers agree that it is a very interesting paper in its field. I share the same opinion. 

The main contribution to this paper is to show that solutions of elliptic PDE of the form
\begin{equation}
\- \nabla \cdot (A \nabla u) + cu = f
\end{equation}
can be approximated by a two-layer neural network in some Sobolev norm. This kind of results is really important due to the increase popularity of PDE solvers based on deep neural networks. 

The main assumption considered by the authors is that the coefficients $A,c$ and $f$ all belong to some Baron spaces which have to be closed by multiplication. To obtain such a results, the authors builds upon results on Baron spaces recently obtained in the literature and on the representation of solutions of elliptic PDE as fixed-points of a steepest descent scheme. 

While, this result and the strategy of the proof may seem not really surprising, the paper is very well-written and succeed in gathering all the ingredients of the proofs smoothly. 

That being said, some points have been raised by the reviewers. I encourage the authors to address these in the final version of their paper.
Decision: Accept (Spotlight)