Sobolev Acceleration and Statistical Optimality for Learning Elliptic Equations via Gradient Descent
Authors: Yiping Lu
Jose Blanchet
Lexing Ying
Venue: NeurIPS 2022 Accept (2022)
Keywords: PDE
Ritz Methods
nonparametric estimation
Physics

Abstract: In this paper, we study the statistical limits in terms of Sobolev norms of gradient descent for solving inverse problem from randomly sampled noisy observations using a general class of objective functions. Our class of objective functions includes Sobolev training for kernel regression, Deep Ritz Methods (DRM), and Physics Informed Neural Networks (PINN) for solving elliptic partial differential equations (PDEs) as special cases. We consider a potentially infinite-dimensional parameterization of our model using a suitable Reproducing Kernel Hilbert Space and a continuous parameterization of problem hardness through the definition of kernel integral operators. We prove that gradient descent over this objective function can also achieve statistical optimality and the optimal number of passes over the data increases with sample size. Based on our theory, we explain an implicit acceleration of using a Sobolev norm as the objective function for training, inferring that the optimal number of epochs of DRM becomes larger than the number of PINN when both the data size and the hardness of tasks increase, although both DRM and PINN can achieve statistical optimality.

Sobolev Acceleration and Statistical Optimality for Learning Elliptic Equations via Gradient Descent
Yiping Lu ICME
Jose Blanchet
Lexing Ying
Management Science and Engineering
Department of Mathematics
Stanford University Stanford, CA 94305 yplu@stanford.. edu
Stanford University Stanford, CA 94305
Stanford University
Stanford, CA 94305
jose. bllanchet@stanford.ccm
lexing@stanforde edu
Abstract
In this paper. we study the statistical limits in terms Sobolev norms of gradient descent for solving inverse problems from randomly sampled noisy observations using a general class of objective functions. Our class of objective functions includes Sobolev training for kernel regression, Deep Ritz Methods (DRM), and Physics Informed Neural Networks (PINN) for solving elliptic partial differential equations (PDEs) as special cases. We consider potentially parameterization of our model using suitable Reproducing Kernel Hilbert Space and continuous parameterization of problem hardness through the definition of kernel integral operators. We prove that gradient descent over this objective function can also achieve statistical optimality and the optimal number of passes over the data increases with sample size. Based on our theory, we explain an implicit acceleration of using Sobolev norm the objective function for training, inferring that the optimal number epochs of DRM becomes larger than the number of PINN when both the data size and the hardness of tasks increase, although both DRM and PINN can achieve statistical optimality.
Introduction
Several learning based methods for solving inverse problems have been proposed recently with state-of-the-art performance across wide range of tasks, including medical image reconstruction
M. inverse scattering [2] and 3D reconstruction [3] In this paper, we study the statistical limit of machine learning methods for solving inverse problems. To be specific, we consider the problem of reconstructing function from random sampled observations with statistical noise in measurements. We apply gradient descent
general class of objective functions for the reconstruction. When the observations are the direct observations of the function, the problem is non con-parametric function estimation 4 5 The observations may also come from certain physical laws described by partial differential equation (PDE) ( 77 Formally, we aim to reconstruct a function f based on independently sampled data set D) (ar,, from an unknown distribution P on X' x ), where is the noisy measurement of u² though measurement procedure A. For simplicity, we assume A self-adjoint this paper. The conditional mean funetion (x) Ey(Y = x)) is the ground truth function for observation of u" through the measurement procedure A, i.e. f = Au". To solve this problem, we consider gradient descending over the following general class of objective function
arg min (r.,( (u(x), Aru(z)) (y. Azux))) WEH.
where - 8(2,, yt) is the empirical distribution, is reproducing kernel Hilbert space (RKHS) and A,, 1, 2 are two self-adjoint operators that satisfy Ai AAz. In Section 2 we show that several algorithms, including kernel regression g via Sobolev training [9] [C Jul and solving PDEs via machine learning based algorithm, 12 cases of this formulation.
44] can be considered as special
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

have considered the statistical limit of learning of elliptic inverse problem, i.e. how many observation of the right hand side function of an elliptic PDE are needed to reach a prescribed performance level. However, none of these papers consider computationally feasible methods for constructing such optimal estimators. In this paper, we consider the statistical optimality of gradient descent 17
Recent works [ 16
19 20]. successful and widely used algorithm in machine learning. We show that proper early stopped gradient descent can achieve information theoretical optimal convergence rate according to continuous scale of suitable Hilbert norm (i.e. Sobolev norms 22 22 detailed definition see Section 2)
18
We first prove that properly early stopped gradient descent algorithm over the class of objective functions can achieve statistical optimality. At the same time, although any suitably early stopped gradient flow of the class of loss function can achieve statistical optimality according to our theory, we discover an acceleration effect of using a Sobolev norm as the loss function for kernel based machine learning algorithms. The implicit acceleration of the Sobolev loss function arises because a differential operator can enlarge the small eigenvalue of the kernel integral operator for high frequency functions, leading better condition numbers and faster convergence in these eigenspaces while maintaining the statistical optimality. We justify our theoretical finding with several numerical experiments.
1.1 Related Works
Machine Learning Based PDE Solver. Partial differential equations (PDEs) are widely used in many disciplines of science and engineering and play a prominent role in modeling and forecasting the dynamics of multiphysics and multiscale systems. The recent breakthroughs in deep learning and the rapid development of sensors, computational power, and data storage in the past decade have drawn attention to numerically solving PDEs via machine learning methods 223 especially in high dimensions where conventional methods become impractical. Based on the natural idea of representing solutions of PDEs by (deep) neural networks, different loss functions for solving PDEs are proposed. [5] 26 utilize the Feynman-Kac formulation which turns solving a PDE into
25 IK
stochastic control problem. The work of (27 solves the weak formulations of PDEs via an adversarial network. In this paper, we focus the convergence rate of the Deep Ritz Method (DRM) 14 2 and the Physics-Informed neural network (PINN) 12 133 DRM 14 2 utilizes the variational structure of the PDE, which is similar to the Ritz-Galerkin method in classical numerical analysis of PDEs, and
trains a neural network to minimize the variational objective. PINN [22 [3] trains a neural network directly to minimize the residual of the PDE, i.e., using the strong form of the PDE. Theoretical convergence results for deep learning based PDE solvers has also received considerable attention investigated the regularity of PDEs approximated further provided generalization analyses. [15]] 16. 40
recently. Specifically, (28 29
30
31
32
R
by a neural network and 28
35
36
37
provided information theoretical optimal lower and upper bounds for solving PDEs from random samples. However, 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. The most relevant work in connection to is [4]. which considers a polynomial-tine type algorithms to sample from the posterior measure of the Bayesian inverse methods. Instead of considering the Bayesian setting, here we optimize on the un-regularized objective. However, the estimator is regularized via early stopping 42
Langevin-
44 i.e. we consider the statistical optimality
of the implicit regularization effect of optimization algorithm. A concurrent paper 45 considered similar stochastic gradient descent approach for statistical inverse problem.
Learning with kernel. Supervised least square regression in RKHS has a long history and its generalization ability and mini-max optimality has been thoroughly studied N 46
48. Sta- tistical optimality of early stopped (stochastic) gradient descent has been widely discussed in
42
52 The convergence of least square regression in Sobolev norm has
been discussed recently in 21 22). Recently, training neural networks with stochastic gradient
descent in certain regimes has been found be equivalent to kernel regression [53] 54 (55]. Gradient
descent training of neural network in the kernel regime has been found optimal for a wide class of
non-parametric functions with both early stopping regularization and ridge regression 56 57
1.2 Contribution
We provide information theoretical lower bounds (Theorem 3.1 for a wide class of inverse problems, including the Sobolev learning rate [2] for the solution of elliptic inverse

---

problems. We also show that the previous lower bound [5 16] for machine learning solving elliptic equations can be considered as a special case of our lower bound.
We provide proof of statistical optimality of the gradient descent algorithm of a general and Deep Ritz Methods of kernel methods. We TG a computational feasible estimator and generalize the previous statistical optimality results of gradient descent 42 [8] [9 to general Sobolev norm.
class of objective functions (Theorem 3.2). including PINN
12
13
[44
2
for solving PDEs as well as Sobolev training 11 9
58
provide
We also characterize the acceleration effect Sobolev loss function for learning with kernel. The acceleration happens because differential operator enlange the small eigenvalues for high frequency functions, leading to better condition number and faster convergence in these eigenspaces while keeping the statistical optimality. Thus when the target function have more high frequency component, the lead of PINN will become larger (Figure 3 We justify our theoretical finding with several numerical experiments (Figure 2 and Figure
Problem Formulation
In this section, we formulate the problem of learning inverse problem using the kernelized gradient descent. As described previously, we aim to reconstruct a function f E RR from random observa- tions of u² Af". where A is an observation process which is modeled by operator maps from Rx to x To solve this problem, we write the operator A in terms of two operators A, (i = 1,2) with A = A2 and build our objective function as
Ep 2
(v. Azu(z))
(1)
where is the joint distribution of x and y with x sampled from the uniform distribution on X' for simplicity and y the noisy observation of f(x) (Au)(z). In other words, B[yl2r) = f(x)). The minimizer of objective function
is the ground truth function o' = f that we are interested in.
Learning with Kernel Consider the case that u is parameterized by a Reproducing Kernel Hilbert Space us (z) (0, K²) (we provide standard notations of RKHS in Appendix (A). At the same where e;
- (se; orthogonal basis of C2(px) with px being the uniform distribution over X, where La denotes the space of all the square integrable functions. Then e; is also the eigenvector of the covariance operator Σ Kx @ K2 with eigenvalue X >> 0, i.e. Σe, Xve- Here g @ h gh" T is an operator from H. to H defined as @ h f (f. h) g. The covariance matrix Σ is the core of the integral operator technique [46 g for kernel regression. For any ʃ H. the reproducing property gives (z))(z) = Ef, = TE(((X)((Xx)) =)] = B[f(X) (x))))())) If we consider the mapping S : H + L2(dr) defined as a parameterization of a vast class of functions in x via H through the mapping (z) = (g, Kn)) (D(x) K₂
time, the kernel function has the following representation K(s, t) = Σ
k(),))) Its adjoint operator S" : Le + H then can be defined as g - Sx (t) Kapx E is the same as the self-adjoint operator S and the self-adjoint operator
SS L2 (dr) + (d(z) can be defined as (z))) fx K(x, ())x))px(()) Based on this notation, we present all our assumptions on the underlying kernel.
Assumption 2.1 (Assumptions on Kernel). We assume the standard capacity condition on kernel covariance operator with a source condition about the regularity of the target function following H. We further assume a regularity condition for our kernel k(-,-) via foo embedding property follows These conditions are stated explicilly below.
59
60
18
21
(a) Standard assumptions. The kernel feature are bounded almost surely, i.e. Ik(x, v)1 - R and the observation y also bounded by M almost surely.
(b) Capacity condition. Consider the spectral representation of the kernel covariance
operator σ = Σ Xre; @ e; we assume polynomial decay of eigenvalues of the covariance matrix >; x 1- for some (c) Source condition. We also impose an assumption on the smoothness of the true function.
1. As result Q tr(E!/a) < oo.
There exists 3 E (0, 1] such that n² = / for some & E 1.2, If uz (x) = (0., K the source condition can also be written as
1-8 0. 11 <
a
3

---

(d) Capacity conditions on A, For theoretical simplicity, we assume that the self- operators A, are diagonalizable in the same orthonormal basis 6G. Thus we can assume
20 4 8 e/
A1 Σ p.e pes 1=1
for positive constants Pt. qi O. We further assume p; X i and qi x 1 This commuting assumptions also made in 66 [2]. due to the Bochner's theorem. We further assume p < 0, < 0, + > O. We refer the detailed discussion to Remark [
(e) Regularity results on RKHS. For μ. E [0, 1], there exists Ki 2 0 such that ((x) @ (xx) < ke 1 holds almost surely. The regularity assumption here is equivalent lIall S K R gli and implies l|gl| I R [1gll ||g for every E H. As a consequence, we know that 224/2-1/2D(2)11/1 S R² R holds almost surely.
159
[8
Remark 1. To simplify the technical exposition, we assume that operator A:(i = 1, 1, commute with the kernel covariance operator Σ. This assumption is also made in 62 61. Here we provide several examples that satisfy this assumption. The simplest case is A A id, which gives rise to the function regression setting.
633 assumes the operator A, to be bounded operator in special case of ours. At the same time, for numerically solving a PDE/elliptic inverse problem, we take A, to become the power of the Laplace operator A, which contradicts with [63] 's assumption. If the domain is sphere, the eigen- functions spherical harmonics which are also the eigen-functions of wide class of kernels, examples includes the dot product kernels [64] and the Neural Tangent Kernel
operator norm, which can be consider
65 66), when the data distribution is uniform distribution. When the domain is the torus, the eigen-functions are Fourier modes. If consider shift invariant kernel K K(x,)) y) sf(x y), from Bochner's Theorem K(x,, y)
Σx= (ww) ius we know that the eigen-functions are also Fourier modes. There are also works that use Green function as the kernel 67 68 where the three operators will automatically commute with each other.
In this paper, we consider the convergence of the estimator in Sobolev norm class. We define the different Sobolev spaces via the power space approaches used in 69 21.
Definition 2.2 (Sobolev Norm). For y > 0, the y-power space is
} c CL2(v),
H
e;:
Σ 121
o S }
121
1/2
equipped with the 7-power norm via Σi21 0:77 1/2 eill> = (Eiz1 az
It is obvious that ||/0/2/1, |// and ||/ < 1 fllx (2I). The source condition can also be understood as the target function u² lies in the 3-power Sobolev space. The regularity condition of the kernel function implics a continuously embedding from H + Loc. Throughout this paper, consider the convergence rate of u u in y-power Sobolev norm (? 0).
2.1 Examples
introduce the idea of training using Sobolev spaces via matching not only the function value but also the derivative of the classifier. Using different Sobolev norms as loss function has also been used widely in image processing, inverse problems, and graphics applications
Sobolev Training
70,
72 IC 73 74 75). The work of [7I] discovered that different Sobolev loss functions would lead
to different implicit bias and that the proper Sobolev preconditioned gradient descent can accelerate the optimization of geometry objectives 77
In this paper, we discover that stochastic gradient descent over Sobolev norm loss class functions can achieve statistical optimal but proper selection of the Sobolev norm loss function can accelerate training. We call this phenomenon Soboley Implicit Acceleration and discuss it in Section 4
74 75
Machine Learning Based PDE Solver. To simplify the exposition, we focus on a prototype elliptic PDE: Poisson's 's equation on torus, í.e. Ω = T [0, 1 Our focus is on the analysis of deep-learning- numerical methods for the elliptic equations
Au + u == in Ω
(2)

---

We mainly focus on amalyzing Deep Ritz Method (DRM) 14 and Physics Informed Neural Network (PINN) 133. DRM solves the equation via minimizing the following variational form
(u) = 2 J Vul² + u² dx - --1/ fudz,
2 =
arg min & NEF
DRM
(3)
while PINNs solves the equation the PDE,
via minimizing the following strong formula, i.e the residual of
1 (Au - uu f)² dx,
arg min & PINN (u) = 2 F
(4)
where u is minimized over parameterized function class FF (for example neural network). Here
we consider the function class to be the RKHS space 776, 77]. [16] showed that empirical risk minimization of both objectives can achieve information theoretical optimal bounds. The objective
function in 3 and g can be considered as special case of objective function ① For DRM, A = Au
and Apu u for all function E I For PINN, Aiu = A and Az Au for all function Rx
E
We discover that PINN convergences faster than DRM consistently due to the implicit Sobolev acceleration, matching the observation made in 78] 6 considered sumi-super learning using Laplacian regularization with kernel parameterization. However, this paper does not consider training with stochastic gradient descent and also does not introduce the source condition assumption that leads to different convergence rate for a hierarchical parameterization of task difficulty.
Main Theorem
We present our main results in this section, including information theoretical lower bound and matching upper bound with proper selected early stopping time.
3.1 Lower Bounds
This subsection investigates the statistical optimality of the Sobolev convergence rate of solving elliptic problem using stochastic gradient descent. We provide the information theoretical lower bound of learning the elliptic problems. Different from [5 [6] formulate the problem in an RKHS. This leads to a different construction of hypothesis and show that [15] [6] is special case of our lower bound using specific kernel and operator Ai = 1, in Section 3.3
Theorem 3.1 (Lower Bound). Let (X, B) be a measurable space, H be a separable RKHS on X with respect to a bounded and measurable kernel k and operator A = A1) satisfies Assumption
A1)
2.1 We have n. i.i.d. random observations {(I;, (I) E X x J of f" Au, E H n L.
Le. Yi = f (xx; ) + Th where πι is a mean zero random noise satisfies the momentum assumption
E E/yl" m < 2 mlo 2 L for some constants
0. Then for all estimators H (X y) 7t
satisfies
inf sup E E|H(((E,)))))))) - u 11 1 (mox)
H
3.2 Upper Bounds
This subsection, we consider the (multiple pass) gradient descent over the empirical data of ob- jective function ( We aim to construct our estimator via optimizing the empirical loss func- tion Ei= 1 {u(x;)) A,u((;; y;u(), where v; is sampled randomly and yı is the associated noisy observation introduced in Section I We consider parameterization u(x) = (u, Ks) and Azu(x) (A,0, Kx)n (0, A,Ku)n and express empirical objective function
1 Ep,(..n) (u(x).Au(zz)) (y. Azu(x)) Ep, (a.))) (u, Ka) (Aiu, Ka) y (Azu, Ka)
(5)
1 Ep. (u, K2 & Ai Kzu) - (u, A2Ka)
Then the gradient descent algorithm can be written as the following procedure:
Initialization: 9n 0u 0, y is a constant to be determined later which is used as the learning rate in the algorithm.
Iteration: For the t-th th iteration, we perform the following gradient descent step
0, 0,
(y1A2Kn, -10-11 A, Ks,)
with an averaging step 0, (1 1)0011 1
5

---

Remark. Note that the optimizing dynamics considered here is not the exact gradi- ent descent dynamies over the empirical objective. The gradient of the quadratic term Di= u(z;) should be 1 Li=1 (0 Kx, + (0z-1, Ka,) A K2,) but we K2, in our dynamics. In the population expectation, the two dynamics are the same due to the commuting assumption between the kernel integral operator and operator A1. Without our modification, the statistical rate will become sub-optimal in some cases due to the fact that the variance in the empirical covariance matrix dominates the statistical rate. This observation matches the reason behind the sub-optimality of the Deep Ritz Method discovered in 16
take instead 1 Ei= A,
The following theorem is the main result for upper bounds with the proof details given in the appendix.
Theorem 3.2. Under Assumption
we have the following three regimes shown in Figure !
For $ >
a+2q-p-1 if we take t = and
n 8a+2(p-9)
we obtain the following
rale
(8-7)0 E116 u |1 = O(n -n-2(p-9)+1 ).
For a+22-pp-1 < 3 <
pa-t2g-ptt if we lake 1. = 11.5 121p TTII and y small enough
o+P
constant, we obtain the following rate
E[10, u [14] = O(n 2p-2(p--)++
The
For 3> pa-t2g-tt we take following rate a
and 7 a small enough constant, we obtain the
E||0, - u [1?] = O(n
(8-1)a patp )
which is not an optimal converging rale.
Sketch of the Proof. We first rewrite the averaged gradient descent in a more compact for- mula as 77 = Th = 7w-1 + (A4] 5%0 - Ldd.A, 17-1) where S, : H + R" defined as Σ O,K₁ @ O2K₁ and Id is the identity opera- tor. For the error of GD, consider early stopping of gradient descent algorithm
S..g < (g(z1), .((.))) Eo,,,
1
spectral 19. Our proof is based on standard bias-variance decomposition. For it-
filtering 779 18
53
eration, GD will behave similarly to ridge regression with 71. regularization strength 442 [8] and
(8-220
this result in bias of (
a+p
For the variance, we provide bound which is related to the
effective dimension given by tr((E1d,A, + (1) Am) and obtain final variance of the form
(nt)
1
Zo 2u
If we only have the first o+p
term of variance, we shall achieve information theoretical optimal bound when t = n 12P
For the section term in the variance is from the convergence of empirical covariance matrix Σid,A, the population one Σid,A,- This term can be reduced using semi-supervised learning techniques as in [80 [6.
3.3
Discussion and Implications of Our Theory
Relationship with [6]. 15 16 provided a lower bound of the form n for a 2/ th order linear PDE A'u = with solution in Ha evaluated in H/ norm. We shall discuss the relation- (0-21a
ship between their bound with our n 1254 lower bound based on the kernel representation of Sobolev spaces. The numerator (3-7) matches the a-s term in 15 16's lower bound and the q-p term is the order of the linear PDE which matches the term in the denominator in [6]]ss 's lower bound. The spectral decay speed of kernel always relative to the dimension d. To understand this problem, we consider the following two examples.
For the first example, the kernel is defined on the torus T = [0, [ppr We consider the space of square integrable functions on Td with mean O and the Matérn kernel KaJ,o v)
B. ( where B, is the modified Bessel function of section kind. The covari- operator is Co o²( 721)= with orthonormal eigenfunctions &m (z) 2mi(m,.n) and corresponding eigenvalues Am o² (4 |m| + - for every gd (0) 81.
21-2 [(w)
[=- vl

---

B
Small LR, a Iteration
0m
Constant LR
Sub-Optimal
Figure I: Phase diagram of different regimes for solving inverse problem using stochastic gradient descent. Except for the gray area, GD can achieve the information theoretic rate.
//
For the second example, we consider the Mercer's decomposition of a translation invariant kernel via Fourier series ((s - t) = 1 Ew (w))e (w(()))
dw. The cigenfunctions of the
2st
translation invariant kernel is the Fourier modes and the eigenvalues are the Fourier coefficients. As proved that the corresponding the eigenfunctions are spherical harmonics that diagonalize the differential equation.
an example, for Neural Tangent Kernel, 8 66
65 (56
प and
For the upper bound, [6 established the convergence rate based on the empirical process technique 48 59 while our paper switches to the integral operator/inverse problem technique g An advantage of the integral operator/inverse problem technique is that it can provide convergence results with respect to continuous scale of Sobolev norms while the empirical process technique can only be used for the Sobolev norm equivalent to the objective function.
Relationship with gradients under the framework of least-square regularized regression in reproducing kernel Hilbert spaces. In this paper, we only have access the noisy observation of the function values but still aim to know about the convergence rate with respect to the Sobolev norm. At the same time, we further consider an inverse problem setting with an early stopping regularization, which is not discussed in [70] However, we introduce a commuting assumption over the differential operator with the kernel integral operator that facilitates our analysis.
70 also considered learning from data involving function value and
Sobolev Implicit Acceleration Below discuss the implication of the choice of early stopping time f
air 1 First of all, the best early stopping time here does not depend on % which means the best model in different Sobolev is the same over the stochastic gradient descent path asymptotically. Secondly, all the components in an iteration step depend on the problem itself except the numerator a + p. For differential operators, the p is actually negative (differential operators have large eigenvalues over high-frequent p more negative, i.e. using a higher order Sobolev norm as loss can lead to earlier stopping. As an implication, the PINN achieves the statistical optimal solution faster than DRM.
basis). Thus we accelerate the training via letting
Relationship with implicit bias of frequency Recent work credit the success of deep learning the fast training in low frequency components 83 preconditioning. the training speed of high frequency part increases, yet achieving statistical optimality in the class of Sobolev norm. This suggests that the implicit bias of frequency is not necessary for good generalization results. We also would like refer to 36, 87 Theorem 8 for the extreme case, where the authors directly invert the population covariance matrix which leads to the same training speed in every eigen-spaces while still maintaining the statistical optimality in l2 norm. However the preconditioning matrix in [86] is the population Fisher information matrix, which requires further sampling of unlabeled data that is not accessible in our setting.
However, in our work, with Sobolev
Discussion of the Sub-Optimal Regime In the sub-optimal regime, the concentration error between the empirical covariance matrix Σia,A, and the population one Σid.A, dominates. With the observa- tion that these concentrations have no relationship with the supervision signal, 16 30 proposed to utilize the semi-supervised learning to reduce the error in this regime. In [16], Deep Ritz method requires semi-supervised learning while PINN does not for the exact empirical risk minimization solution. In our formulation, if [p| is larger, the sub-optimal regime will become smaller, which
7

---

contradict with the observation in [T. However T6 bound but doesn't 't take optimization into consideration. We leave designing algorithm with smaller sub-optimal regime as future work.
only considers the statistical generalization
4 Sobolev implicit acceleration
(e) Kermel
(s1 Neural hetror hetaork
The Sobolev norm has already been proposed as loss function for training neural network [9] and solving PDEs 58 However, all these papers need a further gradient information of the supervision signal. This does not fit the the- oretical framework considered here and hence it is also not fair to compare their algorithms with methods without gradient supervision sig- nal. Thus in this section, we proposed an alterna- tive objective that can perform Sobolev training without gradient supervision loss function. The basic idea is to using an integration by parts
stoe
Hy Lodp
lods
Teetre Lork
Cradson Doceett Eorutions
Crucken, Descer Ellerations
Figure 2: Sobolev Implicit Acceleration of Esti- mating function using kernel method and Neural Network. We observed that using Sobolev Norm as loss function can accelerate training.
Vu Vf = // + 2Au f IVf
(6)
which leads to an objective function without the gradient of the target function. In this section, we shall show how this idea is applied to different machine learning examples.
4.1 Predicting Toy Function on Torus
In this section, conduct experiments illustrate the Sobolev implicit acceleration for function regression. Different from the Sobolev training 19). the objective that we are interested in does not involve the gradient of the target function. As a result, we do not need to train a teacher network to provide the gradient supervision information as done in [9]. In the toy example, for simplicity we ignore the boundary terms introduced by the integral by part. Here consider estimating function on the torus, i.e. periodic function. We consider using f A/I f]] + V + 24u f+ |/V f dz
as our objective function. The goal is fit function y = Σi (in using Gaussian Kernel and simple three layer feed-fo feed-forward network with tanh activation function. We randomly sampled 1000 data in 10 dimension as our dataset and run a gradient descent algorithm. Figure presents our convergence result of the validation error, where the Sobolev norm have shown an accelcration effect for training.
4.2 Solving Partial Differential Equations
In this section, we conduct experiments to illus- trate the Sobolev implicit acceleration for solv- ing partial differential equation using PINNs 11 58 in dimensions. The example is a sim- ple Poisson equation (static schrödinger equa- tion) on the torus
Au+u=fin
= [0, 1l
(7)
(a) Smooth Problem
(b) Harder Problem
We first compare the Physies Informed Neural Network [12 and Deep Ritz Method 14 with online random inputs. To enforce
Figure 3: We show the convergence result of PINN and Deep Ritz Method for smooth
problem Ei_ sin (2TTz) and harder problem > sin (4Tx). PINN convergence faster than DRM for online stream input which also matches our theory and the empirical observation [7 The Sobolev Implicit Acceleration will becomes more significant for harder problem as our theory shows.
the periodic boundary conditions, we add penalty term La
(mma)ep.pppua v)
M(x. y, 1))2 + (u(0, a, y) - u(1, x. y +
(u(x, 0, y) - u(z, 1, y))² dxd to match the peri- odic condition of the function value and another
term Li.grad = Ja (Vu(z, y, 0)
(Vu(r,
Vu(z, y, 1))² ( x. v) Vu(1, x,, +
(Vu(z, O, y) Vu(x, 1, y)) dady to match the periodic condition of the function value. We tested PINN and Deep Ritz on both u(z)= D sin(2x;) and u(x) Σí= sin(Ax;). We use the same
8

---

experiment setting as 78 and keep the learning rate constantly to 1e 3 to match our theory. 50000 data points are randomly sampled in every batch. The results are shown in Figure 3 PINN converges faster than DRM consistently in terms of iteration number and the lead seems to become significant for more oscillatory problems.
To solve equation
Z. we consider minimizing the following Sobolev norm objective function
((u) Al ()) + Vv Vu ffll2,
I 5 also considered using Sobolev norms as the loss function. showed that the Sobolev
norms exhibit acceleration effect. However, in setting, cannot have random samples of f.. To avoid information of f appearing in the objective function, we perform an integration by parts that leads to the following objective function
Lirad / |VAm(>> Vu(x)) (f))
|VAu(z)] | + 2Vu()) 2VAu(a) Vf(z)dr
[VAu(>) [v](()) [V/
2VAu(z) + 2Au(z) 2AAu(T) f())d..
We conduct the Sobolev training with the objective function Cpinn + grrrd + A Co + XLs and compare it with PINN and DRM. Following mostly the experiment setting in [78. we 3000 random samples as the dataset and run stochastic gradient descent with batchsize 50. The result presented in Figure I show the Sobolev implicit acceleration, i.e., the gradient dynamic of higher order Sobolev norm convergence faster. We do not scale the Sobolev training to online setting as under large batch size the Sobolev training consume too much memory at this point.
Buletive Error
450
Iteration
(a) Solution by Sobolev Training.
(b) Convergence Speed.
Figure 4: Solving equation in 3 dimension with 3000 fixed samples using Deep Ritz Method 14] Physics-Ifformed Neural Network 12 and Sobolev Training.
Conclusion and Discussion
In this paper, we consider the statistical optimality of gradient descent for solving elliptic inverse problem using general class of objective functions. Although gradient descent using all the objective functions with proper early stopping time, the early stopping iteration strategy for the optimal solution behaves differently instance, we observed that PINN convergences faster than the DRM method. Generally speaking, by using higher order Sobolev norm loss function, one can accelerate training. The reason is that the differential operator can counteract the kernel integral operator, leading to better condition number for optimization. We call this phenomena Sobolev implicil acceleration.
achieve statistical optimality of
function of the sample size. For
Although we have shown the Sobolev implicit acceleration on several simple examples, the A term is hard to compute in high dimensions, scalable Sobolev training without gradient supervision in higher dimension remains as future work. However, we believe that this direction is promising, accelerate the training. It is also interesting to generalize our results beyond GD, for example to mirror descent [90] and accelerated gradient descent
For example, we can use MIM method SS g
19I]. In this paper, we did not consider operators with continuous spectrum and it will be interesting to extend our results using the techniques in 92 Due to technical issue, we have not considered the
batch stochastic gradient descent. will be interesting to characterize the condition under which the stochastic noise in gradient does not degrade the optimal bounds that we obtain. At the same time, we also want to investigate more complex nonlinear inverse problems as XX e considered. also interesting to consider inverse problem arising from integral equation where p 0.

---

References
[1] Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In International Conference on Medical image computing and computer-assisted intervention, pages 234-241. Springer, 2015.
[2] Yuehaw Khoo, Jianfeng Lu, and Lexing Ying. Solving parametric pde problems with artificial neural networks. arXiv preprint
2017.
[3] Vincent Sitzmann, Julien NP Martel, Alexander W Bergman, David B Lindell, and Gordon Wetzstein. Implicit neural representations with periodic activation functions. arXiv preprint arXiv:2006.06661, 2020.
[4] Ernesto De Vito, Lorenzo Rosasco, Andrea Caponnetto, Umberto De Giovannini, Francesca Odone, and Peter Bartlett. Learning from examples as an inverse problem. Journal of Machine Learning Research, 6(5), 2005.
[5] Alexander Tsybakov. Optimal aggregation of classifiers statistical learning. The Annals of Statistics, 32(1) 32(1):135-166, 2004.
[6] Andrew M Stuart. Inverse problems: bayesian perspective. Acta numerica, 19:451-559, 2010.
[7] Martin Benning and Martin Burger. Modern regularization methods for inverse problems. Acta Numerica, 27:1-111, 2018
[8] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-66,, 2007.
[9] Wojeiech Marian Czarnecki, Simon Osindero, Max Jaderberg. Grzegorz Swirszez, and Razvan Pascanu. Sobolev training for neural networks. arXiv preprint arXiv:/706.04859 2017.
[10] WB Richardson Jr. Sobolev gradient preconditioning for maage-processing pdes. Communica- tions Numerical Methods Engineering, 24(6)4493-504, 2008
[1]] Hwijae Son, Jin Woo Jang, Woo Jin Han, and Hyung Hwang. Sobolev training for the neural network solutions of pdes. arXiv preprint arXiv:2101.0825 2021.
[12] Maziar Raissi, Paris Perdikaris, and George E Karniadakis. Physics-informed neural networks: deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. Journal of Computational Physics, 578:686-707, 2019.
[13] Justin Sirignano and Konstantinos Spiliopoulos. Dgm: A deep learning algorithm for solving partial differential equations. Journal of computational physics, 375:1339-1364 2018.
[14] Weinan E and Bing Yu. The deep ritz method: a deep learning- based numerical algorithm for solving variational problems. Communications Mathematics and Statistics, 6(1):1-12, 2018.
[15] Richard Nickl, Sara de Geer, and Sven Wang. Convergence rates for penalized least squares estimators in pde constrained regression problems. SIAM/ASA Journal on Uncertainty Quantification, 8(1):374-413 2020.
[16] Yiping Lu, Haoxuan Chen, Jianfeng Lu, Lexing Ying, and Jose Blanchet. Machine learning for elliptic pdes: Fast rate generalization bound, neural scaling law and minimax optimality. arXiv preprint 1rXiv:2110.006 068977 2021.
[17] Junhong Lin and Lorenzo Rosasco. Optimal rates for multi-pass stochastic gradient methods. The Journal of Machine Learning Research, 18(1):375-3422) 2017.
[18] Loucas Pillaud-Viviin Alessandro Rudi, and Francis Bach. Statistical optimality of stochas- tic gradient descent on hard learning problems through multiple passes. arXiv preprint arXiv: 1805. /0074, 2018.
[19] Junhong Lin, Alessandro Rudi, Lorenzo Rosasco, and Volkan Cevher. Optimal rates for spectral algorithms with least-squares regression over hilbert spaces. Applied and Computational Harmonic Analysis, 48(3):868-88) 2020.
10

---

[20] Ulysse Marteau- Marteau-Ferey, Dmitrii Ostrovskii, Francis Bach, and Alessandro Rudi. Beyond least- squares: Fast rates for regularized empirical risk minimization through self-concordance. In Conference Learning Theory, pages 2294-2340) PMLR, 2019.
[21] Simon Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least- squs-ssuares algorithms. J. Mach. Learn. Res., 21:205 2020.
[22] Zejian Liu and Meng Li. On the estimation of derivatives using plug-in in kır estimators. arXiv preprint arXiv:2006.00 01350, 2020.
[23] Zichao Long, Yiping Lu, Xianzhong Ma, and Bin Dong. Pde-net: Learning pdes from data. In International Conference Machine Learning, pages 3208-3216. PMLR, 2018.
[24] Zichao Long, Yiping Lu, and Bin Dong. Pde-net 2.0: Learning pdes from data with a numeric- symbolic hybrid deep network. Journal of Computational Physics, 399: 108925, 2019.
[25] Jiequn Han, Amuuf Jentzen, and E Weinan. Solving high-dimensional partial differential equations using deep learning. Proceedings of the National Academy of Sciences, 115(34):8505- 8510, 2018.
[26] Jiequn Han. Jianfeng Lu, and Mo Zhou. Solving -ighddimensional eigenvalue problems using deep neural networks: A diffusion monte carlo like approach. Journal of Computational Physics, 423:109792, 2020.
[27] Yaohua Zang, Gang Bao, Xiaojing Ye, and Haomin Zhou. Weak adversarial networks for high-dimensional partial differential equations. Journal of Computational Physics, 411:109409, 2020.
[28] Jianfeng Lu, Yulong Lu, and Min Wang. A priori generalization analysis of the deep ritz method for solving high dimensional elliptic equations. arXiv preprint arXiv:2101.01708, 2021.
[29] Philipp Grohs and Lukas Herrmann. Deep neural network approximation for high- high-dimensional elliptic pdes with boundary conditions. arXiv preprint arXfvv2007.05384, 2020.
[30] Tanya Marwah, Zachary C Lipton, and Andrej Risteski. Parametric complexity bounds for approximating pdes with neural networks. arXiv preprint arXiv:2103.02/38, 2021.
[31] Stephan Wojtowytsch et al. Some observations on partial differential equations in barron and multi-layer spaces. arXiv preprint arXiv:2012.01444, 2020.
[32] Jinchao Xu. The finite neuron method and convergence analysis. 2rXiv:2010.01458, 2020.
arXiv preprint
[33] Yconjong Shin, Zhongqiang Zhang, and George Em Karniadakis. Error estimates of residual minimization using neural networks for linear pdes. arXiv preprint arXiv:2010.08019, 2020.
[34] Genming Bai, Ujjwal Koley, Siddhartha Mishra, and Roberto Molinaro. Physics informed neural networks (pinns) for approximating nonlinear dispersive pdes. arXiv preprint arXiv:2104.05584, 2021.
[35] Tao Luo and Haizhao Yang. Two-layer neural networks for partial differential equations: Optimization and generalization theory. arXiv preprint drXiv:2006.15733 2020.
[36] Chenguang Duan, Yuling Jiao, Yanming Lai, Xiliang Lu, and Zhijian Yang. Convergence rate analysis for deep ritz method. arXiv preprint arXiv:2103. 103.3330, 2021.
[37] Yuling Jiao, Yanming Lai, Dingwei Li, Xiliang Lu, Yang Wang, and Jerry Zhijian Yang. Convergence analysis for the pinns, 2021.
[38] Yuling Jiao, Yanming Lai, Yisu Luo, Yang Wang, and Yunfei Yang. Error analysis of deep ritz methods for elliptic equations. arXiv preprint arXiv:2107. 14478, 2021.
[39] Jan-Christian Hütter and Philippe Rigollet. Minimax rates of estimation for smooth optimal transport maps. arXiv preprint arXiv:1905.05822 2019.

---

[40] Tudor Manole, Sivaraman Balakrishnan, Jonathan Niles Weed, and Larry Wasserman. Plugin estimation of smooth optimal transport maps. arXiv preprint arXiv:2107.12364. 2021.
[41] Richard Nickl and Sven Wang. On polynomial -time computation of high-dimensional posterior measures by langevin-type algorithms. arXiv preprini urXiv:2009.05298, 2020.
[42] Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent learning. Constructive Approximation, 26(2):289-315, 2007.
[43] Alnur Ali, J Zico Kolter, and Ryan Tibshirani. A continuous-tinn time view of carly stopping for least squares regression. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1370-1378. PMLR, 2019.
[44] Alnur Ali, Edgar Dobriban, and Ryan Tibshirani. The implicit regularization of stochastic gradient flow for least squares. In International Conference Machine Learning, pages 233-244 PMLR, 2020.
[45] Yuri S Fonseca and Yuri F Saporito. Statistical learning and inverse problems: An stochastic gradient approach. arXiv preprint arXiv:2209. 14967,, 2022.
[46] Steve Smale and Ding-Xuan Zhou. Learning theory estimates via integral operators and their approximations. Constructive approximation, 26(2):153-172, 2007.
[47] Lorenzo Rosasco, Mikhail Belkin, and Ernesto De Vito. On learning with integral operators. Journal of Machine Learning Research, 11(2), 2010.
[48] Shahar Mendelson and Joseph Neeman. Regularization in kemell learning. The Annals of Statistics, 38(1):526- 565, 2010.
[49] Aymeric Dieuleveut and Francis Bach. Nonparametric stochastic approximation with large step-sizes. The Annals of Statistics, 44(4):1363 1399, 2016.
[50] Boris T Polyak and Anatoli Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, 30(4))838-88) 855, 1992.
[51] Yuting Wei, Fanny Yang. and Martin J Wainwright. Early stopping for kernel boosting al- gorithms: A general analysis with localized complexities. arXiv preprint arXiv: 100:::7070011 543,, 2017.
[52] Yunwen Lei, Ting Hu, and Ke Tang. Generalization performance of multi-pass stochastic gradient descent with convex loss functions. J. Mach. Learn. Res., 22:25-1, 2021..
[53] Amit Daniely. Sgd learns the conjugate kernel class of the network. arXiv preprint 17Xiv:170..08003, 2017.
[54] Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprint arXiv:/711.00163 2017.
[55] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemnl:: Convergence and generalization in neural networks. arXiv preprint 1 2018.
[56] Atsushi Nitanda and Taiji Suzuki. Optimal rates for averaged stochastic gradient descent under neural tangent kernel regime. arXiv preprint arXiv:2006. 12297, 2020.
[57] Tianyang Hu, Wenjia Wang, Cong Lin, and Guang Cheng. Regularization matters: A non- parametric perspective on overparametrized neural network. arXiv preprint arXiv:2007.02486, 2020.
[58] Jeremy Yu, Lu Lu, Xuhui Meng, and George Em Karniadakis. Gradient-enhanced physics-informed neural networks for forward and inverse pde problems. arXiv preprint arXiv:2111.02801, 2021.
[59] Ingo Steinwart, Don Hush, Clint Scovel, et Optimal rates for regularized least squares regression. In COLT, pages 79-93, 2009.
12

---

[60] Lee H Dicker, Dean P Foster, and Daniel Hsu. Kernel ridge vs. principal component regression: Minimax bounds and the qualification of regularization operators. Electronic Journal of Statistics, 11())10022-1047, 2017.
[61] Vivien Cabannes, Loucas Pillaud-Viviin Francis Bach, and Alessandro Rudi. Overcoming the curse of dimensionality with laplacian regularization in semi-supervised learning. Thirty-Fifth Conference Neural Information Processing Systems, 2021.
[62] Maarten V de Hoop, Nikola B Kovachki, Nicholas H Nelsen, and Andrew M Stuart. Conver- gence rates for learning linear operators from noisy data. arXiv preprint arXiv:2108. 2021.
[63] Gilles Blanchard and Nicole Mücke. Optimal rates for regularization of statistical inverse learning problems. Foundations of Computational Mathematics, 18(4))971-1013, 2018.
[64] Meyer Scetbon and Zaid Harchaoui. A spectral analysis of dot-product kernels. In International Conference Artificial Intelligence and Statistics, pages 3394-3402 PMIR, 2021.
[65] Alberto Bietti and Francis Bach. Deep equals shallow for relu networks in kernel regimes. arXiv preprint arXiv:2009. 14397, 2020.
[66] Lin Chen and Sheng Xu. Deep neural tangent kernel and laplace kernel have the same rkhs. arXiv preprint arXiv:2009.10683, 2020.
[67] Xueyuan Zhou and Mikhail Belkin. Semi-supervised learning by higher order regularization. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 892 2000 JMLR Workshop and Conference Proceedings, 2011.
[68] Gregory E Fasshauer and Qi Ye. Reproducing kernels of generalized sobolev spaces via a green function approach with distributional operators. Numerische Mathematik, 1 11966))585-611 2011.
[69] Ingo Steinwart and Clint Scovel. Mercer's theorem on general domains: On the interaction between measures, kernels, and rkhss. Constructive Approximation, 35(3):363-417, 2012.
[70] Lei Shi, Xin Guo, and Ping-Xuan Zhou, Hermite learning with gradient data. Journal of computational and applied mathematics, 233(11):3046-3059 2010.
[71] Yunan Yang, Jingwei Hu, and Yifei Lou. Implicit regularization effects of the sobolev norms in image processing. arXiv preprint (tt.::2000000555. 2021.
[72] Jeff Calder, A Mansouri, and Anthony Yezzi. Image sharpening via sobolev gradient flows. SIAM Journal on Imaging Sciences, 3(4):981-1014, 2010.
[73] Chris Yu, Henrik Schumacher, and Keenan Crane. Repulsive curves. ACM Transactions on Graphics (TOG), 40(2):1-21, 2021.
[74] Chris Yu, Caleb Brakensiek, Henrik Schumacher, and Keenan Crane. Repulsive surfaces. arXiv preprint 1101v22107.01164, 2021.
[75] Yousuf Soliman, Albert Chern, Olga Diamanti, Felix Knöppel, Ulrich Pinkall, and Peter Schröder. Constrained willmore surfaces. ACM Transactions on Graphics (TOG), 40(4):1-17, 2021.
[76] Yifan Chen, Bamdad Hosseini, Houman Owhadi, and Andrew M Stuart. Solving and learning nonlinear pdes with gaussian processes. arXiv preprint arXiv:2103. 2021.
[77] George Stepaniants. Learning partial differential equations in reproducing kernel hilbert spaces. arXiv preprint arXiv:2108. 17580, 2021.
[78] Jingrun Chen, Rui Du, and Keke Wu. A comprehensive study of boundary conditions when solving pdes by dnns. arXiv preprint arXiv:2005.045 04554, 2020.
[79] Lo Gerfo, Lorenzo Rosasco, Francesca Odone, E De Vito, and Alessandro Verri. Spectral algorithms for supervised learning. Neural Computation, 1877)1873-1187,, 2088,
13

---

[80] Tomoya Murata and Taiji Suzuki. Gradient descent in rkhs with importance labeling. In International Conference on Artificial Intelligence and Statistics, pages 1981-1989, PMLR. 2021.
[81] Michael L Stein. Interpolation of spatial data: some theory for kriging. Springer Science & Business Media, 1999.
[82] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in Neural Information Processing Systems, 12:10666-10846, 2019.
[83] Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. In International Conference on Machine Learning, pages 5301-5310. PMLR, 2019.
[84] Zhi-Qin John Xu, Yaoyu Zhang. Tao Luo,, Yanyang Xiao, and Zheng Ma. Frequency principle: Fourier analysis sheds light on deep neural networks. arXiv preprint arXiv: 190100633,. 2019.
[85] Dimitris Kalimeris, Gal Kaplun, Preetum Nakkiran, Benjamin Edelman, Tristan Yang, Boaz Barak, and Haofeng Zhang. Sgd neural networks learns functions of increasing complexity. Advances in Neural Information Processing Systems, 32:3496-3506, 2019.
[86] Shun-ichi Amari, Jimmy Ba, Roger Grosse, Xuechen Li, Atsushi Nitanda, Taiji Suzuki, Denny Wu, and Ji Xu. When does preconditioning help or hurt generalization? arXiv preprint arXiv:2006. 10732, 2020.
[87] Nicole Mücke and Enrico Reiss. Stochastic gradient descent in hilbert scales: Smoothness, preconditioning and earlier stopping. arXiv preprint arXiv:2006. 10840, 2020.
[88] Liyao Lyu, Zhen Zhang, Minxin Chen, and Jingrun Chen. Mim: A deep mixed residual method for solving high-order partial differential equations. arXiv preprint w0Xiv22006004146 2020.
[89] Quanhui Zhu and Jiang Yang. A local deep learning method for solving high order partial differential equations. arXiv preprint XXiv:2/0330091/ 2021.
[90] Tomas Vaškevičius, Varun Kanade, and Patrick Rebeschini. The statistical complexity of early-stopped mirror descent. arXiv preprint arXi::2002.00189, 2020.
[91] Nicolò Pagliana and Lorenzo Rosasco. Implicit regularization of accelerated methods in hilbert spaces. arXiv preprint 19Xiv:1905.130000 2019.
[92] Matthew Colbrook, Andrew Horning, and Alex Townsend. Computing spectral measures of self-adjoint operators. SIAM Review, 63(3):889-524 2021.
[93] Kweku Abraham and Richard Nickl. On statistical calder) 'on problems. arXiv preprint /906v 03486, 2019.
[94] François Monard, Richard Nickl, and Gabriel P Paternain. Consistent inversion of noisy non- abelian x-ray transforms. Communications on Pure and Applied Mathematics, 1045-1994, 2021.
[95] Robert A Adams and John JF Fournier. Sobolev spaces. Elsevier, 2003.
[96] losif F Pinelis and Aleksandr Ivanovich Sakhanenko. Remarks on inequalities for the probabili- ties of large deviations. Teoriya Veroyatnostei i ee Primeneniya, 30(1)1127-131, 1985.
[97] Alexandre B Tsybakov. Introduction nonparametric estimation. Springer Science & Business Media, 2008
14

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A]- You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets?
[Yes] See Section ??.
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
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? [N/A]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof's of all theoretical results? [Yes]
3. If you 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.? [TODO]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(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)? [Yes]
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'le 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing 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]
15


Reviews:
[{"review_id": "lda4H4t7E_z", "reviewer": "Reviewer_GamV", "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.\n\nThe 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.\n", "questions": "1. In equation (2), should you remove the $-$ sign to be consistent with the rest of the paper?\n\n2. In line 97, for $\\mathcal{A} = \\Delta$, $\\mathcal{A}$ is not invertible. Should the usage of $\\mathcal{A}^{-1}$ be clarified here?\n\n3. Lines 91-92 and line 97: f and u seem to be interchanged, causing some confusion.\n\n4. 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?\n\n5. Can you please write out the gradient step for DRM and PINN separately in elementary terms, perhaps in the supplement?\n", "limitations": "None.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe 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.\n\n\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jRFbCiKkrbR", "reviewer": "Reviewer_bLL7", "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. ", "questions": "Please see the questions in the above section.", "limitations": "I do not see any negative societal impact.\n\nI 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.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThis 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.\n\nWeakness:\n\n1. 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.\n2. 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.\n3. What is the meaning of $\\mathcal{L}^{\\beta/2}$ given that $\\mathcal{L}$ is defined in line 111.\n4. 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?\n5. 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?\n6. 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.\n7. 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.\n8. The accuracy of in Figure 4(b) seems too low to prove that the solution to the PDE is actually recovered.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "iLfJqJQIZh0", "reviewer": "Reviewer_nVgp", "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.", "questions": "Despite the weakness mentioned above, I have the following two questions:\n1. 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.\n2. 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:\n\nLine 100: $e_j\\rightarrow e_i $\n\nLine 106: $k\\rightarrow K$, $K_x\\rightarrow K_z$\n\nLine 117: $k\\rightarrow K$ Line 120: $\\sigma\\rightarrow \\Sigma$\n\nLine 195-197: All $u$ in the inner product should be $theta$ or all $\\theta$ in the inner product should be $u$\n\nThe first case in Theorem 3.2: it should be $\\beta<...$\n\nLine 661-663: do we need the transpose symbol $\\top$ here?\n\nLine 671: I guess the $\\hat{q}_ {\\lambda}$  here is the same as the $\\hat{g}_{\\lambda}$ in Line 718?\n\nLine 712: $\\Sigma_{Id, A_1}$ is not defined.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. 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.\n2. The presentation of this paper is clear and the experiments are detailed.\n\nWeakness:\n1. 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.\n2. There are some typos and mismatches of symbols (part of them listed in \"limitations\"). This paper will benefit from checking the mathematical presentations throughout.\n\nOverall, I am in a positive position for this paper. The paper can be further improved by taking the above suggestions.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hbQIlByEMW", "reviewer": "Reviewer_Ffzb", "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.", "questions": "Please see weaknesses.", "limitations": "The authors have discussed about the limitations.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BcKYt81WgKo", "reviewer": "Reviewer_p5b2", "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. \n", "questions": "1. The authors motivate their study by the example of neural tangent kernel. I wondered their assumptions hold for neural tangent kernels. \n2. 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? \n3. What is the difference between the modified gradient descent in this paper, and gradient descent on kernel regression? \n4. Is there a representer theorem for the modified kernel regression? Would you explain more about its connections with the early stopping? ", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n1. The paper establishes a theoretically sound contribution on min-max lower bound for a generalization of kernel regression.\n2. The paper is very well written \n3.  Assumptions are stated clearly and motivated by examples. \n4. It is interesting to establish the optimality of gradient descent for solving PDEs with kernels. \n\n\n**Weaknesses**\n1.  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. \n2. It would be interesting to experimentally compare the performance of gradient descent with its modified variant considered in this paper. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept