Machine Learning For Elliptic PDEs: Fast Rate Generalization Bound, Neural Scaling Law and Minimax Optimality
Authors: Yiping Lu
Haoxuan Chen
Jianfeng Lu
Lexing Ying
Jose Blanchet
Venue: ICLR 2022 Poster (2022)
Keywords: Numerical PDE
non-parametric statistics
computational physics

Abstract: In this paper, we study the statistical limits of deep learning techniques for solving elliptic partial differential equations (PDEs) from random samples using the Deep Ritz Method (DRM) and Physics-Informed Neural Networks (PINNs). To simplify the problem, we focus on a prototype elliptic PDE: the Schr\"odinger equation on a hypercube with zero Dirichlet boundary condition, which has wide application in the quantum-mechanical systems. We establish upper and lower bounds for both methods, which improves upon concurrently developed upper bounds for this problem via a fast rate generalization bound. We discover that the current Deep Ritz Methods is sub-optimal and propose a modified version of it. We also prove that PINN and the modified version of DRM can achieve minimax optimal bounds over Sobolev spaces. Empirically, following recent work which has shown that the deep model accuracy will improve with growing training sets according to a power law, we supply computational experiments to show a similar behavior of dimension dependent power law for deep PDE solvers.

Published as a conference paper at ICLR 2022
MACHINE LEARNING FOR ELLIPTIC PDES: FAST RATE GENERALIZATION BOUND, NEURAL SCAL- ING LAW AND MINIMAX OPTIMALITY
Yiping Lu
Haoxuan Chen
Institute for Computational Mathematical Engincering Stanford University Stanford, CA 94305, USA yplu@stanford.edd
Department of Computing and Mathematical Sciences,
Caltech
Pasadena, CA 91125, USA haoxuan@caltechh .dd
Jianfeng Lu
Lexing Ying
Mathematics Department Duke University Durham, NC. 27708-0300
Department of Mathematics Stanford University Stanford, CA 94305, USA
jjanfenggemth..uuee.co
Texinggesannford.o
Jose Blanchet
Department of Management Science & Engineering
Stanford University Stanford, CA 94305, USA
ABSTRACT
In this paper, study the statistical limits of deep learning techniques for solving elliptic partial differential equations (PDEs) from random samples using the Deep Ritz Method (DRM) and Physics-Informet Neural Networks (PINNs). To simplify the problem, we focus on a prototype elliptic PDE: the Schrödinger equation on a hypercube with zero Dirichlet boundary condition, which is applied in quantum- mechanical systems. We establish upper and lower bounds for both methods, which improve upon concurrently developed upper bounds for this problem via a fast rate generalization bound. We discover that the current Deep Ritz Method is sub-optimal and propose a modified version of it. We also prove that PINN and the modified version of DRM can achieve minimax optimal bounds over Sobolev spaces. Empirically, following recent work which has shown that the deep model accuracy will improve with growing training sets according to power law, we supply computational experiments to show similar-bchavior dimension dependent power law for deep PDE solvers.
INTRODUCTION
Partial differential equations (PDEs) play prominent role in many disciplines of science and engi- neering. The recent deep learning breakthrough and the rapid development of sensors, computational power, and data storage in the past decade has drawn attention to numerically solving PDEs via machine learning methods (Long et al., 2018; 2019; Raissi et al., 2019; Han et al., 2018; Sirignano & Spiliopoulos, 2018; Khoo et al., 2017), especially in high dimensions where conventional methods become impractical. The set of applications that motivate this interest is wide-ranging, including computational physics (Han et al., 2018; Long et al., 2018; Raissi et al., 2019), inverse problem (Zhang et al., 2018; Gilton et al., 2019; Fan & Ying, 2020) and quantitative finance (Heaton et al., 2017; Germain et al., 2021). The numerical methods generated by the use of deep learning techniques mesh-less methods, see the discussion in (Xu, 2020). A natural deep learning technique in the

---

Published as a conference paper at ICLR 2022
problems that are based on standard feed-forward type of architecture takes advantage (when available) of a variational formulation, whose solution coincides with the solution of the PDE of interest. Despite the success and popularity of adopting neural networks for solving high-dimensional PDEs, the following question still remains poorly answered.
For a given PDE and data-driven approximation architecture, how large the sample size and how complex the model are needed to reach a prescribed performance level?
In this paper, we aim to establish the numerical analysis of such deep learning based PDE solvers. Inspired by recent works which showed that the empirical performance of a model is remarkably predictable via power law of the data number, known as the neural scaling law (Kaplan et al., 2020; Hestness et al., 2017; Sharma & Kaplan, 2020), we aim to explore the neural scaling law for deep PDE solvers and compare its performance to Fourier approximation.
Among the various approaches of using deep learning methods for solving PDEs, in this work, we focus on the Deep Ritz method (DRM) (E & Yu, 2018; Khoo al., 2017) and the Physics-Informed Neural Networks (PINN) approach (Sirignano & Spiliopoulos, 2018; Raissi et al., 2019), both of which are based on minimizing neural network parameters according some loss functional related to the PDEs. To provide theoretical guarantees for DRM and PINN, following (Lu et al., 202 lb;
Duan et al., 2021; Bai et al., 2021), we decompose the error into approximation error (Yarotsky, 2017;
Suzuki, 2018; Shen et al., 2021) and generalization error (Bartlett et al., 2005; Xu & Zeevi, 2020; Farrell et al., 2021: Schmidt- Schmidt-Hieber et al., 2020; Suzuki, 2018). However, instead of the ((1/ Vn) (n is the number of data sampled) slow rate generalization bounds established in prior work (Lu et al., 2021b; Shen et al., 2021; Xu, 2020; Shin al., 2020), we utilize the strongly convex structure of the DRM and PINN objectives and provide an O(1/n) fast rate generalization bound (Bartlett et al., 2005; Xu & Zeevi, 2020) that leads us to a non-parametric estimation bound. Our theory also suggests optimal selection of network size with respect the number of sampled data. Moreover, to illustrate the optimality of our upper bound, we also establish an information information-theoreiic theoretic lower bound which matches our upper bound for PINN and modified version of DRM.
We also test our theory by numerical experiments. Recent works (Hestness et al., 2017; Kaplan et al., 2020; Rosenfeld et al., 2019; Mikami et al., 2021) studying variety of deep learning algorithms all find the same polynomial scaling relation between the testing error and the number of data. As the number of training data n increases. the population loss L of well-trained and well-tuned models scales with n as power-law L x 1 for some a. (Sharma & Kaplan, 2020) also scans over large n
range of and problem dimension d and finds approximately x 1 scaling law. In Section 4, we conduct numerical experiments to show that this phenomenon still appears for deep PDE solvers and this neural scaling law tests more idiosyncratic features of the theory.
1.1 RELATED WORKS
Neural Scaling Law The starting point of our work is the recent observation across speech, vision and text (Hestness et al., 2017: Kaplan et al., 2020; Rosenfeld et al., 2019; Rosenfeld, 2021) that the empirical performance of a model satisfies power law scales as a power-law with model size and dataset size. (Sharma & Kaplan, 2020) further finds out that the power of the scaling law depends on the intrinsic dimension of the dataset. Theoretical works (Schmidt-Hicber et al., 2020; Suzuki, 2018; Suzuki & Nitanda, 2019; Chen et al., 2019b; Imaizumi & Fukumizu, 2020; Farrell al., 2021; Jiao et al., 2021c) explore the optimal power law under the non non-parametric curve estimation setting via plug-in neural network. Our work extends this line of research to solving PDEs.
Deep Network Based PDE Solver. Solving high dimensional partial differential equations (PDEs) has been a long-standing challenge due to the curse of dimensionality. At the same time, deep learning has shown superior flexibility and adaptivity in approximating high dimensional functions, which leads to state-of-the-art performances a wide range of tasks ranging from computer vision to natural language processing. Recent years, pioneer works (Han et al., 2018; Raissi et al., 2019; Long et al., 2018; Sirignano & Spiliopoulos, 2018; Khoo et al., 2017) try to utilize the deep neural networks to solve different types of PDEs and achieve impressive results in many tasks (Lu et al., 2021a; Li et al., 2020). Based on the natural idea of representing solutions of PDEs by (deep) neural networks, different loss functions for solving PDEs are proposed. (Han et al., 2018; 2020) utilize the
2

---

Published as a conference paper at ICLR 2022
Feynman-Kan formulation which turns solving PDE to a stochastic control problem and the weak adversarial network (Zang et al., 2020) solves the weak formulations of PDEs via an adversarial network. In this paper, focus the convergence rate of the Deep Ritz Method (DRM) (E & Yu, 2018; Khoo et al., 2017) and Physics-Informne
neural network (PINN) (Raissi et al., 2019; Sirignano & Spiliopoulos, 2018). DRM (E & Yu, 2018; 8; Khoo et al., 2017) 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 (Raissi et al., 2019; Sirignano Spiliopoulos, 2018) trains neural network directly to minimize the residual of the PDE, i.e., using the strong form of the PDE.
Theoretical Guarantees For Machine Learning Based PDE Solvers. Theoretical convergence results for deep learning based PDE solvers raises wide interest recently. Specifically, (Lu et al., 2021b; Grohs & Herrmann, 2020; Marwah et al., 2021; Wojtowytsch et al., 2020; Xu, 2020; Shin al., 2020; Bai et al., 2021) investigate the regularity of PDEs approximated by neural network and (Lu et al., 202 lb; Luo & Yang, 2020) further provide a generalization analysis. (Nickl et al., 2020) introduces a prior over the solution of the PDE and considers an equivalent white noise model (Brown & Low, 1996). (Nickl et al., 2020) provides the rate of convergence of the posterior. Our paper does not need to introduce the prior on the target function and provides finite number of data. At the same time, (Nickl et al., 2020) can only be applied to linear PDEs while our proof technique can be extended to nonlinear ones. All these papers also fail to answer the question that how to determine the network size corresponding to the sampled data number to achieve desired statistical convergence rate. (Hütter & Rigollet, 2019; Manole et al., 2021) consider the similar problem for the optimal transport problem, i.e. Monge-ampere equation. Nevertheless, the variational problem we considered is different from (Hütter & Rigollet, 2019; Manole et al., 2021) and leads technical difference. The most related works ours are two concurrent papers (Duan et al., 2021; Jiao et al., 2021a;b). However, our upper bound is faster than (Duan et al., 2021; Jiao al., 20211;2)) la:b). In this paper, we also show that generalization analysis in (Lu al., 2021b; Duan et al., 2021; Luo & Yang, 2020) are loose due to the lack of a localization technique (De Boor & De Boor, 1978; Bartlett et al., 2005; Koltchinskii, 2011: I; Xu, 2020). With observation of the strong convexity of the loss function, we follow the fast rate results for ERM (Schmidt- -ieteer et al., 2020; Xu Zeevi, 2020; Farrell et al., 2021) and provide near optimal bound for both DRM and PINN.
-symmtotiiiic guarantee for
1.2 CONTRIBUTION
In short, we summarize our contribution as follows
In this paper, we first considered the statistical limit of learning a PDE solution from sampled observations. The lower bound shows a non-standard exponent different from non- parameemet estimation of a function.
Instead of the O(I/Vn) slow rate generalization bounds in (Lu et al., 2021b; Duan et al., 2021; Jiao et al., 2021a;c), we utilized the strongly convex nature of the variational form and provided a fast rate generalization bound via the localization methods (Van De Geer, 1987; Bartlett We discovered that the current Deep Ritz Methods sub-optimal and propose a modified version of it. We showed that PINN and the modified version of DRM can achieve nearly min-max optimal convergence rate. Our result is listed in Table
al., 2005; Koltchinskii, 2011; Srebro et al., 2010; Xu & Zeevi, 2020),
We tested the recently discovered neural scaling law (Hestness et al., 2017; Kaplan et al., 2020; Rosenfeld et al., 2019; Hashimoto, 2021) for deep PDE solvers numerically. The empirical results verified our theory.
SET-UP
We consider the static Schrödinger equation with zero Dirichlet boundary condition on the domain Ω, which we assume to be the unit hypercube in Rd. In order to precisely introduce the problem, recall some standard notions. We consider our domain as Ω = 1] and use L (S2) to denote the space of square integrable functions Ω with respect to the Lebesgue measure. We let T (Ω) be
3

---

Published as a conference paper at ICLR 2022
Upper Bounds
Lower Bound
Objective Function
Neural Network
Previous Bound
Fourier Basis
2x-2 6920-2
a log n (Duan et al., 2021)
Deep Ritz
71
log 72
n
2+2a-2
n
Modified Deep Ritz
#F26-7
log
/
71
2--4 log n (Jiao al., 2021a)
PINN
log
71
6444-88
2422-1
Table I:
Upper bounds and lower bounds we achieve in this paper and previous work. The upper bound colored in red indicates that the convergence rate matches the min-max lower bound.
the space of essentially bounded (with respect to the Lebesgue measure) functions on Q and C(a2) denotes the space of continuous functions on An.
Let f E (S2), V E L (St), and, E L (S2). Our focus is on the analysis of Seep-Learning-basee numerical methods to solve the elliptic PDE:
- Au + Vu f in Ω
(2.1)
== g on an.
2.1 Loss FUNCTIONS FOR SOLVING PDES AND INDUCED EVALUATION METRIC
In this paper, mainly focus analyzing Deep Ritz Methods (DRM) and Network (PINN). this subsection, we first introduce the objective function and algorithm of the two methods.
Neural
Deep Ritz Methods (E & Yu, 2018; Sirignano & Spiliopoulos, 2018) Recall that the equation 2.1 equivalent following variational form
/ Vuu 2 + Vlul? dx - -f fudx,
arg min DRM (u) == arg min ( 2 J2
(2.2)
(2)
where u is minimized over H. (S) with boundary condition given by on On.
This variational form provides the basis for the DRM type method for solving the static Schrödinger equation based on neural network ansatz. More specifically, the energy functional given in equa- tion 2.2 is viewed as the population risk function to train an optimal estimator approximation of the solution to the PDE within a parameterized hypothesis function class F C H. (S2). In this paper, also rely on the strong convexity the DRM objective with respect to the H² norm.
Proposition 2.1. For DRM, we further assume 0 < Vmin S V(x)= S Vmax. then we have
2
(D) EDDM(w") < Ilu-u"
2
(EDRM (u) EDM
max (1, VInax]
max (1, V Vinin
holds for all u E (2)
Physics-Informed Neural Network (Raissi et al.. 2019; Sirignano Spiliopoulos, 2018). PINN solves 2.1 via minimizing the following objective function
/ [uu(z) ((x)u(z) + f(z)
arg min E PINN (u) = arg min (9)
H
The objective function PINN can also be viewed as the population risk function and we can train an optimal estimator approximation of the solution the PDE within parameterized hypothesis function class F C Hg (2). In this paper, we also rely on the strong convexity of the PINN objective with respect to the 272 norm, for which need some additional assumptions the potential.
4

---

elements of the matrix) and of the elements). Published as a conference paper at ICLR 2022
Proposition 2.2. For PINN, we further assume V E (9) with 0 < Ciia <V² - AV,O Cmin < ((x)= & Vmax and -V(()) S Vmax then we have for all u E (9)
EPINN (u) EPINN (u*) 1 1|u u ul
2 2(1 + Viax + V2
maxx
2
EPINN (u) EEPNN("")) (u")
max 11 Cmin))
2.2 ESTIMATOR SETTING
Empirical Loss Minimization In order to access the d-dimensional integrals, DRM (E & Yu, 2018; Khoo et al., 2017) and PINN (Raissi et al., 2019; Sirignano & Spiliopoulos, 2018) employ a Monte-Carlo method for computing the high dimensional integrals, which leads to the so-called empirical risk minimization training for neural networks. To define the empirical loss, let (X,)²= an i.i.d. sequence of random variables distributed according to the uniform distribution Pn in domain Q. We also have access to noisy observations f, = f(,)) + & (1 S j S n) of the right hand side of the PDE (2.1), where & are i.i.d. bounded random variables with zero mean and independent of X5. Define the empirical losses E,, by setting
;=1 be
EDRM (u) = 1 Σ
[.0]
(IIV(X)))+++ + 1 V( f (,((,)))
(2.3)
n2 j=1
E
(u)
1
[22| (ell-(Auu -Ax(X))-V())dl
(2.4)
where [S2] represents the Lebesgue measure of the domain.
Once given an empirical loss E,, we apply the empirical loss minimization to seek the estimation uny Le. Un arg min Fe E,, (u), where F is the parametrized hypothesis function space consider. Some examples can be reproducing kernel Hilbert space (Chen et al., 2021b) and tensor training format (Richter et al., 2021: Chen et al., 2021a). In this paper, consider sparse neural network and truncated Fourier basis, which can achieve min-max optimal estimation rate for the non-parametric function estimation (Tsybakov, 2008; Schmidt-Hieber et al., 2020; Farrell al., 2021; Suzuki, 2018; Chen et al., 2019b; Jiao et al., 2021c; Nitanda & Suzuki, 2020).
Sparse Neural Network Function Space In this paper, the hypothesis function space F is ex- pressed by the neural network function space following Hieherr et al., 2020; Suzuki, 2018; Farrell et al., 2021). Let us denote the ReLU3 activation by (a(x)) = max 0} (x E RR,, which is used in (E & Yu, 2018). For a vector 7(x)) is operated in element-wise manner. Define the space of all neural networks with height L, width W, sparsity constraint S and norm constraint B as
(L, W) ((V(") (1(+) + (()) ..... (MD(2) + +6(9) (w + 6())
WiLL) E Rxw ,b4)) E IR, w() E Wxd ((a) E R wit E ww ,000 E ERW (1 <<<<<> L),
Σ E(m lbb) S S, max ( lo, v |l I B):
(2.5)
where denotes the function composition, || llo is the no-norm of the matrix (the number of non-zero 0000,,0 is the lo----onn -norm of the matrix (maximum of the absolute values
||
Truncated Fourier Basis Estimator We also consider the Truncated Fourier basis our esti- mator. Denote the domain we are interested in by Ω C [0, 1jd. For any 2 E Nd, we consider the corresponding Fourier basis function (z(x) = 2 (x E I). Any function ʃ E L2( can be represented as weighted sum of the Fourier basis f(x) == Exere (x)= where fa := Sn
(x)) (V V== E No) is the Fourier coefficient. This inspires us to use the Fourier basis whose index lies in a truncated set Z = {2 E 2|| I } to represent the function class F as F =EEne 1E Iellss Se a202/a= R. ||=|| < g
5

---

Published as a conference paper at ICLR 2022
3 LOWER BOUND
In this section, we aim to consider the statistical limit of learning the solution of a PDE. As discussed in Propositions 2.1 and 2.2, we directly consider the H norm for DRM and 2 norm for PINN as the evaluation metric. The lower bounds are shown as follows.
Theorem 3.1 (Lower bound). We denote u u²()) to be the solution of the PDE 2.1 and we can access randomly sampled data ftJ=i..... n as described in Section 2.2. We further assume u' (f) E H" for a given 8 E Zt Then we have the following lower bounds.
DRM Lower Bound.
For all estimators 3 (R.1) @n x R (I2),, we have
(l - ui (f)lm 2 24-2
inf V (S)
sup
(3.1)
PINN Lower Bound.
For all estimators vb: (IR))on x IR
on
H (H2),, we have
inf sup (S)
(1X, - a' (f 2 n 442--4,
2a-4
(3.2)
is the minimax rate estimating the k-th derivative of a 3-smooth density in L (Liu & Wang, 2012: Prakasa Rao, 1996; Müller & Gasser, 1979), the lower bound obtained here is the rate of estimating the right hand side function f in terms of the H -1 norm. Given the H norm error estimate on f. we achieve estimate of which provides an alternative way understand our upper bound. (See discussion in Appendix E.) The lower bound is non-standard, for the 2s in the numerator is different from the 2s 4 in the denominator.
Given that n 2(8-k)
4 UPPER BOUND
To theoretically understand the empirical success of Physics-Informed Neural Networks and the Deep Ritz solver, in this section, aim to prove that the excess risk A,, E(u,,) E(u") of well-trained neural networks on the PINN/DRM loss function will follow precise power-law scaling relations with the size of the training dataset. Similar to (Xu, 2020; Lu al., 2021b; Duan al., 2021; Jiao et al., 202 2021a;b), we decompose the excess risk into approximation error and generalization error. Different from the concurrent bound (Duan al., 2021: Jiao et al., 2021a), we provide a fast rate O(1/n) by utilizing the strong convexity of the objective function established in Section 2.1 and achieve faster and near optimal upper bound. We show that the generalization error can be bounded by the fixed point (i.e. the solution of ((r) r) of the local Rademacher complexity
()()) R,, ((I(() 1 u 12 < r)),
where R2 is the Rademacher complexity, I(u) = Au Vu, IlA || 1| for PINN and I(u)= = V/l 1 Vu, |I-1|A = ||- e| for DRM. We put detailed definition and analysis in Appendix B.4. We first provide meta theorem to decompose the error into approximation and a fast rate generalization етror. Then we plug in the approximation and generalization error calculated in Appendix B.3 and Appendix B.2 and finally achieve the following upper bounds. We also put more detailed proof sketch in Appendix A.2.
Physies Informed Neural Network.
Theorem 4.1. (Informal Upper Bound of PINN with Deep Neural Network Estimator) With proper assumptions, consider the sparse Deep Neural Network function space ΦLL,, W, S, B) with pa-
rameters L = 0(1), W = O x)) ). S = O(n 4), B = O 3), then the Physics Informed estimator uPIN m EPINN( (u) satisfies the following upper bound with high probability
DNN UPINN
2x-4 u 11222 Sn - d+2a-4 logn.
Theorem 4.2. (Informal Upper Bound of PINN with Truncated Fourier Series Estimator) With proper assumptions, consider the Physics Informed Neural Network objective with plug-in Fourier Series estimator ū uPNN min (1)) PPINN (u) with O(n 04paa ), then with high probability we have
Fourter PINN
11 H2 S 1

---

Published as a conference paper at ICLR 2022
Deep Ritz Methods.
Theorem 4.3. (Informal Upper Bound of DRM with Deep Neural Network Estimator) With proper as- sumptions, consider the sparse Deep Neural Network function space (L W, S, B) with parameters
== 0(1,, W = =O S O ) ) B = On ( then the Deep ritz estimator
DNY (.W.E. E EDRM (u) satisfies the following upper bound with high probability
-i2.'s log
DRM
Theorem 4.4. (Informal Upper Bound of DRM with Truncated Fourier Series Estimator) With proper assumptions, consider the Deep Ritz objective with a plug in Fourier Series estimator DRM m EDRM (u) with ç
Fourier
O(n a+ ) then with high probability we have
Fourier
- HI S 1 0
DRM
Remark.
There a common belief that Machine learning based PDE solvers can break the curse of dimensionality (E & Yu, 2018; Grohs et al., 2018; Lanthaler et al., 2021). However, we obtained an n ž
convergence rate, which can become super slow in high dimension. Our analysis showed that it is essential to constrain the function space break the curse of dimensionality. (Lu et al., 2021b) considered the DRM in Barron spaces. (Ongie et al., 2019) showed that functions in the Barron space enjoy a smoothness at the same magnitude as d which will also lead to convergence rate independent of the dimension using our upper bound. Neural network Du, 2019; Suzuki, 2018) and functions on manifold (Nitanda & Suzuki, 2020; Chen et al., 2019b) without curse of dimensionality. Combined with these approximation bounds, can also achieve a bound that breaks the curse of dimensionality using Theorem B. 12 and B.9. In this paper, we aim consider the statistical power the loss function in common function spaces and leave the curse of dimensionality as separate topic.
also approximate mixed sparse grid spaces (Montanelli &
Our bound is faster than the concurrent bound (Duan et al., 2021; Jiao et al., 2021a) for we provided fast rate (1//n) by utilizing the strong convexity of the objective function and improved the convergence rate from 24-2 to n
2x-2 2=2.-2 for Deep Ritz and from
n 24-4--8
2+2--4 for PINN. Compared the lower bound provided in Section 3, bounds for PINN is near-optimal while the upper bound for DRM is sub-optimal. We believe our bound is tight and put the discussion in Appendix E. We'll propose a modified version of DRM to match the upper and lower bound in the next section.
For upper bound of DRM, due to a technical issue, we assumed that the observation we access is clean, ie fa f(X;). We conjecture that add noising observation will not effect the rate and leave this to future work.
5 MODIFIED DEEP RITZ METHODS
Comparing the lower bound in Section 3 and the upper bound in Section 4, we find out that the Physics-Informed Neural Network achieves min-max optimality while the Deep Ritz Method does not. In this section, we propose a modified version of Deep Ritz which can be statistically optimal.
As discussed in Appendix E, the reason behind the suboptimality of DRM comes from the high complexity introduced via the uniform concentration bound of the gradient term the variational form. At the same time, further observed that the f [|Vu||2da does not require any query from the right hand side function f. which means that we can easily make another splitted sample to approximate the ||Vu|| 2dz term more precisely.
E N.
(u)
+ 1
Σ [12] [VVx(X))1
[ (
( -f)((x))))
(5.1)

---

Published as a conference paper at ICLR 2022
Once sampled more data for approximating f Vulddx, achieve optimal bound for the Truncated Fourier Estimator when Z n...2.
Theorem 5.1. (Informal Upper Bound of DRM with Truncated Fourier Series Estimator]With proper assumptions, consider the Deep Ritz objective with a plug in Fourier Series estimator Fourier MDRM
m ENDRM (u) with (n and Z 2 then have
V Fourier MMDM
u 1 S 242x-1
Remark. We still cannot achieve optimal rate for neural network even with modified DRM methods. The reason is because the number of neurons is not good complexity measure for the gradient the function. Thus, the bound for (r) = ( ((I()) 1|u u" l I rr) } is not enough for achieving optimal convergence rate. However, following "Schmidt-Hiehee et al., 2020; Suzuki, 2;18; Imaizumi & Fukumizu, 2020; Chen et al., 2019b; Farrell et al., 2021) to use deep networks for estimating functions, we optimize the best neural network with constrained sparsity in our paper. Here we conjecture that there exists computable complexity measure that can make DRM statistically optimal and leave finding the right complexity the neural network's gradient to be future work.
EXPERIMENTS
In this section, we conduct several numerical experiments verify our theory. We follow the neural network and hyper- param--rrreeter setting in (Chen et al., 2020). Due to the page limit, we only put the experiments for Deep Ritz Methods here.
6.1 THE MODIFIED DEEP RITZ METHODS
In this section, we conduct experiments which substantiate our theoretical results for modified Deep Ritz methods. For simplicity, we take V(x) = our experiment. We conduct experiment in 2-dimension and select the solution of the PDF as =² = Σ. - (x:()) E H We show the log-log plot of the H' loss against the number of sampled data for = 4 in Figure 1. We use an OLS estimator fit the log-log plot and put the estimated slope and corresponding R² score in Figure 1. As our theory predicts, the modified Deep Ritz Method converges faster than the original one. All the derivation the two estimators is listed in Appendix E.
6.2 DIMENSION DEPENDENT SCALING LAW.
We conduct experiments to illustrate that the population loss of well-trained and well-tuned Deep Ritz method will scale with the d- dimensional training data number N as power- range of and a and verify an approximately a 1 scal- ing law as our theory suggests. We use the same test function in Section 6. as the solution of our PDE. For simplicity, we take V(x)) 1 in our experiment. We train the deep Ritz method on 20. 80, 320, 1280, 10240 sampled data points for 5,6,7,8,9,10 dimensional problems and we plot results on the log-log scale. Results shown in Figure 2. We discover the L x मスス scaling law practical situations.
law L x No. We also
Legiterber of Tamne Data"
Loghtmberr of Thxknn Drai
Theory
Score
0.33
Figure 1: The log-log plot and estimated conver- gence slope for Modified DRM and DRM using Fourier basis, showing the median over replicates.
6.3 ADAPTATION TO THE SIMPLER FUNCTIONS.
(Sharma & Kaplan, 2020) showed that the neural scaling law will adapt to the structure that the target function enjoys. This adaptivity enables the neural network to break the cure of the dimensionality for simple functions in high dimension. (Suzuki & Nitanda, 2019; Chen al., 2019a) also observed this theoretically. For solving PDEs, we also observed this adaptivity in practice. Here we tested the following two hypothesis
8

---

Published as a conference paper at ICLR 2022
Figure 2: We verify the dimension dependent scaling law empirically. The multiplicative inverse of the scaling law coefficient is highly linear with the dimension d, showing the mean error over 2 replicates.
Random Neural Network Teacher. Following (Sharma & Kaplan, 2020), we also tested random neural network using He initialization (He et al., 2015) as the ground turth solution u². (De Palma et al., 2018) showed that random deep neural networks are biased towards simple functions and in practice we observed a scaling law at the parametric rate. Specifically, we obtained linear estimate with slope log-log plot. See Figure 3(a).
0.50679429 and R² score 0.96 in the
Simple Polynomials. Neural network can approximate simple polynomials exponentially fast (Wang et al., 2018). Thus, we select the ground truth solution to be the following simple polynomial in 10 dimensional spaces u (x) 21 + ... + Zy In this example, we obtained linear estimate with slope - 0. 0.49755418 and a R score 0.99 in the log-log plot. See Figure 3(b).
7 CONCLUSION AND DISCUSSION
Conclusion In this paper, We considered the statistical min-max optimality of solving a PDE from random samples. We improved the previ- ous bounds (Xu, 2020; Lu et al., 202 Duan al., 2021; Jiao al., 202 la) by providing the first fast rate generalization bound for learning PDE solutions via the strongly convex nature of the two objective functions. We achieved the optimal rate via the PINN and modified Deep Ritz method. We verified our theory via numer- ical experiments and explored the dimension dependent scaling laws of Deep PDE solvers.
Figure 3: Neural networks have the ability to adapt simple functions and achieve convergence with- out curse of dimensionality, showing the median error over replicates.
Discussion and Future Work Here we discuss several drawbacks of our theory
We restricted our target function and estimators in 1,0000 instead of H due bounded- ness assumption made in the local Rademacher complexity arguments. However, typical functional used physics is always unbounded, such as the Newtonian potential which limits the application of our theory.
This paper did not discuss any optimization aspect of the deep PDE solvers and always as- sumed that global optimum can be achieved. However, it is important to investigate whether the optimization error (Suzuki & Akiyama, 2020; Chizat, 2021) will finally dominate.
Instead of solving single PDE, recent works (Long al., 2018: 2019; Li et al., 2020; Lanthaler et al., 2021; Bhattacharya et al., 2020; Fan & Ying, 2020; Feliu-Faba et al., 2020) considered the so-called "operator learning". which aims to learn family of PDF/inverse

---

Published as a conference paper at ICLR 2022
problems using single network. It is interesting to investigate the generalization bound and neural scaling law there.
We find out that the sparsity of the neural network is not a good complexity measure of neural network's ' gradient. We conjecture that there exists an oracle complexity measure, whose approximation and generalization bounds can lead Modified DRM achieve the optimal convergence rate.
ACKNOWLEDGMENTS
Yiping Lu is supported by the Stanford Interdisciplinary Graduate Fellowship (SIGF). Jianfeng Lu supported in part by National Science Foundation via grants DMS-2012286 and CCF1934964. Lexing Ying is supported by National Science Foundation under award DMS-201 1699, Jose Blanchet supported in part by the Air Force Office of Scientific Research under award number FA9550-20- 1-0397 and NSF grants 1915967, 1820942, 1838576. Yiping Lu also thanks Taiji Suzuki, Atsushi Nitanda, Yifan Chen, Junbin Huang, Wenlong Ji, Greg Yang. Yufan Chen, Zong Shang, Denny Wu, Jikai Hou, Jun Hu, Fang Yao, Bin Dong and George Em Karniadakis for helpful comments and feedback.
REFERENCES
Robert A Adams and John JF Fournier. Sobolev spaces. Elsevier, 2003.
Genming Bai, Ujjwal Koley, Siddhartha Mishra, and Roberto Molinaro. Physics informed neural networks (pinns) for approximating nonlinear dispersive pdes. arXiv preprint 2Xiv:2104.05584 2021.
Peter L Bartlett, Olivier Bousquet, Shahar Mendelson, et al. Local rademacher complexities. The Annals of Statistics, 33(4); 1497-1577, 2005.
Kaushik Bhattacharya, Bamdad Hosseini. Nikola B Kovachki. and Andrew M Stuart. Model reduction and neural networks for parametric pdes. arXiv preprint arXiv:2005.031880 2020.
Haim Brezis. Functional analysis, Sobolev spaces and partial differential equations. Springer
Science & Business Media, 2010.
Lawrence D Brown and Mark G Low. Asymptotic equivalence of nonparametric regression and white noise. The Annals of Statistics, 24(6):2384-23) 2398, 1996.
Jingrun Chen, Rui Du, and Keke Wu. A comprehensive study of boundary conditions when solving pdes by duns. arXiv preprint w0X55:2005.04554, 2020.
Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Efficient approximation of deep relu networks for functions on low dimensional manifolds. Advances in Neural Information Processing Systems, 22:8174-8184 2019a.
Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Nonparametric regression low- dimensional manifolds using deep relu networks. arXiv preprint arXiv: 1908.0/99 2019b.
Yian Chen, Jeremy Hoskins, Yuchaw Khoo, and Michael Lindsey. Committor functions via tensor networks. arXiv preprint arXiv:2106. /2515, 2021a.
Yifan Chen, Bamdad Hosseini, Houman Owhadi, and Andrew M Stuart. Solving and learning nonlinear pdes with gaussian processes. arXiv preprint arXiv:2103. 12959, 2021b.
Lénaïc Chizat. Convergence rates of gradient methods for convex optimization in the space of measures. arXiv preprint 115::2005.08368 2021.
Carl De Boor and Carl De Boor. A practical guide to splines, volume 27. springer-verlag New York, 1978.
Giacomo De Palma, Bobak Toussi Kiani, and Seth Lloyd. Random deep neural networks are biased towards simple functions. arXiv preprint 18/iv: 10156, 2018
10

---

Published as a conference paper at ICLR 2022
Chenguang Duan, Yuling Jiao, Yanming Lai, Xiliang Lu, and Zhijian Yang. Convergence rate analysis for deep ritz method. arXiv preprint 0rXiv:2103.13330 2021.
Weinan E and Bing Yu. The deep ritz method: a deep learning- baaiid numerical algorithm for solving variational problems. Communications in Mathematics and Statistics, 6(1):1-12, 2018.
Lawrence C Evans. Partial differential equations. Graduate studies in mathematics, 19(4):7, 1998.
Yuwei Fan and Lexing Ying. Solving electrical impedance tomography with deep learning. Journal of Computational Physics, 404:109119, 19, 2020.
Max H Farrell, Tengyuan Liang, and Sanjog Misra. Deep neural networks for estimation and inference. Econometrica, 89(1):1812113, 2021.
Jordi Feliu-Faba, Yuwei Fan, and Lexing Ying. Meta-learning pseudo-diffcrential operators with deep neural networks. Journal of Computational Physics, 408: 103:10 2020.
Sara A Geer and Sara de Geer. Empirical Processes in M-estimation, volume 6. Cambridge university press, 2000.
Maximilien Germain, Huyên Pham, and Xavier Warin. Neural networks-based algorithms for stochastic control and pdes in finance. arXiv preprint arXiv:2 2021.
Davis Gilton, Greg Ongie, and Rebecca Willett. Neumann networks for linear inverse problems in imaging. IEEE Transactions on Computational Imaging, 6:328-343 303,,,33344 2019.
Philipp Grohs and Lukas Herrmann. Deep neural network approximation for high-dimensional elliptic pdes with boundary conditions. arXiv preprint 2tti:22007.0588444 2020.
Philipp Grohs, Fabian Hornung, Arnulf Jentzen, and Philippe Von Wurstemberger. A proof that artificial neural networks overcome the curse of dimensionality in the numerical approximation of black-scholes partial differential equations. arXiv preprint arXiv:1809.0236) 2018.
Ingo Gühring, Gitta Kutyniok, and Philipp Petersen. Error bounds for approximations with deep relu neural networks in p norms. Analysis and Applications, 18(05):803-835 859, 2020.
Jiequn Han, Arnulf Jentzen, and E Weinan. Solving high-dimensional partial differential equations using deep learning. Proceedings of the National Academy of Sciences, 115(34)88505-8510 2018.
Jiequn Han, Jianfeng Lu, and Mo Zhou. Solving high- high-dimensional eigenvalue problems using deep neural networks: diffusion monte carlo like approach. Journal of Computational Physics, 423: 109792, 2020.
Tatsunori Hashimoto. Predicting the impact of dataset composition on model performance, 2021.
URL https:tp////m pttttp:://openevviiie .et.eeewweeeeeee..ee. forum? but
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015.
James B Heaton, Nick G Polson, and Jan Hendrik Witte. Deep learning for finance: deep portfolios. Applied Stochastic Models in Business and Industry, 33(1):3-12, 2017.
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Patwary, Mostofa Ali, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically. arXiv preprint 1712v0171..00409 2017.
Jan-Christian Hütter and Philippe Rigollet. Minimax rates of estimation for smooth optimal transport 2019.
maps. arXiv preprint
Masaaki Imaizumi and Kenji Fukumizu. Advantage of deep neural networks for estimating functions with singularity on curves. arXiv preprint arXiv:2011.02256, 2020.
Yuling Jiao, Yanming Lai, Dingwei Li, Xiliang Lu, Yang Wang, and Jerry Zhijian Yang. Convergence analysis for the pinns, 2021a
11

---

Published as a conference paper at ICLR 2022
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, 2021b.
Yuling Jiao, Guohao Shen, Yuanyuan Lin, and Jian Huang. Deep nonparametric regression approximately low-dimensional manifolds. arXiv preprint arXiv:2104.06700 2021c.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.00000 000001,....6..... 2020.
Yuehaw Khoo, Jianfeng Lu, and Lexing Ying. Solving parametric pde problems with artificial neural networks. arXiv preprint arXiv: 1edd::1707.335555 2017.
Vladimir Koltchinskii. Oracle Inequalities in Empirical Risk Mininization and Sparse Recovery Problems: Ecole d'Eié de Probabilités de Saint-Flour XXXVIII-2008, volume 2033. Springer Science & Buusieess Media, 2011.
Samuel Lanthaler, Siddhartha Mishra, and George Em Karniadakis. Error estimates for deeponets: A deep learning framework in infinite dimensions. arXiv preprint 1rXii:2102.096188 2021.
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes. Springer Science & Business Media, 2013.
Zongyi Li, Nikola Kovachki, Kamyar Azizzadenesheli, Burigede Liu, Kaushik Bhattacharya, Andrew Stuart, and Anima Anandkumar. Fourier neural operator for parametric partial differential equations. arXiv preprint arXiv:2010.0889) 2020.
Youming Liu and Huiying Wang. Convergence order of wavelet thresholding estimator for differential operators on besov spaces. Applied and Computational Harmonic Analysis, 32(3):342-356, 2012.
Zichao Long, Yiping Lu, Xianzhong Ma, and Bin Dong. Pde-net: Learning pdes from data. In International Conference on Machine Learning, pp. 3208-3216 PMLR, 2018.
Zichao Long, Yiping Lu, and Bin Dong. Pde-net 2.0: Learning pdes from data with numeric- symbolic hybrid deep network. Journal of Computational Physics, 399: 108925, 2019.
Denghui Lu, Han Wang, Mohan Chen, Lin Lin, Roberto Car, Weinan, Weile Jia, and Linfeng Zhang, 86 pflops deep potential molecular dynamics simulation of 100 million atoms with ab initio accuracy. Computer Physics Communications, 259:107624, 2021a.
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.01700 2021b.
Tao Luo and Haizhao Yang. Two-layer neural networks for partial differential equations: Optimization and generalization theory. arXiv preprint arXiv:2006. 15733, 2020.
Tudor Manole, Sivaraman Balakrishnan, Jonathan Niles-Weed, and Larry Wasserman. Plugin estimation of smooth optimal transport maps. arXiv preprint arXiv:2107. 12364, 2021.
Tanya Marwah, Zachary C Lipton, and Andrej Risteski. Parametric complexity bounds for approxi- mating pdes with neural networks. arXiv preprint arXiv:2103.021 2021.
Hiroaki Mikami, Kenji Fukumizu, Shogo Murai, Shuji Suzuki, Yuta Kikuchi, Taiji Suzuki, Shin-ichi Maeda, and Kohei Hayashi. A scaling law for synthetic-to-real transfer: A measure of pre-training. arXiv preprint arXiv:2108. 1018, 2021.
Hadrien Montanelli and Qiang Du. New error bounds for deep relu networks using sparse grids. SIAM Journal on Mathematics of Data Science, 1(1):88-9) 92, 2019.
Hans Hans-Georg Müller and Theo Gasser. Optimal convergence properties of kernel estimates of deriva- tives of a density function. In Smoothing techniques for curve estimation, pp. 144-154. Springer, 1979.
12

---

Published as a conference paper at ICLR 2022
Richard Nickl, Sara van de Geer, and Sven Wang. Convergence rates for penalized least squares esti- mators in pde constrained regression problems. SIAM/ASA Journal on Uncertainty Quantification, 8(1):374-413, 2020.
Atsushi Nitanda and Taiji Suzuki. Optimal rates for averaged stochastic gradient descent under neural tangent kernel regime. arXiv preprint arXiv:2006.12297, 2020.
Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. arXiv preprint arXiv:1910.01635, 2019.
BLS Prakasa Rao. Nomparametrie estimation of the derivatives a density by the method of wavelets. Bulletin of Informatics and Cyberneticx, 28(1):91-100, 1996.
Maziar Raissi, Paris Perdikaris, and George Kariiadakis Physics-informed neural networks: deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. Journal of Computational Physics, 378:686-707, 2019.
Alexander Rakhlin, Karthik Sridharan, and Alexandre B Tsybakov. Empirical entropy. minimax regret and minimax risk. Bernoulli, 23(2):789-83) 2017.
Lorenz Richter, Leon Sallandt, and Nikolas Nüsken. Solving high- dimenssinnii parabolic pdes using the tensor train format. arXiv preprint arXiv:2102.11830. 2021.
Jonathan Rosenfeld. Scaling laws for deep learning. arXiv preprint arXiv:2108.076686 2021.
Jonathan Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit, A constructive prediction of the generalization error across scales. arXiv preprint arXiv: 12673, 2019.
Johannes Schmidt- al. Nonparametric regression using deep neural networks with relu activation function. Annals of Statistics, 48(4): 2020.
Larry Schumaker. Spline functions: basic theory. Cambridge University Press, 2007.
Utkarsh Sharma and Jared Kaplan. neural scaling law from the dimension of the data manifold. arXiv preprint arXiv:2004. 2020.
Zuowei Shen, Haizhao Yang. and Shijun Zhang. Neural network approximation: Three hidden layers are enough. Neural Networks, 2021.
Yeonjong Shin, Zhongqiang Zhang, and George Em Karniadakis. Error estimates of residual minimization using neural networks for linear pdes. arXiv preprint arXiv:20/0.080/9, 2020.
Justin Sirignano and Konstantinos Spiliopoulos. Dgm: deep learning algorithm for solving partial differential equations. Journal of computational physics, 375:1339-1364 2018.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates, Advances in neural information processing systems, 23, 2010.
Taiji Suzuki. Adaptivity of deep relu network for learning besov and mixed smooth besov spaces: optimal rate and curse of dimensionality. arXiv preprint arXiv:18/0.0800 2018.
Taiji Suzuki and Shunta Akiyama. Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods. arXiv preprint arXiv:2012.0322) 2020.
Taiji Suzuki and Atsushi Nitanda. Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic besov space. arXiv preprint arXiv:1910.12799, 2019.
Joel Tropp. An introduction to matrix concentration inequalities. arXiv preprint arXiv:1501.0157/, 2015.
Alexandre B Tsybakov. Introduction to nonparametric estimation. Springer Science Business Media, 2008.
13

---

Published as a conference paper at ICLR 2022
Sara Van De Geer. A new approach to least-squares estimation, with applications. The Annals of Statistics, 15(2)5587-622 1987.
Qingcan Wang et al. Exponential convergence of the deep neural network approximation for analytic functions, arXiv preprint arXiv:1807.00297, 2018.
Stephan Wojtowytsch et al. Some observations on partial differential equations in barron and multi-layer spaces. arXiv preprint arXiv:2012.0148,, 2020.
Jinchao Xu. The finite neuron method and convergence analysis. arXiv preprint arXiv:2010.01458. 2020.
Yunbei Xu and Assaf Zeevi. Towards optimal problem dependent generalization error bounds in statistical learning theory. arXiv preprini arXiv:201 1.06186, 2020.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
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.
Xiaoshuai Zhang, Yiping Lu, Jiaying Liu, and Bin Dong. Dynamically unfolding recurrent restorer: A moving endpoint control method for image restoration, arXiv preprint arXiv 2018.
14

---

Published as a conference paper at ICLR 2022
Appendix
A APPENDIX ORGANIZATION AND PROOF SKETCH
A.1 NOTATIONS
In this section, we provide all the notations we need in the proof. Let C Rd be some open set. We denote C()2) the space of continuous functions on f2 and (12) the space of all functions that are k times continuously differentiable on Ω (V E )) For any n E No (No == - U {0) is the set of all non non-negative integers) and 1 S p S co, we define the Sobolev space W*))((2) by
W == {f (?)): f E (P)), Va Ng with |a| - n)-
In particular, when 2, we define (12( := ( for any n E No- Moreover, for any (L) with p oc, define the Sobolev norm by:
|l II
Σ 0glalsn
D 1 fll
In partieular, when p oo, we have:
(llllwm.>>()) = max
| [l)=>>)
05/a|sa
Consider the Fourier expansion f == ExExa (2)x(x) of the function f WD).(D). We can equivalently express the Sobolev norm as:
IIflwwr = [|==|1/|fal 1/P
where f. = ((z) = Jn f(x)e 2mi(z,a)) dx (x E Q2) is the z Fourier coefficient of f. Moreover, we use l (S2) to denote the closure of C+ (f) in W.)((s). In particular, when p 2, define Ho! (I2) Furthermore, we use || to present the vector 2 norm and, given data sample (Xi C Q || In.p (E,, P) denote the empirical p norm, where EE, T,2 R is the corresponding empirical average operator defined as f= Σn i= f(X)), v ( Given quantities < CY holds, where is some constant, For two
X and Y, we write X = Y when the inequality X
functions f and y mapping from IR+ to IR, write = Ogg) when there exist two constants C' and To independent of f and such that the inequality f(x)) S (()(x) holds for any x 2 Zg. We use X Y denote X S Y and Y X.
A.2 APPENDIX ORGANIZATION AND PROOF SKETCH
In this section, we list the organization of the appendix and put more detailed proof sketch of our main results. We put all the proof of upper bounds in Appendix B and all the proof of lower bounds in Appendix D. All the proof of the results about modified Deep Ritz method is given in Appendix C. The proof of lower bounds based on standard Fano method. In this section, we focus on the proof sketch of the fast rate upper bound.
Error Decomposition. We first decompose the excess risk AE,, Eu,)) E(u") of well- trained neural network on the PINN/DRM loss function into approximation error and generalization error, similar (Xu, 2020; Lu et al., 202 lb; Duan al., 2021; Jiao et al., 2021a;b). The regularity results used in the decomposition are proved in Appendix B. Explicitly, for any F(2), we can decompose the excess risk as
AE (E()) (a) E(i) Elu*)
[E(ū) [ū)] [E)(0) E, (uF)] + (u(()) E(uF)] + [[(F)) E(u*)]
< (E) [ū)] [En( E(uF)
E(u))
Generalization Error
Approximation Error
(A.1)
15

---

Published as a conference paper at ICLR 2022
where the expectation is uniformly sampled data, F(2) is the space of parametrized estimators we used like truncated Fourier series or sparse neural networks, is the minimizer of the empirical loss E, in F(2)) and u² is the minimizer of the population loss E (i.e, ground truth solution). The inequality in the third line follows from the fact that ú is the minimizer of the empirical loss E, in the space F(2), which implies E,, (() S E,, (ur). We call the first term generalization error as it's measuring the difference between E, and E. We call the second term approximation error as it seeks for a parametrized estimator uF that approximates the ground truth solution u² well in F(22). The upper bounds on generalization and approximation error that we achieved in this paper are listed in Table 2.
Let n. denote the number of sampled datapoints, For the generalization error, different from the concurrent upper bound O (a)) (Duan al., 2021; Jiao et al., 2021a), we provide a faster and near optimal upper bound 0 ( by utilizing the strong convexity of the objective function established in Appendix B.I. Via using the Peeling Lemma (I (Lemma B.4, for completeness, we also provide a proof), we show that the generalization error can be bounded by the fixed point of the local Rademacher complexity
((r = R., (fI(u) 1|u- u =r))
where R2 is the Rademacher complexity, I(u)= = Au Vu, lla = ||
11 for PINN and I(u)= = ||Vul|a + Vu, || 11A= -1- for DRM. Once we show that Φ(r) is of magnitude ((v
we can achieve the O convergence rate via solving the fix point equation 6(r) = O(V
(42). Using the solution of the fixed point equation of the local Rademacher complexity to bound the generalization eтror is a standard result in empirical process Bartlett et al. (2005); Srebro et al. (2010); Koltchinskii (2011); Xu & Zeevi (2020); Farrell et al. (2021). The difference is that we used the H HH² norm to define the localized set, while the previous papers used the E distance. The way to obtain the fast rate generalization bound is using the Peeling Lemma.
We present the eтrоr decomposition results as meta theorem, which is shown in Theorem B.12 for PINN, Theorem B.9 for DRM and Theorem C.I for MDRM, respectively. To make the final rate depend on the data number only, we need bounds of the approximation error in Appendix B.3 and bounds of the local Rademacher complexity in Appendix B.2.
Approximation Error. The proof of the approximation results of truncated Fourier series is easy and intuitive. For completeness, we provide it in Appendix 1. The proof of the approximation results of neural networks follows from the fact that B-spline approximation can be formulated as a ReLU3 neural network efficiently. Our proof basically follows Duan et al. (2021); Jiao et al. (2021a), while the only difference is the activation function. Our proof is also very similar to (Yarotsky, 2017; Suzuki, 2018), but the depth of our network is of constant magnitude instead of O log magnitude, where denotes the desired approximation error. Such improvement of depth results from the fact that ReI.U3 activations can approximate B-splines more easily than the ReL.U activations, which is useful in our generalization analysis. Although the proof of the approximation results of neural networks in the Sobolev space is standard, we still list it in Appendix B.3.2.
Generalization Error. As we discussed above, the generalization error can be bounded by the fix point of the local Rademacher complexity, i.e. the solution of Φ(r) r. Once we have D(VH) bound of (r),, we can achieve the ( fast rate generalization bound we want. It remains to upper bound the the local Rademacher complexity ((r).
For the upper bound on the local Rademacher complexity of truncated Fourier series estimators, our proof technique is similar to that of the kernel estimators, whose Rademacher complexity can be bounded by the trace of the Gram matrix (i.e. the effective number of basis). One interesting thing we
showed is that the final upper bound of the Rademacher complexity localized by H norm is / cd-2r
The term gd ed-2 in the numerator is smaller than 5d, which is the exact number of Fourier basis. This improvement results from the H norm localization. The detailed proof is given in Lemma B.6, Lemma B.7 and Lemma B.S.
For the upper bound the local Rademacher complexity bound for neural network, we follow Schmidt-Hiehe et al. (2020); Suzuki (2018); Farrell et al. (2021) to use a Dudley integral theorem and covering number argument. The covering number arguments are shown in Theorem B.4, Theorem
16

---

Published as a conference paper at ICLR 2022
B.5 and Theorem B.6. The final local Rademacher complexity bounds given in Lemma B.17 and Lemma B.18. The difference that the complexity of gradient of ReLU3 activation function makes the covering number depend exponentially of neural network's depth to constant magnitude mentioned above the approximation results saves this problem. One drawback of our proof is that the H norm localization wouldn't improve the bound for Rademacher complexity and leads to sub-optimal upper bounds. We hypothesize that our bound is tight for sparse neural network and put seeking right complexity measure of neural network for solving PDEs as a future work.
the neural network's ' depth. However, the improvement
Objective Function
Estimator
Approximation
Generalization
Complexity Measure
Neural Network
N
N: Number of parameters
PINNs
Fourier Seriers
{ 2((-22)
fmmxximu frequency
Neural Network
N N-
N: Number of parameters E:maximum frequency
DRM
Fourier Seriers
{ (-2(-11)
Neural Network
N 20-2
N
N: Number of parameters
MDRM
Fourier Seriers
22((-1)
m:maximum frequency
Table 2: Approximation and generalization results we achieved this paper.
B PROOF OF THE UPPER BOUNDS
B.1 REGULARITY RESULT FOR THE PDE MODEL.
Regularity Results of the DRM Objective Function
Theorem B.1. We consider the static Schrödinger equation the unit hypercube Rd with the zero Direchlet boundary condition:
Au + Vu on S
(B.1)
0 on O2.
where E (Ω) and V E (P) with O < Vmin S (x) S Vmax > 0. There exists a unique weak solution usg to the equivalent variational problem (Evans, 1998):
( / [[Vull2 + Vlul2] dr Fudz)
Ugg
arg min EDRM (u) == arg min
(B.2)
ME (2)
(E)
Then for any E H (22), we have: min(1, Vimin)
max(1, (, Vmax)
||u us (o)
DRR (u) EDRM (ug) <
||u uts ( (B.3)
2
Proof. To show that us satisfies estimate B.3, we first claim that for any u E HI))..,
2 / |Vu - Vugll2dr +
2 / V(us u)² dr.
1
EDRM (u)
DRM (us)
(B.4)
In fact, by plugging in the first equation of B.1, one has that
/ Vlu's 2 2dr
DRM (us)
V us
dn +
J
fugde
2
nn
1
1
|| dx
V Vlusi 2dx
(Aug Vus)
2 2
nn
ss2
|| dx +
(Auz) A
Vluğldr.
2 n
2 2
17

---

Published as a conference paper at ICLR 2022
Furthermore, applying Green's formula to the true solution u3 yields:
E EDMM (uz)
2 2/1 / /usll2de
1
(Auz)uugr
2/
f Vluss 2r
5
{ Ou's
1
/
2 / Vlug 2d
1
an On uiddt
Vuill
2 1t
/ [usl|l
/ V Vlu5/ /5,
- 2 Jn
2
where the last identity above follows from the second equality in B.1. Now for any ( applying Green's 's formula to u. and the true solution vig implies:
E DRM
(u) (u)
DRM (u')
/ |u
J. Vlul2dx J, fudz + 5n / Vugll dx +
1
2 //1, Vlus dz
1
s2
2
Vul + 2 13
3/1
Vluldd
+ (An's - Vus)udr +
| I do + / V Vlus 2dx
2 2
12
2 52
1 /ul + (Aui)
|
2 %.8
1
V V w)
n
n
f Ou's udr
Vudr + /
/ V u) dx
|ull2dx +
Vug.
| dr + 2 J
2 2
onn On
g
/ Vuu - Vugll= + / V(uss - u)² dx.
= n2
where the last identity above again follows from the second equality in B. This completes our proof of identity B.4. Using the assumptions the potential function V then implies:
E EDRM( (u) (DRM(u3)) S max(1, 1, Vima)
Vuu - Vugll / 1 - u)²² dx
max(1, 1, Viax)
||u u (1l12
EDRM(u) -EDRM min(1, Vmin)) )
|Vu Vušll / (u's u)² do
2
min(1, Vmin)
||u uss (())
2
This completes our proof of B.1.
Regularity Results of the PINN Objective Function
Theorem B.2. We consider the static Schrödinger equation on the unit hypercube on Rd with the Neumann boundary condition:
Au + Vu on Ω
(B.5)
0 on On.
where f E (2( and V E ( with V2
AV Cmin: 0 < Cuin < V(x) S Vmax and
-VV(2) (x) < V max. Then there exists a unique solution uts E Ho (12) to the following minimization problem (Brezis, 2010):
{ {/ |Au - Vu 11
ugg arg min EPINN == arg min
(B.6)
WEH
(E)
Then for any E
H!! (2), we have:
min Cmin u 13 S PINN (u) PINN (wg)
EPNN( 5 2(1 Vmax v2ax))l uillir
(B.7)
18

---

Published as a conference paper at ICLR 2022
Proof. For any Ho (22). we let i u², then we have à E (
EPINN (u)
PINN (u')
AAu Vu- Au + Vuu
A - Vu
52
12
(B.8)
(Aū)de de + / (2 - / VūAūdz.
Using Green's formula, we have:
( VūAūdr / v(Vū). Vüde
/
dū V 0,
Jon ōn
where the last equality above follows from the fact that ū E (2)) This further implies:
EPINN (u) EPPNNN (us) / (Au) + V2 +2
/ V(Vū) Vüdr
jn
/ (Aufdr + / 22 de +
VI de +2 uVV Vüdr.
Using Green's 's formula again, we have:
avV Vüde = / (nn)) Vv = on On
0V
if AV 1 il AV.
i2
11
Then we can further deduce that:
EPINN (u) - EINNN (u's) = (Aū)dæ + ((V2 (V2-AV)ū dx +2 / V||Vūl|?
12
12
For we have assumed V E (I2) with 0 < Cmin < 22- AV,O < Cuin < V(z) s V Vinx and (v S Vmaxx thus we have
[1, Cmin }|u - "gllira()) I EPINN - EPINN EEINN(")) S 2(1 + Vmaxx V - Ug (
(B.9)
B.2 AUXILIARY DEFINITIONS AND LEMMATA ON GENERALIZATION ERROR
To bound the generalization error, the localized Rademacher complexity (Bartlett et al., 2005). Recall that the Rademacher complexity of a function class G is defined by
T Σ E0, gEG n j=l
R, (G) EzE,
sup
Zz, Zn
where Z, are i.i.d samples according to the data distributions and oy are i.i.d Rademacher random variables which take the value with probability 1/ and value -1 with probability }
The following important symmetrization lemma makes the connection between the uniform law of large numbers and the Rademacher complexity.
Lemma B.1 (Symmetrization Lemma). Let F be a set of functions. Then
n
E sup F
Σ n
u(X,) u()) 2R.
j=1
Lemma B.2 (Ledoux-Tallgrrad Talagrand contraction (Ledoux & Talagrand, 2013, Theorem 4.12)). Assume that R- is T-Lipschitz with ((0) = Let {ar) be independent Rademacher random variables. Then for any T C g
E2
Σ aro(ts) < 2L Eg (brr J.T
sup
sup (lir (.)eT 1=1
Σ ost
19

---

Published as a conference paper at ICLR 2022
Let (E, be metric space with metric p. A ô-cover of set A E with respect to p is collection of points {21,-.. End C A such that for every x E A, there exists i E {1.... nu such that 2(z,2;) S 8. The ô-covering number [ A, p) is the cardinality of the smallest 8-cover of the set A with respect to the metric p. Equivalently, the ò-covering number N6,, A,P) number of balls B,(r,, 6) of radius 5 needed to cover the set A.
p) is the minimal
Theorem B.3 (Dudley's Integral theorem). Let F be a function class such that Sur 11/ S M.
Then the Rademacher complexity Rn, (F) satisfies that
12 pd
R (F) S
inf {45 0S85M
Vlog F, 1lm22) de}.
Vn.J
Lemma B.3 (Talagrand Concentration Inequality). Consider a function class F defined on a prob- ability measure y such that for all f E F, we have || $ any > O, we can have the following concentration results.
[y,] O2 [ S 0². Then for
E((2) 2t
21,3
P S
sup SEF T2
E f(a)) 22 sup -
Se
JEF
==1 Lemma B.4 (Peeling lemma (Bartlett et al., 2005)). Consider some measurable function class F. Assume that there exists sub-root function functiion ((r) satisfying
Rnf E F Bif] S r)) S Ø(r) (vr 20)) 0).
(B.10)
Then we have
1
1
4Φ(r)
Eg,,.n
sup JEF +r
22
r) to be the localized set with radius r. Then for fixed set of datapoints {2i ) and a fixed set of Rademacher random variables {oi we have:
Proof. Denote F(r) = EF
B[f]
Di=1 + ozf(2+)
1E=roffee o.f(2t)
E ozf(21)
E.g FEr
sup
sup SEF(r)
sup (EF(NU+))55GA)
E +r
r
r4i +r
1=0
Rr (F(rF)
Rn (F(rr(+)))
((()
6(14++1)
r
r4i +r
r4i +r
1=0
j=0
((r)
00
2 ((T)
40(r)
<
<
r40
+r
1=0
We also modify the peeling lemma above, as we aim to apply it to derive the upper bound for the Modified Deep Ritz Method (MDRM).
Lemma B.5 (Peeling Lemma For MDRM), Given some measurable function class F and two RR we define class F of vector-valued funnttoo by: F= ((g o f, h f) F).
continuous mappings g. h
For any f E F. we use gf and h to denote the two compositions g f and h f. respectively, For any r 0, the localized set F, is defined by:
F, = = ((gg, h2)) E F Ex, (x) Ey(hs(y) S r}.
Moreover, the modified Rademacher Complexity of Fr is defined by:
Ba (F,) == R., (19)/ar, h1) E F..)) + Rmi(tyylas hy) E FF.) Assume that there exists some function [0, oo) + o0) and some r* > O, such that for any T > r", we have:
((4r) S 20(r) and Rn,m (F,) S Φ(r).
Then for any > r", we have:
En o.gr( + de Σド rp)r(wo)] E, (g)(()) (x) + E., (1y( 
40(r) r
Eggr
Bry (sup
FEF
+r
Proof. The proof is the same the original peeling lemma, thus omit the detailed proof here. n
20

---

Published as a conference paper at ICLR 2022
B.2.1 LOCAL RADEMACHER COMPLEXITY OF TRUNCATED FOURIER BASIS
Definition B.1. (Fourier Series) Given a domain Ω S 10.1 For any E N we consider the corresponding Fourier basis function de (x) == e2mi(2,a) (xr E Q). With respect to the Fourier basis, any function f E (It) can be decomposed as the following sum:
f(x) (d)(
(B.11)
=EN
where for any No, the Fourier coefficient J = Sa J
Definition B.2. (Truncated Fourier Series) For a fixed positive integer & E Zt, we define the space Fe(St) of truncated Fourier series as follows:
Fe(S2) = {s Σ
S2b2 f== = 0, |1 > 5).
(B.12)
=ENU
Equivalently, we can decompose any f E (g(S)) as f := E |= SE fxr..
Lemma B.6. (Local Rademacher Complexity of Localized Truncated Fourier Series) For fixed { E E we consider localized class of functions (P)) { E Fe( [I S sp). where
p > 0 is fixed. Then have the following upper bound the local Rademacher complexity:
S &VEE
Le
(F,, Ex
ES
sup (E))
axf(()) XI, Xm]
V
(B.13)
n
Proof. Take an arbitrary function f E (.)). Let f Ejeela a se Seb be the Fourier basis expansion of f. p IIfflinra implies constraint -|+ SE Ifel || S on the Fourier coeffi- cients(Adams & Fournier, 2003).
On the other hand, substituting the Fourier expansion into the average sum 1 E.= oxf( and using Cauchy- Schhwrr inequality imply:
Σ ox,)
1 - of
Σa i=1
Σ
fxx
1
Σ
Σ
n
n
||
11:1100 SE 1=1
1s&P11=112) /
dz (x:) [3
Σ
Σ
n1
|||||
||=||0r I
||=|
Ti
d2 (X.) }}}
|=|1,0
SE
where we have used the constraint El 1 z p in the last step above. Moreover, by taking expectation with respect to the i.i.d Rademacher random variables a; (1 < & n) and the uniformly sampled data points {X,) both sides and applying Jensen's inequality, can deduce that:
E E,r
- 7
Σ
a.
f(x))
<
VP
Ex
Σ
Σ
Os (xx) ()
||
ou
vp
Ex.
Σ
th (x:)
2
||=1,o0 SE
21

---

Published as a conference paper at ICLR 2022
Using independence between the random variables of (1 n), we can further simplify the expectation inside the square root above as below:
Ex,0
Σ |=
da (x.)
| Σ
Ex,0
oj
(x,)
[
|2||
iml 1
|| sc
iml
of ||
(X,i) '
xx,e
Φ
Σ
>
[2
Σ
S ni cd
= =ncd=
|| || 121
|
Combining the two bounds above yields the desired upper bound:
Ex
Eg
sup
oxf(X,) X1, X
x VP
Vngd=2=
P V/
(22)
Lemma B.7. (Local Rademacher Complexity of Localized Trancated Fourier Series' Gradient) For fixed & E zt, we consider localized class of finctions G Gp,e(S)) = fll If E F (9)) where P > O is fixed. Then for any sample {X1) ) Q we have the following upper bound on the local Rademacher complexity:
(G, Ex
Eg
sup ((0)
Σ a (V(()
n
" x,
S Lest.
(B.14)
n
Proof. Take an arbitrary function E (S2). Let f = = SS Szt2s be the Fourier basis expansion of f. Similarly, the norm restriction condition [Ifllin I can be reduced to the following condition about Fourier coefficients:
Σ
1
||=|| SE
Moreover, substituting the Fourier expansion into the average sum 1 Ei_ of [x,)) and using Cauchy-Schware inequality imply:
Σ AVoo(X)11
a: (Vb.(()
n
||
SC
[Vo
||
|=
SE
(X.) )
Σ
|||||
|E
where we have used the constraint -] se f21 S p in the last step above. Moreover, by taking expectation with respect to the i.i.d Rademacher random variables a; (1 < i S n) and the uniformly sampled data points {X.] on both sides and applying Jensen's inequality, we can deduce that:
E ExEE
1 Eo
VP Ex
Σ
Σ
V Vo (X:)I ()$
||
SE
vP
Ex.
Σ
V
(xx) (1)
n
||=
22

---

Published as a conference paper at ICLR 2022
Using independence between the random variables of (1 n), we can further simplify the expectation inside the square root above as below:
,x,0
Σ |=11 SC
(x)
E
Ex,
a
IV
(X.3)
|
11=1
Σ
Ex,
>1
==1
4
1112
Σ
S
Σ
15ned
|=
|
SC
11
Combining the two bounds above yields the desired upper bound:
Ex
Eg
sup (S)) n
axI[VS(Xx)II
XI, Xn]
S VP
/ngd
1 /
72
Lemma B.8. (Local Rademacher Complexity of Localized Truncated Fourier Series' Laplacian) For
a fixed & E _t, we consider a localized class of functions (9t) == { (e())) ( S PJ. where p is fixed. Correspondingly, we define a localized class of Laplacians Kp.((S) {Af E (f))( Then for any sample (Xi]== C -. we have the following upper bound on the local Rademacher complexity:
Rn (n,K (9)) = Exx E.g
sup (E)).((1)
1
Σ i=1
n
(xx)(())) X1,
X=]
S V
LEt. n
(B.15)
71
Proof. Take an arbitrary function f E (.)( Let =1 fzØ: be the Fourier basis expansion of f. Similarly, the norm restriction condition [Ifllir(()) I can be reduced to the following condition about Fourier coefficients:
Σ ||
152/|1111 Sp.
SE
Moreover, substituting the Fourier expansion into the average sum 1 Er=1 A,(,).) and using Cauchy-Sehware inequality imply:
1
Σ o)((()
n
Σ o, Σ fADs(())) n
n
Σ
Σ
n
o
n
n
| SE
< Σ
Is 1/aPll=!1 3
(
Σ
Ax,( ||
||||
1=1
n
|1
where we have used the constraint Σ -||=||== <e 11 S p in the last step above. Moreover, by taking expectation with respect to the i.i.d Rademacher random variables a; (1 < i S n) and the uniformly sampled data points { on both sides and applying Jensen's 's inequality, we can deduce that:
ExL,,
TL H n
x VxEx, n
(E
(X.)
17)
2
||=1|
vP
Ex
Σ
(x,)
(1)
n
||
23

---

Published as a conference paper at ICLR 2022
Using independence between the random variables of (1 < expectation inside the square root above as below:
n), we can further simplify the
xx,a
Σ SC
| SZ (X.)
E
Ex,
oi
A (x,)
|
|
||
i=1
11
Σ
Σ
Ex,
Ax,
||=||
|| SE 1=1
16
|||||
= Σ
S n
Σ 15 ng".
|
||
|1
Combining the two bounds above yields the desired upper bound:
Ex
Eg
sup (EF),c(D)
1 -
( Xi,..., Xn]
S vD
ngd - Let.
T 1=1
11
B.2.2 LOCAL RADEMACHER COMPLEXITY OF THE DEEP NEURAL NETWORK MODEL
In this section we aim to bound the local Rademacher Complexity of a Deep Neural Network. We first bound the covering number of the function space composed by the gradient of all possible neural networks and then apply Duley Integral to achieve the final bound.
Definition B.3. Let yp denote the I-ReLU activiation function. Here we use t3 == max {0, x S & Yu,, 2018) as the activation function to ensure smoothness. We can define the space consisting of all neural network models with depth L,, width W, sparsity constraint S and norm constraint as follows:
(L, W) = (()))))(()++++++00)))))))))))) + ... (W(1) x +b (011) ER (8()) E R, (B.16)
wal E
ER wxd (RW,d E ERW, .w E wxw 8000 ERW (1 <)<L),
(B.17)
Σ(1OO + 1660))) S m,x ( v 10 s {B. 1=1
(B.18)
where -lloo measures the number of nonzero entries in a matrix and || loxc,p measures the maximum of the absolute values of the entries in a matrix. For any E Zt, we refer to an arbitrary element in ((L, W,S, as a ReLU3 Deep Neural Network. Then for any index 1 < k I L, use Fx to denote the i- R-ReLU3 Deep Neural Network composed by the first k layers, Le:
Fx = (W mp(() + b())) (W x + b()).
Also, we use & S, B) to denote the space consisting of all Fi. In particular, when k = L, we have:
F(x) = FL(x) = (W/ nT( +b()) (W/)= x + +b,)), and ( W,S, W,,
Furthermore, given that the domain 52 [0, 1]d is bounded, we have supzen ||0||/0 = 1.
Lemma B.9. (Upper bound on co-norm of functions in DNN space) For any < h: < L, the following inequality holds:
[F(()) & W (B d) bgt bak-1-1
gt kt1
sup
2
zEO, FL (L.WS.))
Proof. We use induction prove this claim.
Base cases: When k = 1, we have that for any x E Ω and any Fi E W,S,),, the following
holds:
[F) |1wf" x + 1 1o ||
(1) a0 |0 + |1
(B.19)
2 < 100,00 + B dB + B < 2BB v)
24

---

Published as a conference paper at ICLR 2022
When & = 2, we have that for any x Ω and any F2 L2(L, W. B), the following holds:
[1 nw ms(i(() + l < |M [ + |1 I WII |1 B.
||
By applying the bound proved in the case when 1, have:
[ I W B B W
W + 3d 3d + 1) B - (BVdd
where the last inequality follows from the assumption that W 2 2. Inductive Step: Now we assume that the claim has been proved for k 1, where S k S L. Similarly, for any x E S2 and any F& E (2, W, S, B), we have:
[+) = -I no + bl >0 S I bl (Fk- + +16% || 1l
S &WIMS so | [1)] + B S W ( +B.
Using inductive hypothesis, we can further deduce that:
[ S WBX
W
(BVd) 2 2 ميي
- 3346
3k+6 + B
S W
(B d)
3k+6 + BV d
3.3k sk-3 3646 + 1]
< W (B
k+2 (k2 3) 2- -
S (BV d)
(BVd)
5.3
k+1
Taking supremum with respect to Z E Ω and Fs E (x W, S, B) on the LHS implies that the given upper bound also holds for k. By induction, the claim is proved.
We also need to show that the ReLU3 activation function is a Lipschitzness functions over a bounded domain.
Lemma B.10. For any k E Zt, consider the ReReLU activation function Th defined on some bounded domain D Rd (i.e, supzed ||=1|0> I for some > 0). Then we have that for any Y.y E DD the following inequalities hold:
Im (x) m (v)l I || ylloo,
[(a(x)) 72(v))l> S 2C||z yllox:
[|)(()) - nr(1)) S 3C - ylloo
Proof. This is because Vnn (x) max 1. [Vz(2)) max(x 03l < 2C and [V)(()]] 33 max(f. (2, 0) < 3C2.
Lemma B.11. (Relation between the covering number of DNN space and parameter space) For any 1 1 k < L, suppose that a pair of different two networks Fs, GR d W,S, B) are given by:
Fs (w) (W/+)
(k) n)()) ((0)
(WF x ((2)):
G (x) == (W
(k) ()(()) b
(W0) x x()))
Furthermore, assume that the || Il norm of the distance between the parameter spaces of Fk and Gy uniformly upper bounded by ö. i.e
| (1)
-w(!) 00.00 S Ibb| - 60 1loo < 8, 1 WIS15 k).
(B.20)
Then we have:
sup [x(2) - Gx(x)llo & DW -ااعع (B BV d) مالجج =en
2 ب اريج k k+13
(B.21)
25

---

Published as a conference paper at ICLR 2022
Proof. Let's prove the claim by using induction on k. Base Case:
When = 1, we have that for any x E and any F1, G1 E D1 S, B) satisfying constraint B.20, the following holds:
(x)) - (x))ll> l x + bbp) We x - 02 x>
|100|111<00 s öd 8 = 5(d+ 1) s (8(vv)) =28(B
I 11 + +166// - -b2 1
(B.22)
When k = 2, we have that for any E Ω and any F2, G2 (2, W. B) satisfying constraint B.20, the following inequality holds:
[2)) - G2(z))l>= IM (F)) +2 (2) -
(=(G( - - 11 م| & IW - - ( + +bb - b0
I IM na (Fi W (FF( (F W (B + +
(F(((x)))
By applying the upper bound proved in equation B.19, we can upper bound the first part I (F(((())) w! (x)((=)) by:
(F((())))))))))>)))))))))))))))) - w (2(F(()))l & || W oo (P S [ S 8W [2 v d)
By applying the Lipschitz condition proved in Lemma B.10 and the bound proved in equation B.22, Vaa Fi (x)) w na (x)) by:
we can further upper bound the second part [IW]
( (z(( (o((((=)))
|| (2)
Do na (Fi (I)) 77s
7a (G1 (I))
WB
sup
[i) IR x [[F(()) - (z)
(1,
WB x 3 d) 25
248W v d)
Summing the two upper bounds above yields:
[F((z) Gz(=)ll> s (B 248W (B d) +8 (BV)'"
where we again use the assumption 2 2 in the last step. Inductive Step: Now we assume that the claim has been proved for k 1, where k 2 3. For any E Ω and F& E (2 S, B), we have that:
[1 - Gx
(k) I na(Fk-1 (0)) wi(h no (G((G=i(z)) (x)) 66 ll
S II 73 (3(Fx-1 W na G (x:) + 11//) bg 1l
(k)
S W na (F+-1(z)) - w n7 G +
Applying triangle inequality helps upper bound the first term above follows:
[ na (FF) - W (k) (z))
IM (F(Fx-1(x)) w (k)
no (F INW na (a(FF-1(s)) w (
< (WDA w a (F +I | m
@W (x)) + BW (1) na
(z))llo
From Lemma B.9, we can upper bound the first term 8W Fx ( (④) 3 by:
SW F SW
B d)
5. g
2 2 36+6
26

---

Published as a conference paper at ICLR 2022
Moreover, applying Lemma B.10 and the inductive hypothesis let upper bound the second term BW (1)) 775 (2xx=11()))le as follows:
BW [na((Fk- - 1
$ BW x 3
sup
[F x 11 (x)]le
s Fu 10 BB)
3BW 8 2-1 (B d) 6x 2- 12 -1--2444 FR (2) - G
& 3BW x - (B d) 6x3 1223"11-1-220
-1 -1-24+4 x MW 2--
(B vd)
B.st 16-1-1 2423k-2
2=
I $3h 1-1
6x8 1-1 3f 36+
(B V d)
Combining the two upper bounds derived above yields:
(BV Sigh 1-3 2 33-+6
[x) Gx(x)]lo S 88
2 2-
+ 3 sW : (BV d)
exat 1-1 sk-1
2
3k +
53 st- (BVd) (BVd 8x
3 -++1
where the last inequality above follows from k 2 3. Taking supremum with respect to E Z on the LHS implies the given upper bound also holds for k. By induction, the claim is proved.
Theorem B.4. (Bounding the DNN space covering number) Fix some sufficiently large N E Z+ Consider Deep Neural Network space (LL W.S, B) with L O(1), W O(N),S O(N) and B = O(N). Then the log value of the covering number of this DNN space with respect to the inf-norm [2)())) == sup Fx)),, which is denoted by (6, (L, W, B), lloo), can be upper bounded by:
log (6, (L W. B) (1.0) = (0ss(o0g(00)) + log( (BB)
(B.23)
Proof. We firstly fix sparsity pattern (i.e, the locations of the non-zero entries are fixed). By picking k L in Lemma B. 1, we get the following upper bound on the covering number with respect to || oooo
5
3 1h-1-1
vVd
L+2
Furthermore, note that the number of feasible configurations is upper bounded by ((++))+) s (W + 1)r.5 (Schmidtt-Hiiiie Hieber al., 2020; Farrell al., 2021) Plug in the previous inequality and yields:
log (00 ((,, B), 11x0) s log
(W +1)
2 ب L+1
34-1W
(BV d)
8 1- + 13-3 1-|
(BVd) d) 2xاh-1 -1 2 a L+1
< S log
x log(ō log 33 1og (B d)) + +34 log
Note that here the dimension is some constant. Thus, by plugging in thee given magnitudes L -= O(1), W O(N), S O(N) and B O(N), we can further deduce that:
log.N(6, (L, W, B), || (1~)) s s ((1og(0=)) 3 log log(W (WB). B))
This finishes proof.
Now let's consider upper bounding the covering number of the norm of the sparse Deep Neural Networks' gradients. Note that for any 1 k < L 1, any &-ReLU3 Deep Neural Network FR E (T, W. S, B) is map from Rd R For any < I < W. we use (x:) denote the
27

---

Published as a conference paper at ICLR 2022
1-th component of the map Fj. This helps write the map Fk(22) and its Jacobian matrix ( explicitly as:
ERRW (((2) = [x), Fk,2(2)),.. ... FR,
8m (x))
a (2)
8r. 1x) 2
2
B8z
(x)
á Fk,((z)
[[Fa((r)=
8m1
80g
E ERWx
8 (x)
kr (a:) das
a
0 FR (x)) dz.
3an
In particular, when L, have that any FL E LL W. S, B) (L, S, is map from Id to R. Thus, its Jacobian can be explicitly written as the following row vector:
J[FL](a)=
( Ox
(x),,,
FL(x),
F
Ox
Ozd
Lemma B.12. (Upper bound on oo-norm of Jacobian/Gradient of elements in the DNN space) For any $ < L, the following inequality holds:
W (BVd) 3igk-1 -6-1 1+1gk-1
sup ZEQ, (L..
Proof. We use induction on l to prove the claim. Base case: & = 1. By the definition of Jacobian matrix, we have that for any x E and any Fi E 4 (L, W, B), the following holds:
[)] || ddB S V(BV
Inductive Step: Assume that the claim has been proved for k 1, where 2 < k S. L. For any (L,
and any F& E 4 (L, W, S, B), by applying the Chain Rule, we can write the Jacobian matrix
[[Fr)(z) as (x) w (k) J[ms Fa-1((x), where the ReLU3 activation function is applied each component 1, (1 s i W) of the map Fg. Then we have the following upper bound:
| V [ I1 F S [B] F
(B.24)
Note that the composition o F is a map from Rd to RW. Hence, the Jacobian matrix J[ns FR-1) ((x) of shape W xd Applying the Chain Rule again implies:
(11((F-111()) F (Fx11.(1))) ISISW
1| F
sup
Furthermore, for any < 1 W, the summation on the RHS above can be upper bounded by:
Σ (3 (F)=(F)))( 0F FFk-11(z) - ( dz, (x))(()))
F( (
dx,
Now let's take supremum with respect 1 and apply the inductive hypothesis and Lemma B.9. This yields:
[|] FR I 3w33-33 (BV d) 2/3.3--2 -1288 12-244 x W (BVd) 6.4-2 gh-1 k+2gk-2
W st-
(B d)
5.gt- sk_1
-12 -222 -3455gh-1
(B.25)
By substituting equation B.25 into equation B.24, we can derive the final bound:
|+)))())) WBB Fx-1](=)|1> S w x4-1-1
5.gh-1 -4 33
(Bvd)
< w
(BVd) B-g--
k+1gh-1
where the last inequality above follows from k 2 2. Taking supremum with respect Ω and Fù E (L, W. S, B) on the LHS implies that the given upper bound also holds for k. By induction, the claim is proved.
28

---

Published as a conference paper at ICLR 2022
For the convenience of the following proof, we first prove this lemma for vector 2 norm and co norm.
Lemma B.13. Given any two row vectors u, v E IR1xd, we have:
||a]||
||
Proof. Assume that the two vectors u, v E Rd can explicitly written as u = [11, u2, 1 , Ma] and inequality, we have:
[U1, U2, :.- u2. val, respectively. By applying
||a|||
|0|||
d
2
u
1=1
1=1
d 2
14
2
0100%
1//
1=1
1=1
11
1 00
Taking the square root both sides yields the desired inequality.
Then we upper bound the Lipschitz constant of the gradient of the neural network. Given a DNN space & (L, W, B), we define a corresponding DNN Gradient space ( W.
B) as:
VO W. S, B) == (IVF E W,,,W, B)).
(B.26)
Lemma B.14. (Relation between the covering number of the DNN Gradient space and parameter space) For any S k L, suppose that pair of different networks Fk, GR 2b W, W,S.D. B) are given by:
(W b(1); Gx (w (s(+)) (()) (W x xb))).
(x) = (W(+) (s()) b(x)
(k)
Furthermore, assume that the oo norm of the distance between the parameter spaces is uniformly upper bounded by i.e
|W
w 11 00.00 56 |b - @ ao s 8, (ISSsM) k).
(B.27)
Then we have:
sup [J(FL](z)) - J[)x[())ll> & oW 34-1 aEf
5.3 11 14 k +1122k22
(B BVA d)
2
(B.28)
In particular, when k = L, have:
[VFL - [VGz < <8W 31-
(B d) بيددع
2- 2 1+11211-2
sup
(B.29)
sEN
Proof. We use induction on & to prove the claim.
Base case: When & 1, we have that for any Ω and any Fi, G1 E W, B), the following holds:
||[F]((>) - |z) = Iw w l < < 28 2 v d)2.
Inductive Step: assume that the claim has been proved for 1, where 2 < k < L. Then for any x E Ω and Fk, G& E (L, W, B) satisfying constraint B.27, applying the Chain Rule and
29

---

Published as a conference paper at ICLR 2022
triangle inequality help upper bound the inf J[C,[(((]
[J[F)(()) - (z)l> = !! J/s o Fx-1((x) - J J[ns Gx-
! J[ns o Fx-1 w/o J(ns F || J/ns Fe-1l(z) - W Jins Gx-Il())l
IW W 11 - Fx + 1| Fx-1((x) J[ms Ga)l(cr)lle
Σ JWi]J o F + BW [J[ns o Fk-1((x) - J/n Gx)
(B.30)
Using equation B.25 helps us upper bound the first term by: 2 =--1-1 SW W fz) S SW
(B V d)
2 M
-kttsgkk
(B.31)
Note that the two compositions 7)s Fk-1 and 77s o Gk-1 both map from R.d to RW, Hence, the two Jacobian matrices J[n (x)) and J[1 o Gk- (z) are of shape R Rwxd Applying the Chain Rule again implies:
(FF(FF1,,(()))) OF 312 (()) Oz.
[1 Pk-1](x)- - J Inn o Gx-1l(2)llo
sup ISISW j=1
l).
Ox,
For any 1 S S W, the summation on the RHS above can be upper bounded by:
(72((Fx-1,(())) FFg-1.(2) (1)(Gx-1,1zz)) 8G 8Gk-1a dx,
dr,
1312 FR (x)) 0 OFk-1.(2)) 312(G2=1,1(z)) 0 1 Ōrz
dr,
OF (F)))1()) 312(Gk-111(0)) (3)2((k-111(x))
0G (.()) dr,
dz,
1=1
13m (1x( 31p (nx(Gr=,,(z) (Fk-
[32((GA-,,(z)] 0F, 01)-11(()) 00k-1,(1)) 0z,
dz, j=1 We denote the two summations above by Ti and T2, respectively:
dz,
1=1
3322 (Fx--1 - -31p(Gk-11111)) 0 (F5x11(2)) Or,
T = j=1
1312 (3+=(G=-1,())) 0Fk-1,(x) 1,k=1,(xx) Ōr,
T2 :
0x;
j=1
For the first sum T,, applying Lemma B.9, Lemma B.10, Lemma B.11 and Lemma 1. yields the following upper bound:
OF. (F)-1,1 On,
T <
sup ref, F2-1 I0..
1 (x0)) (1 - GR (x)]
f=1
<6
sup rEN, F 1
|P
(x) - Gh- Gx-1
2-1 (BVd) sish 2- 3k 1-1
2 - k+2 x ow sh 2-1
s.sk 2- 3h 1-1 k+ k+
3 x W
B V d)
2
dBvd) سタrي 2 - ++2gh-2 sw
- (B d)
2 ا 2 -
For the second sum T2, applying Lemma B.9 and inductive hypothesis yields:
T3 3
sup rEN, Ge-1E0 (G-1E0,,11L,W.... (L,WSS,B)
|[G=-(())| (|J - J[Gr-1l(=)lle
<3 x 303 (B d 5.:3
2 2 -22222 1200 22+4 x SW 2t 2-1 (BVd)
sish 2-1 st
= = 1-( (BVd) d)) 2-
2 -3
30

---

Published as a conference paper at ICLR 2022
Combining the two upper bounds on Ti and T3 yields:
312 (122(Fx-11(z)) 0F 0F)-1,(z)) Jxy
3rp (G)-11(z)) 0Gk-1.16
dr,
Ti +2 22 x Me (B ملا مجم
3k- 3k+ 2
By taking supremum with respect to 2 W on the LHS yields:
Da
2 - 36+622k
[ Fx-1 - J/ns o Gk Gx)ll - 6W
(BVd)
(B.32)
By adding the two upper bounds in B.31 and B.32, we can deduce that:
[[][)](()) (z)l 2 8W +
Sigh-1
2 12 2
B V
(B 5.8k11
2 2-
+ +W
3 OW -h-l1
5.gk
2 sk k+ 1322
(B V d)
where the last inequality above follows from h 2 2. Taking supremum with respect to x E 9 on the LHS implies the given upper bound also holds for k. By induction, the claim is proved.
In particular, when k- = L, we have (x) = J[Fr](z)) for any x E Q. Applying Lemma B.13
then yields:
[VFF(()] || [+)[
|>[[L[(=)*| -
sup =E
sup
=E
< sup [[[[[](x) J(Gr\(=)1l
=E
I sW د
B 1 2 12222
( (BVd)
This finishes our proof of the Lemma.
Theorem B.5. (Bounding the DNN Gradient space covering number) Fix some sufficiently large N e S,S,B) B) with L = and B- = O(N). Then the log value of the covering number of the DNN Gradient space with respect to the 1l norm [F(x) == supzeo [x)),, which is denoted by (8,, V W, B), lloe).
Zt Consider a Deep Neural Network space (L, W,S,
S O(N)
can be upper bounded by:
log W,S, - (5((og(00)) +3 3og((B))
=0
(B.33)
Proof. We firstly a sparsity pattern (i.e, the locations of the non-zero entries are fixed). Using equation B.29 in Lemma B.14, yields the following upper bound on the covering number with respect to :loo
5
W (Bvd) 5.34 34
1+ 121
Furthermore, note that the number of feasible configurations is upper bounded by: (W++))+ S (W + 1)L5 (Schmidt-Hieber et al., 2020; Farrell et al., 2021). Plug this inequality into the previous estimation then yields:
16, ((,, B)S, 1bx)) s log
(W +1)
2 ي 1.+ 1-22--22
W
B d)
< log
[-- + 13 2 (BV
3z 1-8-1 2 24 -277
$ S 1og((-1)) 2L (3W) 36 (W d)) + 3 log 2]
Note that here the dimension d is some constant. Thus, by plugging in thee given magnitudes = 0(1), W = O(N), = O(N) and B = O(N), we can further deduce that:
log.A(6, (L, W.S, B), || (l $ s log(6-') + 3 log(W B))
This finishes our proof.
31

---

Published as a conference paper at ICLR 2022
Now let's consider upper bounding the covering number of the Laplacian of the sparse Deep Neural Networks. Note that for any I & I L 1, any k-ReLU3 Deep Neural Network FR E Lx(L, W, S, B) is vector-valued function mapping from F to R". Moreover, define the Laplacian of Fi (z). which is denoted by [FFi](x)), as follows:
[[F = [A (I), (F)2(z), ... .. AFkw(E)) ER"
where for any s W, we have:
0² (F) Σ 2mg Fa,(
In particular, when k = L, we have that any FL E ( W, B) S,S,W B) is scalar- valued function mapping from I& to R. Thus, its Laplacian can be explicitly written as:
d
82
A[FL](=) (FL Σ FL(x).
For both Lemma 1.15 and Lemma B.16 below, we consider a fixed Deep Neural Network space (L, W,S, S, B) with L = O(1), W = O(N), = and B O(N,, where N Z is fixed and sufficiently large.
Lemma B.15. (Upper bound on co-norm of Laplacian of elements in the DNN space) For any 1 S k S L, we have the following upper bound:
[ = 0(
W stm (Bvd)
sup ZEQ, FEO,FEER (L..F...
Proof. We use induction on & to prove the claim.
Base case: A Note that any F1 E Φ1 (L, W,S, B) is a linear transform, so the Laplacian (IF](x) must be the zero vector for any x E Ω. This implies:
||] 0 - (Bv d)
Inductive Step: Assume that the claim has been proved for k - 1, where 2 < A: S L. For any x E Ω and any F& E &n(L, S, B), using linearity of the Laplacian operator implies:
B),
[[F)((z) = w A/ns o Fb-1)(x).
Taking the inf-norm on both sides of the identity above implies:
| [+)]((>)) S [I || ||1/ F S WB|IA[ms F
now remains to upper bound the term A [77 o F&- Fx-1(())llo- For any 1 1 & W, we will use the
Chain Rule to write the 1-th component have:
A 1173 1
in an explicit form. For any S j S
i
dx," (3 (F (1, dx,
Fi F1-1.(2).
Differentiating with respect to z, on both sides above yields:
02 daz nal F = (F θ Fx FR-1.((x) + 31a [F (F))) du
8²
F Fa-1)(1). (B.34)
0z,
Summing the expression above from j 1 to d implies:
d
0²
(Alos Fa-11(1))
Σ
ns Fx (x))]
da?
6m (Mn(Fx-1,1())
d Σ
+ 3na.Fa Fi-
Σ Pa 11
d
82
Duy
1=1
3=1
2
6 [x(
Σ
②
Fr m
+3 +3/mofh-111110
Σ
82
P (2)
Day
32

---

Published as a conference paper at ICLR 2022
We denote the two summations above by U1 and U2, respectively:
2
U1 = 6 Fk (1))
a dxy
Fh Fh-uu(t))
0² Ozg
U2 = (alFF=1,1
Σ
F Fx-1((x)
On the one hand, by applying Lemma B.9 and Lemma B.12, we can upper bound U1 by:
U1 U.56 6
| |1 -E
|][fe-1](<)]l
sup (L,
sup
SEN, Eh
<6 kk2
W ( d)s.st -1- - 2 -
(BVd)
(BVd)
where the last step above follows from & S L and L ((1. On the other hand, by applying Lemma B.9 and the inductive hypothesis, we have:
[[ ) Í Fi Fx=)((
U2 5 3
sup
ZEB, F (L.,1,,.
3x W 2-1 (B -223-
W 1t
[ d) 5.sk-2
$ w (B
5.ak
where the last step above follows from k S L and L= O Summing the two bounds on Un and U2 implies that for any 1 S W, we have:
( o (()) )|
(B d) 2
< Un + U2 w
(B.35)
Taking supremum with respect to 1 < < W then yields:
||[F](()] S W o Fa-1](=)llo S W (BVd) d)
Taking supremum with respect to z E Ω and Fs E Φx(L, W, S, B) the LHS implies that the given upper bound also holds for k. By induction, the claim is proved.
Lemma B.16. (Relation between the covering number of the DNN Laplacian space and parameter space) For any < l < L,, suppose that pair of different two networks FR. Gk E (b W, B) are given by:
(x) = (W (1(() + ((2)
(W bb.)) ((2))
G (x) == (w(h)) (k) nT(() b (1) ... (W x +b))
Furthermore, assume that the || oo norm of the distance between the parameter spaces is uniformly upper bounded by i.
|W (1) w: (1) 100.00 26, 1b
(1) 1oo0 58, (VI
(B.36)
Then we have:
sup [x] = = 34 - -1
(B V dd 1لا
(B.37)
Proof. We use induction on & to prove the claim.
Base case: & 1. Note that any F E 4, (L, S. is a linear transform, the Laplacian A[Fi(xz) must be the zero vector for any x E Ω. Hence, for any x E Ω and any F1, G E Φ (L, W. S, B), we have:
= [|[F)(>>) =
33

---

Published as a conference paper at ICLR 2022
Inductive Step: assume that the claim has been proved for l - 1, where 2 2 k S L. Then for any x E S2 and Fx. G3 E L2 W, S, B) satisfying constraint B.36, applying linearity of the Laplacian operator indicates:
[|[F]()>> - [G = l AnTs o FR-1I(() W Alns o GR=
( w Alns o Fx-1
+ | (Alma o Fi- 1zxx) - Ann GR- GR-il()) I.
= I - we I hn o Fz)
+ I 11 | || Inn 1 Ann
Gk-
For the first term IW
(/6 |1 A Ims Fa-1 bo applying the bound in equation B.35 and
equation B.36 yields:
IM Ilo F--
F--1((=)11 S oW x W
(BVd) 1-
(B.38)
= sw (Bvd) 8-3-1-88
For the second term [ Imo |A Fh- [1x) Alma GR- we need to upper bound
the norm || [m o F Fx-1](z)= - AlTs o Gz-1[(z)]l
oo at first. Note that for any 1 < 1 & W, we can
use equation B.34 to write the I-th component of A/13 o Fk=1 - Amss o GR-1)(z) as:
as:
0²
d
82
(Anna Fx=1 A/1a o GR=1l(1))
Σ
nal Fa- - (1)))
1/3 (G=))
on
=6 [B (x))
Pk- 11(x)) 2 -mn IG)-
Σ
d
0
Gn (nn,l)))
j=1
j=1
d
82
d Σ
82
+ 1-3m1(FF-20 (x)
F (x) - -31/2 G 11(x)]
Gk (x))
dmy
Ong
j=1
|=1
=6 [F 1, (x))
Σ
F (1-))(1))² - -n (11(Gx-1,(1z))
Σ
F (w))) 2
Ozy
/=1
j=1
+ 6m (x))
Σ
Da. FR- ((-))())) 2 -m (1-=11(()))
G Go-))())) 2
/=1
j=1
82
02
+ 3122 FR (x))
P (1= - -3112 -3 Ga-
Σ
Fr
(x-1,(())
j=1
j=1
d
82
d
82
+ 3/2 1.- (z)
Ph- 11-1,1
3/122 11122 (k-
Gk Gk-1,(1).
On7
j=1
We denote the four summations above by V1, V22 V/ and V4. respectively:
1/2 = 6m (Fa_1,11...10 (x))
Σ
Fk F(-1)(1)) 2 6n (x)
9
F F
dr,
dr,
F=1
5=1
V/2 = 6m [z))
② Fo-Lu(00) 6m [G (x))
Σ
Gk Cl--1101)3 ?
Or.
Ozy
j=1
d
8
d
0²
V3 = 31p Fr. (x)]
Fk
- 3322 Fx-1,((x)-
Fr 7x-1,(3),
Ox3
0x3
j=1
j=1
d
82
02
V4= = 1=:3) 332 (1-
Σ
Fk (x)) - -372 332(Gx=11,
Gk-1,(Z).
]=1
==1
34

---

Published as a conference paper at ICLR 2022
By applying Lemma B.9, Lemma B.10, Lemma B.11 and Lemma B.12, we upper bound V1 by:
d Fo)),(()))
Vi - 6 ((((FF-1,,())) - m [G [GR-1,(z)]
Σ
Fk
2
j=1
< 6]FFa.11(2) - Gh Gx-1,((0)
i
Fk ((()))
s
go.
< SW
(B V d)
k
2-1 V - --123" -1-2t+ig--
2 SW dB
where the last step above follows from A S L and L -= 0(1)
Furthermore, note that for any S j S d, we can upper bound the difference
(
a Fa- Fi-1)(a)) Deyy
2.G GALLL)(() 2
as follows:
ūzj
0r, (2 (0)0)
2 -
( Fu (u))))) - a (2)G0111))))
jzj
Ozg
(ax,
0
θ GA-1.(x)
Fk Fk-1,(z) + Gb G2-1a(z)
Fk F1-1
(B.39)
Ozj
dxig
Ozz
(1 @nn,
Fk Fz-111(x)
+ (o-sl(o)) Ozz,
2 FR (R- dr, dzz
d Gk Go-zllo)
Note that 771 (x))
2 0. Combining the non-negativity with equation B.39, Lemma B.9,
Lemma B. 12 and Lemma 1.14 helps us upper bound 1/2 by:
V/2 = 6m (0x-1,(()))
Σ
d
a Fk- 1,(x))
-Oxx Dxy Gk G)),,(()))
j=1
66 (x)
Σ
Fk (x-1,(xx)
+ Dox
O Ck-ry(o)))
0 F1-1,(1)=
a
G GL)
Oz,
0xx
Oz,
j=1
(F))lo
Σ
d
Fn (x)
+ Σ
d
comssleo) ,ir,
d Σ j=1
Fb-1,(0)-
Gk Ga-ula)))
Oir,
Ory
Ox,
j=1
j=1
< G6 1o [[[(P=Il(<))16 + (G 1000) || J| 1(()) - JK
2 -- - x 2W ---2-1 (BVd) V d)
- g6-ي k+
< 6W (Bvd) d)
(V Digk 2 ++1g2k S 8W 8w 14اي
zat-1-a
x sW
(BV d)
where the last step above follows from k < L and L 0(1)
Moreover, using Lemma B.9, Lemma B.10 and Lemma B. helps us upper bound V/ by:
02
V/= = (312(Fa- - 372 (12())_
F
(,(x)
dx?
j=1
82
< 3m (mm[Fx-1,(x]] 317 |G
Σ
F (z)
Ouy
3=1
< 6
sup
Fx-1 (1)1(
|1 (z) - -G--16+11
JEft F -1,1E0_-1L,,.S.,) (L.W,S,B)
< 6W 14-2
(BVd) 6.gk-
g 94-1 k+2 x SW
B يا-ع -
(BVd)
2
S SW 3
5-ビ-1
x W 2
(BV. V d)
(BV d)
2
35

---

Published as a conference paper at ICLR 2022
where the last step above follows from & I L and L = O1).
Finally, applying Lemma B.9 and inductive hypothesis helps us upper bound V by:
8²
0²
V4+ = B Σ
k- (2)
Σ
GLL((()
duy
duy
1=1
1=1
(=)))11)))11 /| FR. (2) - A
2 33 (B V - 22-44
28+4 OW
(BVd) d) 2-86-2-1
SW : (B -ー
where the last step above follows from k S I. and I. I= Combining the four bounds on V1, V2 V33 and V11 implies:
Alv3 o Fa- - (naa o Gk- Gn-1((a));
Σ Vis ow (Bvd)
S.sk
Taking supremum with respect to < < W gives us an upper bound on the second term [I |n o Fa-1](x) - a o G (z))lo)
Il FR-1((=)= Anss GR S WB ow
(B V d)
5. 1-2
SW
(B
(B.40)
Combining the two bounds derived in equation B.38 and equation B.40 then implies:
(B VBVd d) B.sk- a
+ SW (BVd) b
[|][F]((z) - A S sW
S ow sh-
1-ct-ي11 (B d)
Taking supremum with respect to a E Q on the LHS implies that the given upper bound also holds for k. By induction, the claim is proved.
Given a Neural Network function space L(L, W, S, B), we define a corresponding Neural Network Laplacian space (L, W, S, B) as:
( := (AF) F ((L,W,,,
(B.41)
Theorem B.6. (Bounding the Neural Network Laplacian space covering number) Fix some suffi- ciently large N E Zt Consider a Deep Neural Network space (I,, W, B) with I, = O(1), W O(N).S O(N) and B O(N). Then the log value of the covering number of the DNN Laplacian space with respect to the || 1loo norm [[(())) == supzea [P(x),, which is denoted by (6,, (L, W. S, B), -1- lloo), can be upper bounded by:
log.N A L. W. S, B), 11- (loo) O (0($ (s(10g(8-)) + +34 + log(WB))).
(B.42)
Proof. We firstly fix a sparsity pattern (i.e, the locations of the non-zero entries are fixed). Applying Lemma 1.16 yields that there exists some constant C = O1), such that the covering number with respect to || ol can be upper bounded by:
5
CW (BVd) V d)
5.36-1
Furthermore, note that the number of feasible configurations is upper bounded by (W++))* < (W + (Schmiidt Hieber et al., 2020; Farrell et al., 2021). Then we plug this into the pervious estimation and yields:
log (L, W. S,B) (1x0) < log
(W (W+1) + 1)
1-1 26 2 CW
534
1
B V
d
3
< S log
(8- -1'
16-1
B
< s log(8-1) L log log(W) + 30
log W (B d))
36

---

Published as a conference paper at ICLR 2022
Note that here the dimension d is some constant. Thus, by plugging in thee given magnitudes = O(1), W = ( = O(N) and B = O(N), we can further deduce that:
16, A (L, W, B) - (1xo) z $ log(6 + 34 log(W B)].
This finishes proof.
Lemma B.17 (Local Rademacher Complexity Bound of DNN Estimator for Deep Ritz Method),
Consider a Deep Neural Network space F(2)) = (L, W. B) with L O(1), W O(N). O(N) and B = O(N,, where N E Z* is fixed to be sufficiently large. Moreover, assume that the gradients and function value of F(2), u", and J are uniformly bounded
max
sup NEF(()
[|))
sup WEF(()
[Vu]
(1), (1="|l==())) Vu"lllo> (0), Vmnns |I [ S C.
(B.43)
For any p O, we consider localized set Lp defined by: Lp( == uu: F(S)), ||u - u u0 S p}.
Then for any p Z 2, the Rademacher complexity of localized function space S,( = {n = [9] [Vull=-Ilve 1| IP) + ((22222 - 2V - f(u f(u-u") w²)
u E Lp(11) } can be
upper bounded by a sub-root function
((p)==0 (v
S33
((p) ==
log (BWn)
ie. we have
((pp) 20(()) and R. (S) s d().
(B.44)
holds for all p 2 -2
Proof. Firstly, we will check that for any (2)), the corresponding function h in Sp2) is Lipschitz with respect to u and | - [| Note that for any uj U2 E ( with corresponding functions hi, 1/2 (2)) applying boundedness condition B.43 yields:
1
+ 1
[x)(x) - hx2()) Vu, (x)] (u2(>))1
5 2
+ (())l (2)) [(()))l ug(x))
C
Vuz (x)] - (x)] + (C² + C))u(()) - u2(x))
C
( (x)] (x)]] - (IV (
- [v)(())))
+C² + C)
(u1(x) ())
(1z(x) - u'' u'()))
Let's pick T- C2 + C > C. Applying the Talagrand Contraction Lemma B.2 helps us upper bound the local Rademacher complexity R, (?)) by
R, (S,( = E,
sup LE T
1
oi 2
[uul (1Vu||--1VVulp)
1|
1 V (lul -lo02 1(u wi}
1 n
o (((x)) (xx)
< L.E
sup (E)
n
of [[Vu(z))l (1V
sup (RL, n
$ Rn (fu-u.:ue (u-uu:uuly Lp] + Rn [ Lo))
From the localization constraint 2 ||u Ilu-ue -uu-ull || (1 = ||u wIu-="112: 112 + +l/Vu Vu- 12 we can
deduce that
||u u" ( S vp and Vuu Vn'Il22(0) S Vp.
(B.45)
37

---

Published as a conference paper at ICLR 2022
Moreover, note that ? C [0, 11". Applying triangle inequality yields:
1/1 Vu(z)]] - (x)"(())] dr - 1 [Vu(z)) (x)(2)
V - || (2(0)
=
= =VVu - Vu" 1 sー ||/||- 13(00) S VVD
(B.46)
Using inequality B.45 and inequality B.46, we have:
(a & Rn (fn 1u-ww u. k2]) + Rn ([1VVu)) - || : b,7)
< Rn {u u² u LLL W, B), - l|llllullae = S vp))
[[V VV E ( W, S, BB) -
12(0)) S voo)
+ Rn
(Geer & van de Geer, 2000; Rakhlin et al., 2017) showed a "upper isometry" property. where the metric -| -l|z, is equivalent to -| 1lx.2 with high probability. Combining this fact with Theorem B.3, we can bound the local Rademacher complexities using Dudley integral:
Rn (S,)) X Rm
(( u u² : u E LL B), IIu - u' v'1l S vD))
{ilVu|I - || : uE (L, W. B). |2 |V (7(0)
S vD))
+ Rm
(u--'' : u Q(L W. B). v' 21l2 22v2))
$ Rm
(llVulI |u ||: u E (L. W, B), |ul - ||
$ $2v7}
+ Rm,
n2
12 2VP
inf
{4xx +
Vog.N(8. (1, W.S, B), 1l22)dd
0Ca<2,0
Vn
Jn
12 2/0
inf {la + 0<a<2V7
V Vog.N(6. VolL ld,
Vn a
12 2/8
inf ocac2vp
(4a +
VOL 11 d8
Vn
aa
12 2/8
inf 0<a<2/0
{4a +
VlogN(6b, VDL, || ddō}.
Vn
For any p 2 a.. we pick a = 1 n
x vp and plug in the upper bounds proved in Theorem B.4 and
Theorem B.5, which implies:
1
2/8
/ 1og(6- + 34 l) dō + |.. f 2 / log(b-1) + 34 log(W B) d8
1
R, (S) 1
Vn
53
P n
log (BWn).
Lemma B.18 (Local Rademacher Complexity Bound of DNN Estimator for Physics Informed Neural Network). Consider a Deep Neural Network space ((.)) = (LL, W,S, B) with L = O(1), O(N), ONN) and B O(N), where N Z+ is fixed be sufficiently large. Moreover, assume that the gradients and function value of F(22), u², V and f are uniformly bounded
max
sup uEF(O)
[|)]|==())
sup WEF(R)
|| ||"" (1 || All""llll (2), Vmans || [1] } S C.
(B.47)
For any p O, we consider a localized set M, defined by:
M2) {u:ue F(22), ||ue u" u"llirs S s).
38

---

Published as a conference paper at ICLR 2022
Then for any p PZZ. n the Rademacher complexity of a localized function space To( == {h == [2I-[(Au - Vu + f)² (Au" Vu" +
f) u Mp(1)) can be upper bounded by a sub-root
function
x(p) :0) (0V
(v |S3'p log (BWn)
Lec we have
<(4p) S 2)(p) and R. (T) S <(p).
(B.48)
holds for all p 2 n-
Proof. Firstly, we will check that for any E LP(), the corresponding function I in Sp()) is Lipschitz with respect to u u-u" u² and Au Au". Note that for any u1, U2 E Lp((2) with corresponding functions h1, h2 E Sp()) applying boundedness condition B.47 yields:
Ih (x) - h2(x)) < Aun - Au2 - V(u - A2) - Vmn + Auz - A + 2ʃl
- (2C + 4C) (Auu Au2l + Clui u2l)
(2C + 40) (Au( (x)()) (Auz(x) - Au)
(2C* 109) (wi (()(()='')) (x)) - (u2(#) u" (z)))}
Let's pick max 4C, 20 +4 Applying the Talagrand Contraction Lemma B.2 helps us upper bound the local Rademacher complexity R, (T)) by
(T)()(())) = E2 E.g
sup (E) 1=1
di [(Au - Vu+ f)2 (An" Vv=" + s)
1
[((x;) - u ((x)))
< E,,
sup (E)
i=1
o Au(z)) - Du (at))
+ E.,
sup
MEM, (R)
1=1
U. E M, }) R, (fau- - Au" : u (fsu-Au': M2
$ Rm
S Rm u² LL, W.S, B), (u- (u-w"lllsaa S vol)
Rm (Auu Au" u ((L. W. - S vDJ))
R, (fu {u-un² n" u ob W.S, B), || 1u- "/,,, & 22
RR, ((Au- Au" uu
W. B), W. 1n, S 2/7})
12
208
inf Ocac2pp
{4at +
/o8N((..0L...55B,,II1 1m,
Vn Ja
12
2V8
inf
{4a +
/IoNN6.A0 1d,
0<a<2,7
Vn
12 2V7
inf
(4a
/logN(0, dd
oca<228
Vn
12 2/2
inf {4xx +
Vlg
1,, W). 1 )d5
oca<2.8
Vn
Ja
39

---

Published as a conference paper at ICLR 2022
For any P 2 n², we pick a 1 x vp and plug in the upper bounds proved in Theorem B.4 and
Theorem B.5, which implies:
2/8
1 S log(d-1) 1) + 34 log(W B) d8 + v / Jav | [ log(0-)) + 3 log(W B) d6
R (T (9)) S
S33 P
log (BWn).
n
B.3 AUXILIARY DEFINITIONS AND LEMMATA ON APPROXIMATION ERROR
B.3.1 APPROXIMATION USING TRUNCATED FOURIER BASIS
Lemma B.19. Given > and a fixed integer & E zt, For any fincction f E ( we let f& Se f= be the best approximation of f in the space Fş(S)). Then for any B S a we have the following inequality:
Ilf ff-fellimne fellim(o) 25-20--111111
Proof. For f E (S2), we know the Fourier coefficient satisfies
Σ If |1211 S Il
We directly construct f& = Σ || se Seb to be the truncated Fourier series of the function f, then we have
If fell fe 2
Σ
|f || S 2(a
Σ
|5/111=11000
SE 2(a 2(a--)) f1
||*1|022
||
B.3.2 APPROXIMATION USING NEURAL NETWORK
In this section, we aim to provide approximation bound for deep neural network. Our proof of the approximation upper bound is based on the observation that the B-spline approximation(De Boor & De Boor, 1978; Schumaker, 2007) can be formulated as ReLU3 neural network efficientlySuuzuki, 2018; Gühring al., 2020: Duan et al., 2021; Jiao et al., 2021a). Although the proof of the approximation of the neural network to the Sobolev spaces is a standard approach, we still demonstrate the proof sketch here.
Definition B.4. (Univariate and Multivariate B-splines) Fix an arbitrary integer I Z+. Consider a corresponding uniform partition of [0, 1]:
mi. : = 11 (1) <... (
=1,
where ( = 15000iS Now for any ls Z+, we can define an extended partition Ti,k as:
(1) :t=k++ .... 0 = 1
12 1
())
(1)
TI,
1 = t
14k-1'
Based on the extended partition Tt, the univariate B-splines of order ls with respect to partition m are defined by:
N(A) (x) = (-1) -(()) 1000
(0)
max((I +), E 10, 11, i 4, (B.49)
where I1,k = f-k + 1, -k + 2.... ... ,1 - 1} and (1(1) ... ,. (1 denotes the divided difference operator.
Equivalently, for any E [0, 1). we can rewrite the univariate B-splines (²(0) (x) in an explicit form:
(--T) O (- (-1) 1)(()) max { - -0 (0si5l- 1: +1
1/ (x)
Σ j=0 Biy max {o- {.03 +
k-2 bm + b,o (-k+1<is0
(B.50)
E -41 Gij max for - (1-k11sis-1)
k-1
40

---

Published as a conference paper at ICLR 2022
where - - j - are some fixed constants.
-1
-
2) and
{ci 1 +
For any index vector i (i, i2....
.i)) E 12 we can define a corresponding multivariate B-spline
as a product of univariate B- B-splines:
(1) 1i (z) (z) = -T
(K) 1.g (xz)-
(B.51)
Definition B.5. (Interpolation Schrmmakr, 2007)) Take some domain Q2 [0, 1)dh and two arbitrary integers k. E Zt. Consider the extended partition Litk and the corresponding set of maltivariate B-splines {NL (x)),,, defined in Definition B.4. For any 1f we define the domain Ω4 = fær E Ω2 zjj E [ tiy, 1 S j S d}. There exists a set of linear functionals Ddeliegg, where X L' (Q) R (Vi E IE,)) such that for any E Ig, and p [1) we have:
Xx(N = 54,j and [x((f) & goth 1) (2k + 1) " "Ifle Vf L2)).
(B.52)
The corresponding interpolation operator Qk is defined as:
Quii= MMON (.))
Theorem B.7. [(Schumaker, 2007)] Fix f E W*( with Ω S [0. 10.1 Zz and p (o).
Then for any k,,,r r & z with k 2 and 0 S r S 8, we have that there exists some constant C = C(k, 8, v,P, d), such that:
If - Qu-ffflll S c S-T II
Theorem B.8. (Approximation result of Deep Neural Network) Fix some dimension d E Z+, some
domain Q C [0,1] 1]4. We pick some N'à 2 2, for any 8, E Z+ with 0 S r S 8 and any function H9))), there exists some sparse Deep Neural Network upNN E 4(L, W. B) with L = O(1), W = =ON), O(N), O(N). such that:
||NDNN u 11 & N 1 |1"1
(B.53)
Proof. We firstly show that the given function u" can be approximated well by some linear combi- nation of multivariate splines, which is denoted by usp- Note that N is assumed to be sufficiently large. Hence, we may pick 1 = 1
((v2) z be the partition size of the B-splines. Moreover, by picking A = 4 and = 2 in Theorem B.7, we have that the linear combination Map = Q4,1²" Eierg, A<("")N(' satisfies:
||u" ()) I|u" Q4 ( S sc(
|/ (H CN- [ [-)-))
We will then show that the linear combination Usp Eierg, \(f) can be implemented by S, B) with L = O(1), w O(N), O(N) and B = Ollo N). Firstly, note that for 2 O, both and x² can be expressed in terms of the ReLU3 activation function 8Js with no error:
some Deep Neural Network uDNN E (L,, W,S,
1
x ITa (a + +3 5m + 7ns x + +1 -3)3(x) + +6],
12
1
2²
(ns 2) 4ns(# 1) (1)(x) 4].
6
Applying the explicit formula listed in equation B.50 implies that for any -3 < i < 1. the univariate B-spline function N (x) (a E [0, 1]) can be implemented by some ReLU3 Deep Neural Network upnn with both scalar input and scalar output. We have that for UpNN, the depth L,, 2 and the maximum width W, is upper bounded by 11.
41

---

Published as a conference paper at ICLR 2022
Secondly, for any x. y O, we have that the product operation y can be expressed in terms of the ReLU3 activation function 173 with no error:
1 (x + y)² -2² r²1
x. 2
1
12 77(x + y + 2) 4713(1 + y + 1) + 31 + +V)
71(2 + 2) + 477((1 + +) 3173 (x) (v + 2) + 4ns + +) -37s(1) + 4]
In (Schumaker, 2007), it has been proved that the B-splines are always non-negative, i.e N (2) 2 O, A E [0. Therefore, by multiplying the non-negative univariate B-splines, we can implement any multivariate B-spline N((1) _
N14) Lx (zz) with some ReLU3 Deep Neural Network PDNN-
We have that for PONN. the depth Lp [log2 d + 2 and the maximum width W, max dd). Hence, we can further claim that u" = Everg, N(u"))N" which is linear combination of the
multivariate B-splines N1, can be implemented by some ReLU3 Deep Neural Network uDNN- It remains to check that uDNN E L(L, W, S, B) with L = O(1), W = O(N), S O(N) and B ONN). Note that can ensure that the hidden layers upNN are of the same dimension W by adding inactive neurons.
For the depth of UDNN, we have that L is equal to Lp + 1, where Lp denotes the depth of the ReLU3 Deep Neural Network PDNN- Thus, we have L = Lp + 1 = [log2 d] + 3, which implies that
I. O(1)
For the width W of uDNN. we have that W < |T k. W. where W, denotes the width of the ReI.U3 Deep Neural Network PDNN. This implics:
W < 14 x 11d Lid(l + k)d Lid(I+ +)( 0(()) = W = O(N).
For the sparsity constraint S of üDNN; starting from the third layer, the number of activated neurons is half of the number of activated neurons at previous layer. This yields the following upper bound on S:
I-2 S s 2(W + W +
Σ 20
) sw = S (W) = O(N).
j=0
For the norm constraint B of UDNN, we have the following upper bound on B from equation B.50 and equation B.52:
= Omax sup {e(x"))) = 0max ())) ONN).
iET
Now we have shown that parameters L, W, S, B the Deep Neural Network upNN are the desired magnitude, which completes proof.
B.4 FINAL UPPER BOUND
In this subsection, we provide the proof of upper bounds for PINN and DRM. For both estimator, we first provide meta-theorem illustrate the approximation and generalization decomposition with O(1/n) fast rate generalization Sound(Bartlet) et al., 2005; Xu, 2020). Then we use truncated Fourier basis estimator and neural network estimator example obtain the final rate.
B.4.1 DEEP RITZ METHODS
Theorem B.9 (Meta-theorem for Upper Bounds of Deep Ritz Methods), Let u² E HH) denote the true solution to the PDE model with Dirichlet boundary condition:
-Au + Vu on Ω
(B.54)
u on 0n,
where f E (22) and V E ( with < Vmin I V(x) & Vmax > O. In Theorem B. it has been proved that u² can be obtained by minimizing the loss E(u):
11 / [|V']] + Vlul]] dx - Fude]
u arg min E(u) == arg min (2)
(
(E
.
42

---

Published as a conference paper at ICLR 2022
For function space F(2),, consider the empirical loss induced by the Deep Ritz Method:
1 where {Xz}}=1 are datapoints uniformly sampled from the domain Q2 Then the Deep Ritz estimator associated with function space F(22) is defined as the minimizer of En (u) over the function space F(2)::
Σ | (
En(u)
(B.55)
ĀDRM
min ((F
(u).
Moreover, we assume that there exists some constant C 0 such that all function u in the function spuce FSt), the real solution u² and V.V satisfy the following two conditions.
The gradients and function value are uniformly bounded max
sup [[]] sup [Vuull=<()) ( Vu [ (()) Vinass (1 SC. WEF(O)
(EF(()
(B.56)
All the functions in the function space F(2) satisfies the boundary condition
0 U2.
At the the same time, for any p > 0. we assume the Rademacher complexity of localized function space Sp(
[2]] [|Vu|==-IVu"" V |u [3) f(u- x²)
||u
u" l|2n <p} can be upper bounded by a sub-root function Φ <(p)) (0, [0, 00), i.c.
((4p) S 26(p) and (s,())()))) I <(p) (V 0)-
(B.57)
For all constant t > O. We denote T" to be the solution of the fix point equation of local Rademacher complexity (r)) There exist two constants Cp. Cg such that with probability Cp exp(-Co(1, we have the following upper bound for the Deep Ritz Estimator
E(uF) - E(u')) + max {r" 1 {
@@RRM- - u 1"I S
inf UFFF(()
Proof. To upper bound the excess risk AE E(ÜDRM) E(u"), following(Xu, 2020; Lu et al., 2021b; Duan et al., 2021), we decompase the excess risk into approximation error and generalization error with probability
GG,, where Cg is some constant:
E ()) (ūDRM) = ((ÜDRN) E(u") =
E (ŪDRM) E, ((DRM)) + E, (ÜDRM) E,, (ux))
En (ur) E(uF)] + [E(u)) - E(u*)]
E (ÜDRM) - E,, Em, (UDRM)] + [Er) E(ur)] + [E(r) - E(u))
E ((DRR)) E(u") + E,(u") ((DRR))
E(uF) - E(u*)] + 2n
(B.58)
where the expectation is on all sampled data. The inequality of the third line is because åDRM the minimizer of the empirical loss En the solution set F(?), so we have E, (ŪDRM) S Eu(u)). The last inequality is based the Bersstein inequality. The variance of h [
2 21V=l22 I1?) + V(u/22 |2* f(u w²) can be upper bounded by a' [E(u))
E(u*)] due to the strong convexity of the variation objective (B.60). According to the Bernstein inequality, there exists some constant C2 > 0, such that with probability 1 -CCt we have:
[{(uF) E(u*) 1
1
(uF) E.,(u)) E(ur) + E(u)) <
E(ur) E(u')] + 2n
43

---

Published as a conference paper at ICLR 2022
Note that B.58 holds for all function lies in the function space F. Thus, can take uF arg a E(uo) E((")) and finally get
AE (n)
E(ÜDRM) - E(u") (2n) (n(
inf upEF(()
E(uF) - E((())
L
2n
A Eg
This inequality decompose the excess risk to the generalization enror AE E(ÜDRM) E(w)) En (u") E., (ĀDRM) and the approximation error A Epp = inf E((1) From the lemmata proved in Section B.3, we already have an estimation of the approximation error's convergence rate. So we'll focus providing fast rate upper bounds of the generalization error for the two estimators using the localization technique(Bartinn (Brrtlett et al., 2005; Xu, 2020). To achieve the fast generalization bound, focus the following normalized empirical process
gen
E(uF) - -(uu))-((u')
S,(R) = (h(x) Bih h(a) E/4 +r
| S(2) (r 0).
First, we try to bound the expectation of the normalized empirical process. Applying the Symmetriza- tion Lemma B.I, we can first bound the expectation as
h(x)))
[[
sup Eg (E)
M(x))
< Exp
sup hES(S)
<
(S)
E
where the function class (S2) is defined as:
h(x)
(,() = {h(x)= = E[hh +
h S(2))
where S(R)
[
12
1u s(u (tta-n)) Then ap-
plying the Peeling Lemma B.4 to any function h SS2) helps upper bound the local Rademacher complexity (S,) with the function defined in equation B.57:
1 Σ osh((s)) E[h] +r
< 40(r)
(S)) = E, Eg sup RES(A)
Combining all inequalities derived above yields:
1 n
8ø(r) (r 0).
sup
Eg h(a!)
(S,
(B.59)
(E)
Secondly we'll 'l apply the Talagrand concentration inequality, which requires us verify the condition needed. We will first check that the expectation value E[h] is always non-ne non-negative for any h E S(2):
1
(v(xz)) + ! v f(z)u(x))da 1
E[M]
Ω
[
Jg
[2] ( Vu (x))1 + (()))n><<) (x))x
Ω Ja
E(u) E(u*)
2 = E(M] 2
We will proceed to verify that any = ক that any h S(22 is of bounded inf-norm beforehand. Using boundedness condition listed in
جالر e (2) is of bounded inf-norm. We need to prove
44

---

Published as a conference paper at ICLR 2022
equation B.56 implies:
||
|
V f(u u²)l
$ [/
[22
+ +|
+ 2
[
Vmax (1uul12 + 1-11001 + [12l1ll 100 [|ul|/o + 11021120)
2
[92
[22
< x 20 + mmx x 2C + 2/ = [S2[(Vmax + 3)
2
2
By taking M = [V + 3)C², we then have ||A|| I M for all h E S(2). Note that the denominator can be lower bounded by [[] + r| 2 r 0. Combining these two incqualities help us upper bound the inf-norm || = suPseR h(x)) as follows:
[|] 00 2|1/|| 1 =: B. E
2M
b =
We will then check the normalized functions -()-b(() in S,) have bounded second moment, Bih +r
which is satisfied because the regularity results of the PDE. We aim to show that there exist some constants a, a' > 0, such that for any S(?), the following inequality holds:
S ||u " (() a a'E(
(B.60)
The RHS of the inequality follows from strong convexity of the DRM objective function proved in Theorem B.I:
min(1, Vmin
E = E(u) E(u))
4 ||u u. (1))
The LHS of the inequality follows from boundedness condition listed in equation B.56 and the QM-AM inequality:
/
+ -uu1)) - f(u w)) ) de
|ull - [ 11)
8 2
< Jg (IVull2 - || 2 do + / -111/-110110 + s² - uou--u)e 2d
12
3
|| | (1 + V 11) + V2 // |lu| - |u" || (12) + | (1
(n- S 302 / Vuu Vu 12 dr + 302 + V22x2
/ |u u 12
+ 3C
1
s 33 12 max 1|u u 1121110))
By picking a' min (1, V and a v we have finished proving inequality B.60. Then we can can upper bound the expectation [ as:
[1 E[A)=
E|A3] [E +r
ETM
E + +
E
[E + +r
E
Using the fact that E[h] 2 and inequality B.60, we can lower bound the denominator [E[h]] + r/2 as follows:
2ra
khh] + r|2 2
2h 2 a'
E[h
Therefore, we can deduce that:
E 14
a'
E
[
+
r
2rc
2ra
Hence, any function in the localized class (.) is of bounded second moment.
45

---

Published as a conference paper at ICLR 2022
It is easy to check that for any h (S2), we have
[| [[AA]
E h =
0,
Bhh +r
i.e. any function in the localized class (1)) is of zero mean.
Now we have verified that any function h $, satisfies all the required conditions. By taking je to be the uniform distribution on the domain ! and applying Talagrand's ' Concentration inequality given in Lemma B.3, we have:
21a² +
21,8 n
P
Z
sup
Max) 22
sup Egy (2)
Se
he (02)
n
By using the upper bound deduced above and plugging in the expressions of 3 and we can rewrite Talagrand's Concentration Inequality in the following way. With probability at least 1 -,', the inequality below holds:
h(x)) E
sup
h(x;) <
sup
Ex'
Σ i=1
h(x²)
+
2to²
+
21,3
(E).
7 1=1
hE))
72
n
166(r)
to'
4Mt
=: (r))
r
nar
nr
Let's pick the critical radius ro to be:
24Mt
36a't
To max
(B.61)
n
an
Note that concavity of the function ø implies that Φ(r) for any r" Combining this with the first inequality listed in B.57 yields:
166(r)
211 p
1
To
X
214
8
8
2
2
On the other hand, applying equation B.61 yields:
a't naro
a't
1
na 36a't
6'
4Mt
4Mt
n
X
21
6'
Summing the three inequalities above implies:
166(ru)
to
4Mt
1
1
1
(Fo))
ro naro
+
<
nwo
8
By picking = To. we can further deduce that for any function E F(2), the following inequality holds with probability e_:
E (u) E(u)) (u) + Eu()))
M(xx) S (tro) < 2
E(u) E(u") + ro
Multiplying the denominator on both sides indicates:
A E gen = E1.) E(u") (u) + (u - 2
E(u) E(u") )
+ 2
1
1
+ ro-
2
Substituting the upper bound above into the decomposition (E < AEgen + A that with probability 2e min(C,.1){ we have:
2n yields
3
1 < A
3 A E
t
A AE < A E
- Amp
+
(1))
+ r
+
2n 2
2
2n
46

---

Published as a conference paper at ICLR 2022
Simplifying the inequality above yields that with probability 1 - 2e min(C,.1)1 we have:
24M t 36a' t (B(up) - E((u)) + maxf2 2AM
AE ro + Eap + =3 inf UFFF(
n n
inf (E(up) B(u")) + max frr
t m
2A
FFFF(0)
Moreover, using strong convexity of the DRM objective function proved in Theorem B.1 implies:
AE E(DDRM) E(u") min(1, Vinin
|ÍNDRM 2 21
4
Combining the two bounds above yields that with probability 1 -2e min(C,.)) we have:
(((ur) - E(u*)) + max {r= t
[RRRM - u² (0 2
inf urEF(N)
n
Deep Neural Network Estimator. For any N E Z+ there exists some Deep Neural Network in LL, W,S, S, B) with = O(1), = ONN), S = O(N), B = ONN), such that the approximation
A app O(N -اrي" and generalization error A Egen 0 Nog log N
With optimal selection achieve a422-2 log convergence rate for
N a=2x-2 to balance the bias and variance,
the DNN estimator.
Theorem B.10. (Final Upper Bound of DRM with Deep Neural Network Estimator) Under the assumptions in Theorem B.9, we consider the Deep Ritz objective with the sparse Deep Neural Network function space Φ(L, W, S, where the parameters L O(1), W
B O( On===zz)). Then we have that the DNN estimator Onn x=--)) ), 5 O( EDRM (u) satisfies the following upper bound with high probability: DNN DRM (1..5.(1.W.
26-2 u² || it カ+ log n.
ü DRM
Proof. On the one hand, by taking 8 = and 2 in Theorem B.8 proved above, we have that there exists some Deep Neural Network UDNN (,, with L O(1), W 8 O(N), B = O(N), such that.
||NNN u (0) N 2=m |u""
Applying strong convexity of the DRM objective function proved in Theorem B.I yields the following upper bound on the approximation error of DRM:
Appp $ UNDN - u² (1 N 2m12
On the other hand, from Lemma 1.17 proved above, we know that the function ((p) that upper bounds the local Rademacher complexity of the Deep Neural Network space is of the same magnitude
as 53 o log (BWn). By plugging in the magnitudes L, W.S, B, we can determine the critical
radius r
S
(2log N log n) 2r r" N(log N + log n)
log (BgB)))
Combining the two bounds above with Theorem B.9 yields that with high probability, we have:
DDM " 11r S A Em + +r* S N 26x
+ ((lg N + log n)
n
By equating the two terms above, we can solve for the optimal N that yields the desired bound:
N
N
Plugging in the optimal N gives the magnitudes of the four parameters 0(1), W
O(n 2), S = O(n Iτ 2), B = 0(n 2), as well as the final rate:
DNN i DRM
u" 11 I N -ل--ا + N Nlog N S n 2122 logn. n.
2(-11)
n
47

---

Published as a conference paper at ICLR 2022
Truncated Fourier Series Estimator. For any { E Zt, there exists some Truncated Fourier Series in (22) with approximation error A uup = (0(5-((-11) and generalization error E = 0 5" ).
With optimal selection E = n n to balance the bias and variance, we can achieve n 2422-2 convergence rate for the Fourier estimator.
Theorem B.11. (Final Upper Bound of DRM with Truncated Fourier Series Estimator) Under the assumptions in Theorem B.9, consider the Deep Ritz objective with the Truncated Fourier Series function space (Q()),, where the parameter { (=@ 7) Then we have that the Fourier estimator Fourier min (O)) EDRM (u) satisfies the following upper bound with high probability:
DDM
Fourier DRM
u 11 E n 1426-2
Proof. Let's firstly derive the function ((p) that upper bounds the local Rademacher complexity of + [ - |u" |=*?²) - f(u u²) E (9)) }.
Sp(22 = { h = | [|V || I1²)
where Fo.e( {o E (9) |ell2r (Q) s p denotes the localized Truncated Fourier Series
space. From Talagrand Contraction Lemma B.2, Lemma B.6 and Lemma B.7 proved above, we have
R., (s,( & Rm
(( - v² :uc E (S)) 1lu u² (()) S vot)
|| - Vu : F..e( ||u "" w S vol)
+ Rn
2 Ex
Rgg
sup
(ux))) -gg (x,) 1u
MT (l S pl
uEE F.EFr.C ((
+ Exx
sup
Vul,V((X,) - (Xx)l ||u 1e2"1l (1) sp]
NE P..e (9)
1
o.llseu [x,]
+ +Ex
ES
VII VIllee" (X.Ii (Xx,))]())]]]
+Ex
Eg
i=1
i=1
Eg
sup
(X,)
|100 14 (2) $ pl
VE F.F (9)
72 i=1
+ +Ex
E2
sup
s
(E
12
1
+ +Ex
E
(T)ge((X)))
Ex
E.g
Il
> (xi)
n
M>
I
Les +
{ +
1
P -
2(=-1)
n
n
n
n
(B.62)
where 1leu ;= Σ =||a <g (x) is the projection to the Fourier basis whose frequency is smaller than & and II Σ Ie 0= (z) is the projection to the Fourier basis whose frequency is larger than ę. Then, the critical radius rd can be determined as follows:
1 -
+
2(--1)
+ 1-g-((s-1)
n
n
11.
Moreover, by taking = and 3 1 in Lemma 19 and applying strong convexity of the DRM objective function proved in Theorem B. we can upper bound the approximation error Expp as below:
App S E 2(1
Combining the two bounds above with Theorem B.9 yields that with high probability, have:
F " u111 S A Eggo + ed
+ ----2(s-- 2(s
48

---

Published as a conference paper at ICLR 2022
By equating two of the three terms above, can solve for & that yields the desired bound:
S" = 26= = f= nard.
Plugging in the optimal & gives us the final rate:
111 S çd
DRM
+ 2(s-1)
+ 2 n atse-2
72
n
B.4.2 PHYSICS INFORMED NEURAL NETWORK
Theorem B.12 (eeta-theorem for Upper Bounds of Physics Informed Neural Network). Let u²" H H"t) denote the true solution to the PDE model with Dirichlet boundary condition:
Au + Vu on Ω
(B.63)
W on On,
where f E (2)) and V E (9) with V 1 LVV > Cmins < Cmin < Vxx) S Vmmax and -AV(r) (x) S Vmax In Theorem B.2, it has been proved that u' can be obtained by minimizing the loss E(u):
arg min E(u) == arg (0)
arg min
{ {
|Au- Vu- fldx).
())
For fixed function space F(22), consider the empirical loss induced by the Physics Informed Neural Network:
1 - Σ TI
|2] -(xxx))-(XX)))(X) + f(x)))
(u)
(B.64)
where {X3}ー= are datapoints uniformly sampled from the domain Qt Then the Physics Informed Neural Network estimator associated with function space F(St) is defined as the minimizer of E. (u) over the function space F(2)):
ŪPINN
min E, (u). (EF((
Moreover, we assume that there exists some constant C' > O such that all function u in the function space F(2),, the real solution u² and f, V satisfy the following two conditions.
The gradients and function value are uniformly bounded
max
sup [[]] sup (EF(
|/VulL
sup MEF(
||Au|L
WEF(1)
(B.65)
||u" ||0||l>> /V"ll | (D), Vmazi [ SC.
All the functions in the function space F()) satisfies the boundary condition 0 on M..
At the the same time, for any p > assume the Rademacher complexity of localized function space (S2) := = [2] [(Au- - Vu + f) (Au" - Vu* + +f) be upper bounded by a sub-root function & = x(p) : 10, oc) + [0, x0). i.c.
|u u" u01 S o can
((4p) < 20(p) and R, (T, (S)) I ((p) (V p 0).
(B.66)
For all constant O. We denote r" to the solution of the fix point equation of local Rademacher complexity Φ(r). There exists two constants Cp. Cg such that with probability 1 - Cp exp(-C,tt we have the following upper bound for the Physics Informed Neural Network Estimator
|| - u²" 11pp S inf UPFF(
(E(ur) - E(u')) + max fr+
L
n
49

---

Published as a conference paper at ICLR 2022
Proof. To upper bound the excess risk AE following(Xu, 2020; Lu al., 2021b; Duan et al., 2021), we decompose the excess risk into approximation error and generalization error with probabil- ity -- -e-Cut where C2 > 0 is some constant:
A AE EE (UPINN) = ((pPINN) E(u") = ((PPINN) En (ŪPINN)) + En (ŪPINN) - En (uF)
En ( E(uF)] + [((u)) E(u²)]
<
E (PPINN) - En (ŪPINN] + [En(uF) E(uF)] + [(uF) - E(u))]
<
E ŪPPNNN) B((") En(u") En ([PINN))
E(ur) - E(u")] + 2n'
2
(B.67)
where the expectation is on all sampled data. The inequality of the third line is because ÜPINN the minimizer of the empirical loss E, the solution set F(2), so we have E, (ŪPINN) S
En (uF). The last inequality is based the Bernstein incquality. The variance of h [9] [Au Vu+ + f) (An" Vu" + f) can be bounded by e' [[(u))E((u)) due to the strong convexity of the variation objective (B.69). According to the Bernstein inequality, there exists some constant Cy > 0, such that with probability 1 C₂ we have:
[(Fr) E(u*)
L
E, (ur) Eu(()) E(up) + E(u")
[(uF)) - E(u*)] +
n
2m
Note that C.5 holds for all function lies in the function space F. Thus, take ur arg eF(0) (((u)) - -E(u)) and finally get
3 inf (((u)) - E(u*)) + 2n (n) E(pPINN) - E(u") + Ex())) - En (UPINN)
2 UFEF(()
A
This incquality decompose the excess risk to the generalization error AE gen E(ŪPINN) E(u")
En(u)) E., (ÉPIN) and the approximation error A Epp inf e((()) E(uF) E E(u").
From the lemmata proved in Section B.3, we already have an estimation of the approximation error's convergence rate. So we'll focus providing fast rate upper bounds of the generalization error for the two estimators using the localization techinque et al., 2005; Xu, 2020). To achieve the fast generalization bound, we focus on the following normalized empirical process
B[b h(z)) h T()) (r 0).
T(( = (h(x)
E[h
First, we try to bound the expectation of the normalized empirical process. Applying the Symmetriza- tion Lemma B. we can first bound the expectation as
1
h(x() E[M]] E[h +r
sup Eg (2)
Σ Max))
<
E,
sup NET(O)
2R, (f)
n
where the function class S,( is defined as:
h(x)
f((2)) = {f(x)) = Eih] +r h T()))
where T(2) = hh = |22| [Au - Vu+ f)z (Au - Vv" + f) }. Then applying the Peeling
Lemma B.4 to any function E T(22) helps us upper bound the local Rademacher complexity R, (I, (S2) with the function ó defined in equation B.66:
Er ash((s)) E(h] +
< 46(r)
R2 (T) = E, Ex sup hET(()
50

---

Published as a conference paper at ICLR 2022
Combining all inequalities derived above yields:
80(r) (r 0).
sup
E
Σ h(a!)
(T,,(I
(B.68)
hET-(S)
Secondly we'll ll apply the Talagrand concentration inequality, which requires us to verify the condition needed. We will first check that the expectation value E/h] always non-ne -en-atvtevve for any h E S(2):
[2] / [2] (Au (u) E(u")
1
[2 / |22| (Au Vu + f)
E[h]
Vu d)
K|4
2
We will proceed verify that any
ビ (S2) of bounded inf-norm. We need to prove -
that any h E ( of bounded inf-norm beforehand. Using boundedness condition listed in equation B.65 implies:
| [[]] |I Vu+ f)2 (Au" Vu" + fc 192 I1 Vu + f)
< [0] A/ Vimax |umx||u||oo |1.ll = [m C2
By taking M == [S + 2), we then have |//|l0 I M for all E T(?). Note that the denominator can be lower bounded by [E[h] + r| 2 0. Combining these two inequalities help us upper bound the inf-norm |//l|>> sup [xxx)] as follows:
Dc
2|1
2M B.
|
r
We will then check the normalized functions B(N-h(2) in (S) have bounded second moment, B
which is satisfied because the regularity results of the PDE. We aim to show that there exist some constants a' > O, such that for any h T(2), the following inequality holds:
alE[A>]
< ||u un "1 113200)) S a [h]]
(B.69)
The RHS of the inequality follows from strong convexity of the PINN objective function proved in Theorem B.2:
Ejh| (u) E(u") 2 min Cann u" [1
The LHS of the inequality follows from boundedness condition listed in equation B.65 and the QM-AM inequality:
/ - -v-+ (Aur - Vu" + +)²]² do = 52
[EAA]
/Auu
Alu-Vai Vu+ ff+tr
s 2² / ((uu Vu (Au-Vu-Art Au + Vu') - 2M2 / [(Au Aur)² V2 - u²' 2
2M max(1, 2 ) ||u (1
By picking a' min (1.C.in) and 2MP max (1.2.) have finished proving inequality B.69.
Then can upper bound the expectation B[h2] as:
[( E(AA)* [[hh] + +r
E[A2] B[M]2
EEA31 |E[h] + r|2
E
|E + +r
Using the fact that E[h] 2 0 and inequality B.69, we can lower bound the denominator [[[[]] + r|2 follows:
2ra
[[4] + r|
2E(h]r >
o'
51

---

Published as a conference paper at ICLR 2022
Therefore, can deduce that:
E h
E|h
a' 2ra
= 0².
| +
r|
2ra
E
Hence, any function in the localized class (11) is of bounded second moment.
It is easy to check that for any h (S2). we have
[M] [
Eih
0,
B +r
Le. any function in the localized class (22) is of zero mean.
Now have verified that any function h (22 satisfies all the required conditions. By taking l to be the uniform distribution on the domain D and applying Talagrand's Concentration inequality given in Lemma B.3, we have:
P
sup (2)
Σ h 2 sup Eg kET
- Σ ==1
Matt +
2t
21,3 +
S Set
By using the upper bound deduced above and plugging in the expressions of B and o, we can rewrite Talagrand's Concentration Inequality in the following way. With probability at least 1 - E the inequality below holds:
2to + 2t,3
h(a)) S sup
h(a)) 2 sup
Eg
h(x²))
+
KES. 1=1
hE)
1=1
166(r)
to
4Mt
+ nar
+
=: (r))
nr
Let's pick the critical radius ro to be:
To m 24Mt 36a't
(B.70)
n an
Note that concavity of the function & implies that ((r) S for any 2 r". Combining this with the first inequality listed in B.66 yields:
16)(r)
2 21
2T
1
2
In
1
214
ra
8
2
On the other hand, applying equation B.70 yields:
a't
a't an
1
$
naro
na
36a't
6'
4Mt
4Mt
nrp
24M
6'
Summing the three inequalities above implies:
166(ro) ta
4Mt
1
1
(ru))
+
ro naro nro
8
By picking r = ro. we can further deduce that for any function u E F(22), the following inequality holds with probability -t:
E ()) E(u)) - (u) + (n
h(xz) < (ro)
(wu) E(u)) + To
2
Multiplying the denominator on both sides indicates:
A E gen
E(u) E(u") - (u) + Ex(u") < E(u) E(u*)
+ 2
1 1
A (n)
+ ro-
2
2
52

---

Published as a conference paper at ICLR 2022
Substituting the upper bound above into the decomposition AE < A Agea + A that with probability 2e min(,,C,)f we have:
2n yields
A
AE
A E
3 E
S A
1
AE (n) +
2n
3 A Eapp 2n
t
2n
2
Simplifying the inequality above yields that with probability
2e min(1,C,)] we have:
36a' (B(ur) - -((u)) max(2" 24M
AE
AE(" m) ro + 3A Eapp + =3 inf UFEF(()
(E(up)-E(ut)
n a
n n2
(B(ur) - E(u')) + max {rr -. {
inf (FFF(())
Moreover, using strong convexity of the PINN objective function proved in Theorem B.2 implies:
AE E(pPINn) E(u") 2 min(1, Cmin H|LPINN u -
Combining the two bounds above yields that with probability 1 -2- min(1,Co]t we have:
(B(uF) - E(u")) + max {r" t :s
[[NPNN u² u'Ilaa(0 E
inf (FFF(
Deep Neural Network Estimator. For any N E Z+, there exists some Deep Neural Network in @ (L, W, B) with L = O(1,, W O(N), S = O(N), B ONN), such that the approximation
error A A Epp O(N X6-2 and generalization error A E gen = 0 Nog log
With optimal selection log n convergence rate for
N n to balance the bias and variance, we can achieve n
PINN estimator.
Theorem B.13. (Final Upper Bound of PINN with Deep Neural Network Estimator) Under the assumptions in Theorem B.12. we consider the PINN objective with the sparse Deep Neural Network function space Φ(L, W, S, B), where the parameters L O(1), W
O O 4), $ = O and B = O +). Then we have that the DNN estimator DNN PINN mi..s. (PINN(u) satisfies the following upper bound with high probability:
DNN u PINN
u 11 111= S n 2926-1 log n.
Proof. On the one hand, by taking s = 2 and p 2 in Theorem B.8 proved above, have that there exists some Deep Neural Network uDNN W,,, with L = O(1), O(N), O(N), ONN), such that.
|NDNN 4² (2)) S -N- 2 " ||u||=-(0)-
Applying strong convexity of the PINN objective function proved in Theorem B.2 yields the following upper bound on the approximation error of PINN:
A Emp |INNN - u u0(12r S N 2m-4
On the other hand, from lemma B.18 proved above, know that the function @(p) that upper bounds the local Rademacher complexity of the Deep Neural Networks wpnN is of the same magnitude as
53 log (BWn). By plugging in the magnitudes of T,, W. S. B, we can determine the critical radius r":
35S IBg(
N (2 N logn) ~ -- N(log N log n)
n
n
n
Combining the two bounds above with Theorem B.12 yields that with high probability, we have:
JGNNN u² 11222 S Expp + S NN- 26--2) 2 +
(loo N + logn) n)
n
53

---

Published as a conference paper at ICLR 2022
By equating the two terms above, can solve for the optimal N that yields the desired bound:
N
Plugging in the optimal N gives the magnitudes of the four parameters L O(1), W
O(n (iazz- 4), S = O(n 2 +), B = O(n2rz as well as the final rate:
|| PPPIN - " - SNN 2) N Nlog N
21a-2) S n2 4+3(--2) log n.
n
Truncated Fourier Series Estimator. For any & E Zt, there exists some Truncated Fourier Series in (22) with approximation error A Eapp = (0(-2(x-))) and generalization error E = 0 E
With optimal selection { n n4422-4 to balance the bias and variance, we can achieve 2--3 convergence rate for the Fourier estimator.
Theorem B.14. (Final Upper Bound of PINN with Truncated Fourier Series Estimator) Under the assumptions in Theorem 1.12, we consider the PINN objective with the Truncated Fourier Series function space F(()),, where the parameter & = (n ==)- Then we have that the Fourier estimator UPINN F EPINN (u) satisfies the following upper bound with high probability:
Fourier u 11222 S
Proof. Let's firstly derive the function p(p) that upper bounds the local Rademacher complexity
of (9) = { h = |02| [(Au - Vu + f)² (Au" - Vu" + f) u E (12) }, where
(P.)( {u E Fe (92) ||01B32(0) S } denotes the localized Truncated Fourier Series space. From Talagrand Contraction Lemma B.2, Lemma B.6 and Lemma B.8 proved above, we have
RA (T,())) S Rn ((
u² : u E Jo (2), 1|u n" (и S vo))
+ R,
Au
Au" : u E J (9)), ||00 un (I)) S vot)
S Ex
E
sup
(u(x)) - Ue uee (X:)) ||u Me S p]
MEE M.EFFccCR
i=1
|1u 11 11 spl a,(A((X))) - Alleu((xi)
+ +Ex
Eg
sup
WE F. (
+ +Ex
E
0, All Sussuu"X (x,)
+Ex
Eg n
o (x,)
1=1
Ex
E2
sup
(X,)
|1111120000 s
1=1 ME F F,.((()) (92
+ Exx
sup
1
Au(iX)
|101 sm]
UE (
o II TT (xx))(xx)) (x,)
+ +Ex
E
+Ex
E
i=1
P
H2
Le
2(x-2)
P Le
1
2(s-2))
V
(B.71)
where mçu : Σ =|| Se (x) is the projection to the Fourier basis whose frequency is smaller
than & and IT = Σ 1=llas se (=d2(x)) is the projection to the Fourier basis whose frequency is
54

---

Published as a conference paper at ICLR 2022
larger than &. Then, the critical radius r" can be determined follows:
gd 1
5 + + ---2(0-2) 2(a-2) ~r
+ +
---
n
Moreover, by taking and 3 in Lemma B. and applying strong convexity of the DRM objective function proved in Theorem B.2, we can upper bound the approximation error Eup as below:
Epp S -
Combining the two bounds above with Theorem B.12 yields that with high probability, we have:
ed
il PINN
Fourier
u u S Eup
+ 2(s-2))
n n
By equating two of the three terms above, we can solve for & that yields the desired bound:
2(x-2) + =
n
Plugging in the optimal gives us the final rate:
S ed
Fourier [UPINN - w²'l
+
2(--))
+
~ n
u12
2u
C PROOF OF MODIFIED DRM
In this section, we provide the proof of the modified deep Ritz method here. We first provide similar meta-theorem as we did for DRM.
Theorem C.1 (Meta-theorem for Upper Bounds of Modified Deep Ritz Method), Let u² E H*(Ω) denote the true solution to the PDE model with Dirichlet boundary condition:
- + Vu on Ω in
(C.1)
where f E (12) and V ( with 0 < Vinn S (x) < Vimax O. In Theorem B.1, it has been proved that u can be obtained by minimizing the loss E(u):
(2 / [IVu]2 + Vlul] dr Fudz):
u
arg min E(u) = arg min (E)
(E .
For fixed function space F(Q), consider the empirical loss induced by the Modified Deep Ritz Method (N 2 n):
(u) = Σ N
1
N
[ [[x(X))] + 1 Σ 12 1 - f(X))u(X)))
(C.2)
where (X) and (Xz)ī=1 datapoints uniformly and independently sampled from the domain Ω. Then the Modified Deep Ritz estimator associated with function space F(2)) is defined as the minimizer of EN, over the function space F(2)::
ÜMDRM
min FFF(
(u..
Moreover, we assume that there exists some constant C 0 such that all function u in the function space FS2), the real solution x² and f. V.V. satisfy the following two conditions.
The gradients and function value are uniformly bounded
max
sup [| sup [VVullg>> ||u II Vu' I Vmary (ifl:llflll SC (EF(())
F(F
(C.3)
55

---

Published as a conference paper at ICLR 2022
All the functions in the function space F(2)) satisfy the boundary condition
OΩ.
At the the same time, for any > 0, we assume the Rademacher complexity of the following vector-valued function space
S,( = { {1111 == |22|
[ (|Vu]|-IlVil) [PP]]=-1|V''[33] 1
2
h2 := |2l|
1 V -
-1 12- - [(u - ((u-ur) .1|u w'2 s sp).
can be upper bounded by sub-root function & 6()) :0, - [0, i.e
x(4p) S 26(p) and R. (S,( <(p) (Vp>0) WD>0), 0),
(C.4)
where RN a RN (er((tu (0r 12) E S)) + Ra (1h h22 E S}). For constant t denote r" to be the solution of the fix point equation of local Rademucher complexity r Φ(r). There exists two constants Cp. Cg such that with probability Cp expp(-Cgt we have the following upper bound for the Modified Deep Ritz Estimator
[ - -u"ll S inf (E(uF)-E(u") + max {rr; -
(FEF(()
Proof. To upper bound the excess risk A (E(.)) = (((MDRM) E(u"), following(Xu, 2020; Lu et al., 2021b; Duan et al., 2021). we decompose the excess risk into approximation error and generalization error with probability 1 e
A AE (N.) ((ŪMDRM) E(u")
E (ÜMDRM) EN.a (UMDRM) + (UNDRR)) - EN,.(uF)
( E(uF)] + [E(u)) - E(u")]
E (ÜMURM) EN. (MMM((MDMM]] [EN,n [[Er) [E(ur) E(u")]
E (ÜMDRM) E(u") + EN,(u") EN
4t
[[((F) E(u")] min(NNn)
(C.5)
where the expectation is all sampled data. The inequality of the third line is because ÜMDRM is the minimizer the empirical loss E,, in the solution set F(2).. so we have EN (ÜMDRM) I E (up). The last incquality based on the Bernstein inequality. For any ur F(2)), use h to denote the following two functions:
hF
hF 2 V(lux(2 |u+ f(ur-u()
- 2²))
Applying Bernstein's inequality twice to hF and hr.2 implies that there exists some constant Cg. such that with probability 1 Cc,, the following two inequalities hold simultaneously:
(x E(hpa)
1.
h
F.
N
a E P.2.
E
E, E(hr22 S
n
Note that the variance sum E 1 + E to the strong convexity of the variation objective (C.9). Adding the two inequalities above implies
can be upper bounded by g' [[(u)) - E(u")] due
56

---

Published as a conference paper at ICLR 2022
with probability 1 - 2e Cot we have:
(N,((F)= EN,a(u")- B(ur) + E(u") EN (1r,.)) E(hF,I) (b 2(
1 E 11
E
( F22
N
n
2t at E || + E P1
min (N.
2t E(ux) - E(u)) min(N,n)
4t [E(up) E(u")] min(N, m)
Note that C.5 holds for all function lies in the function space F. Thus, take ur arg e E(up) - -((")) and finally get:
E(ur) E(u')) + 41
AE (F(N.) E ((MDRM) E(u") + (N,n(u") EN, (ÜMDRM)
inf UPEF(
A
Aap
This inequality decomposes the excess risk to the generalization error A == E ((ÜDDM))
E(u") + (v,n(u)) - ((MDRM) and the approximation error A = infureF(() ((uF))
E(u"). From the lemmata proved in Section B.3, we already have an estimation the approx- imation error's convergence rate. So now we'll focus on providing fast rate upper bounds of the generalization error for the two estimators using the localization techinque(Bartlet et al., 2005; Xu, 2020). To achieve the fast generalization bound, we focus on the following two normalized empirical processes:
[B(,,] hn (1r)
(9, = {h)(z)
(h2, h2) E S(2) (r > 0),
E[h + E h22 +
[|/ lz2
(0,( {ha(x))
(hi, E S(L) (r> 0).
E E(b] + E h22 +
where the space S(2) is defined as:
S(2) = { (h1. h2) h1 = |02|
2 | - ||V (|Vui[2-|VV>>]3))
2 ( |2* f(u f(u- un) uue F(D)).
h2 = |02]
First, try to bound the expectation of the two normalized empirical processes. Applying the Symmetrization Lemma B. we can first bound the two expectations as:
1 N
h (v() E[hr]]
sup ())8,,10))
Ey
in
(v/)
< Eyg
sup
< (Rxx(
()ES)(R)
N
E
[bb] + E.
[12 +
i=1
h2(y,) E[he]
Ey (21))
sup
h2
(11))
$ Ey
sup
(S,2(9))))
n
n
B + B[h +
where the function classes (.)) (1
< 2) are defined as:
hx
$21 (h1(x) := B[hr] + [hh2]] + (h1, S(9)).
h2(2)
(1) (ha(s)= Elhy] + Elh2] +r (hi, S()))
57

---

Published as a conference paper at ICLR 2022
Applying the modified Peeling Lemma B.5 to any function h hh1,h2) E S helps upper bound the sum of the two local Rademacher complexities Ry (y,(,,, (5,2(()) with the function & defined in equation C.4:
N E (v)) B[h1] + h + + ]
E Tzha(ub)) Eih1 + Bihal tr
(x, + R., (S))(())) Eg
Ey
sup NES(D)
+ E
By
sup
NES(
N Σ N (vh)
1 + T, n2
Eo
Ey.w
sup
sup hES(R)
NES(S)
B|h1] + E[h2] +
||hi] + h/ + r
4
RN (S, v
r
Combining all inequalities derived above yields:
N (v()
1 h2(wn)
sup (11)
Ey
+
sup
Ey
(
11
j=1
(C.6)
86(r) S ( (12) + 2R, (S., 2n (S, S r (r > 0).
Secondly we'll apply the Talagrand concentration inequality to the two function classes S (22 and (12), which requires to verify the conditions needed. We will first check that the expectation sum [[hi] + [/2 is always non-negative for any (h1, h22 E S(2):
B + [[h22]
[2]
2 (I] (2)))u(1)) {(x)u(x))ddr
1
[2]
R
[ Jn |2| 2 Va (x) V( (x)) f(x) ((=)u" (x))do
E(u) E(m)) 2 0
= E E(b1] + E(h2] 20
Next, We will verify that (9)) satisfies all three requirements. At first. we will show that any E0h hi E + (S2) is of bounded inf-norm. We need to prove that any h (.t is of bounded inf-norm beforehand. Using boundedness condition listed in equation C.3 implies:
|| = -1 [ || | 1oc S 1/2
1 (IVull + + S C
By taking M1 == C², we then have | 11.0 < M, for all h1 E (I)). Note that the denominator of
hy can be lower bounded by E [[h]] + [8(ha] + r| 2 > 0. Combining these two inequalities help us upper bound the inf-norm | blo supzen 10 (I) as follows:
[[[(},] Aag loc
2///1/ S 2M
B1.
E E
+ B[ha] +
Also, it is easy check that for any hn (9)), have
Ehh - E[ha] O,
[E + [[h2] +r
i.e. any function in the localized class (1)) is of zero mean.
Moreover, we take of = e B[h to be the upper bound on the second moment of
functions in (.)). Now we have verified that any function h E (92) satisfies all the required conditions. By taking μ to be the uniform distribution on the domain Ω and applying Talagrand's Concentration inequality given in Lemma B.3, we have:
21 N
2131
P
sup
Σ (x:) 1=1
2 sup
Ey Σ In()))
+
Se
(1)
(
N
(C.7)
58

---

Published as a conference paper at ICLR 2022
Moreover, We will verify that (92) also satisfies all three requirements. At first, we will show that Elke]_ha any l22 = k4 + E (92) is bounded inf-norm. We need to prove that any h2 E S2(12 is of bounded inf-norm beforehand. Using boundedness condition listed in equation C.3 implies:
|
v |2* - -f(uu=")lla =0oo
2
Vinax (Iullso + 11101123) + 111 (Iulloo + llu0
< Vmax x 202 + 202 = (Vmax + C)
By taking M2 = (Viax + 2)C², we then have ||A2||oc S M2 for all h2 E S2 Note that the denominator of f2 can be lower bounded by [[][,]] + [b]]]] + r| 2 r > 0. Combining these two inequalities help us upper bound the inf-norm |/aalloo supxen 1 (a)) as follows:
[B[ha]] h2 loe
211b2llac 2M2
32-
E + [/22] +r|
r
Also, it is easy to check that for any h2 E (S2), we have
B[ha] El/ + [12]] +r
O,
Le any function in the localized class (12) is of zero mean. Moreover, we take o = 2 B[ha] to be the upper bound on the second moment of functions in (12). Now we have verified that any function h2 E ((2) satisfies all the required conditions. By taking μ to be the uniform distribution on the domain Ω and applying Talagrand's Concentration inequality given in Lemma B.3, we have:
Fs
sup (1)) n
a Σ h2(a)) 1=1
2 sup (0)
Ey H
b2((T))
2to
2t.2
Set
n
n
(C.8) By applying a union bound to the two inequalities derived in C.7 and C.8, we can derive that with probability at least 1 - 2e t, the inequality below holds:
h (z +
h(az))
<
sup ES,
h1(xz) +
sup
hz(2z)
N
(0)
2=
j=1
N
2to
21
< sup
Ey LN ha(
+
+
N
N
2tt
2tB²
+ 2
sup
Eny
+
he (
n J=1
12
n
160(r)
21
21(3 + (2))
<
+
(a, + 02)
+
n
By the definition of 81 and B2, we have that the term
2(())+82))
can be upper bounded by:
21(31 + B2) 4t(M + M2)
4( Vmn.x 3)C²t
n
nr
nr
Now we will derive some upper bound on the sum 01 + 02. By definition we have that: (0) + 02)² < 2 og) 2 sup
E + sup
E
(2))
[B[A]] - E 12
E h
[122]
2 sup (ES(1)
sup hES(O)
[E[|,]] + 16 [12) + r|2
[| + [hh r|2
| + ETh3
< sup Aes(0)
| + E h2 + +
59

---

Published as a conference paper at ICLR 2022
Now it suffices to derive an upper bound of 1 + Elga |+ for any h E S(2). The existence of such an upper bound is guaranteed because of the regularity results of the PDE. We aim to show that there exist some constants a, a' > 0. such that for any h E (S2), the following inequality holds:
a [E[hi) + E(1))) & u - u 12 (0) S a' (B + E(h2))-
(C.9)
The RHS of the inequality follows from strong convexity of the DRM objective function proved in Theorem B.I:
[ + B[h2] E(u) - E(u")> min 1, Vmin |
E(u))
|/u u² 11
The LHS of the inequality follows from boundedness condition listed in equation C.3 and the QM-AM inequality:
dx + S 1 |Vul - -1 Vu'
/
1 -1 -f(u ((u-u")) -u') dr
| + E[ha]
/ (IVul)² 1P) dx +
1
/
V2 (1ul - 1) dx + 2 /./ f2 pu 3
< 4 Jn
2 nn
1 / ||Vi|| Vu 1| Vll + V/ 11) + 1 mmxx [ | - ||'l|
$ J
-iuil (Iu) + lui 1)2
(u uu= C² / |Vu Vu 1 + 20 (1 + Vi / lu 2 12122a 22
+ 20
12
3 20 (1 + max )l|u u²" (())
By picking a'
min (in) and 2C²(1+ v we have finished proving inequality C.9. Then
E[h +[bb] as:
can can upper bound the term
E[ba]
+r|
E E [
E[hi] B[h2]
a'
S
E[h] + [/g + r|
2r
[[h1] +
B[h22]
20r
Combining the bounds derived above helps us upper bound the term
2t (ar + 02) as below:
21 lo + 02)
88
E E + E
4a't
sup NES(D)
n
n
|[/1]] + E|h2 +r|2
nar
Thus, using the two upper bounds on
21 (a1 02) and 20(
we have
h (x()
+ Σ h(zz)
16p(r)
2t
(01 02) + 2t(31 + B2)
N
r
n
n
16
4a't
4(V max + +3 ())).
+
ner
nr
Let's pick the critical radius ro to be:
To max (2,, 24Mt 144a't
(C.10)
an
Note that concavity of the function & implies that Φ(r) S r for any 2 r", Combining this with the first inequality listed in C.4 yields:
160(ro)
2 C
1
<
To
214
2
Iu
8
P1
8
60

---

Published as a conference paper at ICLR 2022
On the other hand, applying equation C.10 yields:
4a't nara
4a't an
na 144a't 6'
4 (aVaxx max
+ 3)
4(Viux + 3)C
n
n
24 max + +
6
Summing the three inequalities above implies:
(ro)) = 160(ro)
4a't
4(Vmux + +
+
+
0o
naTo
nro
8
6
2
By picking 7 = ro. we can further deduce that for any function u E F(2), the following inequality holds with probability 2:-
E(u) E(u") + (u") (N, (u)) E(u") + +ro
1
Σ Max) S ((ro)
<
Multiplying the denominator on both sides indicates:
1
1 - + 22
1 A
A gen Euu) E(u") + (u.) Ev,.(u) (u)
2 E(u) E(u")
+ TTo
Substituting the upper bound above into the decomposition AE I A Egen +2 Enp + yields that with probability 4e min[I,C,){ have:
3
1 1
(n) + 20 + 22 E + 41
A E (n) < A gen
A +
2n AE
2
Simplifying the incquality above yields that with probability 1 - 4e -minn(..C)) we have:
A AE(") S rr + 4A Eapp + St
(B(ur) - E(u")) + max 24M
36a' t 8t
= inf aFEF(()
+
n
n a
n
2/ inf (E(up) - B(nt)) + max {or (FFF((D)
t m
Moreover, using strong convexity of the DRM objective function proved in Theorem B.1 implies:
(E E(ÜMDRM) E(u") Z (MMDRM u² |122-
Combining the two bounds above yields that with probability 1 4e- min[1,0,] we have:
(B(ur) - E(u')) + max {r- 1 (
MMMDRM - -='l 11 S inf aFEF(()
Truncated Fourier Series Estimator. Next we aim to show that the truncated Fourier series estimator can achieve the min-max optimal rate using the MDRM objective function. For any Ç E + satisfying ?² < n there exists some Truncated Fourier Series in (5( with approximation
N.
With optimal selection error A Epp = ((g-2(s-1)) and generalization error E O a ( = n2 2T2
balance the bias and variance, we can achieve n Fourier estimator.
convergence rate for the
Theorem C.2. (Final Upper Bound of MDRM with Truncated Fourier Series Estimator) Under the assumptions Theorem C. we consider the Modified Deep Ritz objective with the Truncated Fourier Series function space Fe (52)), where the parameter ç = (n ( By assuming & < ==-=
we have that the Fourier estimator à Fourier = min N, (u) satisfies the following upper
MDRM
bound with high probability:
Fourier ü MDRM "1" 111
61

---

Published as a conference paper at ICLR 2022
Proof. Following the proof as shown for the DRM upper bound in Theorem B.11, we firstly need to determine the critical radius r":
5 2-2 + +V N V
+
- + - m
1 1 N
For have assumed Nr -" the solution of the fixed point equation is - + + On the other hand, by taking a = 8 and / = 1 in Lemma B. 1919 and applying strong convexity of the DRM objective function proved in Theorem B. upper bound the approximation error A app as below:
A Eap (-2(1-1),
Combining the two bounds above with Theorem C.1 yields that with high probability, have:
ed-2
MDMRM
u 11 X Aapp + r"
-
By equating the two of the three terms above, we can solve for that yields the desired bound:
ed-2
n
Plugging in the expression of & gives the final upper bound:
ed-2
MDRM
-u'l"" 113
+
2(x
+
< n --2--1
71
n
D PROOF OF THE LOWER BOUNDS
D.I PRELIMINARIES ON TOOLS FOR LOWER BOUNDS
In this section, list the standard tools the Fano's 's inequailty and the Varshamov- Gilber Lemma.
establish the lower bound. The main tool is
Lemma D.1 (Fano's methods). Assume that V is unifrom random variable over set V, then for any markov chain V + X - V, we always have:
P(V 1 I(V;X) + log
log((V))
Lemma D.2 Warshamov-Gillben Lemma, Lemma, (Tsybakov, 2008) Theorem 2.9). Let D 2 8. There
exists subset {-(0),... /(2D/1)) of D dimensional hypercube H. {0, 1}2 such that -(0) (0, 0, ... ,0) and the e distance between every two elements larger than D.
D
D for all 0 5
(8) 2 8 1
D.2 PROOF OF LOWER BOUND
In this section, provide the proof of the lower bound for learning PDE. Our proof uses standard Fano method to establish minimax lower bound but finally leads to non-standard convergence rate. We state standard results for Fano methods in Appendix D.1. Following the proof our main lower bound.
Theorem D.1 (Lower bound). We denote u² (f) to be the solution of the PDE 2.1 and we can access randomly sampled data (X,, Yihi=,,-.. n as described in Section 2.2.
DRM Lower Bound. For all estimators 2b (R-) on
R HI)),, we have
inf 1 ())(((
sup ((K, n' (f) Z कt.
2e-2
(D.I)
62

---

Published as a conference paper at ICLR 2022
PINN Lower Bound.
For all estimators v/ (IR)) 8n
x &R HH(),,, we have
inf sup
( - a' (f) 2 n 4 (OL
(D.2)
Proof. We construct the following bump function to construct the multiple hypothesis test used for proving the lower bound. Consider a simple C bump function supported on [0, 1]
( II E(xe), ""1,"",,,
where { R - R a non-zero funtion in C with support contained in [0, 1] and satisfies 5(x:) # 0, de {(x) # O. Then Vg(z) * 0 and the support of function 9 is [0, 1]d.
Next, we take m = in क and consider a regular gird x0),j E [m]] According to the Varshamov-
Gilbert lemma, there exist 2m /8 -e.uue-seesssss ,()),... , ( (*) E {0, 1)m such that ||
7(80|122 2 n² for all 0 k # k/' 2 /8, Then construct the multiple hypothesis /8.
S
un (x) =
m g(m(1 - =(1)) 1,2, .... 2m
jE[m]
where w is constant to be determined later. It is easy to find out that ug E C
Then we reduce solving the PDE multiple hypothesis testing problem, which considers all mappings from n sampled data to the constructed hypothesis (R2) 8n x R + V = {u,li =
1,2, , /8/ Then we apply the local Fano method and check that we can obtain a constant lower bound of P(V * V) for any estimator V. From the local Fano method, we know that
I(V; < VI2
ΣΣ (kI(P.))P) vighe!
where Ps denotes the joint distribution of the sampled data (x. y). In specific, x follows a uniform distribution on [0, 1]d and f(X) + where is independently sampled from standard Gaussian distribution (O, 1). Then we have
dPr
Cw
KL( = E Elog(
dPs
=
|| Auu + Vuelii, S
22--4"
Using Fano inequality, if we select m x In [nt] then we have the following lower bound when w taken be sufficiently large:
P(V 4V)21 X(V:X) + log
SCW
20
1/2.
log([V))
mnd log
At the same time, we can estimate the separation of the hypotheses in two different norms:
Deep Ritz Method:
f Youje Vuu Vuk Prr
R²
7(8) / [Vg(z)) v 2
1| (k)
m2
2+d
jE(m]
Physic Informed Neural Network:
So.p Ilu - Aurl/dd m²--
11 (M) 1 / Ag(x) m
jE [m]]
63

---

Published as a conference paper at ICLR 2022
Plugging in [n (12],,,, we know that with constant probability have
2,²],
inf sup ((EH((2)
([X, (Y) (=) (f)l Z n -
(D.3)
inf sup (H))
- (f)l 2n 4420-1,
20-4
(D.4)
E INTUITION BEHIND THE SUB-OPTIMALITY OF THE UNMODIFIED DEEP RITZ METHODS
In this section, aim to discuss the intuition behind the sub-optimality of the unmodified DRM via using the truncation Fourier basis. To simplify the notation, in this section we consider the following simplest Poisson equation Au illustrate the necessity of the modification we made, we consider the difference between the following two estimators
the hypercube with zero Dirichlet boundary condition. To
Estimator 1. We use the truncated Fourier basis estimator to learn the right hand side function f and then we invert the PDE exactly to get the estimated u.
Estimator 2. We plug in parametrization the truncated fourier basis into the empirical DRM objective
We would like to point out that estimator 1 isn't I build for computational consideration. Instead, we use to consider the statistical limit of our sampled data. We first show that the estimator 1 can achieve the minimax optimal estimation error.
Error Of Estimator 1 Firstly, we show that if one wants to learn the function u in Hb norm, one need learn the right hand side function f Hy norm. The Ho- norm defined as the dual norm of the H norm, i.e. ||ul|,, max $1 (u, v). Once we assume we have an estimate f of f in Ho we can have an estimate of via à (A) 1 f. whose distance in the H' norm satisfies:
Vu Vûllng
max ||lllin 2
(Vu Vū, Vv)
max Auu ||lllng $1
Ad, r)
(f- f.0) = -Iff- ffl
max |ollln $1
Estimator using the truncated Fourier estimator estimate the right hand side function f. Suppose we can access a random sample of observed data as {Ii, [mx))]_.. then the Fourier coefficient fz (u, Φ2) can be estimated as ft Σn (x.).. To bound the estimation error of = E1t feb in H we first apply the bias-variance decomposition:
Elií - Al S |Ef - fI??, ElI Efil
We first bound the bias term |Ef f||3- Given E,f Σ1 < sz f.p.. we have that for truncation set Z of the from Z {= E N 11// b}, the bias term can be controlled by:
11 Σ
fe 2 < Σ
||l||
1) 11
|| >Z
>2
64

---

Published as a conference paper at ICLR 2022
Next estimate the variance of the estimator by decomposing the variance into the following sum:
E f - f 1 E
Σ (fx f1) S
Σ
varr'))
Finally we achieve a 2 2" upper bound for estimator 1. With optimal selection of Z, we can achieve the min-max optimal convergence rate n 212
Difference Between Estimator 1 and Estimator 2 Next aim to understand the Deep Ritz Method objective function via plugging in a truncated Fourier series estimator. We consider an estimator of the form Σ 0= (æ). which lies in the space of truncated Fourier series. Then the empirical DRM objective function can be expressed as
Σ úz Vol((a)
+ Σ (=))(
(E.1)
2m
We observe that (E.1) is quadratic formula with respect to the Fourier coefficients Thus, we can rewrite it as the following matrix form
(=l)
1 min ju uu "u++ + u where A
E n
(V(
(E.2)
|| $2.11l
Based on the matrix formulation E.2, we can compare the solution given by the two estimators
Estimator 1: The Fourier coefficients of the solution of Estimator I are
diag [I==1>)|++1>>>>>
(E.3)
Estimator 2: The Fourier coefficients of the solution of Estimator 2 are
ú f
(E.4)
Note that EÁ (1|=11?) |= SZ Thus, we can further introduce another variance from the sampling Sz
of A. By directly estimating új ūz we will show that this term will be larger than the final convergence rate. Notice that
|| وz 11 = S
- -A-1) diag (II=112) |= (1-))1-AA-))
(E.5)
Next we aim bound (EA))-IAA A-1). We first use the Matrix Bernstein Inequality(Tropp. 2015) to bound the 2 distance between ú, and u2 According to the Matrix Bernstein Inequality, we have that with probability e the following inequality holds
((E - A)
Z
(E.6)
n
n
where || 1|e the matrix operator norm respect the vector
|| || defined as ||
TT ddag (1 = sz= z. Note that
(1+ ( (A- (EA))) (LEA) - A-1)= -(EA)- (A- (EA) (EA)-1
(E.7)
When n is large enough, we know that 1/ // 1 (BA)-1 (Ā )A)AA) < I with high probability.
Thus the term - وي I,fm is at the scale of ( A) 1|2 zd which is of the same magnitude
what we get from the empirical process approach in our main proof. It is also larger than 2 which is the magnitude of the variance term for û, Therefore, here we conjecture that the our bound for DRM itself is tight and leads to the sub-optimal convergence rate.
65


Reviews:
[{"review_id": "mVWq8dgEQF", "reviewer": "Reviewer_16v3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "A number of recent works (many but not all cited by the authors) analyze ML-inspired numerical methods for PDE, with one\noutstanding question being to what extent these methods evade the curse of dimension.  The present work uses far more sophisticated techniques from statistical learning theory, in particular a \"localization technique for Rademacher complexity sums\", and gets stronger results.  While not leading to dramatically new conclusions, these are apparently the first tight bounds for these problems.", "summary_of_the_paper": "This paper carries out a variety of studies, both theoretical and numerical, on numerical solution of a Schrodinger equation using deep learning inspired methods.  The main results are upper and lower bounds on a power law scaling for sample complexity, function of dimension and regularity, which are tight for one of the methods.  Another method (Deep Ritz) has a proposed improvement.", "summary_of_the_review": "Valuable technical advances on an important and popular topic.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "cVmt2Kux10w", "reviewer": "Reviewer_RB8r", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well motivated and understanding the generalization and optimality rates for NNs for PDEs is an important problem. Moreover, the authors provide a lower bound which is important. \n\nHowever, I would like to point out that currently the way the paper is presented is very hard to follow. Most of the discussion and proof sketches are left for the appendix, and the theorems that are presented in the main paper are informally stated. Furthermore, there is not proof sketch provided with the theorems that would intuit how the result was proved. This makes it hard to verify the results. \n\nFor example, like the previous work (Duan et al., 2022 and Jiao et al., 2021) the authors use a spline based construction to prove the neural network approximability. However the authors point out that they get better bounds due to the strong convexity of DRM and PINN loss. However, I am not sure where exactly is it helping when compared to the proof sketch provided in the previous paper? An explanation of this in the main paper is lacking. \n\nRegarding the lower bound, I am quite confused about what authors mean by \"The lower bound shows a non-standard exponent different from non-parametric estimation of a function.\" ", "summary_of_the_paper": "This paper establishes statistical lower bounds and upper bounds for (a modified) Deep Ritz method and PINNs based learning of solutions of PDEs when the estimators belong either to a class of sparse neural networks or lie in truncated fourier basis. They utilize the fact that the objective in DRM and PINNS is strongly convex, and use it to get a faster generalization bound O(1/n) instead of O(1/\\sqrt{n}). Given that the upper bound for the initial non-modified version of DRM does not match the lower bound, they introduced a modified deep ritz method, where the number of samples to estimate the gradient squared is greater than (the ration is provided in the statement) rest of the objective. This enables them to achieve minimax optimality for DRM as well. \n\nThrough their experiments they verify that the number of training samples n and the test error follows a power low with \\alpha = 1/d as indicated by the derived rates.", "summary_of_the_review": "I think the results of the paper are relevant however, I think that the exposition needs to be improved for the main paper, as currently it is hard to follow. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QU8-dsOxpQX", "reviewer": "Reviewer_Er9e", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: \n1. The authors derived faster upper bound for PINN and DRM than existing results.\n\n2. The authors proposed a modified DRM. The modified method together with truncated Fourier basis method.\n\n3. The proof is very detailed and clear.\n\n\nWeakness:\n1. Compared with the network architecture in (Jiao et. al., 2021a) and (Duan et. al., 2021), the architecture used in this paper is a sparse network, which makes it less practical. \n\n2. Another draw back is that the authors assumes the gradient of any function in the network class is bounded by a constant. This assumption is difficult to satisfy since the gradient depends on the network width and depth. In the theorems, the depth depends on the number of samples.\n\n3. The organization of the paper needs to be improved. I believe the main theorems are Theorem A10, A11, A13 and A14. However, the authors only stated informal versions of these theorems in the body part. Even in these theorem mentioned above, the conditions are unclear. For example, in Theorem A9, the authors require the network class has bounded gradient. But this assumption is not mentioned in A10 and A11, which I believe is proved based on A9. The assumption in Proposition 2.1 is not mentioned in A10 and A11, either.\n\n4. For numerical experiments, the authors only presented the errors versus the number of training data. The network architecture and how it is trained are not mentioned. What is the computational cost?\n\nComments:\n1. On page 3, the authors said the variational problem considered in this paper and that considered in (Hutter & Rigollet, 2019; Manole et al, 2021) are different and leads to technical difference. Could the authors comment on the difference?\n\n2. On page 3, the authors said the proof in this paper can be extended to nonlinear ones. Could the authors briefly explain how to extend it?\n\n3. Page 15: At the end of the proof of Theorem A.1, the right-hand side of the last inequality has a factor max(1,V_{min}). The inequality does not hold when V<1. But I think this can be fixed.\n\nTypo:\npage 3: '... can be extend to ...'-> '... can be extended to ...'", "summary_of_the_paper": "This paper studies the the statistical error of the Deep Ritz Method and Physics-Informed Neural Networks using neural networks and truncated Fourier basis in solving PDEs. The static Schrodinger equation is used as a prototype PDE. With appropriate assumptions, the authors established upper and lower bounds of the error for both methods. The upper bound derived in this paper improves existing results with a faster rate. The authors also proved that the upper bound of PINN is nearly optimal. Some numerical experiments are conducted to verify the results.", "summary_of_the_review": "In general, this paper is a good paper and provides solid theoretical results on solving PDEs by deep neural networks. But the writing and organization need to be improved.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DxL0j3pHgg9", "reviewer": "Reviewer_7DAR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studies approximation power of DL-based PDE solvers, mainly the Deep Ritz Methods (DRM) and Physics-informed neural neural network method (PINN). A key observations is proposition 2.1/2.2, in which generalization/approximation error is upper/lower bounded tightly by certain energy functional $ E = E(u, |\\nabla u|, \\Delta u, ...)$. As such, the problems themself are reduced to the classical machine learning setting:  **generalization bound = complexity bound + approximation bound**. The paper proceeds (in the appendix) to control these two using local Rademacher complexity argument (where assumptions of uniform bounded are needed), B-splines, covering numbers... (The appendix is not very well organized!)\n\nA couple comments of the experimental sections. \n\n(1) Sec 6.3 seems not directly related to the paper (PDE solver). They are quite universally observed in DL. \n(2) Could you provide a link for the code/ colab? \n\nCrucial assumptions for Theorem 4.2, 4.2 etc have been mentioned in the main text, though it is brought up in discussion section. \n\n[Strength] The paper provides several bounds (rigorous proof) for the approximation error for deep-learning-based PDE solvers, some of these bounds are tight. \n\n\n[Weakness] \n(1) The assumptions (e.g. eq (A.43), the functions, derivatives are UNIFORMLY bounded) are quite strong as acknowledged by the authors, which rule out many interesting cases and remove higher order terms in the proof.  \n(2) The paper is about approximation / representation power of neural networks. Optimization and thus optimization-related-generalization are not covered by the paper. \n\n\n\n\nMinor: \n(1) The appendix is long. It is not easy to find the proof of each theorem in the appendix. Please provide a pointer to the proof of each theorem. \n(2) Given the length of the appendix ~ 50 pages, it should have a content page, a brief introduction to walk the readers through its main structure, what is the main theme of each section, etc.  ", "summary_of_the_paper": "Applying deep learning (DL) to solving PDEs numerically has been a very exciting research directions. The current paper studies certain statistics properties of approximating linear Elliptic PDEs using neural networks (and truncated Fourier series). Under certain (quite strong) assumptions on the function class, the authors proved sharper (in some cases, tight)  bounds for the approximation errors. ", "summary_of_the_review": "DL-based PDE solvers are important and exciting direction of deep learning. The current paper provides several insights about the statistical properties of DL-based solver. Although there are several limitation (mentioned above), I think the contribution is significant enough for a ICLR publication and many researchers in the ICLR community will find it insightful (at least for me)   ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new theory for modified DRM and PINN for solving elliptical PDEs, and delivers valuable advances on important topics.
Decision: Accept (Poster)