remarkRemark hypothesisHypothesis claimClaim Statistical Numerical PDEPreprint
Version ex_supplement

# Machine Learning For Elliptic PDEs:
Fast Rate Generalization Bound, Neural Scaling Law and Minimax Optimality

Yiping Lu Institute for Computational and Mathematical Engineering, Stanford
University, Stanford, CA (, https://web.stanford.edu/~yplu/).
<EMAIL_ADDRESS>Haoxuan Chen Department of Computing and Mathematical
Sciences, Caltech<EMAIL_ADDRESS>Jianfeng Lu Mathematics Department,
Duke University<EMAIL_ADDRESS>Lexing Ying) Department of
Mathematics and Institute for Computational and Mathematical Engineering,
Stanford University, Stanford, CA<EMAIL_ADDRESS>Jose Blanchet
Department of Management Science & Engineering, Stanford University, Stanford,
CA<EMAIL_ADDRESS>
###### 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ö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 a power law, we supply computational experiments to show similar-behavior
of dimension dependent power law for deep PDE solvers.

###### keywords:

Machine Learning, Non-parametric Statistics, Deep Ritz Methods, Physics
Informed Neural Network

62G05, 65N15, 68T07

##  1 Introduction

Partial differential equations (PDEs) play a prominent role in many
disciplines of science and engineering. 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 [45, 44, 58, 26, 68, 38], especially in high dimensions where
conventional methods become impractical. The set of applications that motivate
this interest is wide-ranging, including computational physics [26, 45, 58],
inverse problem [82, 22, 17] and quantitative finance [30, 21]. The numerical
methods generated by the use of deep learning techniques are mesh-less
methods, see the discussion in [78]. A natural deep learning technique in the
problems that are based on a 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 a 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 a power law of
the data number, known as the neural scaling law [37, 31, 65], 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) [15, 38] and the Physics-
Informed Neural Networks (PINN) approach [68, 58], both of which are based on
minimizing neural network parameters according to some loss functional related
to the PDEs. To provide theoretical guarantees for DRM and PINN, following
[47, 14, 2], we decompose the error into approximation error [80, 70, 66] and
generalization error [3, 79, 18, 63, 70]. However, instead of the
$O(1/\sqrt{n})$ ($n$ is the number of data sampled) slow rate generalization
bounds established in prior work [47, 66, 78, 67], we utilize the strongly
convex structure of the DRM and PINN objectives and provide an $O(1/n)$ fast
rate generalization bound [3, 79] that leads us to a non-parametric estimation
bound. Our theory also suggests an optimal selection of network size with
respect to the number of sampled data. Moreover, to illustrate the optimality
of our upper bound, we also establish an information-theoretic lower bound
which matches our upper bound for PINN and a modified version of DRM.

We also test our theory by numerical experiments. Recent works [31, 37, 62,
51] studying a 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
$\mathcal{L}$ of well-trained and well-tuned models scales with $n$ as a
power-law $\mathcal{L}\propto\frac{1}{n^{\alpha}}$ for some $\alpha$. [65]
also scans over a large range of $\alpha$ and problem dimension $d$ and finds
an approximately $\alpha\propto\frac{1}{d}$ 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 [31, 37, 62, 61] that the empirical performance of a model satisfies
a power law scales as a power-law with model size and dataset size. [65]
further finds out that the power of the scaling law depends on the intrinsic
dimension of the dataset. Theoretical works [63, 70, 72, 9, 33, 18, 36]
explore the optimal power law under the non-parametric curve estimation
setting via a 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 in a
wide range of tasks ranging from computer vision to natural language
processing. Recent years, pioneer works [26, 58, 45, 68, 38] try to utilize
the deep neural networks to solve different types of PDEs and achieve
impressive results in many tasks [46, 42]. Based on the natural idea of
representing solutions of PDEs by (deep) neural networks, different loss
functions for solving PDEs are proposed. [26, 27] utilize the Feynman-Kac
formulation which turns solving PDE to a stochastic control problem and the
weak adversarial network [81] solves the weak formulations of PDEs via an
adversarial network. In this paper, we focus on the convergence rate of the
Deep Ritz Method (DRM) [15, 38] and Physics-Informed neural network (PINN)
[58, 68]. DRM [15, 38] 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 [58,
68] trains a 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, [47, 23, 50, 77, 78, 67, 2] investigate
the regularity of PDEs approximated by neural network and [47, 48] further
provide a generalization analysis. [54] introduces a prior over the solution
of the PDE and considers an equivalent white noise model [6]. [54] provides
the rate of convergence of the posterior. Our paper does not need to introduce
the prior on the target function and provides a non-asymptotic guarantee for
finite number of data. At the same time, [54] can only be applied to linear
PDEs while our proof technique can be extend 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 a desired statistical
convergence rate. [32, 49] consider the similar problem for the optimal
transport problem, _i.e._ Monge-ampere equation. Nevertheless, the variational
problem we considered is different from [32, 49] and leads to technical
difference. The most related works to ours are two concurrent papers [14, 34,
35]. However, our upper bound is faster than [14, 34, 35]. In this paper, we
also show that generalization analysis in [47, 14, 48] are loose due to the
lack of a localization technique [12, 3, 39, 78]. With observation of the
strong convexity of the loss function, we follow the fast rate results for ERM
[63, 79, 18] and provide a near optimal bound for both DRM and PINN.

###  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-parametric estimation of a function.

  * •

Instead of the $O(1/\sqrt{n})$ slow rate generalization bounds in [47, 14, 34,
36], we utilized the strongly convex nature of the variational form and
provided a fast rate generalization bound via the localization methods [75, 3,
39, 69, 79]. We discovered that the current Deep Ritz Methods is 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 1.

  * •

We tested the recently discovered neural scaling law [31, 37, 62, 28] for deep
PDE solvers numerically. The empirical results verified our theory.

Upper Bounds | Lower Bound
---|---
Objective Function | Neural Network | Previous Bound | Fourier Basis
Deep Ritz | $n^{-\frac{2s-2}{d+2s-2}}\log n$ |  $n^{-\frac{2s-2}{d+4s-4}}\log n$ [14] | $n^{-\frac{2s-2}{d+2s-2}}$ | $n^{-\frac{2s-2}{d+2s-4}}$
Modified Deep Ritz | $n^{-\frac{2s-2}{d+2s-2}}\log n$ | / | $n^{-\frac{2s-2}{d+2s-4}}$ | $n^{-\frac{2s-2}{d+2s-4}}$
PINN | $n^{-\frac{2s-4}{d+2s-4}}\log n$ |  $n^{-\frac{2s-4}{d+4s-8}}\log n$ [34] | $n^{-\frac{2s-4}{d+2s-4}}$ | $n^{-\frac{2s-4}{d+2s-4}}$
Table 1: 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.

##  2 Set-up

We consider the static Schrödinger equation with zero Dirichlet boundary
conditions on the domain $\Omega$, which we assume to be the unit hypercube in
${\mathbb{R}}^{d}$. In order to precisely introduce the problem, we recall
some standard notions. We consider our domain as $\Omega=[0,1]^{d}$ and use
$L^{2}(\Omega)$ to denote the space of square integrable functions on $\Omega$
with respect to the Lebesgue measure. We let $L^{\infty}(\Omega)$ be the space
of essentially bounded (with respect to the Lebesgue measure) functions on
$\Omega$ and $C(\partial\Omega)$ denotes the space of continuous functions on
$\partial\Omega$.

Let $f\in L^{2}(\Omega)$, $V\in L^{\infty}(\Omega)$, and , $g\in
L^{\infty}(\Omega)$. Our focus is on the analysis of Deep-Learning-based
numerical methods to solve the elliptic equations

(2.1) $\displaystyle-\Delta u+Vu$ $\displaystyle=f\quad\text{ in }\Omega,$
$\displaystyle u$ $\displaystyle=g\quad\text{ on }\partial\Omega.$

###  2.1 Loss Functions for Solving PDEs and Induced Evaluation Metric

In this paper, we mainly focus on analyzing Deep Ritz Methods (DRM) and
Physics Informed Neural Network (PINN). In this subsection, we first introduce
the objective function and algorithm of the two methods.

##### Deep Ritz Methods

[15, 68] Recall that the equation 2.1 is equivalent to following variational
form

(2.2)
$u^{\ast}=\arg\min_{H_{0}^{1}(\Omega)}{\mathcal{E}}^{\text{DRM}}(u):=\frac{1}{2}\int_{\Omega}|\nabla
u|^{2}+V|u|^{2}\ dx-\int_{\Omega}fudx,$

where $u$ is minimized over $H_{0}^{1}(\Omega)$ with boundary condition given
by $g$ on $\partial\Omega$.

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 equation 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
${\mathcal{F}}\subset H^{1}(\Omega)$. In this paper, we also rely on the
strong convexity of the DRM objective respect to the $H^{1}$ norm.

######  Proposition 2.1.

We further assume $0<V_{\min}\leq V(x)\leq V_{\max}$, then we have

$\frac{2}{\max\\{1,V_{\max}\\}}\left({\mathcal{E}}^{\text{DRM}}(u)-{\mathcal{E}}^{\text{DRM}}(u^{\ast})\right)\leq\|u-u^{\ast}\|_{H^{1}}^{2}\leq\frac{2}{\max\\{1,V_{\min}\\}}\left({\mathcal{E}}^{\text{DRM}}(u)-{\mathcal{E}}^{\text{DRM}}(u^{\ast})\right)$

holds for all $u\in H_{0}^{1}(\Omega)$

##### Physics-Informed Neural Network

[58, 68]. PINN solves 2.1 via minimizing the following objective function

$u^{\ast}=\arg\min_{H_{0}^{1}(\Omega)}{\mathcal{E}}^{\text{PINN}}(u):=\arg\min_{H_{0}^{1}(\Omega)}\int_{\Omega}|\Delta
u(x)-V(x)u(x)+f(x)|^{2}dx.$

The objective function ${\mathcal{E}}^{\text{PINN}}$ can also be viewed as the
population risk function and we can train an optimal estimator approximation
of the solution to the PDE within a parameterized hypothesis function class
${\mathcal{F}}\subset H_{0}^{1}(\Omega)$. In this paper, we also rely on the
strong convexity of the PINN objective with respect to the $H^{2}$ norm, for
which we need some additional assumptions on the potential.

######  Proposition 2.2.

For PINN, we further assume $V\in L^{\infty}(\Omega)$ with
$0<C_{\min}<V^{2}-\Delta V,0<C_{\min}<V(x)\leq V_{\max}$ and $-\Delta V(x)\leq
V_{\max}$, then we have for all $u\in H_{0}^{1}(\Omega)$

$\frac{1}{2\left(1+V_{\max}+V_{\max}^{2}\right)}\left({\mathcal{E}}^{\text{PINN}}(u)-{\mathcal{E}}^{\text{PINN}}(u^{\ast})\right)\leq\|u-u^{\ast}\|_{H^{2}}^{2}\\\
\leq\frac{2}{\max\\{1,C_{\min}\\}}\left({\mathcal{E}}^{\text{PINN}}(u)-{\mathcal{E}}^{\text{PINN}}(u^{\ast})\right).$

###  2.2 Estimator Setting

##### Empirical Loss Minimization

In order to access the $d$-dimensional integrals, DRM [15, 38] and PINN[58,
68] 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_{j}\\}_{j=1}^{n}$ be an
i.i.d. sequence of random variables distributed according to the uniform
distribution in domain ${\mathcal{P}}_{\Omega}$. We also have access to
$f_{j}=f(X_{j})+\xi_{i},j=1,\cdots,n$ is the noisy observation of the right
hand side of the PDE (2.1) and $\xi$ is a bounded random variable with mean
zero and independent with $X_{j}$. Define the empirical losses
${\mathcal{E}}_{n,S}$ by setting

(2.3) $\displaystyle{\mathcal{E}}^{\text{DRM}}_{n}(u)$
$\displaystyle=\frac{1}{n}\sum_{j=1}^{n}\Big{[}|\Omega|\cdot\Big{(}\frac{1}{2}|\nabla
u(X_{j})|^{2}+\frac{1}{2}V(X_{j})|u(X_{j})|^{2}-f_{j}u(X_{j})\Big{)}\Big{]},$
(2.4) $\displaystyle{\mathcal{E}}^{\text{PINN}}_{n}(u)$
$\displaystyle=\frac{1}{n}\sum_{j=1}^{n}\Big{[}|\Omega|\cdot\Big{(}\Delta
u(X_{j})-V(X_{j})u(X_{j})+f_{j}\Big{)}^{2}\Big{]},$

where $|\Omega|$ represent the Lebesgue measure of the sets.

Once given an empirical loss ${\mathcal{E}}^{\prime}_{n}$, we apply the
empirical loss minimization to seek the estimation $u_{n}$, i.e.
$u_{n}=\operatorname*{arg\,min}_{u\in{\mathcal{F}}}{\mathcal{E}}_{n}(u)$ where
${\mathcal{F}}$ is the parametrized hypothesis function space we consider. For
example, reproducing kernel Hilbert space[10] and tensor training format[60].
In this paper, we consider sparse neural network and truncated fourier basis,
which can achieves min-max optimal estimation rate for the non-parametric
function estimation[74, 63, 18, 70, 9, 36, 55].

##### Sparse Neural Network Function Space

In this paper, the hypothesis function space $\mathcal{F}$ is expressed by the
neural network following [63, 70, 18]. Let us denote the ReLU3 activation by
$\eta_{3}(x)=\max\\{x^{3},0\\}~{}(x\in\mathbb{R})$ which is used in [15], and
for a vector $x$, $\eta(x)$ is operated in an element-wise manner. Define the
neural network with height $L$, width $W$, sparsity constraint $S$ and norm
constraint $B$ as

$\displaystyle\Phi(L,W,S,B):=\\{(\mathcal{W}^{(L)}\eta_{3}(\cdot)+b^{(L)})\circ\cdots(\mathcal{W}^{(2)}\eta_{3}(\cdot)+b^{(2)})\circ(\mathcal{W}^{(1)}x+b^{(1)})\
|\ $ $\displaystyle\mathcal{W}^{(L)}\in\mathbb{R}^{1\times
W},b^{(L)}\in\mathbb{R},\mathcal{W}^{(1)}\in\mathbb{R}^{W\times
d},b^{(1)}\in\mathbb{R}^{W},\mathcal{W}^{(l)}\in\mathbb{R}^{W\times
W},b^{(l)}\in\mathbb{R}^{W}(1<l<L),$ (2.5)
$\displaystyle\sum_{l=1}^{L}(\|\mathcal{W}^{(l)}\|_{0}+\|b^{(l)}\|_{0})\leq
S,\max_{l}\|\mathcal{W}^{(l)}\|_{\infty,\infty}\vee\|b^{(l)}\|_{\infty}\leq
B\\},$

where $\circ$ denotes the function composition, $\|\cdot\|_{0}$ is the
$\ell_{0}$-norm of the matrix (the number of non-zero elements of the matrix)
and $\|\cdot\|_{\infty,\infty}$ is the $\ell_{\infty}$-norm of the matrix
(maximum of the absolute values of the elements).

##### Truncated Fourier Basis Estimator

We also considered the Truncated Fourier basis as our estimator. Suppose the
domain we interested $\Omega\subseteq[0,1]^{d}$. For any $z\in\mathbb{N}^{d}$,
we consider the corresponding Fourier basis function $\phi_{z}(x):=e^{2\pi
i\langle z,x\rangle}\ (x\in\Omega)$. Any function $f\in L^{2}(\Omega)$ can be
represented as weighted sum of the Fourier basis
$f(x):=\sum_{z\in\mathbb{N}^{d}}f_{z}\phi_{z}(x)$ where
$f_{z}:=\int_{\Omega}f(x)\overline{\phi_{z}(x)}dx\ (\forall\
z\in\mathbb{N}^{d})$ is the Fourier coefficient. This inspired us to use the
Fourier Basis whose index lies in a truncated set
$Z_{\xi}=\\{z\in\mathcal{Z}|\|z\|_{\infty}\leq\xi\\}$ to represent the
function class ${\mathcal{F}}$ as
${\mathcal{F}}_{\xi}=\\{\sum_{\|z\|_{\infty}\leq\xi}a_{z}\phi_{z}|a_{z}\in\mathbb{R},\|z\|_{\infty}\leq\xi\\}$.

##  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^{1}$ norm for DRM and $H^{2}$ norm for PINN as the evaluation
metric. The lower bound shown as follows.

######  Theorem 3.1 (Lower bound).

We denote $u^{\ast}(f)$ to be the solution of the PDE 2.1 and we can access
randomly sampled data $\\{X_{i},f_{i}\\}_{i=1,\cdots,n}$ as described in
Section 2.2. We further assume $u^{\ast}(f)\in H^{s}$ for a given
$s\in\mathbb{Z}^{+}$, we have the following lower bounds.

##### DRM Lower Bound.

For all estimators $\psi:\left(\mathbb{R}^{d}\right)^{\otimes
n}\times\mathbb{R}^{\otimes n}\rightarrow H^{s}(\Omega)$, we have

(3.1) $\displaystyle\inf_{\psi}\sup_{u^{\ast}\in
H^{s}(\Omega)}\mathbb{E}\|\psi(\\{X_{i},f_{i}\\}_{i=1,\cdots,n})-u^{\ast}(f)\|_{H^{1}}^{2}\gtrsim
n^{-\frac{2s-2}{d+2s-4}}.$

##### PINN Lower Bound.

For all estimators $\psi:\left(\mathbb{R}^{d}\right)^{\otimes
n}\times\mathbb{R}^{\otimes n}\rightarrow H^{s}(\Omega)$, we have

(3.2) $\displaystyle\inf_{\psi}\sup_{u^{\ast}\in
H^{s}(\Omega)}\mathbb{E}\|\psi(\\{X_{i},f_{i}\\}_{i=1,\cdots,n})-u^{\ast}(f)\|_{H^{2}}^{2}\gtrsim
n^{-\frac{2s-4}{d+2s-4}}.$

######  Proof 3.2.

We construct the following bump function to construct the multiple hypothesis
test used for proving the lower bound. Consider a simple $C^{\infty}$ bump
function supported on $[0,1]^{d}$

$g(x)=\prod_{i=1}^{d}\xi(x_{i}),x=(x_{1},\cdots,x_{d}),$

where $\xi:\mathbb{R}\rightarrow\mathbb{R}$ is a non-zero funtion in
$C^{\infty}(\mathbb{R})$ with support contained in $[0,1]$ and satisfies
$\xi(x)\not=0,\frac{d}{dx}\xi(x)\not=0$. Then $\nabla g(x)\not=0$ and the
support of function $g$ is $[0,1]^{d}$.

Next, we take $m=[n^{\frac{1}{2s-4+d}}]$ and consider a regular gird
$x^{(j)},j\in[m]^{d}$. According to the Varshamov-Gilbert lemma, there exist
$2^{m^{d}/8}$ $(0,1)$-sequences
$\tau^{(1)},\cdots,\tau^{(2^{m^{d}/8})}\in\\{0,1\\}^{m^{d}}$ such that
$\|\tau^{(k)}-\tau^{(k^{\prime})}\|^{2}\geq\frac{m^{d}}{8}$ for all
$0<k\not=k^{\prime}\leq 2^{m^{d}/8}$. Then we construct the multiple
hypothesis as

$u_{k}(x)=\sum_{j\in[m]^{d}}\tau_{j}^{(k)}\frac{\omega}{m^{s+\frac{d}{2}}}g(m(x-x^{(j)})),k=1,2,\cdots,2^{m^{d}/8},$

where $\omega$ is a constant to be determined later. It is easy to find out
that $u_{k}\in C^{s}$.

Then we reduce solving the PDE to a multiple hypothesis testing problem, which
considers all mappings from $n$ sampled data to the constructed hypothesis
$\Psi:\left(\mathbb{R}^{d}\right)^{\otimes n}\times\mathbb{R}^{\otimes
n}\rightarrow\mathcal{V}:=\\{u_{i}|i=1,2,\cdots,2^{m^{d}/8}\\}$. Then we apply
the local Fano method and check that we can obtain a constant lower bound of
$\mathcal{P}(\hat{V}\not=V)$ for any estimator $\hat{V}$. From the local Fano
method, we know that

$\displaystyle
I(V;X)\leq\frac{1}{|\mathcal{V}|^{2}}\sum_{z}\sum_{v\not=v^{\prime}}D_{KL}(P_{v}||P_{v}^{\prime}),$

where $P_{k}$ denotes the joint distribution of the sampled data $(x,y)$. In
specific, $x$ follows a uniform distribution on $[0,1]^{d}$ and
$y=f(X)+\epsilon$, where $\epsilon$ is independently sampled from a standard
Gaussian distribution $N(0,1)$. Then we have

$KL(P_{k}||P_{k^{\prime}})=\mathbb{E}\log(\frac{dP_{k}}{dP_{k^{\prime}}})=\|\Delta
u_{k}+Vu_{k}\|_{L_{2}}^{2}\leq\frac{C\omega}{m^{2s-4}}.$

Using Fano inequality, if we select $m\propto[n^{\frac{1}{2s-4+d}}]$ then we
have the following lower bound when $\omega$ is taken to be sufficiently
large:

$\mathcal{P}(\hat{V}\not=V)\geq 1-\frac{I(V;X)+\log
2}{\log(|\mathcal{V}|)}\geq 1-\frac{\frac{8C\omega}{m^{2s-4}}}{m^{d}\log
2}\geq 1/2.$

At the same time, we can estimate the separation of the hypotheses in two
different norms:

  * •

Deep Ritz Method:

$\int_{[0,1]^{d}}\|\nabla u_{k}-\nabla
u_{k^{\prime}}\|^{2}dx=\frac{\kappa^{2}}{m^{2s-2+d}}\sum_{j\in[m]^{d}}\|\tau_{j}^{(k)}-\tau_{j}^{(k^{\prime})}\|_{1}\int_{\mathbb{R}^{d}}\|\nabla
g(x)\|^{2}dx\gtrsim\frac{1}{m^{2s-2}}.$

  * •

Physic Informed Neural Network:

$\int_{[0,1]^{d}}\|\Delta u_{k}-\Delta
u_{k^{\prime}}\|^{2}dx=\frac{\kappa^{2}}{m^{2s-4+d}}\sum_{j\in[m]^{d}}\|\tau_{j}^{(k)}-\tau_{j}^{(k^{\prime})}\|_{1}\int_{\mathbb{R}^{d}}\Delta
g(x)^{2}dx\gtrsim\frac{1}{m^{2s-4}}.$

Plugging in $m\propto[n^{\frac{1}{2s-4+d}}]$, we know that with constant
probability we have

(3.3) $\displaystyle\inf_{\psi}\sup_{u^{\ast}\in
H^{s}(\Omega)}\mathbb{E}\|\psi(\\{X_{i},Y_{i}\\}_{i=1,\cdots,n})-u^{\ast}(f)\|_{H^{1}}^{2}\gtrsim
n^{-\frac{2s-2}{d+2s-4}},$

(3.4) $\displaystyle\inf_{\psi}\sup_{u^{\ast}\in
H^{s}(\Omega)}\mathbb{E}\|\psi(\\{X_{i},Y_{i}\\}_{i=1,\cdots,n})-u^{\ast}(f)\|_{H^{2}}^{2}\gtrsim
n^{-\frac{2s-4}{d+2s-4}}.$

Given that $n^{-\frac{2(\beta-k)}{d+2\beta}}$ is the minimax rate of
estimation of the $k$-th derivative of a $\beta$-smooth density in $L_{2}$
[43, 57, 53], 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^{-1}$
norm error estimate on $f$, we can achieve estimate of $u$, which provides an
alternative way to understand our upper bound. The lower bound is non-
standard, for the $2s-2$ in the numerator is different from the $2s-4$ in the
denominator.

##  4 Upper Bound

To theoretically understand the empirical success of Physics Informed Neural
Networks and the Deep Ritz solver, in this section, we aim to prove that the
excess risk
$\Delta{\mathcal{E}}_{n}:={\mathcal{E}}(u_{n})-{\mathcal{E}}(u^{\ast})$ of a
well-trained neural networks on the PINN/DRM loss function will follow a
precise power-law scaling relations with the size of the training dataset.
Similar to [78, 47, 14, 34, 35], we decompose the excess risk into
approximation error and generalization error. Different from the concurrent
bound [14, 34], we provided a fast rate $O(1/n)$ by utilizing the strong
convexity of the objective function established in Section 2.1 and achieved a
faster and near optimal upper bound.

###  4.1 Proof Sketch

##### Error Decomposition.

We first decompose the excess risk
$\Delta{\mathcal{E}}_{n}:={\mathcal{E}}(u_{n})-{\mathcal{E}}(u^{\ast})$ of a
well-trained neural network on the PINN/DRM loss function into approximation
error and generalization error, similar to [78, 47, 14, 34, 35]. The
regularity results used in the decomposition are proved in Appendix A.2.
Explicitly, for any $u_{{\mathcal{F}}}\in{\mathcal{F}}(\Omega)$, we can
decompose the excess risk as

(4.1) $\displaystyle\Delta{\mathcal{E}}^{(n)}(\hat{u})$
$\displaystyle={\mathcal{E}}(\hat{u})-{\mathcal{E}}(u^{\star})$
$\displaystyle=\big{[}{\mathcal{E}}(\hat{u})-{\mathcal{E}}_{n}(\hat{u})\big{]}+\big{[}{\mathcal{E}}_{n}(\hat{u})-{\mathcal{E}}_{n}(u_{{\mathcal{F}}})\big{]}+\big{[}{\mathcal{E}}_{n}(u_{{\mathcal{F}}})-{\mathcal{E}}(u_{{\mathcal{F}}})\big{]}+\big{[}{\mathcal{E}}(u_{{\mathcal{F}}})-{\mathcal{E}}(u^{\star})\big{]}$
$\displaystyle\leq\underbrace{\big{[}{\mathcal{E}}(\hat{u})-{\mathcal{E}}_{n}(\hat{u})\big{]}+\big{[}{\mathcal{E}}_{n}(u_{{\mathcal{F}}})-{\mathcal{E}}(u_{{\mathcal{F}}})\big{]}}_{\text{Generalization
Error}}+\underbrace{\big{[}{\mathcal{E}}(u_{{\mathcal{F}}})-{\mathcal{E}}(u^{\star})\big{]}}_{\text{Approximation
Error}},$

where the expectation is on uniformly sampled data, ${\mathcal{F}}(\Omega)$ is
the space of parametrized estimators we used like truncated Fourier series or
sparse neural networks, $\hat{u}$ is the minimizer of the empirical loss
${\mathcal{E}}_{n}$ in ${\mathcal{F}}(\Omega)$ and $u^{\ast}$ is the minimizer
of the population loss ${\mathcal{E}}$ (i.e, ground truth solution). The
inequality in the third line follows from the fact that $\hat{u}$ is the
minimizer of the empirical loss ${\mathcal{E}}_{n}$ in the space
${\mathcal{F}}(\Omega)$, which implies
${\mathcal{E}}_{n}(\hat{u})\leq{\mathcal{E}}_{n}(u_{{\mathcal{F}}})$. We call
the first term generalization error as it’s measuring the difference between
${\mathcal{E}}_{n}$ and ${\mathcal{E}}$. We call the second term approximation
error as it seeks for a parametrized estimator $u_{{\mathcal{F}}}$ that
approximates the ground truth solution $u^{\ast}$ well in
${\mathcal{F}}(\Omega)$. 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(\frac{1}{\sqrt{n}})$ [14, 34], we
provide a faster and near optimal upper bound $O(\frac{1}{n})$ by utilizing
the strong convexity of the objective function established in Appendix A.2.
Via using the Peeling Lemma (Lemma A.9, 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

$\phi(r)=R_{n}(\\{\mathcal{I}(u)\ |\ \|u-u^{\ast}\|_{A}^{2}\leq r\\}),$

where $R_{n}$ is the Rademacher complexity, $\mathcal{I}(u)=\Delta
u+Vu,\|\cdot\|_{A}=\|\cdot\|_{H^{2}}$ for PINN and $\mathcal{I}(u)=\|\nabla
u\|^{2}+Vu,\|\cdot\|_{A}=\|\cdot\|_{H^{1}}$ for DRM. Once we show that
$\phi(r)$ is of magnitude $O(\sqrt{\frac{r}{n}})$, we can achieve the
$O(\frac{1}{n})$ convergence rate via solving the fix point equation
$\phi(r)=O(\sqrt{\frac{r}{n}})=r\Rightarrow r=O(\frac{1}{n})$. Using the
solution of the fixed point equation of the local Rademacher complexity to
bound the generalization error is a standard result in empirical process [3,
69, 39, 79, 18]. The difference is that we used the $H^{1}$/$H^{2}$ norm to
define the localized set, while the previous papers used the $\ell_{2}$
distance. The way to obtain the fast rate generalization bound is using the
Peeling Lemma.

We present the error decomposition results as a meta theorem, which is shown
in Theorem 4.19 for PINN (proof in Appendix A.4), Theorem 4.13 for DRM and
Theorem 5.1 for MDRM (proof in Appendix A.5), respectively. To make the final
rate depend on the data number only, we need bounds of the approximation error
in Section 4.2 and bounds of the local Rademacher complexity in Appendix A.3.

##### Approximation Error.

The proof of the approximation results of truncated Fourier series is easy and
intuitive. For completeness, we provide it in Section 4.2.1. The proof of the
approximation results of neural networks follows from the fact that a B-spline
approximation can be formulated as a ReLU3 neural network efficiently. Our
proof basically follows [14, 34], while the only difference is the activation
function. Our proof is also very similar to [80, 70], but the depth of our
network is of constant magnitude instead of $O(\frac{1}{\log\epsilon})$
magnitude, where ${\varepsilon}$ denotes the desired approximation error. Such
improvement of depth results from the fact that ReLU3 activations can
approximate B-splines more easily than the ReLU 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 4.2.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 $\phi(r)=r$.
Once we have a $O(\sqrt{\frac{r}{n}})$ bound of $\phi(r)$, we can achieve the
$O(\frac{1}{n})$ fast rate generalization bound we want. It remains to upper
bound the the local Rademacher complexity $\phi(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^{1}$ norm is $\sqrt{\frac{\xi^{d-2}r}{n}}$. The term $\xi^{d-2}$ in the
numerator is smaller than $\xi^{d}$, which is the exact number of Fourier
basis. This improvement results from the $H^{1}$ norm localization. The
detailed proof is given in Lemma 4.8, Lemma 4.9 and Lemma 4.10.

For the upper bound on the local Rademacher complexity bound for neural
network, we follow [63, 70, 18] to use a Dudley integral theorem and a
covering number argument. The covering number arguments are shown in Theorem
A.28, Theorem A.36 and Theorem A.42. The final local Rademacher complexity
bounds are given in Lemma 4.11 and Lemma 4.12. The difference is that the
complexity of gradient of ReLU3 activation function makes the covering number
depend exponentially on the neural network’s depth. However, the improvement
of neural network’s depth to constant magnitude mentioned above in the
approximation results saves this problem. One drawback of our proof is that
the $H^{1}$ 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 a right complexity
measure of neural network for solving PDEs as a future work.

Objective Function | Estimator | Approximation | Generalization | Complexity Measure
---|---|---|---|---
PINNs | Neural Network | $N^{-\frac{2s-4}{d}}$ | $\frac{N}{n}$ |  $N$: Number of parameters
Fourier Seriers | $\xi^{-2(s-2)}$ | $\frac{\xi^{d}}{n}$ |  $\xi$:maximum frequency
DRM | Neural Network | $N^{-\frac{2s-2}{d}}$ | $\frac{N}{n}$ |  $N$: Number of parameters
Fourier Seriers | $\xi^{-2(s-1)}$ | $\frac{\xi^{d}}{n}$ |  $\xi$:maximum frequency
MDRM | Neural Network | $N^{-\frac{2s-2}{d}}$ | $\frac{N}{n}$ |  $N$: Number of parameters
Fourier Seriers | $\xi^{-2(s-1)}$ | $\frac{\xi^{d-2}}{n}$ |  $\xi$:maximum frequency
Table 2: Approximation and generalization results we achieved in this paper.

###  4.2 Bounding the Approximation Error

####  4.2.1 Approximation using Truncated Fourier Basis

######  Lemma 4.1.

Given $\alpha>0$ and a fixed integer $\xi\in\mathbb{Z}^{+}$. For any function
$f\in H^{\alpha}(\Omega)$ , we let
$f_{\xi}=\sum_{\|z\|_{\infty}\leq\xi}f_{z}\phi_{z}$ be the best approximation
of $f$ in the space $F_{\xi}(\Omega)$. Then for any $0<\beta\leq\alpha$, we
have the following inequality:

$\displaystyle\|f-f_{\xi}\|_{H^{\beta}(\Omega)}^{2}\leq\xi^{-2(\alpha-\beta)}\|f\|_{H^{\alpha}}^{2}.$

######  Proof 4.2.

For $f\in H^{\alpha}(\Omega)$, we know the Fourier coefficient satisfies

$\displaystyle\sum_{\|z\|_{\infty}\geq\xi}|f_{z}|^{2}\|z\|^{2\alpha}\lesssim\|f\|_{H^{\alpha}}^{2}.$

We directly construct $f_{\xi}=\sum_{\|z\|_{\infty}\leq\xi}f_{z}\phi_{z}$ to
be the truncated Fourier series of the function $f$, then we have

$\displaystyle\|f-f_{\xi}\|_{H^{\beta}(\Omega)}^{2}\lesssim\sum_{\|z\|_{\infty}\geq\xi}|f_{z}|^{2}\|z\|^{2\beta}\leq\xi^{-2(\alpha-\beta)}\sum_{\|z\|_{\infty}\geq\xi}|f_{z}|^{2}\|z\|^{2\alpha}\leq\xi^{-2(\alpha-\beta)}\|f\|_{H^{\alpha}}^{2}.$

####  4.2.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[12, 64] can be formulated as a
ReLU3 neural network efficiently[70, 25, 14, 34]. 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 4.3.

(Univariate and Multivariate B-splines) Fix an arbitrary integer
$l\in\mathbb{Z}^{+}$. Consider a corresponding uniform partition $\pi_{l}$ of
$[0,1]$:

$\displaystyle\pi_{l}:0=t_{0}^{(l)}<t_{1}^{(l)}<\cdots<t_{l-1}^{(l)}<t_{l}^{(l)}=1,$

where $t_{i}^{(l)}=\frac{i}{l}\ (\forall\ 0\leq i\leq l)$. Now for any
$k\in\mathbb{Z}^{+}$, we can define an extended partition $\pi_{l,k}$ as:

$\displaystyle\pi_{l,k}:t_{-k+1}^{(l)}=\cdots
t_{-1}^{(l)}=0=t_{0}^{(l)}<t_{1}^{(l)}<\cdots<t_{l-1}^{(l)}<t_{l}^{(l)}=1=t_{l+1}^{(l)}=\cdots=t_{l+k-1}^{(l)}$

Based on the extended partition $\pi_{l,k}$, the univariate B-splines of order
$k$ with respect to partition $\pi_{l}$ are defined by:

(4.2)
$N_{l,i}^{(k)}(x):=(-1)^{k}(t_{i+k}^{(l)}-t_{i}^{(l)})\cdot\Big{[}t_{i}^{(l)},\cdots,t_{i+k}^{(l)}\Big{]}\max\\{(x-t),0\\}^{k-1},\
x\in[0,1],\ i\in I_{l,k}$

where $I_{l,k}=\\{-k+1,-k+2,\cdots,l-1\\}$ and
$\Big{[}t_{i}^{(l)},\cdots,t_{i+k}^{(l)}]$ denotes the divided difference
operator.
Equivalently, for any $x\in[0,1]$, we can rewrite the univariate B-splines
$N_{l,i}^{(k)}(x)$ in an explicit form:

(4.3)
$N_{l,i}^{(k)}(x)=\begin{cases}\frac{l^{k-1}}{(k-1)!}\sum_{j=0}^{k}(-1)^{j}{k\choose
j}\max\Big{\\{}x-\frac{i+j}{l},0\Big{\\}}^{k-1},\ (0\leq i\leq l-k+1)\\\
\sum_{j=0}^{k-1}a_{ij}\max\Big{\\{}x-\frac{j}{l},0\Big{\\}}^{k-1}+\sum_{n=1}^{k-2}b_{in}x^{n}+b_{i0},\
(-k+1\leq i\leq 0)\\\
\sum_{j=l-k+1}^{l}c_{ij}\max\Big{\\{}x-\frac{j}{l},0\Big{\\}}^{k-1},\
(l-k+1\leq i\leq l-1)\end{cases}$

where $\\{a_{ij}\ |\ -k+1\leq i\leq 0,\ 0\leq j\leq k-1\\}$, $\\{b_{in}\ |\
-k+1\leq i\leq 0,\ 1\leq n\leq k-2\\}$ and $\\{c_{ij}\ |\ l-k+1\leq i\leq
l-1,\ l-k+1\leq j\leq l-1\\}$ are some fixed constants.
For any index vector $\bm{i}=(i_{1},i_{2},\cdots,i_{d})\in I_{l,k}^{d}$, we
can define a corresponding multivariate B-spline as a product of univariate
B-splines:

(4.4) $N_{l,\bm{i}}^{(k)}(\bm{x}):=\Pi_{j=1}^{d}N_{l,i_{j}}^{(k)}(x_{j}).$

######  Definition 4.4.

(Interpolation Operator[64]) Take some domain $\Omega\subset[0,1]^{d}$ and two
arbitrary integers $k,l\in\mathbb{Z}^{+}$. Consider the extended partition
$\pi_{l,k}$ and the corresponding set of multivariate B-splines
$\\{N_{l,\bm{i}}^{(k)}(x)\\}_{\bm{i}\in I_{l,k}^{d}}$ defined in Definition
4.3. For any $\bm{i}\in I_{l,k}^{d}$, we define the domain
$\Omega_{\bm{i}}:=\\{\bm{x}\in\Omega:x_{j}\in[t_{i_{j}},t_{i_{j}+k}],\ 1\leq
j\leq d\\}$. There exists a set of linear functionals
$\\{\lambda_{\bm{i}}\\}_{\bm{i}\in I_{k,l}^{d}}$, where
$\lambda_{\bm{i}}:L^{1}(\Omega)\rightarrow\mathbb{R}\ (\forall\ \bm{i}\in
I_{k,l}^{d})$, such that for any $\bm{i}\in I_{k,l}^{d}$ and $p\in[1,\infty]$,
we have:

(4.5) $\lambda_{\bm{i}}(N_{l,\bm{j}}^{(k)})=\delta_{\bm{i},\bm{j}}\text{ and
}|\lambda_{\bm{i}}(f)|\leq
9^{d(k-1)}(2k+1)^{d}\Big{(}\frac{k}{l}\Big{)}^{-\frac{d}{p}}\|f\|_{L^{p}(\Omega_{\bm{i}})},\
\forall\ f\in L^{p}(\Omega).$

The corresponding interpolation operator $Q_{k,l}$ is defined as:

$\displaystyle Q_{k,l}f:=\sum_{\bm{i}\in
I_{k,l}^{d}}\lambda_{i}(f)N_{l,\bm{i}}^{(k)},\ \forall\ f\in L^{1}(\Omega).$

######  Theorem 4.5.

[[64]] Fix $f\in W^{s}(\Omega)$ with
$\Omega\subseteq[0,1]^{d},s\in\mathbb{Z}^{+}$ and $p\in[1,\infty)$. Then for
any $k,l,r\in\mathbb{Z}^{+}$ with $k\geq s$ and $0\leq r\leq s$, we have that
there exists some constant $C=C(k,s,r,p,d)$, such that:

$\displaystyle\|f-Q_{k,l}f\|_{H^{r}(\Omega)}\leq
C\Big{(}\frac{1}{l}\Big{)}^{s-r}\|f\|_{H^{s}(\Omega)}.$

######  Theorem 4.6.

(Approximation result of Deep Neural Network) Fix some dimension
$d\in\mathbb{Z}^{+}$, some domain $\Omega\subseteq[0,1]^{d}$. We pick some
$l=N^{\frac{1}{d}}\geq 2$, for any $s,r\in\mathbb{Z}^{+}$ with $0\leq r\leq s$
and any function $u^{\ast}\in H^{s}(\Omega)$, there exists some sparse Deep
Neural Network $u_{\text{DNN}}\in\Phi(L,W,S,B)$ with
$L=O(1),W=O(N),S=O(N),B=O(N)$, such that:

(4.6) $\|u_{DNN}-u^{\ast}\|_{H^{r}(\Omega)}\lesssim
N^{-\frac{s-r}{d}}\|u^{\ast}\|_{H^{s}(\Omega)}.$

######  Proof 4.7.

We firstly show that the given function $u^{\ast}$ can be approximated well by
some linear combination of multivariate splines, which is denoted by
$u_{\text{sp}}$. Note that $N$ is assumed to be sufficiently large. Hence, we
may pick $l=\lceil
N^{\frac{1}{d}}\rceil=\Theta(N^{\frac{1}{d}})\in\mathbb{Z}^{+}$ to be the
partition size of the B-splines. Moreover, by picking $k=4$ and $p=2$ in
Theorem 4.5, we have that the linear combination
$u_{\text{sp}}:=Q_{4,l}u^{\ast}=\sum_{\bm{i}\in
I_{4,l}^{d}}\lambda_{i}(u^{\ast})N_{l,\bm{i}}^{(4)}$ satisfies:

$\displaystyle\|u^{\ast}-u_{\text{sp}}\|_{H^{r}(\Omega)}=\|u^{\ast}-Q_{4,l}u^{\ast}\|_{H^{r}(\Omega)}\leq
C\Big{(}\frac{1}{l}\Big{)}^{s-r}\|u^{\ast}\|_{H^{s}(\Omega)}=CN^{-\frac{s-r}{d}}\|u^{\ast}\|_{H^{s}(\Omega)}.$

We will then show that the linear combination $u_{\text{sp}}=\sum_{\bm{i}\in
I_{4,l}^{d}}\lambda_{i}(f)N_{l,\bm{i}}^{(4)}$ can be implemented by some Deep
Neural Network $u_{\text{DNN}}\in\Phi(L,W,S,B)$ with $L=O(1),W=O(N),S=O(N)$
and $B=O(\log N)$. Firstly, note that for $x\geq 0$, both $x$ and $x^{2}$ can
be expressed in terms of the ReLU3 activation function $\eta_{3}$ with no
error:

$\displaystyle x$
$\displaystyle=-\frac{1}{12}[\eta_{3}(x+3)-5\eta_{3}(x+2)+7\eta_{3}(x+1)-3\eta_{3}(x)+6]$
$\displaystyle x^{2}$
$\displaystyle=-\frac{1}{6}[\eta_{3}(x+2)-4\eta_{3}(x+1)+3\eta_{3}(x)-4]$

Applying the explicit formula listed in equation 4.3 implies that for any
$-3\leq i\leq l-1$, the univariate B-spline function $N_{l,i}^{(4)}(x)\
(x\in[0,1])$ can be implemented by some ReLU3 Deep Neural Network
$v_{\text{DNN}}$ with both scalar input and scalar output. We have that for
$v_{\text{DNN}}$, the depth $L_{v}$ is $2$ and the maximum width $W_{v}$ is
upper bounded by $11$.
Secondly, for any $x,y\geq 0$, we have that the product operation $x\cdot y$
can be expressed in terms of the ReLU3 activation function $\eta_{3}$ with no
error:

$\displaystyle x\cdot y$ $\displaystyle=\frac{1}{2}[(x+y)^{2}-x^{2}-y^{2}]$
$\displaystyle=-\frac{1}{12}\Big{[}\eta_{3}(x+y+2)-4\eta_{3}(x+y+1)+3\eta_{3}(x+y)$
$\displaystyle-\eta_{3}(x+2)+4\eta_{3}(x+1)-3\eta_{3}(x)-\eta_{3}(y+2)+4\eta_{3}(y+1)-3\eta_{3}(y)+4\Big{]}$

In [64], it has been proved that the B-splines are always non-negative, i.e
$N_{l,i}^{(4)}(x)\geq 0,\ \forall\ x\in[0,1]$. Therefore, by multiplying the
non-negative univariate B-splines, we can implement any multivariate B-spline
$N_{l,\bm{i}}^{(4)}=\Pi_{j=1}^{d}N_{l,i_{j}}^{(4)}(x_{j})$ with some ReLU3
Deep Neural Network $p_{\text{DNN}}$. We have that for $p_{\text{DNN}}$, the
depth $L_{p}=\lceil\log_{2}d\rceil+2$ and the maximum width
$W_{p}=\max\\{11d,\frac{9}{2}d\\}$.
Hence, we can further claim that $u^{\ast}=\sum_{\bm{i}\in
I_{4,l}^{d}}\lambda_{i}(u^{\ast})N_{l,\bm{i}}^{(4)}$, which is a linear
combination of the multivariate B-splines $N_{l,\bm{i}}^{(4)}$, can be
implemented by some ReLU3 Deep Neural Network $u_{\text{DNN}}$. It remains to
check that $u_{\text{DNN}}\in\Phi(L,W,S,B)$ with $L=O(1),W=O(N),S=O(N)$ and
$B=O(N)$. Note that we can ensure that the hidden layers of $u_{\text{DNN}}$
are of the same dimension $W$ by adding inactive neurons.
For the depth $L$ of $u_{\text{DNN}}$, we have that $L$ is equal to $L_{p}+1$,
where $L_{p}$ denotes the depth of the ReLU3 Deep Neural Network
$p_{\text{DNN}}$. Thus, we have $L=L_{p}+1=\lceil\log_{2}d\rceil+3$, which
implies that $L=O(1)$.
For the width $W$ of $u_{\text{DNN}}$, we have that $W\leq|I_{k,l}^{d}|W_{p}$,
where $W_{p}$ denotes the width of the ReLU3 Deep Neural Network
$p_{\text{DNN}}$. This implies:

$\displaystyle W\leq|I_{k,l}^{d}|\times
11d=11d(l+k)^{d}=11d(l+4)^{d}=O(l^{d})\Rightarrow W=O(N)$

For the sparsity constraint $S$ of $u_{\text{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$:

$\displaystyle S\leq 2(W+W+\sum_{j=0}^{L-2}\frac{W}{2^{j}})\leq 8W\Rightarrow
S=O(W)=O(N)$

For the norm constraint $B$ of $u_{\text{DNN}}$, we have the following upper
bound on $B$ from equation 4.3 and equation 4.5:

$\displaystyle B=O(\max\\{l^{k-1},\sup_{\bm{i}\in
I_{k,l}^{d}}\lambda_{\bm{i}}(u^{\ast})\\})=O(\max\\{l^{3},l^{d}\\})=O(N)$

Now we have shown that parameters $L,W,S,B$ of the Deep Neural Network
$u_{\text{DNN}}$ are of the desired magnitude, which completes our proof.

###  4.3 Bounding the Local Rademacher Complexity

####  4.3.1 Local Rademacher Complexity of Truncated Fourier Basis

In this subsection, we aim to bound the local Rademacher complexity of the
Truncated Fourier Basis estimator. The proof is standard and we put the proof
in the appendix.

######  Lemma 4.8.

(Local Rademacher Complexity of Localized Truncated Fourier Series) For a
fixed $\xi\in\mathbb{Z}^{+}$, we consider a localized class of functions
${\mathcal{F}}_{\rho,\xi}(\Omega)=\Big{\\{}f\in F_{\xi}(\Omega)\ \Big{|}\
\|f\|_{H^{1}(\Omega)}^{2}\leq\rho\Big{\\}}$, where $\rho>0$ is fixed. Then we
have the following upper bound on the local Rademacher complexity:

(4.7)
$R_{n}({\mathcal{F}}_{\rho,\xi}(\Omega))={\mathbb{E}}_{X}\left[{\mathbb{E}}_{\sigma}\Big{[}\sup_{f\in{\mathcal{F}}_{\rho,\xi}(\Omega)}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}f(X_{i})\
\Big{|}\
X_{1},\cdots,X_{n}\Big{]}\right]\lesssim\sqrt{\frac{\rho}{n}}\xi^{\frac{d-2}{2}}.$

######  Lemma 4.9.

(Local Rademacher Complexity of Localized Truncated Fourier Series’ Gradient)
For a fixed $\xi\in\mathbb{Z}^{+}$, we consider a localized class of functions
${\mathcal{G}}_{\rho,\xi}(\Omega)=\\{\|\nabla f\|\ |\ f\in
F_{\rho,\xi}(\Omega)\\}$, where $\rho>0$ is fixed. Then for any sample
$\\{X_{i}\\}_{i=1}^{n}\subset\Omega$, we have the following upper bound on the
local Rademacher complexity:

(4.8)
$R_{n}({\mathcal{G}}_{\rho,\xi}(\Omega))={\mathbb{E}}_{X}\left[{\mathbb{E}}_{\sigma}\Big{[}\sup_{f\in{\mathcal{F}}_{\rho,\xi}(\Omega)}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\|\nabla
f(X_{i})\|\ \Big{|}\
X_{1},\cdots,X_{n}\Big{]}\right]\lesssim\sqrt{\frac{\rho}{n}}\xi^{\frac{d}{2}}.$

######  Lemma 4.10.

(Local Rademacher Complexity of Localized Truncated Fourier Series’ Laplacian)
For a fixed $\xi\in\mathbb{Z}^{+}$, we consider a localized class of functions
${\bm{J}}_{\rho,\xi}(\Omega):=\Big{\\{}f\in F_{\xi}(\Omega)\ \Big{|}\
\|f\|_{H^{2}(\Omega)}^{2}\leq\rho\Big{\\}}$, where $\rho>0$ is fixed.
Correspondingly, we define a localized class of Laplacians
${\bm{K}}_{\rho,\xi}(\Omega):=\\{\Delta f\ |\ f\in J_{\rho,\xi}(\Omega)\\}$.
Then for any sample $\\{X_{i}\\}_{i=1}^{n}\subset\Omega$, we have the
following upper bound on the local Rademacher complexity:

(4.9)
$R_{n}({\bm{K}}_{\rho,\xi}(\Omega))={\mathbb{E}}_{X}\left[{\mathbb{E}}_{\sigma}\Big{[}\sup_{f\in{\mathcal{F}}_{\rho,\xi}(\Omega)}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\Delta
f(X_{i})\ \Big{|}\
X_{1},\cdots,X_{n}\Big{]}\right]\lesssim\sqrt{\frac{\rho}{n}}\xi^{\frac{d}{2}}.$

####  4.3.2 Local Rademacher Complexity of Deep Neural Networks

In this subsection, we aim to bound the local Rademacher complexity of the
Neural Network estimator. Informally, we showed that the local Rademacher
complexity is at the scale of $\sqrt{\frac{N}{n}}$, where $N$ is the number of
neuron of a neural network. For simplicity, we put the proof in the appendix.

######  Lemma 4.11 (Local Rademacher Complexity Bound for Deep Ritz Method).

Consider a Deep Neural Network space ${\mathcal{F}}(\Omega)=\Phi(L,W,S,B)$
with $L=O(1),W=O(N),S=O(N)$ and $B=O(N)$, where $N\in\mathbb{Z}^{+}$ is fixed
to be sufficiently large. Moreover, assume that the gradients and function
value of ${\mathcal{F}}(\Omega),V$ and $f$ are uniformly bounded

(4.10)
$\max\Big{\\{}\sup_{u\in{\mathcal{F}}(\Omega)}\|u\|_{L^{\infty}(\Omega)},\sup_{u\in{\mathcal{F}}(\Omega)}\|\nabla
u\|_{L^{\infty}(\Omega)},\|u^{\ast}\|_{L^{\infty}(\Omega)},\|\nabla
u^{\ast}\|_{L^{\infty}(\Omega)},V_{max},\|f\|_{L^{\infty}(\Omega)}\Big{\\}}\leq
C.$

For any $\rho>0$, we consider a localized set $L_{\rho}$ defined by:

${\bm{L}}_{\rho}(\Omega):=\\{u:u\in{\mathcal{F}}(\Omega),\|u-u^{\ast}\|_{H^{1}}^{2}\leq\rho\\}.$

Then for any $\rho\gtrsim n^{-2}$, the Rademacher complexity of a localized
function space
${\mathcal{S}}_{\rho}(\Omega):=\Big{\\{}h:=|\Omega|\cdot\left[\frac{1}{2}\Big{(}\|\nabla
u\|^{2}-\|\nabla
u^{\ast}\|^{2}\Big{)}+\frac{1}{2}V(|u|^{2}-|u^{\ast}|^{2})-f(u-u^{\ast})\right]\
\ \Big{|}\ u\in L_{\rho}(\Omega)\Big{\\}}$ can be upper bounded by a sub-root
function

$\phi(\rho):=O\left(\sqrt{\frac{S3^{L}\rho}{n}\log\left(BWn\right)}\right).$

_i.e._ we have

(4.11) $\phi(4\rho)\leq 2\phi(\rho)\text{ and
}R_{n}({\mathcal{S}}_{\rho}(\Omega))\leq\phi(\rho).\ $

holds for all $\rho\gtrsim n^{-2}$.

######  Lemma 4.12 (Local Rademacher Complexity Bound for Physics Informed
Neural Network).

Consider a Deep Neural Network space ${\mathcal{F}}(\Omega)=\Phi(L,W,S,B)$
with $L=O(1),W=O(N),S=O(N)$ and $B=O(N)$, where $N\in\mathbb{Z}^{+}$ is fixed
to be sufficiently large. Moreover, assume that the gradients and function
value of ${\mathcal{F}}(\Omega),V$ and $f$ are uniformly bounded

(4.12)
$\max\Big{\\{}\sup_{u\in{\mathcal{F}}(\Omega)}\|u\|_{L^{\infty}(\Omega)},\sup_{u\in{\mathcal{F}}(\Omega)}\|\Delta
u\|_{L^{\infty}(\Omega)},\|u^{\ast}\|_{L^{\infty}(\Omega)},\|\Delta
u^{\ast}\|_{L^{\infty}(\Omega)},V_{max},\|f\|_{L^{\infty}(\Omega)}\Big{\\}}\leq
C.$

For any $\rho>0$, we consider a localized set $M_{\rho}$ defined by:

${\mathcal{M}}_{\rho}(\Omega):=\\{u:u\in{\mathcal{F}}(\Omega),\|u-u^{\ast}\|_{H^{2}}^{2}\leq\rho\\}.$

Then for any $\rho\gtrsim n^{-2}$, the Rademacher complexity of a localized
function space
${\mathcal{T}}_{\rho}(\Omega):=\Big{\\{}h:=|\Omega|\cdot\left[(\Delta
u-Vu+f)^{2}-(\Delta u^{\ast}-Vu^{\ast}+f)^{2}\right]\ \ \Big{|}\ u\in
M_{\rho}(\Omega)\Big{\\}}$ can be upper bounded by a sub-root function

$\phi(\rho):=O\left(\sqrt{\frac{S3^{L}\rho}{n}\log\left(BWn\right)}\right).$

_i.e._ we have

(4.13) $\phi(4\rho)\leq 2\phi(\rho)\text{ and
}R_{n}({\mathcal{T}}_{\rho}(\Omega))\leq\phi(\rho).\ $

holds for all $\rho\gtrsim n^{-2}$.

###  4.4 Final Upper Bound

##### Deep Ritz Methods.

In this subsection, we provide the proof of upper bounds for DRM. We first
provide a meta-theorem to illustrate the approximation and generalization
decomposition with a $O(1/n)$ fast rate generalization bound[3, 78]. Then we
use truncated fourier basis estimator and neural network estimator as example
to obtain the final rate.

######  Theorem 4.13 (Meta-theorem for Upper Bounds of Deep Ritz Methods).

Let $u^{\ast}\in H^{s}(\Omega)$ denote the true solution to the PDE model with
Dirichlet boundary condition:

(4.14) $\displaystyle-\Delta u+Vu$ $\displaystyle=f\text{ on }\Omega,$
$\displaystyle u$ $\displaystyle=0\text{ on }\partial\Omega,$

where $f\in L^{2}(\Omega)$ and $V\in L^{\infty}(\Omega)$ with $0<V_{\min}\leq
V(x)\leq V_{\max}>0$. For a fixed function space ${\mathcal{F}}(\Omega)$,
consider the empirical loss induced by the Deep Ritz Method:

(4.15) $\displaystyle{\mathcal{E}}_{n}(u)$
$\displaystyle=\frac{1}{n}\sum_{j=1}^{n}\Big{[}|\Omega|\cdot\Big{(}\frac{1}{2}|\nabla
u(X_{j})|^{2}+\frac{1}{2}V(X_{j})|u(X_{j})|^{2}-f(X_{j})u(X_{j})\Big{)}\Big{]},$

where $\\{X_{j}\\}_{j=1}^{n}$ are datapoints uniformly sampled from the domain
$\Omega$. Then the Deep Ritz estimator associated with function space
${\mathcal{F}}(\Omega)$ is defined as the minimizer of ${\mathcal{E}}_{n}(u)$
over the function space ${\mathcal{F}}(\Omega)$:

$\displaystyle\hat{u}_{\text{DRM}}=\min_{u\in{\mathcal{F}}(\Omega)}{\mathcal{E}}_{n}(u)$

Moreover, we assume that there exists some constant $C>0$ such that all
function $u$ in the function space ${\mathcal{F}}(\Omega)$, the real solution
$u^{\ast}$ and $f,V$ satisfy the following two conditions.

  * •

The gradients and function value are uniformly bounded

(4.16)
$\max\Big{\\{}\sup_{u\in{\mathcal{F}}(\Omega)}\|u\|_{L^{\infty}(\Omega)},\sup_{u\in{\mathcal{F}}(\Omega)}\|\nabla
u\|_{L^{\infty}(\Omega)},\|u^{\ast}\|_{L^{\infty}(\Omega)},\|\nabla
u^{\ast}\|_{L^{\infty}(\Omega)},V_{max},\|f\|_{L^{\infty}(\Omega)}\Big{\\}}\leq
C.$

  * •

All the functions in the function space ${\mathcal{F}}(\Omega)$ satisfies the
boundary condition

$u=0\text{ on }\partial\Omega.$

At the the same time, for any $\rho>0$, we assume the Rademacher complexity of
a localized function space
${\mathcal{S}}_{\rho}(\Omega):=\Big{\\{}h:=|\Omega|\cdot\left[\frac{1}{2}\Big{(}|\nabla
u|^{2}-|\nabla
u^{\ast}|^{2}\Big{)}+\frac{1}{2}V(|u|^{2}-|u^{\ast}|^{2})-f(u-u^{\ast})\right]\
\ \Big{|}\ \|u-u^{\ast}\|_{H^{1}}^{2}\leq\rho\Big{\\}}$ can be upper bounded
by a sub-root function $\phi=\phi(\rho):[0,\infty)\rightarrow[0,\infty)$,
_i.e._

(4.17) $\phi(4\rho)\leq 2\phi(\rho)\text{ and
}R_{n}({\mathcal{S}}_{\rho}(\Omega))\leq\phi(\rho)\ (\forall\ \rho>0).$

For all constant $t>0$. We denote $r^{*}$ to be the solution of the fix point
equation of local Rademacher complexity $r=\phi(r)$. There exists a constant
$C_{p}$ such that for probability $1-C_{p}\exp(-t)$, we have the following
upper bound for the Deep Ritz Estimator

$\|\hat{u}_{\text{DRM}}-u^{\ast}\|_{H^{1}}^{2}\lesssim\inf_{u_{{\mathcal{F}}}\in{\mathcal{F}}(\Omega)}\Big{(}{\mathcal{E}}(u_{{\mathcal{F}}})-{\mathcal{E}}(u^{\star})\Big{)}+\max\Big{\\{}r^{*},\frac{t}{n}\Big{\\}}.$

######  Proof 4.14.

To upper bound the excess risk
$\Delta{\mathcal{E}}^{(n)}:={\mathcal{E}}(\hat{u}_{\text{DRM}})-{\mathcal{E}}(u^{\ast})$,
following[78, 47, 14], we decompose the excess risk into approximation error
and generalization error with probability $1-e^{-t}$:

(4.18)
$\displaystyle\Delta{\mathcal{E}}^{(n)}(\hat{u}_{\text{DRM}})={\mathcal{E}}(\hat{u}_{\text{DRM}})-{\mathcal{E}}(u^{\star})$
$\displaystyle=\big{[}{\mathcal{E}}(\hat{u}_{\text{DRM}})-{\mathcal{E}}_{n}(\hat{u}_{\text{DRM}})\big{]}+\big{[}{\mathcal{E}}_{n}(\hat{u}_{\text{DRM}})-{\mathcal{E}}_{n}(u_{{\mathcal{F}}})\big{]}$
$\displaystyle+\big{[}{\mathcal{E}}_{n}(u_{{\mathcal{F}}})-{\mathcal{E}}(u_{{\mathcal{F}}})\big{]}+\big{[}{\mathcal{E}}(u_{{\mathcal{F}}})-{\mathcal{E}}(u^{\star})\big{]}$
$\displaystyle\leq\big{[}{\mathcal{E}}(\hat{u}_{\text{DRM}})-{\mathcal{E}}_{n}(\hat{u}_{\text{DRM}})\big{]}+\big{[}{\mathcal{E}}_{n}(u_{{\mathcal{F}}})-{\mathcal{E}}(u_{{\mathcal{F}}})\big{]}+\big{[}{\mathcal{E}}(u_{{\mathcal{F}}})-{\mathcal{E}}(u^{\star})\big{]}$
$\displaystyle\leq\big{[}{\mathcal{E}}(\hat{u}_{\text{DRM}})-{\mathcal{E}}(u^{\ast})+{\mathcal{E}}_{n}(u^{\ast})-{\mathcal{E}}_{n}(\hat{u}_{\text{DRM}})\big{]}$
$\displaystyle+\frac{3}{2}\big{[}{\mathcal{E}}(u_{{\mathcal{F}}})-{\mathcal{E}}(u^{\star})\big{]}+\frac{t}{2n},$

where the expectation is on all sampled data. The inequality of the third line
is because the $u$ is the minimizer of the empirical loss ${\mathcal{E}}_{n}$
in the solution set ${\mathcal{F}}(\Omega)$, so we have
${\mathcal{E}}_{n}(u)\leq{\mathcal{E}}_{n}(u_{{\mathcal{F}}})$. The last
inequality is based on the Bernstein inequality. The variance of
$h=|\Omega|\cdot\left[\frac{1}{2}\Big{(}|\nabla u|^{2}-|\nabla
u^{\ast}|^{2}\Big{)}+\frac{1}{2}V(|u|^{2}-|u^{\ast}|^{2})-f(u-u^{\ast})\right]$
can be bounded by
$\big{[}{\mathcal{E}}(u_{{\mathcal{F}}})-{\mathcal{E}}(u^{\star})\big{]}$ due
to the strong convexity of the variation objective (4.20). According to the
Bernstein inequality, we know with probability $1-e^{-t}$ we have

$\displaystyle{\mathcal{E}}_{n}(u_{{\mathcal{F}}})-{\mathcal{E}}_{n}(u^{\ast})-{\mathcal{E}}(u_{{\mathcal{F}}})+{\mathcal{E}}(u^{\ast})\leq\sqrt{\frac{t\big{[}{\mathcal{E}}(u_{{\mathcal{F}}})-{\mathcal{E}}(u^{\star})\big{]}}{n}}\leq\frac{1}{2}\big{[}{\mathcal{E}}(u_{{\mathcal{F}}})-{\mathcal{E}}(u^{\star})\big{]}+\frac{t}{2n}.$

Note that 4.18 holds for all function lies in the function space
${\mathcal{F}}$. Thus, we can take
$u_{{\mathcal{F}}}:=\arg\min_{u_{0}\in{\mathcal{F}}(\Omega)}\Big{(}{\mathcal{E}}(u_{0})-{\mathcal{E}}(u^{\star})\Big{)}$
and finally get

$\displaystyle\Delta{\mathcal{E}}^{(n)}$
$\displaystyle\leq\underbrace{{\mathcal{E}}(\hat{u}_{\text{DRM}})-{\mathcal{E}}(u^{\ast})+{\mathcal{E}}_{n}(u^{\ast})-{\mathcal{E}}_{n}(u)}_{\Delta{\mathcal{E}}_{\text{gen}}}+\frac{3}{2}\underbrace{\inf_{u_{{\mathcal{F}}}\in{\mathcal{F}}(\Omega)}\Big{(}{\mathcal{E}}(u_{{\mathcal{F}}})-{\mathcal{E}}(u^{\star})\Big{)}}_{\Delta{\mathcal{E}}_{\text{app}}}+\frac{t}{2n}.$

This inequality decompose the excess risk to the generalization error
$\Delta{\mathcal{E}}_{\text{gen}}:={\mathcal{E}}(\hat{u}_{\text{DRM}})-{\mathcal{E}}(u^{\ast})+{\mathcal{E}}_{n}(u^{\ast})-{\mathcal{E}}_{n}(\hat{u}_{\text{DRM}})$
and the approximation error
$\Delta{\mathcal{E}}_{\text{app}}=\inf_{u_{{\mathcal{F}}}\in{\mathcal{F}}(\Omega)}\Big{(}{\mathcal{E}}(u_{{\mathcal{F}}})-{\mathcal{E}}(u^{\star})\Big{)}$.
We’ll focus on providing fast rate upper bounds of the generalization error
for the two estimators using the localization technique[3, 78]. To achieve the
fast generalization bound, we focus on the following normalized empirical
process

$\displaystyle\tilde{{\mathcal{S}}}_{r}(\Omega):=\big{\\{}\tilde{h}(x):=\frac{\mathbb{E}[h]-h(x)}{{\mathbb{E}}[h]+r}\
|\ h\in{\mathcal{S}}(\Omega)\big{\\}}\ (r>0).$

First, we try to bound the expectation of the normalized empirical process.
Applying the Symmetrization Lemma A.5, we can first bound the expectation as

$\displaystyle\sup_{\tilde{h}\in\tilde{S}_{r}(\Omega)}\mathbb{E}_{x^{\prime}}\left[\frac{1}{n}\sum_{i=1}^{n}\tilde{h}(x_{i}^{\prime})\right]\leq\mathbb{E}_{x^{\prime}}\left[\sup_{h\in
S(\Omega)}\Big{|}\frac{1}{n}\sum_{i=1}^{n}\frac{h(x_{i}^{\prime})-{\mathbb{E}}[h]}{{\mathbb{E}}[h]+r}\Big{|}\right]\leq
2R_{n}(\hat{{\mathcal{S}}}_{r}(\Omega)).$

where the function class $\hat{{\mathcal{S}}}_{r}(\Omega)$ is defined as:

$\displaystyle\hat{{\mathcal{S}}}_{r}(\Omega):=\big{\\{}\hat{h}(x):=\frac{h(x)}{{\mathbb{E}}[h]+r}\
|\ h\in{\mathcal{S}}(\Omega)\big{\\}},$

where
${\mathcal{S}}(\Omega)=\Big{\\{}h:=|\Omega|\cdot\left[\frac{1}{2}\Big{(}|\nabla
u|^{2}-|\nabla
u^{\ast}|^{2}\Big{)}+\frac{1}{2}V(|u|^{2}-|u^{\ast}|^{2})-f(u-u^{\ast})\right]\Big{\\}}.$
Then Applying the Peeling Lemma to any function $h\in{\mathcal{S}}(\Omega)$
helps us upper bound the local Rademacher complexity
$R_{n}(\hat{{\mathcal{S}}}_{r}(\Omega))$ with the function $\phi$ defined in
equation 4.17:

$R_{n}(\hat{{\mathcal{S}}}_{r}(\Omega))={\mathbb{E}}_{\sigma}\left[{\mathbb{E}}_{x}\Big{[}\sup_{h\in{\mathcal{S}}(\Omega)}\frac{\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}h(x_{i})}{{\mathbb{E}}[h]+r}\Big{]}\right]\leq\frac{4\phi(r)}{r}.$

Combining all inequalities derived above yields:

(4.19)
$\sup_{\tilde{h}\in\tilde{S}_{r}(\Omega)}\mathbb{E}_{x^{\prime}}\left[\frac{1}{n}\sum_{i=1}^{n}\tilde{h}(x_{i}^{\prime})\right]\leq
2R_{n}(\hat{{\mathcal{S}}}_{r}(\Omega))\leq\frac{8\phi(r)}{r}\ (r>0).$

Secondly we’ll apply the Talagrand concentration inequality, which requires us
to verify the condition needed. We will first check that the expectation value
${\mathbb{E}}[h]$ is always non-negative for any $h\in{\mathcal{S}}(\Omega)$:

$\displaystyle{\mathbb{E}}[h]$
$\displaystyle=\frac{1}{|\Omega|}\int_{\Omega}|\Omega|\cdot(\frac{1}{2}|\nabla
u(x)|^{2}+\frac{1}{2}V(x)|u(x)|^{2}-f(x)u(x))dx$
$\displaystyle-\frac{1}{|\Omega|}\int_{\Omega}|\Omega|\cdot(\frac{1}{2}|\nabla
u^{\star}(x)|^{2}+\frac{1}{2}V(x)|u^{\star}(x)|^{2}-f(x)u^{\star}(x))dx$
$\displaystyle={\mathcal{E}}(u)-{\mathcal{E}}(u^{\star})\geq
0\Rightarrow{\mathbb{E}}[h]\geq 0.$

We will proceed to verify that any
$\tilde{h}=\frac{{\mathbb{E}}[h]-h}{{\mathbb{E}}[h]+r}\in\tilde{{\mathcal{S}}}_{r}(\Omega)$
is of bounded inf-norm. We need to prove that any $h\in{\mathcal{S}}(\Omega)$
is of bounded inf-norm beforehand. Using boundedness condition listed in
equation 4.16 implies:

$\displaystyle\|h\|_{\infty}$
$\displaystyle=|\Omega|\|\frac{1}{2}\Big{(}|\nabla u|^{2}-|\nabla
u^{\ast}|^{2}\Big{)}+\frac{1}{2}V(|u|^{2}-|u^{\ast}|^{2})-f(u-u^{\ast})\|_{\infty}$
$\displaystyle\leq\frac{|\Omega|}{2}\Big{(}\|\nabla u\|_{\infty}^{2}+\|\nabla
u^{\ast}\|_{\infty}^{2}\Big{)}+\frac{|\Omega|}{2}V_{\text{max}}\Big{(}\|u\|_{\infty}^{2}+\|u^{\ast}\|_{\infty}^{2}\Big{)}+|\Omega|\|f\|_{\infty}\Big{(}\|u\|_{\infty}+\|u^{\ast}\|_{\infty}\Big{)}$
$\displaystyle\leq\frac{|\Omega|}{2}\times
2C^{2}+\frac{|\Omega|}{2}V_{\text{max}}\times
2C^{2}+2|\Omega|C^{2}=|\Omega|(V_{\text{max}}+3)C^{2}$

By taking $M:=|\Omega|(V_{\text{max}}+3)C^{2}$, we then have
$\|h\|_{\infty}\leq M$ for all $h\in{\mathcal{S}}(\Omega)$. Note that the
denominator can be lower bounded by $|{\mathbb{E}}[h]+r|\geq r>0$. Combining
these two inequalities help us upper bound the inf-norm
$\|\tilde{h}\|_{\infty}=\sup_{x\in\Omega}|\tilde{h}(x)|$ as follows:

$\displaystyle\|\tilde{h}\|_{\infty}=\frac{\|{\mathbb{E}}[h]-h\|_{\infty}}{|{\mathbb{E}}[h]+r|}\leq\frac{2\|h\|_{\infty}}{r}\leq\frac{2M}{r}=:\beta.$

We will then check the normalized functions
$\frac{\mathbb{E}[h]-h(x)}{{\mathbb{E}}[h]+r}$ in $\tilde{S}_{r}(\Omega)$ have
bounded second moment, which is satisfied because of the regularity results of
the PDE. We aim to show that there exist some constants
$\alpha,\alpha^{\prime}>0$, such that for any $h\in{\mathcal{S}}(\Omega)$, the
following inequality holds:

(4.20)
$\alpha\mathbb{E}[h^{2}]\leq\|u-u^{\ast}\|_{H^{1}(\Omega)}^{2}\leq\alpha^{\prime}\mathbb{E}[h].$

The RHS of the inequality follows from strong convexity of the DRM objective
function proved in Theorem A.1:

$\displaystyle\mathbb{E}[h]={\mathcal{E}}(u)-{\mathcal{E}}(u^{\ast})\geq\frac{\min\\{1,V_{\text{min}}\\}}{4}\|u-u^{\ast}\|_{H^{1}(\Omega)}^{2}$

The LHS of the inequality follows from boundedness condition listed in
equation 4.16 and the QM-AM inequality:

$\displaystyle\mathbb{E}[h^{2}]$
$\displaystyle=\int_{\Omega}\left[\frac{1}{2}\Big{(}|\nabla u|^{2}-|\nabla
u^{\ast}|^{2}\Big{)}+\frac{1}{2}V(|u|^{2}-|u^{\ast}|^{2})-f(u-u^{\ast})\right]^{2}dx$
$\displaystyle\leq\frac{3}{4}\int_{\Omega}\Big{(}|\nabla u|^{2}-|\nabla
u^{\ast}|^{2}\Big{)}^{2}dx+\frac{3}{4}\int_{\Omega}V^{2}(|u|^{2}-|u^{\ast}|^{2})^{2}dx+3\int_{\Omega}f^{2}(u-u^{\ast})^{2}dx$
$\displaystyle\leq\frac{3}{4}\int_{\Omega}\Big{|}|\nabla u|-|\nabla
u^{\ast}|\Big{|}^{2}(|\nabla u|+|\nabla
u^{\ast}|)^{2}dx+\frac{3}{4}V_{\text{max}}^{2}\int_{\Omega}\Big{|}|u|-|u^{\ast}|\Big{|}^{2}(|u|+|u^{\ast}|)^{2}dx$
$\displaystyle+3C^{2}\int_{\Omega}(u-u^{\ast})^{2}dx\leq
3C^{2}\int_{\Omega}|\nabla u-\nabla
u^{\ast}|^{2}dx+3C^{2}(1+V_{\text{max}}^{2})\int_{\Omega}|u-u^{\ast}|^{2}dx$
$\displaystyle\leq
3C^{2}(1+V_{\text{max}}^{2})\|u-u^{\ast}\|_{H^{1}(\Omega)}^{2}$

By picking $\alpha^{\prime}=\frac{4}{\min\\{1,V_{\text{min}}\\}}$ and
$\alpha=\frac{1}{3C^{2}(1+V_{\text{max}}^{2})}$, we have finished proving
inequality 4.20. Then we can can upper bound the expectation
${\mathbb{E}}[\tilde{h}^{2}]$ as:

$\displaystyle\mathbb{E}[\tilde{h}^{2}]=\frac{\mathbb{E}[(h-\mathbb{E}[h])^{2}]}{|{\mathbb{E}}[h]+r|^{2}}=\frac{{\mathbb{E}}[h^{2}]-{\mathbb{E}}[h]^{2}}{|{\mathbb{E}}[h]+r|^{2}}\leq\frac{{\mathbb{E}}[h^{2}]}{|{\mathbb{E}}[h]+r|^{2}}.$

Using the fact that ${\mathbb{E}}[h]\geq 0$ and inequality 4.20, we can lower
bound the denominator $|{\mathbb{E}}[h]+r|^{2}$ as follows:

$\displaystyle|{\mathbb{E}}[h]+r|^{2}\geq
2{\mathbb{E}}[h]r\geq\frac{2r\alpha}{\alpha^{\prime}}\mathbb{E}[h^{2}].$

Therefore, we can deduce that:

$\displaystyle\mathbb{E}[\tilde{h}^{2}]\leq\frac{\mathbb{E}[h^{2}]}{|{\mathbb{E}}[h]+r|^{2}}\leq\frac{{\mathbb{E}}[h^{2}]}{\frac{2r\alpha}{\alpha^{\prime}}{\mathbb{E}}[h^{2}]}=\frac{\alpha^{\prime}}{2r\alpha}=:\sigma^{2}.$

Hence, any function in the localized class $\tilde{{\mathcal{S}}}_{r}(\Omega)$
is of bounded second moment.

It is easy to check that for any
$\tilde{h}\in\tilde{{\mathcal{S}}}_{r}(\Omega)$, we have

$\displaystyle{\mathbb{E}}[\tilde{h}]=\frac{{\mathbb{E}}[h]-{\mathbb{E}}[h]}{{\mathbb{E}}[h]+r}=0,$

_i.e._ any function in the localized class $\tilde{{\mathcal{S}}}_{r}(\Omega)$
is of zero mean.

Now we have verified that any function
$\tilde{h}\in\tilde{{\mathcal{S}}}_{r}(\Omega)$ satisfies all the required
conditions. By taking $\mu$ to be the uniform distribution on the domain
$\Omega$ and applying Talagrand’s Concentration inequality given in Lemma A.8,
we have:

$\displaystyle\mathbb{P}_{x}\left[\sup_{\tilde{h}\in\tilde{{\mathcal{S}}}_{r}(\Omega)}\frac{1}{n}\sum_{i=1}^{n}\tilde{h}(x_{i})\geq
2\sup_{\tilde{h}\in\tilde{{\mathcal{S}}}_{r}(\Omega)}\mathbb{E}_{x^{\prime}}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\tilde{h}(x_{i}^{\prime})\Big{]}+\sqrt{\frac{2t\sigma^{2}}{n}}+\frac{2t\beta}{n}\right]\leq
e^{-t}.$

By using the upper bound deduced above and plugging in the expressions of
$\beta$ and $\sigma$, we can rewrite Talagrand’s Concentration Inequality in
the following way. With probability at least $1-e^{-t}$, the inequality below
holds:

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\tilde{h}(x_{i})\leq\sup_{\tilde{h}\in\tilde{{\mathcal{S}}}_{r}(\Omega)}\frac{1}{n}\sum_{i=1}^{n}\tilde{h}(x_{i})$
$\displaystyle\leq
2\sup_{\tilde{h}\in\tilde{{\mathcal{S}}}_{r}(\Omega)}\mathbb{E}_{x^{\prime}}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\tilde{h}(x_{i}^{\prime})\Big{]}+\sqrt{\frac{2t\sigma^{2}}{n}}+\frac{2t\beta}{n}$
$\displaystyle\leq\frac{16\phi(r)}{r}+\sqrt{\frac{t\alpha^{\prime}}{n\alpha
r}}+\frac{4Mt}{nr}=:\psi(r).$

Let’s pick the critical radius $r_{0}$ to be:

(4.21) $\displaystyle
r_{0}=\max\\{2^{14}r^{\ast},\frac{24Mt}{n},\frac{36\alpha^{\prime}t}{\alpha
n}\\}.$

Note that concavity of the function $\phi$ implies that $\phi(r)\leq r$ for
any $r\geq r^{\ast}$. Combining this with the first inequality listed in 4.17
yields:

$\displaystyle\frac{16\phi(r)}{r}$
$\displaystyle\leq\frac{2^{11}\phi(\frac{r_{0}}{2^{14}})}{2^{14}\frac{r_{0}}{2^{14}}}=\frac{1}{8}\times\frac{\phi(\frac{r_{0}}{2^{14}})}{\frac{r_{)}}{2^{14}}}\leq\frac{1}{8}.$

On the other hand, applying equation 4.21 yields:

$\displaystyle\sqrt{\frac{\alpha^{\prime}t}{n\alpha r_{0}}}$
$\displaystyle\leq\sqrt{\frac{\alpha^{\prime}t}{n\alpha}\frac{\alpha
n}{36\alpha^{\prime}t}}=\frac{1}{6},$ $\displaystyle\frac{4Mt}{nr_{0}}$
$\displaystyle\leq\frac{4Mt}{n}\times\frac{n}{24Mt}=\frac{1}{6}.$

Summing the three inequalities above implies:

$\displaystyle\psi(r_{0})=\frac{16\phi(r_{0})}{r_{0}}+\sqrt{\frac{t\alpha^{\prime}}{n\alpha
r_{0}}}+\frac{4Mt}{nr_{0}}\leq\frac{1}{8}+\frac{1}{6}+\frac{1}{6}<\frac{1}{2}.$

By picking $r=r_{0}$, we can further deduce that for any function
$u\in{\mathcal{F}}(\Omega)$, the following inequality holds with probability
$1-e^{-t}$:

$\displaystyle\frac{{\mathcal{E}}(u)-{\mathcal{E}}(u^{\ast})-{\mathcal{E}}_{n}(u)+{\mathcal{E}}_{n}(u^{\ast})}{{\mathcal{E}}(u)-{\mathcal{E}}(u^{\ast})+r_{0}}=\frac{1}{n}\sum_{i=1}^{n}\tilde{h}(x_{i})$
$\displaystyle\leq\psi(r_{0})<\frac{1}{2}.$

Multiplying the denominator on both sides indicates:

$\displaystyle\Delta{\mathcal{E}}_{\text{gen}}={\mathcal{E}}(u)-{\mathcal{E}}(u^{\ast})-{\mathcal{E}}_{n}(u)+{\mathcal{E}}_{n}(u^{\ast})\leq\frac{1}{2}\Big{[}{\mathcal{E}}(u)-{\mathcal{E}}(u^{\ast})\Big{]}+\frac{1}{2}r_{0}=\frac{1}{2}\Delta{\mathcal{E}}^{(n)}+\frac{1}{2}r_{0}.$

Substituting the upper bound above into the decomposition
$\Delta{\mathcal{E}}^{(n)}\leq\Delta E_{\text{gen}}+\frac{3}{2}\Delta
E_{\text{app}}+\frac{t}{2n}$ yields that with probability $1-e^{-t}$, we have:

$\displaystyle\Delta{\mathcal{E}}^{(n)}\leq\Delta{\mathcal{E}}_{\text{gen}}+\frac{3}{2}\Delta{\mathcal{E}}_{\text{app}}+\frac{t}{2n}\leq\frac{1}{2}\Delta{\mathcal{E}}^{(n)}+\frac{1}{2}r_{0}+\frac{3}{2}\Delta{\mathcal{E}}_{\text{app}}+\frac{t}{2n}.$

Simplifying the inequality above yields that with probability $1-e^{-t}$, we
have:

$\displaystyle\Delta{\mathcal{E}}^{(n)}$ $\displaystyle\leq
r_{0}+3\Delta{\mathcal{E}}_{\text{app}}+\frac{t}{n}=3\inf_{u_{{\mathcal{F}}}\in{\mathcal{F}}(\Omega)}\Big{(}{\mathcal{E}}(u_{{\mathcal{F}}})-{\mathcal{E}}(u^{\star})\Big{)}+\max\\{2^{14}r^{\ast},24M\frac{t}{n},\frac{36\alpha^{\prime}}{\alpha}\frac{t}{n}\\}+\frac{t}{n}$
$\displaystyle\lesssim\inf_{u_{{\mathcal{F}}}\in{\mathcal{F}}(\Omega)}\Big{(}{\mathcal{E}}(u_{{\mathcal{F}}})-{\mathcal{E}}(u^{\star})\Big{)}+\max\Big{\\{}r^{*},\frac{t}{n}\Big{\\}}$

Moreover, using strong convexity of the DRM objective function proved in
Theorem A.1 implies:

$\displaystyle\Delta{\mathcal{E}}^{(n)}={\mathcal{E}}(\hat{u}_{\text{DRM}})-{\mathcal{E}}(u^{\ast})\geq\frac{\min\\{1,V_{\text{min}}\\}}{4}\|\hat{u}_{\text{DRM}}-u^{\ast}\|_{H^{1}(\Omega)}^{2}$

Combining the two bounds above yields that with probability $1-e^{-t}$, we
have:

$\displaystyle\|\hat{u}_{\text{DRM}}-u^{\ast}\|_{H^{1}(\Omega)}^{2}\lesssim\inf_{u_{{\mathcal{F}}}\in{\mathcal{F}}(\Omega)}\Big{(}{\mathcal{E}}(u_{{\mathcal{F}}})-{\mathcal{E}}(u^{\star})\Big{)}+\max\Big{\\{}r^{*},\frac{t}{n}\Big{\\}}$

######  Theorem 4.15.

(Final Upper Bound of DRM with Deep Neural Network Estimator) With proper
assumptions, consider the sparse Deep Neural Network function space
$\Phi(L,W,S,B)$ with parameters $L=O(1),\ W=O(n^{\frac{d}{d+2s-2}}),\
S=O(n^{\frac{d}{d+2s-2}}),\ B=O(1)$, then the Deep ritz estimator
$\hat{u}_{\text{DRM}}^{\text{DNN}}=\min_{u\in\Phi(L,W,S,B)}{\mathcal{E}}_{n}^{\text{DRM}}(u)$
satisfies the following upper bound with high probability:

$\displaystyle\|\hat{u}_{\text{DRM}}^{\text{DNN}}-u^{\ast}\|_{H^{1}}^{2}\lesssim
n^{-\frac{2s-2}{d+2s-2}}\log n.$

######  Proof 4.16.

On the one hand, by taking $s=1$ and $p=2$ in Theorem 4.6 proved above, we
have that there exists some Deep Neural Network
$u_{\text{DNN}}\in\Phi(L,W,S,B)$ with $L=O(1),W=O(N),S=O(N),B=O(N)$, such
that.

$\displaystyle\|u_{\text{DNN}}-u^{\ast}\|_{H^{1}(\Omega)}^{2}\leq
N^{-\frac{2s-2}{d}}\|u^{\ast}\|_{H^{s}(\Omega)}.$

Applying strong convexity of the DRM objective function proved in Section 2.1
further implies:

$\displaystyle\Delta{\mathcal{E}}_{\text{app}}\lesssim\|u_{\text{DNN}}-u^{\ast}\|_{H^{1}(\Omega)}^{2}\leq
N^{-\frac{2s-2}{d}}.$

On the other hand, from Lemma 4.11 proved above, we know that the function
$\phi(\rho)$ that upper bounds the local Rademacher complexity of the Deep
Neural Network space is of the same magnitude as
$\sqrt{\frac{S3^{L}\rho}{n}\log\left(BWn\right)}$. By plugging in the
magnitudes of $L,W,S,B$, we can determine the critical radius $r^{\ast}$:

$\sqrt{\frac{r^{\ast}3^{L}S}{n}\log(BWn)}\simeq\sqrt{\frac{r^{\ast}N}{n}(2\log
N+\log n)}\simeq r^{\ast}\Rightarrow r^{\ast}\simeq\frac{N(\log N+\log
n)}{n}.$

Combining the two bounds above with Theorem 4.13 yields that with high
probability, we have:

$\|\hat{u}_{\text{DRM}}^{\text{DNN}}-u^{\ast}\|_{H^{1}}^{2}\lesssim\Delta{\mathcal{E}}_{\text{app}}+\hat{r}\lesssim
N^{-\frac{2(s-1)}{d}}+\frac{N(\log N+\log n)}{n}.$

By equating the two terms above, we can solve for the optimal $N$ that yields
the desired bound:

$N^{-\frac{2(s-1)}{d}}\simeq\frac{N}{n}\Rightarrow N\simeq
n^{\frac{d}{d+2s-2}}.$

Plugging in the optimal $N$ gives us the magnitudes of the four parameters
$L=O(1),\ W=O(n^{\frac{d}{d+2s-2}}),\ S=O(n^{\frac{d}{d+2s-2}}),\
B=O(n^{\frac{d}{d+2s-2}})$, as well as the final rate:

$\|\hat{u}_{\text{DRM}}^{\text{DNN}}-u^{\ast}\|_{H^{1}}^{2}\lesssim
N^{-\frac{2(s-1)}{d}}+\frac{N\log N}{n}\lesssim
n^{-\frac{2(s-1)}{d+2(s-1)}}\log n.$

######  Theorem 4.17.

(Final Upper Bound of DRM with Truncated Fourier Series Estimator)With proper
assumptions, consider the Deep Ritz objective with a plug in Fourier Series
estimator
$\hat{u}_{\text{DRM}}^{\text{Fourier}}=\min_{u\in{\mathcal{F}}_{\xi}(\Omega)}{\mathcal{E}}_{n}^{\text{DRM}}(u)$
with $\xi=\Theta(n^{\frac{1}{d+2s-2}})$, then with high probability we have

$\displaystyle\|\hat{u}_{\text{DRM}}^{\text{Fourier}}-u^{\ast}\|_{H^{1}}^{2}\lesssim
n^{-\frac{2s-2}{d+2s-2}}.$

######  Proof 4.18.

On the one hand, from Lemma 4.8 and Lemma 4.9 proved above, we know that the
function $\phi(\rho)$ that upper bounds the local Rademacher complexity for
Truncated Fourier Series can be dominated by the term

(4.22) $\displaystyle R_{n}({\mathcal{S}}_{\rho}(\Omega))$
$\displaystyle\lesssim
R_{n}\left(\Big{\\{}u-u^{\ast}:u\in{\mathcal{F}}_{\rho,\xi}(\Omega),\|u-u^{\ast}\|_{L^{2}(\Omega)}\leq\sqrt{\rho}\Big{\\}}\right)$
$\displaystyle+R_{n}\left(\Big{\\{}\|\nabla u-\nabla
u^{\ast}\|:u\in{\mathcal{F}}_{\rho,\xi}(\Omega),\Big{\|}\nabla u-\nabla
u^{\ast}\Big{\|}_{L^{2}(\Omega)}\leq\sqrt{\rho}\Big{\\}}\right)$
$\displaystyle\lesssim{\mathbb{E}}_{X}\left[{\mathbb{E}}_{\sigma}\Big{[}\sup_{f\in{\mathcal{F}}_{\rho,\xi}(\Omega)}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}(u(X_{i})-u^{\ast}(X_{i}))\Big{|}\|u-\Pi_{\xi}u^{\ast}\|_{H^{1}(\Omega)}^{2}\leq\rho\Big{]}\right]$
$\displaystyle+{\mathbb{E}}_{X}\left[{\mathbb{E}}_{\sigma}\Big{[}\sup_{f\in{\mathcal{F}}_{\rho,\xi}(\Omega)}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\|\nabla
u(X_{i})-\nabla u^{\ast}(X_{i})\|\
\Big{|}\|u-\Pi_{\xi}u^{\ast}\|_{H^{1}(\Omega)}^{2}\leq\rho\Big{]}\right]$
$\displaystyle+{\mathbb{E}}_{X}\left[{\mathbb{E}}_{\sigma}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\|\nabla\Pi_{>\xi}u^{\ast}(X_{i})\|\Big{]}\right]+{\mathbb{E}}_{X}\left[{\mathbb{E}}_{\sigma}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\Pi_{>\xi}u^{\ast}(X_{i})\Big{]}\right]$
$\displaystyle\lesssim{\mathbb{E}}_{X}\left[{\mathbb{E}}_{\sigma}\Big{[}\sup_{f\in{\mathcal{F}}_{\rho,\xi}(\Omega)}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}f(X_{i})\
\Big{|}\|f\|_{H^{1}(\Omega)}^{2}\leq\rho\Big{]}\right]$
$\displaystyle+{\mathbb{E}}_{X}\left[{\mathbb{E}}_{\sigma}\Big{[}\sup_{f\in{\mathcal{F}}_{\rho,\xi}(\Omega)}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\|\nabla
f(X_{i})\|\ \Big{|}\|f\|_{H^{1}(\Omega)}^{2}\leq\rho\Big{]}\right]$
$\displaystyle+{\mathbb{E}}_{X}\left[{\mathbb{E}}_{\sigma}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\|\nabla\Pi_{\xi}u^{\ast}(X_{i})\|\Big{]}\right]+{\mathbb{E}}_{X}\left[{\mathbb{E}}_{\sigma}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\Pi_{>\xi}u^{\ast}(X_{i})\Big{]}\right]$
$\displaystyle\leq\sqrt{\frac{\rho}{n}}\xi^{\frac{d}{2}}+\sqrt{\frac{\|\Pi_{\xi}f\|_{H^{1}}^{2}}{n}}\leq\sqrt{\frac{\rho}{n}}\xi^{\frac{d}{2}}+\sqrt{\frac{\xi^{-2(s-1)}}{n}}\lesssim\sqrt{\frac{\rho}{n}}\xi^{\frac{d}{2}}+\frac{1}{n}+\xi^{-2(s-1)},$

where $\Pi_{\xi}u:=\sum_{\|z\|_{\infty}\leq\xi}u_{z}\phi_{z}(x)$ is the
projection to the Fourier basis whose frequency is smaller than $\xi$ and
$\Pi_{\xi}u:=\sum_{\|z\|_{\infty}\leq\xi}u_{z}\phi_{z}(x)$ is the projection
to the Fourier basis whose frequency is larger than $\xi$. Then, the critical
radius $\hat{r}$ can be determined as follows:

$\displaystyle\sqrt{\frac{\rho}{n}}\xi^{\frac{d}{2}}+\frac{1}{n}+\xi^{-2(s-1)}\simeq\rho\Rightarrow\hat{r}\simeq\frac{\xi^{d}}{n}+\frac{1}{n}+\xi^{-2(s-1)},$

On the other hand, by taking $\alpha=s$ and $\beta=1$ in Lemma 4.1 and
applying strong convexity of the DRM objective function proved in Theorem A.1,
we can upper bound the approximation error $\Delta{\mathcal{E}}_{\text{app}}$
as below:

$\displaystyle\Delta{\mathcal{E}}_{\text{app}}\lesssim\xi^{-2(s-1)},$

By equating the two terms above, we can solve for $\xi$ that yields the
desired bound:

$\displaystyle\frac{\xi^{d}}{n}\simeq\xi^{-2(s-1)}\Rightarrow\xi\simeq
n^{\frac{1}{d+2s-2}},$

Plugging in the expression of $\xi$ gives the final upper bound:

$\displaystyle\mathbb{E}_{x\sim\mu}[\Delta{\mathcal{E}}_{n}]\lesssim\hat{r}+\Delta{\mathcal{E}}_{\text{app}}\lesssim\frac{\xi^{d}}{n}+\xi^{-2(s-1)}\simeq
n^{-\frac{2s-2}{d+2s-2}}.$

##### Physics Informed Neural Network.

Then we aim to provide the upper bound for the Physics Informed Neural Network
with a Similar meta-theorem followed by upper bounds of DNN and truncated
Fourier Estimators. For simplicity, we drop the proof of the meta-theorem to
appendix for all the proof follows the similar idea of the DRM one.

######  Theorem 4.19 (Meta-theorem for Upper Bounds of Physics Informed Neural
Network).

Let $u^{\ast}\in H^{s}(\Omega)$ denote the true solution to the PDE model with
Dirichlet boundary condition:

(4.23) $\displaystyle-\Delta u+Vu$ $\displaystyle=f\text{ on }\Omega,$
$\displaystyle u$ $\displaystyle=0\text{ on }\partial\Omega,$

where $f\in L^{2}(\Omega)$ and $V\in L^{\infty}(\Omega)$ with $0<V_{\min}\leq
V(x)\leq V_{\max}>0$. For a fixed function space ${\mathcal{F}}(\Omega)$,
consider the empirical loss induced by the Physics Informed Neural Network:

(4.24) $\displaystyle{\mathcal{E}}_{n}(u)$
$\displaystyle=\frac{1}{n}\sum_{j=1}^{n}\Big{[}|\Omega|\cdot\Big{(}\Delta
u(X_{j})-V(X_{j})u(X_{j})+f(X_{j})\Big{)}^{2}\Big{]},$

where $\\{X_{j}\\}_{j=1}^{n}$ are datapoints uniformly sampled from the domain
$\Omega$. Then the Physics Informed Neural Network estimator associated with
function space ${\mathcal{F}}(\Omega)$ is defined as the minimizer of
${\mathcal{E}}_{n}(u)$ over the function space ${\mathcal{F}}(\Omega)$:

$\displaystyle\hat{u}_{\text{PINN}}=\min_{u\in{\mathcal{F}}(\Omega)}{\mathcal{E}}_{n}(u)$

Moreover, we assume that there exists some constant $C>0$ such that all
function $u$ in the function space ${\mathcal{F}}(\Omega)$, the real solution
$u^{\ast}$ and $f,V$ satisfy the following two conditions.

  * •

The gradients and function value are uniformly bounded

(4.25) $\displaystyle\max\Big{\\{}$
$\displaystyle\sup_{u\in{\mathcal{F}}(\Omega)}\|u\|_{L^{\infty}(\Omega)},\sup_{u\in{\mathcal{F}}(\Omega)}\|\nabla
u\|_{L^{\infty}(\Omega)},\sup_{u\in{\mathcal{F}}(\Omega)}\|\Delta
u\|_{L^{\infty}(\Omega)},$
$\displaystyle\|u^{\ast}\|_{L^{\infty}(\Omega)},\|\nabla
u^{\ast}\|_{L^{\infty}(\Omega)},\|\Delta
u^{\ast}\|_{L^{\infty}(\Omega)},V_{max},\|f\|_{L^{\infty}(\Omega)}\Big{\\}}\leq
C.$

  * •

All the functions in the function space ${\mathcal{F}}(\Omega)$ satisfies the
boundary condition

$u=0\text{ on }\partial\Omega.$

At the the same time, for any $\rho>0$, we assume the Rademacher complexity of
a localized function space
${\mathcal{T}}_{\rho}(\Omega):=\Big{\\{}h:=|\Omega|\cdot\left[(\Delta
u-Vu+f)^{2}-(\Delta u^{\ast}-Vu^{\ast}+f)^{2}\right]\ \ \Big{|}\
\|u-u^{\ast}\|_{H^{2}}^{2}\leq\rho\Big{\\}}$ can be upper bounded by a sub-
root function $\phi=\phi(\rho):[0,\infty)\rightarrow[0,\infty)$, _i.e._

(4.26) $\phi(4\rho)\leq 2\phi(\rho)\text{ and
}R_{n}({\mathcal{T}}_{\rho}(\Omega))\leq\phi(\rho)\ (\forall\ \rho>0).$

For all constant $t>0$. We denote $r^{*}$ to be the solution of the fix point
equation of local Rademacher complexity $r=\phi(r)$. There exists a constant
$C_{p}$ such that for probability $1-C_{p}\exp(-t)$, we have the following
upper bound for the Physics Informed Neural Network Estimator

$\|\hat{u}_{\text{PINN}}-u^{\ast}\|_{H^{2}}^{2}\lesssim\inf_{u_{{\mathcal{F}}}\in{\mathcal{F}}(\Omega)}\Big{(}{\mathcal{E}}(u_{{\mathcal{F}}})-{\mathcal{E}}(u^{\star})\Big{)}+\max\Big{\\{}r^{*},\frac{t}{n}\Big{\\}}.$

Then we aim to calculate the final upper bound for DNN and truncated Fourier
series based PINN estimator.

######  Theorem 4.20.

(Informal Upper Bound of PINN with Deep Neural Network Estimator) With proper
assumptions, consider the sparse Deep Neural Network function space
$\Phi(L,W,S,B)$ with parameters $L=O(1),\ W=O(n^{\frac{d}{d+2s-4}}),\
S=O(n^{\frac{d}{d+2s-4}}),\ B=O(1)$, then the Physics Informed estimator
$\hat{u}_{\text{PINN}}^{\text{DNN}}=\min_{u\in\Phi(L,W,S,B)}{\mathcal{E}}_{n}^{\text{PINN}}(u)$
satisfies the following upper bound with high probability:

$\displaystyle\|\hat{u}_{\text{PINN}}^{\text{DNN}}-u^{\ast}\|_{H^{2}}^{2}\lesssim
n^{-\frac{2s-4}{d+2s-4}}\log n.$

######  Proof 4.21.

On the one hand, by taking $s=2$ and $p=2$ in Theorem 4.6 proved above, we
have that there exists some Deep Neural Network
$u_{\text{DNN}}\in\Phi(L,W,S,B)$ with $L=O(1),W=O(N),S=O(N),B=O(1)$, such
that.

$\displaystyle\|u_{\text{DNN}}-u^{\ast}\|_{H^{2}(\Omega)}^{2}\leq
N^{-\frac{2s-4}{d}}\|u\|_{H^{s}(\Omega)}.$

Applying strong convexity of the DRM objective function proved in Section 2.1
further implies:

$\displaystyle\Delta{\mathcal{E}}_{\text{app}}\lesssim\|u_{\text{DNN}}-u^{\ast}\|_{H^{2}(\Omega)}^{2}\leq
N^{-\frac{2s-4}{d}}.$

On the other hand, from lemma 4.12 proved above, we know that the function
$\phi(\rho)$ that upper bounds the local Rademacher complexity of the Deep
Neural Networks $u_{\text{DNN}}$ is dominated by the term $\sqrt{\frac{\rho
3^{L}S}{n}\log(W(B\vee 1)n)}$. By plugging in the magnitudes of $L,W,S,B$, we
can determine the critical radius $\hat{r}$:

$\sqrt{\frac{\rho 3^{L}S}{n}\log(W(B\vee 1)n)}\simeq\sqrt{\frac{\rho
N}{n}(\log N+\log n)}\simeq\rho\Rightarrow\hat{r}\simeq\frac{N(\log N+\log
n)}{n}.$

Combining the two bounds above gives us:

$\mathbb{E}_{x\sim\mu}[\Delta{\mathcal{E}}_{n}]\lesssim\Delta{\mathcal{E}}_{\text{app}}+\hat{r}\lesssim
N^{-\frac{2(s-2)}{d}}+\frac{N(\log N+\log n)}{n}.$

By equating the two terms above, we can solve for the optimal $N$ that yields
the desired bound:

$N^{-\frac{2(s-2)}{d}}\simeq\frac{N}{n}\Rightarrow N\simeq
n^{\frac{d}{d+2s-4}}.$

Plugging in the optimal $N$ gives us the magnitudes of the four parameters
$L=O(1),\ W=O(n^{\frac{d}{d+2s-4}}),\ S=O(n^{\frac{d}{d+2s-4}}),\ B=O(1)$, as
well as the final rate:

$\mathbb{E}_{x\sim\mu}[\Delta{\mathcal{E}}_{n}]\lesssim
N^{-\frac{2(s-2)}{d}}+\frac{N\log N}{n}\lesssim
n^{-\frac{2(s-2)}{d+2(s-2)}}\log n.$

######  Theorem 4.22.

(Informal Upper Bound of PINN with Truncated Fourier Series Estimator) With
proper assumptions, consider the Physics Informed Neural Network objective
with a plug-in Fourier Series estimator
$\hat{u}_{\text{PINN}}^{\text{Fourier}}=\min_{u\in{\mathcal{F}}_{\xi}(\Omega)}{\mathcal{E}}_{n}^{\text{PINN}}(u)$
with $\xi=\Theta(n^{\frac{1}{d+2s-4}})$, then with high probability we have

$\displaystyle\|\hat{u}_{\text{PINN}}^{\text{Fourier}}-u^{\ast}\|_{H^{2}}^{2}\lesssim
n^{-\frac{2s-4}{d+2s-4}}.$

######  Proof 4.23.

On the one hand, from Lemma 4.8 and Lemma 4.9 proved above, we know that the
function $\phi(\rho)$ that upper bounds the local Rademacher complexity for
Truncated Fourier Series is dominated by

(4.27) $\displaystyle R_{n}({\mathcal{S}}_{\rho}(\Omega))$
$\displaystyle\lesssim R_{n}\left(\Big{\\{}|\Delta u-\Delta
u^{\ast}|:u\in{\mathcal{F}}_{\rho,\xi}(\Omega),|\Delta u-\Delta
u^{\ast}|_{L^{2}(\Omega)}\leq\sqrt{\rho}\Big{\\}}\right)$
$\displaystyle\lesssim{\mathbb{E}}_{X}\left[{\mathbb{E}}_{\sigma}\Big{[}\sup_{f\in{\mathcal{F}}_{\rho,\xi}(\Omega)}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}|\Delta
u(X_{i})-\Delta u^{\ast}(X_{i})|\
\Big{|}\|u-\Pi_{\xi}u^{\ast}\|_{H^{2}(\Omega)}^{2}\leq\rho\Big{]}\right]$
$\displaystyle+{\mathbb{E}}_{X}\left[{\mathbb{E}}_{\sigma}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}|\Delta\Pi_{>\xi}u^{\ast}(X_{i})|\Big{]}\right]$
$\displaystyle\lesssim{\mathbb{E}}_{X}\left[{\mathbb{E}}_{\sigma}\Big{[}\sup_{f\in{\mathcal{F}}_{\rho,\xi}(\Omega)}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}|\Delta
f(X_{i})|\ \Big{|}\|f\|_{H^{2}(\Omega)}^{2}\leq\rho\Big{]}\right]$
$\displaystyle+{\mathbb{E}}_{X}\left[{\mathbb{E}}_{\sigma}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\|\nabla\Pi_{\xi}u^{\ast}(X_{i})\|\Big{]}\right]$
$\displaystyle\lesssim{\mathbb{E}}_{X}\left[{\mathbb{E}}_{\sigma}\Big{[}\sup_{f\in{\mathcal{F}}_{\rho,\xi}(\Omega)}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}|\Delta
f(X_{i})|\ \Big{|}\|f\|_{H^{2}(\Omega)}^{2}\leq\rho\Big{]}\right]$
$\displaystyle+{\mathbb{E}}_{X}\left[{\mathbb{E}}_{\sigma}\Big{[}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\|\Delta\Pi_{\xi}u^{\ast}(X_{i})\|\Big{]}\right]$
$\displaystyle\leq\sqrt{\frac{\rho}{n}}\xi^{\frac{d}{2}}+\sqrt{\frac{\|\Pi_{\xi}f\|_{H^{2}}^{2}}{n}}\leq\sqrt{\frac{\rho}{n}}\xi^{\frac{d}{2}}+\sqrt{\frac{\xi^{-2(s-1)}}{n}}\lesssim\sqrt{\frac{\rho}{n}}\xi^{\frac{d}{2}}+\frac{1}{n}+\xi^{-2(s-2)}$

Thus, the localization radius $\hat{r}$ can be determined as follows:

$\displaystyle\sqrt{\frac{\rho}{n}}\xi^{\frac{d}{2}}+\frac{1}{n}+\xi^{-2(s-2)}\simeq\rho\Rightarrow\hat{r}\simeq\frac{\xi^{d}}{n}+\frac{1}{n}+\xi^{-2(s-2)},$

On the other hand, by taking $\alpha=s$ and $\beta=1$ in Lemma 4.1 and
applying strong convexity of the DRM objective function proved in Theorem A.1,
we can upper bound the approximation error $\Delta{\mathcal{E}}_{\text{app}}$
as below:

$\displaystyle\Delta{\mathcal{E}}_{\text{app}}\lesssim\xi^{-2(s-2)},$

By equating the two terms above, we can solve for $\xi$ that yields the
desired bound:

$\displaystyle\frac{\xi^{d}}{n}\simeq\xi^{-2(s-2)}\Rightarrow\xi\simeq
n^{\frac{1}{d+2s-4}},$

Plugging in the expression of $\xi$ gives the final upper bound:

$\displaystyle\mathbb{E}_{x\sim\mu}[\Delta{\mathcal{E}}_{n}]\lesssim\hat{r}+\Delta{\mathcal{E}}_{\text{app}}\lesssim\frac{\xi^{d}}{n}+\xi^{-2(s-2)}\simeq
n^{-\frac{2s-4}{d+2s-4}}.$

##### Remark.

  * •

There is a common belief that Machine learning based PDE solvers can break the
curse of dimensionality [15, 24, 40]. However we obtained an
$n^{-\frac{2s-2}{2s-4+d}}$ convergence rate which can become super slow in
high dimension. Our analysis showed that it is essential to constrain the
function space to break the curse of dimensionality. [47] considered the DRM
in Barron spaces. [56] showed that functions in the Barron space enjoy a
smoothness $s$ at the same magnitude as $d$ , which will also leads to
convergence rate independent of the dimension using our upper bound. Neural
network can also approximate mixed sparse grid spaces [52, 70], function on
manifold [55, 9] without curse of dimensionality. Combined with these
approximation bounds, we can also achieve a bound that breaks the curse of
dimensionality using Theorem 4.19 and 4.13. In this paper, we aim to consider
the statistical power of the loss function in common function spaces and leave
the curse of dimensionality as a separate topic.

  * •

Our bound is faster than the concurrent bound [14, 34] for we provided a fast
rate $O(1/n)$ by utilizing the strong convexity of the objective function and
improves the convergence rate from $n^{-\frac{2s-2}{d+4s-4}}$ to
$n^{-\frac{2s-2}{d+2s-2}}$ for Deep Ritz and from $n^{-\frac{2s-4}{d+4s-8}}$
to $n^{-\frac{2s-4}{d+2s-4}}$ for PINN. Comparing to the lower bound provided
in Section3, we show that our bound for PINN is near optimal and we’ll let our
bound for DRM become near optimal in the next section.

  * •

For upper bound of DRM, due to a technical issue, we assume the observation we
access is clean, _i.e_ $f_{i}=f(X_{i})$. We conjecture that add noising on
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 achieved min-max optimality
while the Deep Ritz Method does not. In this section, we proposed a modified
version of deep Ritz which can be statistically optimal.

As discussed in Appendix B, the reason behind the suboptimality of DRM comes
from the high complexity introduced via the uniform concentration bound of the
gradient term in the variational form. At the same time, we further observed
that the $\int\|\nabla u\|^{2}dx$ 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 $\int\|\nabla u\|^{2}dx$ term more precisely.

(5.1) $\displaystyle{\mathcal{E}}_{N,n}(u)$
$\displaystyle=\frac{1}{N}\sum_{j=1}^{N}\Big{[}|\Omega|\cdot\frac{1}{2}\|\nabla
u(X_{j}^{\prime})\|^{2}\Big{]}+\frac{1}{n}\sum_{j=1}^{n}\Big{[}|\Omega|\cdot\Big{(}\frac{1}{2}V(X_{j})|u(X_{j})|^{2}-f_{j}u(X_{j})\Big{)}\Big{]}$

Once we sampled more data for approximating $\int|\nabla u|^{2}dx$, we can
achieve an near optimal bound for the Truncated Fourier Estimator when
$\frac{N}{n}\gtrsim n^{\frac{2}{d+2s-4}}$. The proof is based on a similar
meta-theorem as following.

######  Theorem 5.1 (Meta-theorem for Upper Bounds of Modified Deep Ritz
Method).

Let $u^{\ast}\in H^{s}(\Omega)$ denote the true solution to the PDE model with
Dirichlet boundary condition:

(5.2) $\displaystyle-\Delta u+Vu$ $\displaystyle=f\text{ on }\Omega,$
$\displaystyle u$ $\displaystyle=0\text{ on }\partial\Omega,$

where $f\in L^{2}(\Omega)$ and $V\in L^{\infty}(\Omega)$ with $0<V_{\min}\leq
V(x)\leq V_{\max}>0$. For a fixed function space ${\mathcal{F}}(\Omega)$,
consider the empirical loss induced by the Modified Deep Ritz Method $(N\geq
n)$:

(5.3) $\displaystyle{\mathcal{E}}_{N,n}(u)$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\Big{[}|\Omega|\cdot\frac{1}{2}|\nabla
u(X_{i}^{\prime})|^{2}\Big{]}+\frac{1}{n}\sum_{j=1}^{n}\Big{[}|\Omega|\cdot\Big{(}\frac{1}{2}V(X_{j})|u(X_{j})|^{2}-f(X_{j})u(X_{j})\Big{)}\Big{]},$

where $\\{X_{i}^{\prime}\\}_{i=1}^{N}$ and $\\{X_{j}\\}_{j=1}^{n}$ are
datapoints uniformly and independently sampled from the domain $\Omega$. Then
the Modified Deep Ritz estimator associated with function space
${\mathcal{F}}(\Omega)$ is defined as the minimizer of
${\mathcal{E}}_{N,n}(u)$ over the function space ${\mathcal{F}}(\Omega)$:

$\displaystyle\hat{u}_{\text{MDRM}}=\min_{u\in{\mathcal{F}}(\Omega)}{\mathcal{E}}_{N,n}(u)$

Moreover, we assume that there exists some constant $C>0$ such that all
function $u$ in the function space ${\mathcal{F}}(\Omega)$, the real solution
$u^{\ast}$ and $f,V$ satisfy the following two conditions.

  * •

The gradients and function value are uniformly bounded

(5.4)
$\max\Big{\\{}\sup_{u\in{\mathcal{F}}(\Omega)}\|u\|_{L^{\infty}(\Omega)},\sup_{u\in{\mathcal{F}}(\Omega)}\|\nabla
u\|_{L^{\infty}(\Omega)},\|u^{\ast}\|_{L^{\infty}(\Omega)},\|\nabla
u^{\ast}\|_{L^{\infty}(\Omega)},V_{max},\|f\|_{L^{\infty}(\Omega)}\Big{\\}}\leq
C.$

  * •

All the functions in the function space ${\mathcal{F}}(\Omega)$ satisfy the
boundary condition

$u=0\text{ on }\partial\Omega.$

At the the same time, for any $\rho>0$, we assume the Rademacher complexity of
two localized function spaces

${\mathcal{S}}_{\rho}(\Omega):=\Big{\\{}(h_{1},h_{2})\big{|}h1:=|\Omega|\cdot\left[\frac{1}{2}\Big{(}|\nabla
u|^{2}-|\nabla u^{\ast}|^{2}\Big{)}\right],\
h2:=|\Omega|\cdot\left[\frac{1}{2}V(|u|^{2}-|u^{\ast}|^{2})-f(u-u^{\ast})\right],\|u-u^{\ast}\|_{H^{1}}^{2}\leq\rho\Big{\\}}$

can be upper bounded by a sub-root function
$\phi=\phi(\rho):[0,\infty)\rightarrow[0,\infty)$, _i.e._

(5.5) $\phi(4\rho)\leq 2\phi(\rho)\text{ and
}R_{N,n}({\mathcal{S}}_{\rho}(\Omega))\leq\phi(\rho)\ (\forall\ \rho>0),$

where
$R_{N,n}({\mathcal{S}}):=R_{N}(\\{h_{1}|(h_{1},h_{2})\in{\mathcal{S}}\\})+R_{n}(\\{h_{2}|(h_{1},h_{2})\in{\mathcal{S}}\\})$.
For all constant $t>0$. We denote $r^{\ast}$ to be the solution of the fix
point equation of local Rademacher complexity $r=\phi(r)$. There exist a
constant $C_{p}$ such that for probability $1-C_{p}\exp(-t)$, we have the
following upper bound for the Modified Deep Ritz Estimator

$\|\hat{u}_{\text{MDRM}}-u^{\ast}\|_{H^{1}}^{2}\lesssim\inf_{u_{{\mathcal{F}}}\in{\mathcal{F}}(\Omega)}\Big{(}{\mathcal{E}}(u_{{\mathcal{F}}})-{\mathcal{E}}(u^{\star})\Big{)}+\max\Big{\\{}r^{*},\frac{t}{n}\Big{\\}}.$

######  Theorem 5.2.

(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
$\hat{u}_{\text{DRM}}^{\text{Fourier}}=\min_{u\in{\mathcal{F}}_{\xi}(\Omega)}{\mathcal{E}}_{n}^{\text{DRM}}(u)$
with $\xi=\Theta(n^{\frac{1}{d+2s-4}})$ and $\frac{N}{n}\gtrsim
n^{\frac{2}{d+2s-4}}$, then we have

$\displaystyle\|\hat{u}_{\text{DRM}}^{\text{Fourier}}-u^{\ast}\|_{H^{1}}^{2}\lesssim
n^{-\frac{2s-2}{d+2s-4}}.$

######  Proof 5.3.

On the one hand, from Lemma 4.8 and Lemma 4.9 proved above, we know that the
function $\phi(\rho)$ that upper bounds the local Rademacher complexity is
dominated by the term $\sqrt{\frac{\rho}{n}}\xi^{\frac{d}{2}}$ for Truncated
Fourier Series in ${\mathcal{F}}_{\xi}(\Omega)$. Following the same proof as
shown for DRM upper bound, the localization radius $\hat{r}$ can be determined
as follows:

$\displaystyle\sqrt{\frac{\rho}{n}}\xi^{\frac{d-2}{2}}+\sqrt{\frac{\rho}{N}}\xi^{\frac{d}{2}}+\frac{1}{n}+\frac{1}{N}+\xi^{-2(s-1)}\simeq\rho.$

For we have assumed $\frac{\xi^{d}}{N}<\frac{\xi^{d-2}}{n}$, the solution of
the fixed point equation is $\hat{r}\simeq\frac{\xi^{d}}{n}$. On the other
hand, by taking $\alpha=s$ and $\beta=1$ in Lemma 4.1 and applying strong
convexity of the DRM objective function proved in Theorem A.1, we can upper
bound the approximation error $\Delta{\mathcal{E}}_{\text{app}}$ as below:

$\displaystyle\Delta{\mathcal{E}}_{\text{app}}\lesssim\xi^{-2(s-1)},$

By equating the two terms above, we can solve for $\xi$ that yields the
desired bound:

$\displaystyle\frac{\xi^{d-2}}{n}+\xi^{-2(s-1)}\simeq\xi^{-2(s-1)}\Rightarrow\xi\simeq
n^{\frac{1}{d+2s-4}}+\xi^{-2(s-1)},$

Plugging in the expression of $\xi$ gives the final upper bound:

$\displaystyle\mathbb{E}_{x\sim\mu}[\Delta{\mathcal{E}}_{n}]\lesssim\hat{r}+\Delta{\mathcal{E}}_{\text{app}}\lesssim\frac{\xi^{d-2}}{n}+\xi^{-2(s-2)}\simeq
n^{-\frac{2s-2}{d+2s-4}}.$

##### Remark.

We still cannot achieve optimal rate for neural network even with modified DRM
methods. The reason is because the number of neuron is not a good complexity
measure for the gradient of the function thus the bound for
$\psi(r)=R_{n}(\\{\mathcal{I}(u)|\|u-u^{\ast}\|_{H^{1}}^{2}\leq r\\})$ is not
enough for achieving optimal convergence rate. However, following [63, 70, 33,
9, 18] using deep networks for estimating functions, we optimize the best
neural network with constrained sparsity in our paper. Here we conjecture that
there exists a computable complexity measure can makes DRM statistical optimal
and leave finding the right complexity of the neural network’s gradient to be
future work.

##  6 Experiments

In this section, we conduct several numerical experiments to verify our
theory. We follow the neural network and hyper-parameter setting in [7]. 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)=1$ in
our experiment. We conduct experiment in 2-dimension and select the solution
of the PDE as $u^{\ast}=\sum_{z}\|z\|^{-s}\phi_{z}(x)\in H^{s}$. We show the
log-log plot of the $H^{1}$ loss against the number of sampled data for $s=4$
in Figure 1. We use an OLS estimator to fit the log-log plot and put the
estimated slope and corresponding $\text{R}^{2}$ score in Figure 1. As our
theory predicts, the modified Deep Ritz Method converges faster than the
original one. All the derivation of the two estimators is listed in Appendix
B.

Figure 1: The Log-Log plot and estimated convergence slope for Modified DRM
and DRM using Fourier basis, showing the median error over 5 replicates.

###  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 a power-law $\mathcal{L}\propto\frac{1}{N^{\alpha}}$. We
also scan over a range of $d$ and $\alpha$ and verify an approximately
$\alpha\propto\frac{1}{d}$ scaling law as our theory suggests. We use the same
test function in Section 6.1 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 our results on the log-log scale. Results are shown in Figure 2. We
discover the $L\propto n^{\frac{1}{d+2}}$ scaling law in practical situations.

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.

###  6.3 Adaptation To The Simpler Functions.

[65] 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. [72, 8]
also observed this theoretically. For solving PDEs, we also observed this
adaptivity in practice. Here we tested the following two hypothesis

Figure 3: Neural network have the ability to adapt to simple functions and
achieves convergence without curse of dimensionality, showing the median error
over 5 replicates.

  * •

Random Neural Network Teacher. Following [65], we also tested random neural
network using He initialization [29] as the ground turth solution $u^{\ast}$.
[13] 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 a linear estimate with slope $\alpha=-0.50679429$
and a $\text{R}^{2}$ score $=0.96$ in the log-log plot. See Figure 3(a).

  * •

Simple Polynomials. Neural network can approximate simple polynomials
exponentially fast [76]. Thus, we select the ground truth solution to be the
following simple polynomial in 10 dimensional spaces
$u^{\ast}(x)=x_{1}x_{2}+\cdots+x_{9}x_{10}.$ In this example, we obtained a
linear estimate with slope $\alpha=-0.49755418$ and a $\text{R}^{2}$ 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 previous bounds [78, 47, 14, 34] 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 a modified Deep Ritz method. We verified our
theory via numerical experiments and explored the dimension dependent scaling
laws of Deep PDE solvers.

##### Discussion and Future Work

Here we discuss several drawbacks of our theory

  * •

We restricted our target function and estimators in $W^{1,\infty}$ instead of
$H^{1}$ due to boundedness assumption made in the local Rademacher complexity
arguments. However, typical functional used in physics is always unbounded,
such as the Newtonian potential $\frac{1}{\|x-y\|^{d-2}}$, which limits the
application of our theory.

  * •

This paper did not discuss any optimization aspect of the deep PDE solvers and
always assumed achieves global optimum. However, it is important to
investigate whether the optimization error [71, 11] will finally dominate.

  * •

Instead of solving a single PDE, recent works[45, 44, 42, 40, 4, 17, 19]
considered the so-called "operator learning", which aims to learn a family of
PDE/inverse problems using a 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 to achieve the optimal convergence rate.

## Acknowledgments

Yiping Lu is supported by the Stanford Interdisciplinary Graduate Fellowship
(SIGF). Jianfeng Lu is supported in part by National Science Foundation via
grants DMS-2012286 and CCF1934964. Lexing Ying is supported by National
Science Foundation under award DMS-2011699. Jose Blanchet is 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 and
Bin Dong for helpful comments and feedback.

## References

  * [1] R. A. Adams and J. J. Fournier, Sobolev spaces, Elsevier, 2003.
  * [2] G. Bai, U. Koley, S. Mishra, and R. Molinaro, Physics informed neural networks (pinns) for approximating nonlinear dispersive pdes, arXiv preprint arXiv:2104.05584, (2021).
  * [3] P. L. Bartlett, O. Bousquet, S. Mendelson, et al., Local rademacher complexities, The Annals of Statistics, 33 (2005), pp. 1497–1537.
  * [4] K. Bhattacharya, B. Hosseini, N. B. Kovachki, and A. M. Stuart, Model reduction and neural networks for parametric pdes, arXiv preprint arXiv:2005.03180, (2020).
  * [5] H. Brezis, Functional analysis, Sobolev spaces and partial differential equations, Springer Science & Business Media, 2010.
  * [6] L. D. Brown and M. G. Low, Asymptotic equivalence of nonparametric regression and white noise, The Annals of Statistics, 24 (1996), pp. 2384–2398.
  * [7] J. Chen, R. Du, and K. Wu, A comprehensive study of boundary conditions when solving pdes by dnns, arXiv preprint arXiv:2005.04554, (2020).
  * [8] M. Chen, H. Jiang, W. Liao, and T. Zhao, Efficient approximation of deep relu networks for functions on low dimensional manifolds, Advances in Neural Information Processing Systems, 32 (2019), pp. 8174–8184.
  * [9] M. Chen, H. Jiang, W. Liao, and T. Zhao, Nonparametric regression on low-dimensional manifolds using deep relu networks, arXiv preprint arXiv:1908.01842, (2019).
  * [10] Y. Chen, B. Hosseini, H. Owhadi, and A. M. Stuart, Solving and learning nonlinear pdes with gaussian processes, arXiv preprint arXiv:2103.12959, (2021).
  * [11] L. Chizat, Convergence rates of gradient methods for convex optimization in the space of measures, arXiv preprint arXiv:2105.08368, (2021).
  * [12] C. De Boor and C. De Boor, A practical guide to splines, vol. 27, springer-verlag New York, 1978.
  * [13] G. De Palma, B. T. Kiani, and S. Lloyd, Random deep neural networks are biased towards simple functions, arXiv preprint arXiv:1812.10156, (2018).
  * [14] C. Duan, Y. Jiao, Y. Lai, X. Lu, and Z. Yang, Convergence rate analysis for deep ritz method, arXiv preprint arXiv:2103.13330, (2021).
  * [15] W. E and B. Yu, The deep ritz method: a deep learning-based numerical algorithm for solving variational problems, Communications in Mathematics and Statistics, 6 (2018), pp. 1–12.
  * [16] L. C. Evans, Partial differential equations, Graduate studies in mathematics, 19 (1998), p. 7.
  * [17] Y. Fan and L. Ying, Solving electrical impedance tomography with deep learning, Journal of Computational Physics, 404 (2020), p. 109119.
  * [18] M. H. Farrell, T. Liang, and S. Misra, Deep neural networks for estimation and inference, Econometrica, 89 (2021), pp. 181–213.
  * [19] J. Feliu-Faba, Y. Fan, and L. Ying, Meta-learning pseudo-differential operators with deep neural networks, Journal of Computational Physics, 408 (2020), p. 109309.
  * [20] S. A. Geer and S. van de Geer, Empirical Processes in M-estimation, vol. 6, Cambridge university press, 2000.
  * [21] M. Germain, H. Pham, and X. Warin, Neural networks-based algorithms for stochastic control and pdes in finance, arXiv preprint arXiv:2101.08068, (2021).
  * [22] D. Gilton, G. Ongie, and R. Willett, Neumann networks for linear inverse problems in imaging, IEEE Transactions on Computational Imaging, 6 (2019), pp. 328–343.
  * [23] P. Grohs and L. Herrmann, Deep neural network approximation for high-dimensional elliptic pdes with boundary conditions, arXiv preprint arXiv:2007.05384, (2020).
  * [24] P. Grohs, F. Hornung, A. Jentzen, and P. 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.02362, (2018).
  * [25] I. Gühring, G. Kutyniok, and P. Petersen, Error bounds for approximations with deep relu neural networks in w s, p norms, Analysis and Applications, 18 (2020), pp. 803–859.
  * [26] J. Han, A. Jentzen, and E. Weinan, Solving high-dimensional partial differential equations using deep learning, Proceedings of the National Academy of Sciences, 115 (2018), pp. 8505–8510.
  * [27] J. Han, J. Lu, and M. Zhou, Solving high-dimensional eigenvalue problems using deep neural networks: A diffusion monte carlo like approach, Journal of Computational Physics, 423 (2020), p. 109792.
  * [28] T. Hashimoto, Predicting the impact of dataset composition on model performance, 2021, https://openreview.net/forum?id=butEPeLARP_.
  * [29] K. He, X. Zhang, S. Ren, and J. Sun, Delving deep into rectifiers: Surpassing human-level performance on imagenet classification, in Proceedings of the IEEE international conference on computer vision, 2015, pp. 1026–1034.
  * [30] J. B. Heaton, N. G. Polson, and J. H. Witte, Deep learning for finance: deep portfolios, Applied Stochastic Models in Business and Industry, 33 (2017), pp. 3–12.
  * [31] J. Hestness, S. Narang, N. Ardalani, G. Diamos, H. Jun, H. Kianinejad, M. Patwary, M. Ali, Y. Yang, and Y. Zhou, Deep learning scaling is predictable, empirically, arXiv preprint arXiv:1712.00409, (2017).
  * [32] J.-C. Hütter and P. Rigollet, Minimax rates of estimation for smooth optimal transport maps, arXiv preprint arXiv:1905.05828, (2019).
  * [33] M. Imaizumi and K. Fukumizu, Advantage of deep neural networks for estimating functions with singularity on curves, arXiv preprint arXiv:2011.02256, (2020).
  * [34] Y. Jiao, Y. Lai, D. Li, X. Lu, Y. Wang, and J. Z. Yang, Convergence analysis for the pinns, 2021, https://arxiv.org/abs/2109.01780.
  * [35] Y. Jiao, Y. Lai, Y. Luo, Y. Wang, and Y. Yang, Error analysis of deep ritz methods for elliptic equations, arXiv preprint arXiv:2107.14478, (2021).
  * [36] Y. Jiao, G. Shen, Y. Lin, and J. Huang, Deep nonparametric regression on approximately low-dimensional manifolds, arXiv preprint arXiv:2104.06708, (2021).
  * [37] J. Kaplan, S. McCandlish, T. Henighan, T. B. Brown, B. Chess, R. Child, S. Gray, A. Radford, J. Wu, and D. Amodei, Scaling laws for neural language models, arXiv preprint arXiv:2001.08361, (2020).
  * [38] Y. Khoo, J. Lu, and L. Ying, Solving parametric pde problems with artificial neural networks, arXiv preprint arXiv:1707.03351, (2017).
  * [39] V. Koltchinskii, Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems: Ecole d’Eté de Probabilités de Saint-Flour XXXVIII-2008, vol. 2033, Springer Science & Business Media, 2011\.
  * [40] S. Lanthaler, S. Mishra, and G. E. Karniadakis, Error estimates for deeponets: A deep learning framework in infinite dimensions, arXiv preprint arXiv:2102.09618, (2021).
  * [41] M. Ledoux and M. Talagrand, Probability in Banach Spaces: isoperimetry and processes, Springer Science & Business Media, 2013.
  * [42] Z. Li, N. Kovachki, K. Azizzadenesheli, B. Liu, K. Bhattacharya, A. Stuart, and A. Anandkumar, Fourier neural operator for parametric partial differential equations, arXiv preprint arXiv:2010.08895, (2020).
  * [43] Y. Liu and H. Wang, Convergence order of wavelet thresholding estimator for differential operators on besov spaces, Applied and Computational Harmonic Analysis, 32 (2012), pp. 342–356.
  * [44] Z. Long, Y. Lu, and B. Dong, Pde-net 2.0: Learning pdes from data with a numeric-symbolic hybrid deep network, Journal of Computational Physics, 399 (2019), p. 108925.
  * [45] Z. Long, Y. Lu, X. Ma, and B. Dong, Pde-net: Learning pdes from data, in International Conference on Machine Learning, PMLR, 2018, pp. 3208–3216.
  * [46] D. Lu, H. Wang, M. Chen, L. Lin, R. Car, E. Weinan, W. Jia, and L. Zhang, 86 pflops deep potential molecular dynamics simulation of 100 million atoms with ab initio accuracy, Computer Physics Communications, 259 (2021), p. 107624.
  * [47] J. Lu, Y. Lu, and M. Wang, A priori generalization analysis of the deep ritz method for solving high dimensional elliptic equations, arXiv preprint arXiv:2101.01708, (2021).
  * [48] T. Luo and H. Yang, Two-layer neural networks for partial differential equations: Optimization and generalization theory, arXiv preprint arXiv:2006.15733, (2020).
  * [49] T. Manole, S. Balakrishnan, J. Niles-Weed, and L. Wasserman, Plugin estimation of smooth optimal transport maps, arXiv preprint arXiv:2107.12364, (2021).
  * [50] T. Marwah, Z. C. Lipton, and A. Risteski, Parametric complexity bounds for approximating pdes with neural networks, arXiv preprint arXiv:2103.02138, (2021).
  * [51] H. Mikami, K. Fukumizu, S. Murai, S. Suzuki, Y. Kikuchi, T. Suzuki, S.-i. Maeda, and K. Hayashi, A scaling law for synthetic-to-real transfer: A measure of pre-training, arXiv preprint arXiv:2108.11018, (2021).
  * [52] H. Montanelli and Q. Du, New error bounds for deep relu networks using sparse grids, SIAM Journal on Mathematics of Data Science, 1 (2019), pp. 78–92.
  * [53] H.-G. Müller and T. Gasser, Optimal convergence properties of kernel estimates of derivatives of a density function, in Smoothing techniques for curve estimation, Springer, 1979, pp. 144–154.
  * [54] R. Nickl, S. van de Geer, and S. Wang, Convergence rates for penalized least squares estimators in pde constrained regression problems, SIAM/ASA Journal on Uncertainty Quantification, 8 (2020), pp. 374–413.
  * [55] A. Nitanda and T. Suzuki, Optimal rates for averaged stochastic gradient descent under neural tangent kernel regime, arXiv preprint arXiv:2006.12297, (2020).
  * [56] G. Ongie, R. Willett, D. Soudry, and N. Srebro, A function space view of bounded norm infinite width relu nets: The multivariate case, arXiv preprint arXiv:1910.01635, (2019).
  * [57] B. Prakasa Rao, Nonparametric estimation of the derivatives of a density by the method of wavelets, Bulletin of Informatics and Cybernetics, 28 (1996), pp. 91–100.
  * [58] M. Raissi, P. Perdikaris, and G. E. Karniadakis, Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations, Journal of Computational Physics, 378 (2019), pp. 686–707.
  * [59] A. Rakhlin, K. Sridharan, and A. B. Tsybakov, Empirical entropy, minimax regret and minimax risk, Bernoulli, 23 (2017), pp. 789–824.
  * [60] L. Richter, L. Sallandt, and N. Nüsken, Solving high-dimensional parabolic pdes using the tensor train format, arXiv preprint arXiv:2102.11830, (2021).
  * [61] J. S. Rosenfeld, Scaling laws for deep learning, arXiv preprint arXiv:2108.07686, (2021).
  * [62] J. S. Rosenfeld, A. Rosenfeld, Y. Belinkov, and N. Shavit, A constructive prediction of the generalization error across scales, arXiv preprint arXiv:1909.12673, (2019).
  * [63] J. Schmidt-Hieber et al., Nonparametric regression using deep neural networks with relu activation function, Annals of Statistics, 48 (2020), pp. 1875–1897.
  * [64] L. Schumaker, Spline functions: basic theory, Cambridge University Press, 2007.
  * [65] U. Sharma and J. Kaplan, A neural scaling law from the dimension of the data manifold, arXiv preprint arXiv:2004.10802, (2020).
  * [66] Z. Shen, H. Yang, and S. Zhang, Neural network approximation: Three hidden layers are enough, Neural Networks, (2021).
  * [67] Y. Shin, Z. Zhang, and G. E. Karniadakis, Error estimates of residual minimization using neural networks for linear pdes, arXiv preprint arXiv:2010.08019, (2020).
  * [68] J. Sirignano and K. Spiliopoulos, Dgm: A deep learning algorithm for solving partial differential equations, Journal of computational physics, 375 (2018), pp. 1339–1364.
  * [69] N. Srebro, K. Sridharan, and A. Tewari, Smoothness, low noise and fast rates, Advances in neural information processing systems, 23 (2010).
  * [70] T. Suzuki, Adaptivity of deep relu network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality, arXiv preprint arXiv:1810.08033, (2018).
  * [71] T. Suzuki and S. Akiyama, Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods, arXiv preprint arXiv:2012.03224, (2020).
  * [72] T. Suzuki and A. Nitanda, Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic besov space, arXiv preprint arXiv:1910.12799, (2019).
  * [73] J. A. Tropp, An introduction to matrix concentration inequalities, arXiv preprint arXiv:1501.01571, (2015).
  * [74] A. B. Tsybakov, Introduction to nonparametric estimation, Springer Science & Business Media, 2008.
  * [75] S. Van De Geer, A new approach to least-squares estimation, with applications, The Annals of Statistics, 15 (1987), pp. 587–602.
  * [76] Q. Wang et al., Exponential convergence of the deep neural network approximation for analytic functions, arXiv preprint arXiv:1807.00297, (2018).
  * [77] S. Wojtowytsch et al., Some observations on partial differential equations in barron and multi-layer spaces, arXiv preprint arXiv:2012.01484, (2020).
  * [78] J. Xu, The finite neuron method and convergence analysis, arXiv preprint arXiv:2010.01458, (2020).
  * [79] Y. Xu and A. Zeevi, Towards optimal problem dependent generalization error bounds in statistical learning theory, arXiv preprint arXiv:2011.06186, (2020).
  * [80] D. Yarotsky, Error bounds for approximations with deep relu networks, Neural Networks, 94 (2017), pp. 103–114.
  * [81] Y. Zang, G. Bao, X. Ye, and H. Zhou, Weak adversarial networks for high-dimensional partial differential equations, Journal of Computational Physics, 411 (2020), p. 109409.
  * [82] X. Zhang, Y. Lu, J. Liu, and B. Dong, Dynamically unfolding recurrent restorer: A moving endpoint control method for image restoration, arXiv preprint arXiv:1805.07709, (2018).

##  Appendix A Proof of the Upper Bounds

###  A.1 Notations

In this section, we provide all the notations we need in the proof. Let
$\Omega\subset\mathbb{R}^{d}$ be some open set. We denote $C(\Omega)$ the
space of continuous functions on $\Omega$ and $C^{k}(\Omega)$ the space of all
functions that are $k$ times continuously differentiable on $\Omega$ ($\forall
k\in\mathbb{Z}^{+}$). For any $n\in\mathbb{N}_{0}$
($\mathbb{N}_{0}:=\mathbb{Z}^{+}\cup\\{0\\}$ is the set of all non-negative
integers) and $1\leq p\leq\infty$, we define the Sobolev space
$W^{n,p}(\Omega)$ by

$\displaystyle W^{n,p}(\Omega):=\\{f\in L^{p}(\Omega):\ D^{\alpha}f\in
L^{p}(\Omega),\ \forall\alpha\in\mathbb{N}_{0}^{d}\text{ with }|\alpha|\leq
n\\}.$

In particular, when $p=2$, we define $H^{n}(\Omega):=W^{n,2}(\Omega)$ for any
$n\in\mathbb{N}_{0}$. Moreover, for any $f\in W^{n,p}(\Omega)$ with $1\leq
p<\infty$, we define the Sobolev norm by:

$\displaystyle\|f\|_{W^{n,p}(\Omega)}:=\Big{(}\sum_{0\leq|\alpha|\leq
n}\|D^{\alpha}f\|^{p}_{L^{p}(\Omega)}\Big{)}^{\frac{1}{p}}.$

In particular, when $p=\infty$, we have:

$\displaystyle\|f\|_{W^{n,\infty}(\Omega)}:=\max_{0\leq|\alpha|\leq
n}\|D^{\alpha}f\|_{L^{\infty}(\Omega)}.$

Consider the Fourier expansion $f:=\sum_{z\in\mathbb{N}^{d}}f_{z}\phi_{z}(x)$
of the function $f\in W^{n,p}(\Omega)$. We can equivalently express the
Sobolev norm as:

$\|f\|_{W^{n,p}(\Omega)}=\Big{(}\sum_{z}\|z\|^{np}|f_{z}|^{p}\Big{)}^{1/p},$

where
$f_{z}=\int_{\Omega}f(x)\overline{\phi_{z}(x)}dx=\int_{\Omega}f(x)e^{-2\pi
i\langle z,x\rangle}dx\ (x\in\Omega)$ is the $z-$th Fourier coefficient of
$f$.
Moreover, we use $W^{1,p}_{0}(\Omega)$ to denote the closure of
$C_{c}^{1}(\Omega)$ in $W^{1,p}(\Omega)$. In particular, when $p=2$, we define
$H_{0}^{1}(\Omega):=W_{0}^{1,2}(\Omega)$.
Furthermore, we use $\|\cdot\|$ to present the vector 2 norm and, given a data
sample $\\{X_{i}\\}_{i=1}^{n}\subset\Omega$,
$\|\cdot\|_{n,p}=\left({{\mathbb{E}}_{n}\cdot^{p}}\right)^{1/p}$ denote the
empirical $p$ norm, where
${\mathbb{E}}_{n}:L^{2}(\Omega)\rightarrow\mathbb{R}$ is the corresponding
empirical average operator defined as
${\mathbb{E}}_{n}f:=\frac{1}{n}\sum_{i=1}^{n}f(X_{i}),\ \forall\ f\in
L^{2}(\Omega).$ Given two quantities $X$ and $Y$, we write $X\lesssim Y$ when
the inequality $X\leq CY$ holds, where $C$ is some constant. For two functions
$f$ and $g$ mapping from $\mathbb{R}^{+}$ to $\mathbb{R}$, we write $f=O(g)$
when there exist two constants $C^{\prime}$ and $x_{0}$ independent of $f$ and
$g$, such that the inequality $f(x)\leq C^{\prime}g(x)$ holds for any $x\geq
x_{0}$. We use $X\simeq Y$ to denote $X\lesssim Y$ and $Y\lesssim X$.

###  A.2 Regularity Result For the PDE model.

##### Regularity Results of the DRM Objective Function

######  Theorem A.1.

We consider the static Schrödinger equation on the unit hypercube on
${\mathbb{R}}^{d}$ with the zero Direchlet boundary condition:

(A.1) $\displaystyle-\Delta u+Vu$ $\displaystyle=f\text{ on }\Omega,$
$\displaystyle u$ $\displaystyle=0\text{ on }\partial\Omega.$

where $f\in L^{2}(\Omega)$ and $V\in L^{\infty}(\Omega)$ with $0<V_{\min}\leq
V(x)\leq V_{\max}>0$. There exists a unique weak solution $u^{\ast}_{S}$ to
the equivalent variational problem [16]:

(A.2) $u^{\ast}_{S}=\operatorname*{arg\,min}_{u\in
H^{1}_{0}(\Omega)}{\mathcal{E}}^{\text{DRM}}_{S}(u):=\operatorname*{arg\,min}_{u\in
H^{1}_{0}(\Omega)}\Big{\\{}\frac{1}{2}\int_{\Omega}\Big{[}\|\nabla
u\|^{2}+V|u|^{2}\Big{]}\ dx-\int_{\Omega}fudx\Big{\\}}.$

Then for any $u\in H^{1}(\Omega)$, we have:

(A.3)
$\frac{\min(1,V_{\min})}{2}\|u-u^{\ast}_{S}\|^{2}_{H^{1}(\Omega)}\leq{\mathcal{E}}^{\text{DRM}}_{S}(u)-{\mathcal{E}}^{\text{DRM}}_{S}(u^{\ast}_{S})\\\
\leq\frac{\max(1,V_{\max})}{2}\|u-u^{\ast}_{S}\|^{2}_{H^{1}(\Omega)}.$

######  Proof A.2.

To show that $u^{\ast}_{S}$ satisfies estimate A.3, we first claim that for
any $u\in H^{1}(\Omega)$,

(A.4)
${\mathcal{E}}_{S}^{\text{DRM}}(u)-{\mathcal{E}}_{S}^{\text{DRM}}(u^{\ast}_{S})=\frac{1}{2}\int_{\Omega}\|\nabla
u-\nabla u^{\ast}_{S}\|^{2}dx+\frac{1}{2}\int_{\Omega}V(u^{\ast}_{S}-u)^{2}\
dx.$

In fact, by plugging in the first equation of A.1, one has that

$\displaystyle{\mathcal{E}}_{S}^{\text{DRM}}(u^{\ast}_{S})$
$\displaystyle=\frac{1}{2}\int_{\Omega}\|\nabla
u^{\ast}_{S}\|^{2}dx+\frac{1}{2}\int_{\Omega}V|u^{\ast}_{S}|^{2}dx-\int_{\Omega}fu_{S}^{\ast}dx$
$\displaystyle=\frac{1}{2}\int_{\Omega}\|\nabla
u^{\ast}_{S}\|^{2}dx+\frac{1}{2}\int_{\Omega}V|u^{\ast}_{S}|^{2}dx+\int_{\Omega}(\Delta
u^{\ast}_{S}-Vu^{\ast}_{S})u_{S}^{\ast}dx$
$\displaystyle=\frac{1}{2}\int_{\Omega}\|\nabla
u^{\ast}_{S}\|^{2}dx+\int_{\Omega}(\Delta
u^{\ast}_{S})u_{S}^{\ast}dx-\frac{1}{2}\int_{\Omega}V|u^{\ast}_{S}|^{2}dx.$

Furthermore, applying Green’s formula to the true solution $u^{\ast}_{S}$
yields:

$\displaystyle{\mathcal{E}}_{S}^{\text{DRM}}(u^{\ast}_{S})$
$\displaystyle=\frac{1}{2}\int_{\Omega}\|\nabla
u^{\ast}_{S}\|^{2}dx+\int_{\Omega}(\Delta
u^{\ast}_{S})u_{S}^{\ast}dx-\frac{1}{2}\int_{\Omega}V|u^{\ast}_{S}|^{2}dx$
$\displaystyle=\int_{\partial\Omega}\frac{\partial u_{S}^{\ast}}{\partial
n}u_{S}^{\ast}dx-\frac{1}{2}\int_{\Omega}\|\nabla
u^{\ast}_{S}\|^{2}dx-\frac{1}{2}\int_{\Omega}V|u^{\ast}_{S}|^{2}dx$
$\displaystyle=-\frac{1}{2}\int_{\Omega}\|\nabla
u^{\ast}_{S}\|^{2}dx-\frac{1}{2}\int_{\Omega}V|u^{\ast}_{S}|^{2}dx,$

where the last identity above follows from the second equality in A.1. Now for
any $u\in H^{1}(\Omega)$, applying Green’s formula to $u$ and the true
solution $u^{\ast}_{S}$ implies:

$\displaystyle{\mathcal{E}}_{S}^{\text{DRM}}(u)-{\mathcal{E}}_{S}^{\text{DRM}}(u^{\ast}_{S})$
$\displaystyle=\frac{1}{2}\int_{\Omega}\|\nabla
u\|^{2}dx+\frac{1}{2}\int_{\Omega}V|u|^{2}dx-\int_{\Omega}fudx+\frac{1}{2}\int_{\Omega}\|\nabla
u^{\ast}_{S}\|^{2}dx+\frac{1}{2}\int_{\Omega}V|u^{\ast}_{S}|^{2}dx$
$\displaystyle=\frac{1}{2}\int_{\Omega}\|\nabla
u\|^{2}dx+\frac{1}{2}\int_{\Omega}V|u|^{2}dx+\int_{\Omega}(\Delta
u^{\ast}_{S}-Vu^{\ast}_{S})udx+\frac{1}{2}\int_{\Omega}\|\nabla
u^{\ast}_{S}\|^{2}dx+\frac{1}{2}\int_{\Omega}V|u^{\ast}_{S}|^{2}dx$
$\displaystyle=\frac{1}{2}\int_{\Omega}\|\nabla u\|^{2}dx+\int_{\Omega}(\Delta
u^{\ast}_{S})udx+\frac{1}{2}\int_{\Omega}\|\nabla
u^{\ast}_{S}\|^{2}dx+\frac{1}{2}\int_{\Omega}V\big{(}u^{\ast}_{S}-u\big{)}^{2}dx$
$\displaystyle=\frac{1}{2}\int_{\Omega}\|\nabla
u\|^{2}dx+\int_{\partial\Omega}\frac{\partial u_{S}^{\ast}}{\partial
n}udx-\int_{\Omega}\nabla u_{S}^{\ast}\cdot\nabla
udx+\frac{1}{2}\int_{\Omega}\|\nabla
u^{\ast}_{S}\|^{2}dx+\frac{1}{2}\int_{\Omega}V\big{(}u^{\ast}_{S}-u\big{)}^{2}dx$
$\displaystyle=\frac{1}{2}\int_{\Omega}\|\nabla u-\nabla
u^{\ast}_{S}\|^{2}dx+\frac{1}{2}\int_{\Omega}V(u^{\ast}_{S}-u)^{2}\ dx,$

where the last identity above again follows from the second equality in A.1.
This completes our proof of identity A.4. Using the assumptions on the
potential function $V$ then implies:

$\displaystyle{\mathcal{E}}_{S}^{\text{DRM}}(u)-{\mathcal{E}}_{S}^{\text{DRM}}(u^{\ast}_{S})$
$\displaystyle\leq\frac{\max(1,V_{\max})}{2}\Big{[}\int_{\Omega}\|\nabla
u-\nabla u^{\ast}_{S}\|^{2}dx+\int_{\Omega}(u^{\ast}_{S}-u)^{2}\ dx\Big{]}$
$\displaystyle=\frac{\max(1,V_{\max})}{2}\|u-u^{\ast}_{S}\|^{2}_{H^{1}(\Omega)},$
$\displaystyle{\mathcal{E}}_{S}^{\text{DRM}}(u)-{\mathcal{E}}_{S}^{\text{DRM}}(u^{\ast}_{S})$
$\displaystyle\geq\frac{\max(1,V_{\min})}{2}\Big{[}\int_{\Omega}\|\nabla
u-\nabla u^{\ast}_{S}\|^{2}dx+\int_{\Omega}(u^{\ast}_{S}-u)^{2}\ dx\Big{]}$
$\displaystyle=\frac{\max(1,V_{\min})}{2}\|u-u^{\ast}_{S}\|^{2}_{H^{1}(\Omega)}.$

This completes our proof of A.1.

##### Regularity Results of the PINN Objective Function

######  Theorem A.3.

We consider the static Schrödinger equation on the unit hypercube on
${\mathbb{R}}^{d}$ with the Neumann boundary condition:

(A.5) $\displaystyle-\Delta u+Vu$ $\displaystyle=f\text{ on }\Omega,$
$\displaystyle u$ $\displaystyle=0\text{ on }\partial\Omega.$

where $f\in L^{2}(\Omega)$ and $V\in L^{\infty}(\Omega)$ with
$V-\frac{1}{2}\Delta V>C_{\min},0<C_{\min}<V(x)\leq V_{\max}$ and $-\Delta
V(x)\leq V_{\max}$. Then there exists a unique solution $u^{\ast}_{S}\in
H_{0}^{1}(\Omega)$ to the following minimization problem [5]:

(A.6) $u^{\ast}_{S}=\operatorname*{arg\,min}_{u\in
H_{0}^{1}(\Omega)}{\mathcal{E}}^{\text{PINN}}_{S}(u):=\operatorname*{arg\,min}_{u\in
H_{0}^{1}(\Omega)}\Big{\\{}\int_{\Omega}|\Delta u-Vu+f|^{2}dx\Big{\\}}.$

Then for any $u\in H^{1}_{0}(\Omega)$, we have:

(A.7)
$\min\\{1,C_{\min}\\}\|u-u^{\ast}_{S}\|^{2}_{H^{2}(\Omega)}\leq{\mathcal{E}}^{\text{PINN}}_{S}(u)-{\mathcal{E}}^{\text{PINN}}_{S}(u^{\ast}_{S})\\\
\leq 2(1+V_{\max}+V_{\max}^{2})\|u-u^{\ast}_{S}\|^{2}_{H^{2}(\Omega)}.$

######  Proof A.4.

For any $u\in H_{0}^{1}(\Omega)$, we let $\tilde{u}=u-u^{\ast}$, then we have
$\tilde{u}\in H_{0}^{1}(\Omega)$.

(A.8)
$\displaystyle{\mathcal{E}}^{\text{PINN}}_{S}(u)-{\mathcal{E}}^{\text{PINN}}_{S}(u^{\ast}_{S})$
$\displaystyle=\int_{\Omega}|\Delta u-Vu-\Delta
u^{\ast}+Vu^{\ast}|^{2}dx=\int_{\Omega}|\Delta\tilde{u}-V\tilde{u}|^{2}dx$
$\displaystyle=\int_{\Omega}(\Delta\tilde{u})^{2}dx+\int_{\Omega}V^{2}\tilde{u}^{2}dx-2\int_{\Omega}V\tilde{u}\Delta\tilde{u}dx.$

Using Green’s formula, we have:

$\displaystyle\int_{\Omega}V\tilde{u}\Delta\tilde{u}dx+\int_{\Omega}\nabla(V\tilde{u})\cdot\nabla\tilde{u}dx=\int_{\partial\Omega}\frac{\partial\tilde{u}}{\partial
n}V\tilde{u}ds=0,$

where the last equality above follows from the fact that $\tilde{u}\in
H_{0}^{1}(\Omega)$. This further implies:

$\displaystyle{\mathcal{E}}^{\text{PINN}}_{S}(u)-{\mathcal{E}}^{\text{PINN}}_{S}(u^{\ast}_{S})$
$\displaystyle=\int_{\Omega}(\Delta\tilde{u})^{2}dx+\int_{\Omega}V^{2}\tilde{u}^{2}dx+2\int_{\Omega}\nabla(V\tilde{u})\cdot\nabla\tilde{u}dx$
$\displaystyle=\int_{\Omega}(\Delta\tilde{u})^{2}dx+\int_{\Omega}V^{2}\tilde{u}^{2}dx+2\int_{\Omega}V\|\nabla\tilde{u}\|^{2}dx+2\int_{\Omega}\tilde{u}\nabla
V\cdot\nabla\tilde{u}dx.$

Using Green’s formula again, we have:

$\displaystyle 2\int_{\Omega}\tilde{u}\nabla
V\cdot\nabla\tilde{u}dx=\int_{\Omega}\nabla(u^{2})\cdot\nabla
Vdx=\int_{\partial\Omega}\frac{\partial V}{\partial
n}\tilde{u}^{2}ds-\int_{\Omega}\tilde{u}^{2}\Delta
Vdx=-\int_{\Omega}\tilde{u}^{2}\Delta Vdx.$

Then we can further deduce that:

$\displaystyle{\mathcal{E}}^{\text{PINN}}_{S}(u)-{\mathcal{E}}^{\text{PINN}}_{S}(u^{\ast}_{S})=\int_{\Omega}(\Delta\tilde{u})^{2}dx+\int_{\Omega}(V^{2}-\Delta
V)\tilde{u}^{2}dx+2\int_{\Omega}V\|\nabla\tilde{u}\|^{2}dx.$

For we have assumed $V\in L^{\infty}(\Omega)$ with $0<C_{\min}<V^{2}-\Delta
V,0<C_{\min}<V(x)\leq V_{\max}$ and $-\Delta V(x)\leq V_{\max}$, thus we have

(A.9)
$\min\\{1,C_{\min}\\}\|u-u^{\ast}_{S}\|^{2}_{H^{2}(\Omega)}\leq{\mathcal{E}}^{\text{PINN}}_{S}(u)-{\mathcal{E}}^{\text{PINN}}_{S}(u^{\ast}_{S})\\\
\leq 2(1+V_{\max}+V_{\max}^{2})\|u-u^{\ast}_{S}\|^{2}_{H^{2}(\Omega)}.$

###  A.3 Auxiliary definitions and lemmata On Generalization Error

To bound the generalization error, we use the localized Rademacher complexity
[3]. Recall that the Rademacher complexity of a function class ${\mathcal{G}}$
is defined by

$R_{n}({\mathcal{G}})={\mathbb{E}}_{Z}{\mathbb{E}}_{\sigma}\Big{[}\sup_{g\in{\mathcal{G}}}\Big{|}\frac{1}{n}\sum_{j=1}^{n}\sigma_{j}g(Z_{j})\Big{|}\;\Big{|}\;Z_{1},\cdots,Z_{n}\Big{]},$

where $Z_{i}$ are i.i.d samples according to the data distributions and
$\sigma_{j}$ are i.i.d Rademacher random variables which take the value $1$
with probability $\frac{1}{2}$ and value $-1$ with probability $\frac{1}{2}$.

The following important symmetrization lemma makes the connection between the
uniform law of large numbers and the Rademacher complexity.

######  Lemma A.5 (Symmetrization Lemma).

Let ${\mathcal{F}}$ be a set of functions. Then

${\mathbb{E}}\sup_{u\in{\mathcal{F}}}\Big{|}\frac{1}{n}\sum_{j=1}^{n}u(X_{j})-{\mathbb{E}}_{X\sim{\mathcal{P}}_{\Omega}}u(X)\Big{|}\leq
2R_{n}({\mathcal{F}}).$

######  Lemma A.6 (Ledoux-Talagrand contraction [41, Theorem 4.12]).

Assume that $\phi:{\mathbb{R}}{\rightarrow}{\mathbb{R}}$ is $L$-Lipschitz with
$\phi(0)=0$. Let $\\{\sigma_{i}\\}_{i=1}^{n}$ be independent Rademacher random
variables. Then for any $T\subset{\mathbb{R}}^{n}$

${\mathbb{E}}_{\sigma}\Big{[}\sup_{(t_{1},\cdots,t_{n})\in
T}\sum_{i=1}^{n}\sigma_{i}\phi(t_{i})\Big{]}\leq
2L\cdot{\mathbb{E}}_{\sigma}\Big{[}\sup_{(t_{1},\cdots,t_{n})\in
T}\sum_{i=1}^{n}\sigma_{i}t_{i}\Big{]}.$

Let $(E,\rho)$ be a metric space with metric $\rho$. A $\delta$-cover of a set
$A\subset E$ with respect to $\rho$ is a collection of points
$\\{x_{1},\cdots,x_{n}\\}\subset A$ such that for every $x\in A$, there exists
$i\in\\{1,\cdots,n\\}$ such that $\rho(x,x_{i})\leq\delta$. The
$\delta$-covering number ${\mathcal{N}}(\delta,A,\rho)$ is the cardinality of
the smallest $\delta$-cover of the set $A$ with respect to the metric $\rho$.
Equivalently, the $\delta$-covering number ${\mathcal{N}}(\delta,A,\rho)$ is
the minimal number of balls $B_{\rho}(x,\delta)$ of radius $\delta$ needed to
cover the set $A$.

######  Theorem A.7 (Dudley’s Integral theorem).

Let ${\mathcal{F}}$ be a function class such that
$\sup_{f\in{\mathcal{F}}}\|f\|_{n,2}\leq M$. Then the Rademacher complexity
$R_{n}({\mathcal{F}})$ satisfies that

$R_{n}({\mathcal{F}})\leq\inf_{0\leq\delta\leq
M}\Big{\\{}4\delta+\frac{12}{\sqrt{n}}\int_{\delta}^{M}\sqrt{\log{\mathcal{N}}({\varepsilon},{\mathcal{F}},\|\cdot\|_{n,2})}\,d{\varepsilon}\Big{\\}}.$

######  Lemma A.8 (Talagrand Concentration Inequality).

Consider a function class $\mathcal{F}$ defined on a probability measure $\mu$
such that for all $f\in\mathcal{F}$, we have
$\|f\|_{\infty}\leq\beta,\mathbb{E}_{\mu}[f]=0,\mathbb{E}_{\mu}[f^{2}]\leq\sigma^{2}$.
Then for any $t>0$, we can have the following concentration results.

$\mathbb{P}_{z_{1},\cdots,z_{n}\sim\mu}\left[\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}f(z_{i})\geq
2\sup_{f\in\mathcal{F}}\mathbb{E}_{z_{1}^{\prime},\cdots,z_{n}^{\prime}\sim\mu}\frac{1}{n}\sum_{i=1}^{n}f(z_{i}^{\prime})+\sqrt{\frac{2t\sigma^{2}}{n}}+\frac{2t\beta}{n}\right]\leq
e^{-t}.$

######  Lemma A.9 (Peeling lemma [3]).

Consider some measurable function class $\mathcal{F}$. Assume that there
exists a sub-root function $\phi(r)$ satisfying

(A.10) $R_{n}(\\{f\in\mathcal{F}\ |\ {\mathbb{E}}[f]\leq r\\})\leq\phi(r)\
(\forall\ r>0).$

Then we have

$\mathbb{E}_{\sigma_{i},z_{n}}\left[\sup_{f\in\mathcal{F}}\frac{\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}f(z_{i})}{{\mathbb{E}}[f]+r}\right]\leq\frac{4\phi(r)}{r}.$

######  Proof A.10.

Denote $\mathcal{F}(r)=\\{f\in\mathcal{F}\ |\ {\mathbb{E}}[f]\leq r\\}$ to be
the localized set with radius $r$. Then for a fixed set of datapoints
$\\{z_{i}\\}_{i=1}^{n}$ and a fixed set of Rademacher random variables
$\\{\sigma_{i}\\}_{i=1}^{n}$, we have:

$\displaystyle\mathbb{E}_{\sigma_{i},z_{n}}\left[\sup_{f\in\mathcal{F}}\frac{\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}f(z_{i})}{{\mathbb{E}}[f]+r}\right]$
$\displaystyle\leq\mathbb{E}_{\sigma_{i},z_{n}}\left[\sup_{f\in\mathcal{F}(r)}\frac{\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}f(z_{i})}{r}\right]+\sum_{j=0}^{\infty}\mathbb{E}_{\sigma_{i},z_{n}}\left[\sup_{f\in\mathcal{F}(r4^{j+1})\backslash\mathcal{F}(r4^{j})}\frac{\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}f(z_{i})}{r4^{j}+r}\right]$
$\displaystyle\leq\frac{R_{n}(\mathcal{F}(r))}{r}+\sum_{j=0}^{\infty}\frac{R_{n}(\mathcal{F}(r4^{j+1}))}{r4^{j}+r}\leq\frac{\phi(r)}{r}+\sum_{j=0}^{\infty}\frac{\phi(r4^{j+1})}{r4^{j}+r}$
$\displaystyle\leq\frac{\phi(r)}{r}+\sum_{j=0}^{\infty}\frac{2^{j+1}\phi({r})}{r4^{j}+r}\leq\frac{4\phi(r)}{r}.$

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 A.11 (Peeling Lemma For MDRM).

Given some measurable function class $\mathcal{F}$ and two continuous mappings
$g,h:\mathcal{F}\rightarrow\mathbb{R}$, we define a set $\mathcal{F}$ of
vector functions by:

$\mathcal{F}:=\\{(g\circ f,h\circ f)\ |\ f\in{\mathcal{F}}\\}.$

For any $r>0$, the localized set $\mathcal{F}_{r}$ is defined by:

$\mathcal{F}_{r}=\\{(g_{f},h_{f})\in\mathcal{F}\ |\
{\mathbb{E}}_{x}[g_{f}(x)]+{\mathbb{E}}_{y}[h_{f}(y)]\leq r\\}.$

Moreover, the modified Rademacher Complexity of $\mathcal{F}_{r}$ is defined
by:

$R_{n,m}(\mathcal{F}_{r}):=R_{n}\Big{(}\\{g_{f}|(g_{f},h_{f})\in\mathcal{F}_{r}\\}\Big{)}+R_{m}(\\{h_{f}|(g_{f},h_{f})\in\mathcal{F}_{r}\\}\Big{)}.$

Assume that there exists some function $\phi:[0,\infty)\rightarrow[0,\infty)$
and some $r^{\star}>0$, such that for any $r>r^{\star}$, we have:

$\phi(4r)\leq 2\phi(r)\text{ and }R_{n,m}(\mathcal{F}_{r})\leq\phi(r).$

Then for any $r>r^{\star}$, we have:

${\mathbb{E}}_{\sigma,\tau}\Big{[}{\mathbb{E}}_{x,y}[\sup_{f\in{\mathcal{F}}}\frac{\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}g_{f}(x_{i})+\frac{1}{m}\sum_{j=1}^{m}\tau_{j}h_{f}(y_{j})}{{\mathbb{E}}_{x}[g_{f}(x)]+{\mathbb{E}}_{y}[h_{f}(y)]+r}]\Big{]}\leq\frac{4\phi(r)}{r}.$

######  Proof A.12.