Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors study error bounds for estimating the solution $u$ of Poisson’s equation $\Delta u = f$ using early stopped gradient descent. The function $f$ is observed via noisy measurements $y_i$ at random points $x_i$, satisfying $E[y_i | x_i] = f(x_i)$. Poisson’s equation can be solved using the DRM or PINN approaches where the optimization objective function is crafted to be an integral. The integrals are then approximated with empirical risk and then gradient descent can be applied.

The authors establish lower bounds in Sobolev norms, given smoothness levels of $f, u^*$ and the smoothness of the operators $\mathcal{A}_1, \mathcal{A}_2$ that define the integral objective. They further show that early stopped gradient descent can achieve matching upper bounds in several cases and discuss suboptimality in the rest of the cases.

strengths_and_weaknesses: The results are interesting. The upper bound proof technique is interesting. The lower bound proof is standard, but that is not a negative.

The paper is pretty dense in terms of mathematics. One simplification could be to give examples (such as DRM, PINN) when introducing abstract concepts such as the operators $\mathcal{A}, \mathcal{A}_i$. In general, I suggest that the authors should make the text more amenable to machine learning graduate students.




questions: 1. In equation (2), should you remove the $-$ sign to be consistent with the rest of the paper?

2. In line 97, for $\mathcal{A} = \Delta$, $\mathcal{A}$ is not invertible. Should the usage of $\mathcal{A}^{-1}$ be clarified here?

3. Lines 91-92 and line 97: f and u seem to be interchanged, causing some confusion.

4. The relation between $\mathcal{A}, \mathcal{A}_1, \mathcal{A}_2$ in line 94 and line 186 are consistent given the Assumption 2.1 (d), but does not seem to hold in general?

5. Can you please write out the gradient step for DRM and PINN separately in elementary terms, perhaps in the supplement?

limitations: None.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper studies statistical optimality of a slightly modified gradient descent for learning elliptic equations with kernels. This problem is an extension of kernel regression. The first sound theoretical contribution is a min-max lower-bound in Thm.3. Then, the authors analyze the gradient descent on a batch of observations drawn i.i.d. In Thm 3.2. Combining these two results, statistical optimality of gradient is established. The key assumptions providing such statistical optimality relies on the critical capacity condition that holds for ridge regression and also toy examples of PDE solvers. The result is compared to existing analysis in literature which focus on more restrictive instances of the problem such as those in [15,16,68]. Then, the authors provide intuitions on the influence of loss function on the convergence of gradient descent leveraging their theoretical analysis and assumptions. 

strengths_and_weaknesses: **Strengths**

1. The paper establishes a theoretically sound contribution on min-max lower bound for a generalization of kernel regression.
2. The paper is very well written 
3.  Assumptions are stated clearly and motivated by examples. 
4. It is interesting to establish the optimality of gradient descent for solving PDEs with kernels. 


**Weaknesses**
1.  I am not sure about the significance of the result. Given results from kernel regression, one can translate them to the settings of this paper. Assuming that u(x) and u*(x) are in RKHS with kernel k, then A u(x) = <\theta, A(K_x)> for all operators x. Therefore, given observations $A_2^{-1} A_1 u(x)$, one can compute observations from $A_1 u(x)$ and given that the original measurements are i.i.d, they remain i.i.d.. Then a straightforward change of variables as $y = A^{1/2} u(x)$ leads to the standard kernel regression settings for which all min-max lower bound and the convergence of gradient descent is well known. The only difference with the standard kernel regression setting is the convergence metric which can be sandwiched by the l2 distance in kernel ridge regression settings under standard assumptions. In particular, the change of gradient is equivalent to the change of objective which makes the gradient descent on the modified objective same as the gradient descent on kernel regression. 
2. It would be interesting to experimentally compare the performance of gradient descent with its modified variant considered in this paper. 

questions: 1. The authors motivate their study by the example of neural tangent kernel. I wondered their assumptions hold for neural tangent kernels. 
2. Would you please elaborate why it is not possible to invoking the existing results on kernel regression (early stopping and the lower-bound analysis) to get the same results? 
3. What is the difference between the modified gradient descent in this paper, and gradient descent on kernel regression? 
4. Is there a representer theorem for the modified kernel regression? Would you explain more about its connections with the early stopping? 
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper provides the analysis of the statistical limits of the gradient descent algorithm used on a class of objective functions for solving the inverse problem. Specifically, the main use case of this analysis is utilizing neural networks as PDE solvers. The theorem shows in what cases the gradient descent algorithm can achieve an optimal convergence. It also demonstrates the influence of early stopping on PINN and DRM methods.
strengths_and_weaknesses: As far as I understand, utilizing deep learning based numerical methods to solve PDE is a promising direction thus the analysis to understand its convergence is also important. The authors include detailed discussion about the link between the proposed theorem and other existing works, which facilitates the interpretation of the result. The proposed theorems match well with the empirical observation made on PINN and DRM methods about the Sobolev implicit acceleration. One weakness is that the result only applies to gradient descent. If would be more useful if the accelerated gradient descent is covered since it's widely used in practice when training deep networks.
questions: Please see weaknesses.
limitations: The authors have discussed about the limitations.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper considers the statistical optimality of gradient descent for solving a class of inverse problems. When the function of interest is contained in a suitable Reproducing Kernel Hilbert Space, the authors show that the gradient descent of a general objective function achieves statistical optimality. As an implication, the authors show that using a Sobolev norm as the objective function for training leads to an implicit acceleration in terms of training efficiency. 
strengths_and_weaknesses: Strengths:

This paper considers the statistical limitations of solving PDEs by parameterizing the solution as a function in a Reproducing Kernel Hilbert Space. I believe the study of the statistical limitations of solving PDEs with a parameterized model is fundamental and crucial to the literature of "AI for science". The authors show that running gradient descent on a general class of objective function already achieves the statistical optimality and is able to explain the advantage of PINN over DRM via the implicit acceleration of the Sobolev training objective.

Weakness:

1. In lines 54 to 58, the authors provide a nice review of the information theoretical limit for solving PDEs with random samples. To distinguish this submission from the previous works, the authors state that "all these papers assume accessibility of the global solution of empirical loss minimization. In contrast, here we consider the gradient descent algorithm for learning the estimator.". Could you explain why using gradient descent as a specific estimator is of great importance? From a practical perspective, we typically use stochastic gradient for the purpose of training which has quite different behavior from gradient descent. So I guess maybe the major difference lies in the analysis. It would be great if the authors could elaborate on this.
2. I am a little confused by the notation in line 97. Is $f$ related to $f^*$? I thought the goal was to recover $f^*$ as claimed in line 91.
3. What is the meaning of $\mathcal{L}^{\beta/2}$ given that $\mathcal{L}$ is defined in line 111.
4. The definition of the Sobolev norm in Definition 2.2 is not the same as the standard one, could you explain how the standard Sobolev norm can be related or translated to the one in Definition 2.2?
5. I see that the parameters $\alpha, \beta, p, q$ are crucial to the theoretical result in Theorem 3.2. Could you please explain what are the meanings of them?
6. What is the dependence on the dimension $d$? A major problem of previous numerical PDE solvers is that they become inefficient when $d$ is large. Hence, the dependence on $d$ is crucial and should be taken into account.
7. The current submission considers the periodic boundary condition (the torus) and hence the integration over the boundary automatically vanishes. However, this is not true for other more practical boundary conditions like Dirichlet and Neumann boundary conditions. It would be great if the authors could elaborate on this as well. Without this zero boundary integral property, integral by parts will introduce extra terms which might break the proof.
8. The accuracy of in Figure 4(b) seems too low to prove that the solution to the PDE is actually recovered.
questions: Please see the questions in the above section.
limitations: I do not see any negative societal impact.

I believe the quality of this work can be improved if the dependence on the problem dimension is also taken into account. Besides, being able to handle more complicated boundary conditions will also be a big plus.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper provides a theoretical analysis of the optimization process of the optimization-based PDE solvers. Specifically, the authors (1). first generalize the objective function of PINN and DRM for solving elliptic PDEs into a unified formulation, and (2). then provides upper and lower error bounds for gradient descent over a Reproducing Kernel Hilbert Space using the unified objective function. The discovery is two-fold: (1). In most cases, the upper bound matches the lower bound, which shows in this case gradient descent can achieve statistical optimality. (2). Furthermore, it is also observed that the training time that gradient descent first achieves statistical optimality decreases when higher-order derivatives are employed (called "Sobolev Acceleration"). Numerical experiments are conducted to support the theoretical findings.
strengths_and_weaknesses: Strengths:
1. Most importantly, this paper provides a theoretical and sound explanation of an interesting phenomenon (i.e., Sobolev Acceleration) of optimization-based PDE solvers. I believe such a contribution is of the communities' interest.
2. The presentation of this paper is clear and the experiments are detailed.

Weakness:
1. The gradient descent in this paper is actually a modified version. While the authors highlight this and mention "Without our modification, the statistical rate will become sub-optimal in some cases", it will be great if the results with the original gradient descent could be provided to facilitate the understanding of the gap.
2. There are some typos and mismatches of symbols (part of them listed in "limitations"). This paper will benefit from checking the mathematical presentations throughout.

Overall, I am in a positive position for this paper. The paper can be further improved by taking the above suggestions.
questions: Despite the weakness mentioned above, I have the following two questions:
1. Could you give an intuitive explanation of the Sobolev acceleration, despite the analysis through the form of the achieving time? It will be great if such an explanation can be included in the paper.
2. Could you provide an example of how the eigenvalues of differential operators behave (and how they change when the order of the differential operator gets higher)? This can make the discussion "For differential operators, the p is actually negative (differential operators have large eigenvalues over high-frequency basis)" more clear.
limitations: Please refer to the "weakness" part. Here I list the typos:

Line 100: $e_j\rightarrow e_i $

Line 106: $k\rightarrow K$, $K_x\rightarrow K_z$

Line 117: $k\rightarrow K$ Line 120: $\sigma\rightarrow \Sigma$

Line 195-197: All $u$ in the inner product should be $theta$ or all $\theta$ in the inner product should be $u$

The first case in Theorem 3.2: it should be $\beta<...$

Line 661-663: do we need the transpose symbol $\top$ here?

Line 671: I guess the $\hat{q}_ {\lambda}$  here is the same as the $\hat{g}_{\lambda}$ in Line 718?

Line 712: $\Sigma_{Id, A_1}$ is not defined.
review_title: null

Meta-review: metareview: This paper studies the statistical performance of Deep Ritz Methods (DRM) and Physics Informed Neural Networks (PINN) for solving an inverse problem with respect to elliptic equations. As a key example, consider the problem of estimating the solution $u$ to Poisson's equation $\Delta u = f$ given noisy observations of $f$. When the solution is a function in an RKHS, and using a Sobolev norm as the objective function, they show that gradient descent achieves implicit acceleration. They use this theory to show that both DRM and PINN achieve statistical optimality, but the number of epochs needed for DRM is larger. This is a nice contribution to the growing area of deep PDE solvers, and provides some illuminating theoretical insights. There was some debate between a reviewer and the authors about whether the results follow from existing bounds for kernel regression, but the authors convincingly argued that the norm of $A^{-1}$ in general need not be bounded and so those results cannot be applied in a blackbox manner. Additionally there are other differences and complications.
confidence: Certain
Decision: Accept