Nearly Optimal VC-Dimension and Pseudo-Dimension Bounds for Deep Neural Network Derivatives
Authors: Yahong Yang
Haizhao Yang
Yang Xiang
Venue: NeurIPS 2023 poster (2023)
Keywords: VC-dimension
pseudo-dimension
Sobolev space
generalization error
nearly optimal approximation

Abstract: This paper addresses the problem of  nearly optimal Vapnik--Chervonenkis dimension (VC-dimension) and pseudo-dimension estimations of the derivative functions of deep neural networks (DNNs). Two important applications of these estimations include: 1) Establishing a nearly tight approximation result of DNNs in the Sobolev space; 2)  Characterizing the generalization error of machine learning methods with loss functions involving function derivatives. This theoretical investigation fills the gap of learning error estimations for a wide range of physics-informed machine learning models and applications including generative models, solving partial differential equations, operator learning, network compression, distillation, regularization, etc.

Nearly Optimal VC-Dimension and Pseudo-Dimension Bounds for Deep Neural Network Derivatives
Yahong YANG
Department of Mathematics
The Pennsylvania State University. University Park, State College, PA, USA
and Department of Mathematics
Hong Kong University of Science and Technology Clear Water Bay. Hong Kong SAR, China yxy54988psu. edu
Haizhao YANG"
Department of Mathematics and Department of Computer Science University of Maryland College Park College Park, MD, USA
hzyangoumd.. edu
Yang XIANG
Department of Mathematics
Hong Kong University of Science and Technology Clear Water Bay, Hong Kong SAR, China
and
Algorithms of Machine Learning and Autonomous Driving Research Lab HKUST Shenzhen-Hong Kong Collaborative Innovation Research Institute Futian, Shenzhen, China maxiangQust.in
Abstract
This paper addresses the problem of nearly optimal Vapnik- Chenik-Cherooeeniss dimen- sion (VC-dimension) and pseudo-dimension estimations of the derivative functions of deep neural networks (DNNs). Two important applications of these estima- tions include: 1) Establishing a nearly tight approximation result of DNNs in the Sobolev space; 2) Characterizing the generalization error of machine learning meth- ods with loss functions involving function derivatives. This theoretical investigation fills the gap of learning error estimations for wide range of cesssics-informn machine learning models and applications including generative models, solving partial differential equations, operator learning, network compression, distillation, regularization, etc.
Introduction
The Sobolev training 8
of deep neural networks (DNNs) has had a significant impact on scientific and engineering fields, including solving partial differential equations 255
40
46
45
22
42
"Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

33 10,, operator learning 29 26 network compression [35 distillation [21 34 regularization g
and dynamic programming 15 48 etc. For example, Sobolev (semi) norms have been applied to 30 to control the Lipschitz constant of DNNs. Moreover, Sobolev norms and equivalent formulas are commonly used to define loss functions in various applications such as dynamic programming [15 48), solving partial differential equations [2 [22 [3], and distillation [4] 35]. These loss functions enable models to learn DNNs that can approximate the target function with small discrepancies in both magnitude and derivative. For example, when utilizing the Deep Ritz method [2] to solve PDEs such as the following one:
penalize function gradients in loss functions 2 17 15
v f in S2 0u 8v
= 0 on a2,
the corresponding loss function can be expressed as:
( 1 Vo(x; dx + n
1 - (L
2 o(z;; 0)dz)
f fólæ;; O)dæ,
where 0 represents all the parameters in the neural network. Here, Ω denotes the domain (0, 1)d Proposition 1 in (27] establishes the equivalence between the loss function (D) and [ 0) - u² (x) ((oo.))) where u²(x) (x) denotes the exact solution of the PDEs in equation I
1/2 Thus, the Sobolev norm ((0, 1)4) serves
and || ((o.))) == (Coslass D IIlL)((01))))
as a measure of the loss function, and Sobolev training is employed to solve PDEs within the Deep Ritz method.
Two natural questions that arise are: 1) What is the optimal approximation error of DNNs described by Sobolev norm? 2) What is the generalization eгтоr of the loss function defined by a Sobolev norm? The key step to address these questions to estimate the optimal Vapnik- Chervonennkss dimension (VC-dimension) and pseudo-dimension 3 46 22 of DNNs and their derivatives. Intuitively, these concepts characterize the complexity or richness of a function set and, hence, they can be applied to establish the best possible approximation and generalization power of DNNs.
Definition 1 (VC-dimension [.. Let H denote a class of functions from X to {0, 13. For any non-negative integer m, define the growth function of H as
Hu (m) = max
[(h(z1), h(z))..,))))......))) M(E)) h HYI
21.22..-.S EX
The Vapnik- Chervonekesss dimension (VC-dimension) of H, denoted by VCdim H), ) the largest m such that (m) = For class G of real-valued functions, function,, define VCdim(G) ;= VCdim where sgn(g) == [ssgn()): : E G} and sgu(x) = 1[x 0).
Definition 2 (pscudo-dimensie) pseudo-dimension of F. denoted by Pdim(F), is the largest integer m for which there exists (I1, 22 Ims 31, 1/2, .... vm) E x RR" such that for any (b.....,bm) 10,1) 1]mh there is E such that Vi (Ix) > Vi b 11
(32). Let F be class of functions from X to R. The
The main contribution of this paper pseudo-dimensio of DNN derivatives. Based on these bounds, we can prove the optimality of our DNN approximation, as measured by Sobolev norms (Theorem 33). and obtain a tighter generalization error of loss functions defined by Sobolev norms. Our results facilitate the understanding of Sobolev training and the performance of DNNs in Sobolev spaces.
estimate nearly optimal bounds of the VC-dimension and
Bounds for the VC-dimension and pseudo-dimension of DNNs have been established in [66] 5 3
4. 20 However, these approaches and findings cannot be applied to Sobolev training, as they do not account for the derivatives of DNNs, which represent a key difference between Sobolev training and classical methods. Obtaining such bounds for DNN derivatives is much more difficult due to their complex compositional structures. DNN derivatives consist of a series of interdependent parts that are multiplied together via the chain rule, rendering existing methods for estimating bounds inapplicable. Estimating the VC-dimension and challenging problem addressed in this paper. In [II, the VC-dimension and pseudo-dimension of DNN derivatives were analyzed, but the results were suboptimal due to lack of consideration for the relationships between the multiplied terms DNN derivative. As a result, their findings do not provide the optimal approximation of DNNs in Sobolev spaces and can only give generalization
of DNN derivatives is the most crucial and

---

error that is much larger than the actual error that may arise from Sobolev training. In this paper, we introduce a novel method that investigates these relationships, resulting in simplified complexity of DNN derivatives. This, in turn, allows us to obtain nearly optimal bounds on their VC-dimension and pseudo-dimension.
The paper is divided into two parts. In the first part, we establish a nearly optimal bound on the VC-dimension of DNN derivatives with the ReLU activation function ø (z) == max(0,
Theorem 1. For any N, L, d E N4, there exists a constant C independent with N, such that VCdim(DD)) 3 CC L logg L log2 N,
(2)
for
df, where 4 :- ( 01 NNN in Rd with width N and depth L}. and Dr is the weak derivative in the i-th variable.
DΦ == {v== Djo : : E 2, i
(3)
By utilizing Theorem we prove that our DNN approximation rate for approximating functions in Sobolev spaces W wm, 1))) using Sobolev norms W ((0, 1)d) nearly optimal. We present our construction of DNNs for this approximation in Theorem 3 and we demonstrate the optimality of such approximation in Theorem Furthermore, we generalize our method approximate DNNs in Sobolev spaces measured by Sobolev norms Wmm,00 ((0, 1)d) for m 2 2. The details of this generalization are presented in Corollaries and 2 The Sobolev spaces, equipped with Sobolev (semi) norms, are defined follows:
Definition 3 (Sobolev Spaces [3).. Denote St as (0. 1)s, D as the weak derivative of single variable function and D D D22 ... ...Dr Da as the partial derivative where a [a 022,... ........ ,al" and D, is the derivative in the i-th variable. Let E N and 1 S p S co. Then we define Sobolev spaces
Wn- (S2) = L f ('( for all a E Nº with |a| 5n}
with a norm IIfll = (Eosialzn D fllL(())))
1/P ipp
if < co, and ( = maxoglalgn D fll(x( Furthermore, for f = (J,, Sa). f E (2, if and only if ft E W0 (I2) for each i 1,2,..... ........ and [l == max; ((lffll..lllllllll....... Definition 4 (Sobolev semi-norm 13 ) Let n E N+ and 1 S S co. Then we define
1/9 ).P ifp < xc. and Iflw =
Sobolev semi-norm If [flwa.(0) = Σ |a || (11P())))))
max | [l)= Furthermore, for f E Wl,00 Rd), we define (flw..(22.)) =
max;=I.....d (f0x:=_.....(ff/lw........ ([fllw
In the second part of our paper, we utilize our previous work on estimating the VC-dimension of DNN derivatives to obtain an upper bound on the pseudo-dimension of DNN derivatives:
Theorem 2. For any N, L, d E N4, there exists a constant Ö independent with N, L such that
Pdim(DD) (D)) S T,2 L log, N,
where Dt is defined in Theorem
Based on Theorem 2 we can estimate the generalization error of loss functions defined by Sobolev norms, as demonstrated in Theorem [ Specifically, the error is bounded by ON NN log2 1/2) with respect to the width N and depth L of DNNs. This bound is significantly smaller than the previously reported bound of L/ N log, 1)2 in [II. We attribute this improvement our more accurate estimation of the pseudo- dineeddon of DNN derivatives. Our findings indicate that learning target functions with loss functions defined by Sobolev norms does not require substantially more sample points than those defined by -orms [14. as their generalization error orders are equivalent with respect to the width N and depth L of DNNs.
Our main contributions are:
We propose method to achieve nearly optimal estimations of the VC-dimension and pseudo- dimension of DNN derivatives.
3

---

By utillizigg our estimation of the VC-dimension of DNN derivatives, we demonstrate the optimality of our DNN approximation, measured by Sobolev norms.
By applying our estimation of the pseudo-dimension of DNN derivatives, we obtain a hound for the generalization error measured by the Sobolev norm. Importantly, results demonstrate that the degree of generalization error defined by Sobolev norms is equivalent to that defined by Lo-norms, corresponding to the width N and depth L of DNNs.
2 Preliminaries
Let us summarize all basic notations used in the DNNs as follows:
1. Matrices are denoted by bold uppercase letters. For example, A R=x" is real matrix of size m X n and AT denotes the transpose of A.
2. Vectors are denoted by bold lowercase letters. For example, E I"" is column vector of size Furthermore, denote vii) as the i-th elements of v.
3. For a d-dimensional mudti-innex as follows: (a) |a| = =|arl + l02l + ... + loal: (b) x= = x1 x2 (c) ad a.!!!!.......................... a.g..
[a1, ag2, ... E No, denote several related notations os x = [T1, T2, 1 Tal"
4. Let (xx) C Rd be the closed ball with a center a E Id and a radius measured by the Euclidean distance. Similarly, Br, (a:) C Rd be the closed ball with a center æ E Rd and radius r measured by the -nom.
5. Assume n E N then f(n) = (g(()) means that there exists positive C independent of n, f.g such that (n) < Cg(n) when all entries of go +00.
Define 01 (2) = (x) max(0, x and 02 == (x). We call the neural networks with activation function o, with t as 0, neural networks (N,,.Ns)) With the abuse of notations, (1111)
define o, : Rdd + Rd as (x)
for any x = [x1, , xal E Rdd.
7. Define L, N_, No = d and N = 1, N, the width N and depth can be described as follows:
E.N, N4 for = 1,2,..., then oN-NN á with
x ho Wieh h Bis h1... We-ke hy 24 hi Wennhe+ x(x) h
where W. E &RNN and b, E RV are the weight matrix and the bias vector in the i-th linear transform in o, respectively, i.e., h; == - for 1.ri= L++1 and h: a, (h,), for i
1..... L. In this paper, an DNN with the width N and depth L, means (a) The maximum width of this DNN for all hidden layers less than or equal to N. (b) The number of hidden layers of this DNN less than or equal to
3 Nearly Optimal Approximation Results of DNNs in Sobolev Spaces Measured by Sobolev Norms
3.1 Approximation of functions in W with 1. norm by ReLU neural networks
In this subsection, we construct deep neural networks (DNNs) with width of ON log N) and depth of (L L) to approximate functions in the Sobolev space Wm, as measured by Sobolev norms in 11, The approximation rate achieved by these networks is (LNN-(nn1)/ee 22 1)/d).
Theorem 3. For any f E W"...' 1)d) with n 2 and [I I 1, any N, N_, there is a oi-NN with the width (34 + d) I (N log, and depth 26 1) logg (4L) such that
I1(x)) - (x)))ll))) S Co(n, d)N N
2(n 2(m- 2(m 1
where Co is the constant independent with N, L.

---

The proof of Theorem 3 can be outlined in five parts, and the complete proof is provided in Appendix
(i): First of all, define a sequence of subsets of f2:
Definition 5. Given K,d d N+, and for any m = (m1, m2, .... ma) E (1,2)* we define 4.m
I Bmy, where Q2 == U KK
K-1
+ ik! G2 = U
3
2R K + IK 0 1].
Then define partition of unity (9m) (1.234 (0, 1)d with supp Im n no, 1)d C Im for each m E (1,
Definition 6. Given K, d N4, we define
1,
E
K
+
4k
K
+
2k]
0,
x E
+
3
++1
(1))) =
K
1K
K
(2(x)) = 91 x + 2K (5)
4K (xr i
R
K
K
i
+ 4K
4K (x
3
E
+
1K
2K
K
for i E &o For any m (m,, m2, (21, P.,
..,,,........................... ma) (1,2}4 define 9m = -1
Im, (xz))
91
0
3
7
1
4K
2K
4K
4K
Figure 1: The schematic diagram of gi for i = 1,2.
(ii): Then use the following proposition to approximate [9mJme by oI-NNs and construct sequence of a -NNs {Øm me(1,,pe
Proposition Given any N,L,n E N+ for K = [ then for any m = (m1, m2,...,... ma) E 21, there is ONN with the width smaller than (Q+d)(N+1) ([[[++)++++) and depth smaller than 15d(d 1)mL such as [[0m(x) Im (=))))l===(((0011 I 50d (N + 1) 4dmI.
The proof of Proposition T presented in Appendix 7.2.1
(iii): For each 2' C [0, 1]d, where m E (1,2)4, we find a function JK.m satisfying
If fK ol (Rm) S C1 d) dn (n-1) (n-1),
|| - JK. ( (n,
(6)
where Cj a constant independent of K. Moreover, each fK.m can be expressed as fK. Σ -jalgn-19 af.a. (m))= where I (x: is piecewise constant function Ωm The proof of
this result is based the Bramble-Hilbert Lemma 7 Lemma 4.3.8), and the details are provided in Appendix 7.2.2]
(iv): The fourth step involves approximating fk.m using neural networks t'm following the approach outlined in (28). This method suitable for our work because m is a piecewise constant function Ωm and the weak derivative of gf.a.m (x))) on 2m is zero. This property allows for the use of the L norm approximation method presented in (28] Thus, we obtain a neural network vim with width O log N) and depth (L log L) such that
II5km - v/m (1))l S Cs(n, 2 -(n-
[l.x.mm vm S Cz d) 2n/d/ 2n//
5

---

where C3 is a constant independent of N and L.
By combining (iii) and (iv) and setting K | |2|L2/d], we obtain that for each m e {1,2)*
there exists neural network 3'm with width O(N log N) and depth Oo L) such that
llf(z)) I'm (2)) S
[l( - e'm (Am) S Cn - 2
(8)
where C9 is a constant independent of N and L. Further details are provided in Appendix 7.2.3
(v): The final step is to combine the sequences {&mm me (1,234 and {#m (1,21) to construct a network that can approximate f over the entire space [0, 1] We define the sequence {Øm) J ( (1,2)4 because I'm may not accurately approximate f on [0, 1mm The purpose of Φm is remove this portion of the domain and allow other networks approximate on [0, 1]d (2m- Further details on this step are provided in Appendix (72.44
9 19 have studied the approximation of smooth functions or functions in Sobolev spaces by DNNs measured in the norm of L (S2) or W*),(S), they typically present results that are not optimal or are measured in L L"-norms. For example, in (28), they applies Taylor's 's expansion to approximate smooth functions but cannot be applied directly in Sobolev spaces. In 139, they improve on this by using the Sobolev spaces, but their error is still measured in T/o-norms. In [18], the authors show that there exists ReLU neural network that can approximate f E WL),((2), but their approximation rate is not optimal and is the same as that in traditional methods such as the finite element theory. Our work provides superior approximation rate. Later, a rigorous proof of optimality of Thehorm discussed in Appendix 7.2 Subsection 3.3
While recent works 28 23 39
18
31
Lemma to approximate functions in
3.2 Approximation of functions in 7 measured by Wm, norm with m > 1 by neural networks (sketches of the proofs of the Corollaries I and
In this subsection, we utilize neural networks to approximate functions in W7.00 measured by Wmm,00, where > 1. The proof strategy is similar to the approximation measured in the norm of W1.00." However, we cannot rely on ReLU neural networks alone to achieve this goal, as ReLU neural networks are piece-wise linear functions that do not belong to Wmm,00 with > 1. Note that the Bramble-Hilbert Lemma is still applicable in higher-order approximation. Therefore, we need to approximate the function fKmm- E|es Sn-1 a (ar) x within each domain Ωm using DNNs, where 9f.a.m (x) represents a piece-wise constant function within 22 Consequently, ReLU-based DNNs can effectively approximate 9f.a.m(z) within 2m when measured by higher-order Sobolev spaces, since both the higher-order derivatives of Jf.amm (z) and ReLU-based DNNs are zero The parts of ReLU- b-baeed DNNs that do not have high-order derivatives appear in the domain Ω 220m and we will use the partition of unity to ensure that this part disappears in the final presentation, this is the reason why it is still acceptable to have ReLU activations appearing in the network. However, when it comes to approx approximating ax for lox| > 1 based on high-order Sobolev norms, ReI.Ubasse DNNs fail to provide accurate results. Therefore, we require DNNs that utilize the square of ReLU activation in this specific scenario. This is how we construct our approach and the reason why we employ both ReLU and the square of ReLU activation functions.
Instead, we examine the use of 02 neural networks for approximating functions measured in the norm of W2. As per Corollary [ a neural network with O(N log N) width and O log L) depth can achieve a nonasymptotic approximation rate of ONN (2((n)))/ (//ddd_2(nnn))//1/10 2(n-))/d) with respect to the W/2.00 ((0. 1)d) norm. Moreover, our method can be extended to approximations measured in the norm of Wm,.00 with m > 2, as shown in Corollary 2 The proof strategy is similar to that used in Subsection 3.1 except that we need to construct a smoother partition of unity rather than {gm Jmmmm The corollaries are presented below, and further details are provided in Appendix
7.3
Corollary 1. For any f E Wm, ((0, 1)d) with II ((0,)))) S 1, any E with NL +
2 logg NJ 2 max(d, n) and L 2 [ogg N1, there is a 02-NN ((x) with the width 2d46, (N
d) (8g)( and depth 15n (L+ + 2) log (4L) such that
2 [lf()) (x))]l=== (1) < 2d7 "Coln, d)N 2(n - 2(n-2// 1 2(n 2)/d

---

where C10 is the constant independent with N, L.
Corollary 2. For any f E W ((0, 1) with [1 S 1, any N, L, m E N2 with NI+ 21ogg, NJ 2 max (d. n) and T. 2 [log2 N,, there is a 02-NN ((x)) with the width O N Nlog N) and depth O log L) such that
llf(x)) (wm))))mmm000)) ((0.)4) S Cu1 (n, d, m) -(aaa)a----------------aaa-- 2(a-m)/d --(n (nnmm//d where C11 is the constant independent with N, L.
3.3 Optimality of Theorem 3 via estimation of VC-dimension of DNN derivatives (Theorem
In this section, we demonstrate that the approximation rate presented in Theorem 3 is nearly asymp- totically optimal:
Theorem 4. Given any p. C1 C2. Ca, Jn > 0 and n, d N+, there exist N, L E N with NL 2 Jo and J with [! ()(0,1))1) S 1, satisfying for any ONNNN with the width smaller than C log N and depth smaller than C log L, we have
Φ ((.1)) > C3L 2mn
(9)
2(n In other words, the approximation rate of O (( 2(11)/ddd) cannot be achieved asymptotically when ReLU o1-NNs with width ON N) and depth OL L) to approximate functions in Fn,d == {ʃ E Wn. ((0, 1)²): (1/l))=>*(000)))) < 51}. The proof of Theorem 4 is based on the estimation of the VC-dimension of DNN derivatives, which is provided in Theorem
Theorem D plays a crucial role in our proof of Theorem 4 which is established through a proof by contradiction following the approach outlined in Ref. [28] Further details on the proof can be found in Appendix (7.4] The main idea behind the proof is that Theorem [
characterizes the complexity of DNN derivatives, which in turn limits the ability of DNNs to approximate functions in Sobolev spaces.
In this paper, focus the optimality of approximation rate with respect to width N and depth L of DNNs. The dimensionality d is not the focus that we consider in our research. Addressing the question about mitigating the exponential dependence of width on dimensionality, that this arises from the utilization of methods like Taylor's expansion or average Taylor polynomials in our approximation techniques. It remains an open question for future research to explore alternative approaches to address the challenge of getting the dependence of d in the lower bounds.
have observed
4 Generalization Analysis in Sobolev Spaces via Estimation of Pseudo-dimension of DNN Derivatives (Theorem
In typical supervised learning algorithm, the objective is to learn high- dineh-ddmesiinall target function fxx defined on (0, 1)dt with |I (.fllw..==((l. ((0.1)d) I from finite set of data samples {(x,. f(x,))) When training a DNN, we aim to identify DNN (xx; 0s) that approximates f(x) based on random
IM is an i.i.d. sequence of random variables data samples ((, (xx)) Vi=i- We assume that { uniformly distributed on (0, 1)dt in this section. Denote
inf (0) arg inf I
OD ing
[V[(x)) ((; 0)) (f(z)) dxx:; 0)1 da,
(10)
((0.))
1 M
0s = ing (0) == arg inf
[V(((x;) -(=;; 6(=;0))11 + (f(;)) a(x;; 011 (11)
M
The overall inference error is (R)((s) which can be divided into two parts: ERp(Os) =Ro(Od) + (0p) - (p + (0s - ERs(Op) + ERD(Os) - ERs(0s)
< (D(0D) + (R))(O)) RD(00 - ERD 0s) (Rs(
(12)
approximation error
generalization error
where the last inequality is due to (Rs( < (Rs(OD) by the definition of 0s.
7

---

4(n- - Due to Theorem we know that the approximation error (D(( is O(N term since f
$ llf(z) ([]))l In this section, we bound
generalization error in the H ((0, 1) sense:
Theorem 5. For any N, L, d, B, C1. C2. if ó(x; 0D). o(z; E C. will have that there are
constants Cs = Cs( d, Ci C2) and J = J(d, L, CT C2) such that for any M 2 J, we have
ERs((0)) (n + (0s (Rs
sup 0 0.(
E(Rs(()) (D)
S6 Nlog, L Log N)
log M.
(13)
VM
where == {o o with the width < C2 log N and depth I C2L log L, and Rs. Rn Ss OD are defined in Eqs. 11111)
S B).
The proof of Theorem iis based on the works of [ 26 We begin by bounding the generalization error using the Rademacher Complexity and then bound the Rademacher Complexity by the uniform covering number. We further bound the uniform covering number by the pseudo-dimension. Finally, we estimate the pseudo-dimension by Theorem The proof of Theorem 5 is presented in Appendix
7.5
Theorem 2 hhlps to control the degree of the generalization error with respect to N and L in Theorem In the generalization error is bounded by O(NLE). ). In (24), the authors estimate the covering number using the Lipschitz condition of DNNs instead of the pseudo dimeed--n leading to
generalization error that is exponentially dependent on the depth of the DNNs. Our result is much better than them due to the optimal estimation of pseudo-dimension of DNN derivatives (Theorem 2}.
Proof Sketches for Theorems land 2
As Theorems 1 and 2 address the estimation of VC-dimension and pseudo-dimension of DNN derivatives, which is the main contribution of this paper, we provide the proofs for these theorems in this section. The distinction in approach compared to that of [4] lies in the fact that the application of the chain rule requires the considcration of correlations among distinct segments of the deep neural networks, as opposed to treating them independent components multiplied together.
In the proof of Theorem we use the following lemmas:
Lemma (14) Lemma 171.3] Theorem 8.3]). Suppose W S. M and let Pi..... Pas be polynomials of degree at most D in W variables. Define K == [((sgn(P(())........ .gn.......((((
a Rw)
then we have K < 2(2e
Lemma Lemma 18). Suppose that 2 < (mor/w)) for some r 2 16 and m 2 w 2 Then, < 1 + w logg (2r loggr). r).
As the proof of Theorem D
represents the most critical and challenging question our work, we present sketch of it below.
Proof Sketch of Theorem] 7 An element in + can be represented as WL+10 (Wio) (... a (Wix + b.)...) + bz) + bLt1. Therefore, an element in D& can be represented as
(xx) Dio(x) = WL-10% (Wo.o ( + b,) + bz)
(14) where W; E N.N.1 (W), is i-th column of W) and b, E R. are the weight matrix and the bias vector in the i-th linear transform in o, and on(xx) sg) 1 [x 0], which is the derivative of the ReLU function and ao (xx) = diag(on(z:)).
W + b,) ..... ... W20 (Wiz + (Wii,,
Let x E Rdd be an input and 0 E RW be parameter vector in vb. We denote the output of e with input x and parameter vector O as f(x, 0). For fixed æ æ2. Zm in Rd we aim to bound
K = [[ 0)), ..r......sngff... sgn(f( 0))) R R
(15)
8

---

The proof is inspired by 4 Theorem 7]. For any partition S = P of the parameter domain RW, have K E [f ()),..., (f 0))) 0 P.Hl- We choose the
partition such that within each region P. the functions f(zz. are all fixed polynomials of bounded degree. This allows us bound each term in the sum using Lemma] [
The partition of W is constructed layer by layer through successive refinements denoted by Sp. Si...., Sy. These refinements possess the following properties:
Ei W.
We have |So| 1, and for each n 1....,,,, L, we have
ISmll [S
S
2emmiN > W.
2. For each = o,.... L - I, each element S of Sn. when O varies in S, the output of each term in
F, is fixed polynomial function in Σ;= W, variables of 0, with a total degree no more than 1.
For each element S of St. when varies in S, the h-th term in FL for E {1, 21 L + 1] is a fixed polynomial function in W, variables of 0, with total degree more than 1. The sequence of sets of functions {E3} with respect to parameters 0 E R w is defined as:
Fo == {(W1); Wie + b
F1 = ((Wi); W2 (Wiæ + b1), W20 ( + b1) + b2} F2 = ((W1); o Wi + bi), W W2 WW
(Wi + b)) b2),
Wa 1 + b,) + b2) b3}
FL = ((W1); W2o b1)..... W ( bL)}. (16)
The details of the refinements required to obtain the partitions are presented in the appendix. By U
leveraging Property 3 and Lemma we can deduce that K S 2 20m (++))
where
20
U LN) N is the width of the network, and the last incquality is due weighted AM-GM. For
U
the definition of the VC-dimension, we have VCdim((Do) < 2 (VCdin(DD) Lemma 2 we obtain that VDdim(DD)) < I.+1 Ulog, (2 O(N2 1,2 log2 I. loga N) since U = T.2..
Due
1)( 2)]
Note that the "C-dimension estimation achieved in Theorem
T nearly optimal, demonstrated
in Corollary 3 combined with the upper bound in Theorem If the polynomial degree in the VC-dimension bound as a function of N and I. were any smaller, would contradict Theorem 3
which is based on our proof of Theorem 4
Corollary 3. For any d E N4. C,Ju, > there exists N, E N with NL 2 Ju such that VCdim(DD) CN2-EI2-e
(17)
where DΦ is defined in Theorem
We discuss the proof of Corollary 3 at the end of Section 7.4 Next we now present the proof for Theorem
The proof of Theorem 2 can be found in the appendix. The key idea behind the proof is to reformulate the pseudo-dimension of DNN derivatives as the VC-dimension larger set. Based on the definition of pseudo- secudo-dimensions, it follows that Pdim DΦ) VCdim DT). Consequently, following corollary, utilizing Corollary 3 to demonstrate the near optimality the pseudo-dimense estimate presented in Theorem 2
derive the
Corollary 4. For any E N4, C, > O, there exists N, L E N with NL 2 Jo such that
Pd)m(DD) CN
(18)
where Dt is defined in Theorem 7
6 Conclusions and Discussions
In this paper, we establish nearly optimal bounds the VC-dimension and pseudo-dimension of DNN derívatives. Based on these bounds, two contributions to Sobolev training [8] 40 46 are made in

---

this paper. Firstly, we show that the optimal approximation rate of DNNs with width of (N log N) and depth of ( log L) is ((N- ability of DNNs to learn target functions well in Sobolev training. Secondly, we find that the degree of the pseudo-dimension of DNN derivatives is the same as that for DNNs corresponding to the width N and depth L of DNNs. This result suggests that despite the apparent complexity of DNN derivatives, the degree of generalization error of loss functions containing derivatives of DNNs is equivalent to that without derivatives, corresponding to the width N and depth DNNs, As a result, we do not need to use significantly larger number of sample points to learn the target function in Sobolev training compared to regular training.
in Sobolev spaces. This demonstrates the
The estimations of the VC-dimension and pseudo-dimension of DNN derivatives have broad applica- tions deep learning research. For example, in classification tasks, the VC-dimension characterizes the uniform convergence of misclassification frequencies to probabilities and asymptotically deter- mines the sample complexity of PAC learning [4 44 6]. These applications can be explored in the further work. Our focus in this paper is on the Sobolev training with loss functions containing first-order derivatives, and we also obtain the approximation rate 02-NNs described by higher-order Sobolev norms (Corollaries [ and 2). The optimality of these results and the generalization error of Sobolev training with loss functions containing higher-order derivatives of DNNs remain open problems, as estimating the VC-dimension and pseudo-dimension of higher-order derivatives of -2-NNs requires further investigation.
Acknowledgments and Disclosure of o Funding
This work was done during Y.Y.' visit under the supervision of Prof. H.Y., in the Department of Mathematics, University of Maryland College Park. The work of H. Y. was partially supported by the US National Science Foundation under award Naval Research Award N00014-23-1-22 23-2777 The work of Y.X. was supported by the Project of Hetao HKUST Innovation Cooperation Zone BZQB-KCZYB-20222
DMS-220633
and the Office of
References
[1] Y. Abu-Mostafa. The Vapnik-Chervonn Chervonenkis dimension: Information versus complexity in learning. Neural Computation, 1(3):312-317, 1989.
[2] J. Adler and S. Lunz. Banach wasserstein Gan. Advances in neural information processing systems, 31, 2018
[3] M. Anthony, P. Bartlett, et al. Neural network learning: Theoretical foundations, volume 9, cambridge university press Cambridge, 1999.
[4] Bartlett, N. Harvey, C. Liaw, and A. Mehrabian. Nearly-tight VC-dimension and pseu- dodimension bounds for piccewise linear neural networks. The Journal of Machine Learning Research, 20(1):2255-23)) 2301, 2019.
[5] P. Bartlett, V. Maiorov, and R. Meir. Almost linear VC dimension bounds for piecewise polynomial networks. Advances in neural information processing systems, 11. 1998.
[6] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth. Learnability and the Vapnik- Chervonenkis dimension. Journal of the ACM (JACM), 36(4):929 965, 1989.
[7] S. Brenner, L. Scott, and Scott. The mathematical theory finite element methods, volume 3. Springer, 2008
[8] W. Czamecki, S. Osindero, M. Jaderberg, G. Swirszcz, and R. Pascanu. Sobolev training for neural networks. Advances in neural information processing systems, 30, 2017.
[9] T. De Ryck, S. Lanthaler, and S. Mishra. On the approximation of functions by tanh neural networks. Neural Networks, 143:732-750, 2021.
[10] De Ryck and Mishra. Error analysis for physics-informed neural networks (PINNs) approximating Kolmogorov PDEs. Advances in Computational Mathematics, 48(6):1-40, 2022.
10

---

[11] C. Duan, Y. Jiao, Y. Lai, X. Lu, and Z. Yang. Convergence rate analysis for Deep Ritz method. arXiv preprint 0rXiv:2103.13338 2021.
[12] W. E, J. Han, and A. Jentzen. Deep learning-based numerical methods for high-dimensional parabolic partial differential equations and backward stochastic differential equations. Commu- nications in Mathematics and Statistics, 5(4):349-380, 2017.
[13] L. Evans. Partial differential equations, volume 19. American Mathematical Society, 2022.
[14] M. Farrell, T. -iiang. and S. Misra. Deep neural networks for estimation and inference. Econo- metrica, 89(1):181-213, 2021.
[15] C. Finlay, J. Calder, B. Abbasi, and A. Oberman. Lipschitz regularized deep neural networks generalize and are adversarially robust. arXiv preprint arXiv:1808 1808:09540, 2018.
[16] P. Goldberg and M. Jerrum. Bounding the Vapnik- Chink--hervooenkis dimension of concept classes parameterized by real numbers. In Proceedings of the sixth annual conference on Computational learning theory, pages 361-369, 1993.
[17] S. Gu and L. Rigazio. Towards deep neural network architectures robust to adversarial examples. arXiv preprint
2014.
[18] I. Gühring, G. Kutyniok, and Petersen. Error bounds for approximations with deep ReLU neural networks in WaP norms. Analysis and Applications, 18(05):803-85, 2020.
[19] I. Gühring and M. Raslan. Approximation rates for neural networks with encodable weights in smoothness spaces. Neural Networks, 134:107-130, 2021.
[20] N. Harvey, C. Liaw, and A. Mehrabian. Nearly-tight ve-dimension bounds for piecewise linear neural networks. In Conference on learning theory, pages 1064-1068. PMLR, 2017.
[21] G. Hinton, O. Vinyals, and Dean. Distilling the knowledge neural network. arXiv preprint arXiv: 1r3iv:1503.0253/ 2015.
[22] J. Hoffman, D. Roberts, and S. Yaida. Robust learning with jacobian regularization. arXiv preprint arXiv: 02729, 2019.
[23] S. Hon and H. Yang. Simultaneous neural network approximation for smooth functions. Neural Networks, 144:122-16, 2022.
[24] Y. Jiao, Y. Lai, Y. Lo, Y. Wang, and Y. Yang. Error analysis of Deep Ritz methods for elliptic equations. arXiv preprint arXiv:2107.14477 14478, 2021.
[25] I. Lagaris, A. Likas, and D. Fotiadis. Artificial neural networks for solving ordinary and partial differential equations. IEEE Transactions on Neural Networks, 955:987711000, 1998.
[26) H. Liu, H. Yang, M. Chen, T, Zhao, and W. Liao. Deep nonparametric estimation of operators between infinite dimensional spaces. arXiv preprint arXiv:2201.00211 2022.
[27] J. Lu, Y. Lu, and M. Wang. A priori generalization analysis of the Deep Ritz method for solving high dimensional elliptic partial differential equations. In Conference on Learning Theory, pages 3196-3241. PMLR, 2021.
[28] J. Lu, Z. Shen, H. Yang, and S. Zhang. Deep network approximation for smooth functions. SIAM Journal on Mathematical Analysis, 53(5):54555556, 2021.
[29] L. Lu, P. Jin, G. Pang, Z. Zhang, and G. Karniadakis. Learning nonlinear operators via DeepONet based on the universal approximation theorem of operators. Nature machine intelligence, 3(3):218-229, 2021.
[30] Y. Mroueh, Li, Sercu, A. Raj, and Y. Cheng. Sobolev Gan. In International Conference on Learning Representations. International Conference on Learning Representations, ICLR, 2018
[31] Müller and M. Zeinhofer. Error estimates for the Deep Ritz method with boundary penalty. In Mathematical and Scientific Machine Learning, pages 215-230. PMLR, 2022.
11

---

[32] D. Pollard. Empirical processes: theory and applications. Ims, 1990.
[33] M. Raissi, P. Perdikaris, and G. 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:686-707, 2019.
[34] A. A Rusu, S. Colmenarejo, C. Gulcehre, G. Desjardins, J. Kirkpatrick, R. Pascanu, V. Mnih, K. Kavukcuoglu, and R. Hadsell. Policy distillation. arXiv preprint arXiv:1511.06295. 2015.
[35] B. Sau and V. Balasubramanian. Deep model compression: Distilling knowledge from noisy teachers. arXiv preprint urXiv:1610.096533 2016.
[36] Z. Shen, H. Yang, and Zhang. Nonlinear upproximation via compositions. Neural Networks, 119:74-88 84, 2019.
[37] Z. Shen, H. Yang, and S. Zhang. Deep network approximation characterized by number of neurons. Communications Computational Physics, 28(5), 2020.
[38] Z. Shen, H. Yang, and S. Zhang. Optimal approximation rate of ReLU networks in terms of width and depth. Journal de Mathématiques Pures et Appliquées, 157:101-133: 2022.
[39] Siegel. Optimal approximation rates for deep ReLU neural networks Sobolev spaces. arXiv preprint arXiv:2211 1444000 2022.
[40] H. Son, J. Jang, W. Han, and H. Hwang. Sobolev training for the neural network solutions of PDEs. arXiv preprint arXiv:2001.08932. 2021.
[41] E. Sontag et al. Ve dimension neural networks. NATO ASI Series F Computer and Systems Sciences, 168:69-96. 1998.
[42] S. Srinivas and F. Fleuret. Knowledge transfer with jacobian matching. In International Conference on Machine Learning, pages 1723-47311 PMLR, 2018.
[43] E. Stein. Singular integrals and differentiability properties of functions, volume 2. Princeton university press, 1970.
[44] V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Measures of complexity: festschrift for alexey chervonenkis, pages I 11-30, 2015.
[45] N. Vlassis, R. Ma, and W. Sun. Geometric deep learning for computational mechanics part i: Anisotropic hyperelasticity. Computer Methods in Applied Mechanics and Engineering, 371: 17::9,, 2020.
[46] N. Vlassis and W. Sun. Sobolev training of thermodynamii-infoome neural networks for interpretable elasto-plasticity models with level set hardening. Computer Methods in Applied Mechanics and Engineering, 377:1 13695, 2021.
[47] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cam- bridge university press, 2019.
[48] Werbos. Approximate dynamic programming for real-time control and neural modeling. Handbook of intelligent control, 1992.
12

---

7 Supplementary Material
7.1 Proofs of [
Proof of Theorem 7 An element in & can be represented as Φ = 1 (W
b1)...) by) + 11+1- Therefore, element in D& can be represented
(xx) D,o(z) - WL--oo(WLoo ( b.)...) +b)
(19) where W; E -N (WW); is i-th column of W) and b, R. are the weight matrix and the bias vector in the i-th linear transform in o, and (n(x) sgn(x) = 1 0], which is the derivative of the ReLU function and (x) = (1:)())(z;)), Denote W; as the number of parameters in W, b, i.e., W; = N N₁-
Wr.0o(... 0n (W x + bi) ). W20 ( (Wii,,
Let E IRd be an input and 0 RWW be parameter vector in vh We denote the output of with input x and parameter vector 0 as (ax 0). For fixed 11, 22,.... 2m in R4, we aim to bound
K [sgg(f(( .gg............... (m 0)))
R }
(20)
The proof is inspired by Theorem 7]. For any partition S (P,, 1P,.P. ....... ,r} of the parameter domain RW, we have K S Σ [(sgn( (( (on)....,snn([[/ (g 0))) 0 E P: We choose the partition such that within each region P., the functions fax all fixed polynomials of bounded
degree. This allows us to bound each term in the sum using Lemma
We detine sequence of sets of functions { 1/ with respect to parameters 0 RW;
Fo = {(Wi); W x + b,}
Fi ((Wi); W2 Wix b1), W20 (w + b1) b2}
F2 == ((W1); Wo + Woo (W + b.) b2), W Wi b1) + b2) bs}
FL = ((W1). W2oo(Wi bb)..... WL... bb) bb)}. (21)
The partition of W is constructed layer by layer through successive refinements denoted by So, SI....,S,, These refinements possess the following properties:
1. We have |Sa| 1, and for each 1, ..... L. have [S.-1l
SSa
2emm No S
Eist W;
2ist W;
For each n = 0, o,..., - 1, each element S of Sn, when O varies S, the output each term in F, is fixed polynomial function in Σi= W, variables of O, with a total degree no more than 1.
For each element S of Sz. when varies in S, the h-th term in FL for {1, .....
........ L +1 is
fixed polynomial function in W₁, variables of 0, with a total degree no more than 1.
We define So {R..), J. which satisfies properties 1,2 above, since Wa + b and (W1): W affine functions of Wi, bj.
To define Sn, we use the last term of F' Fx inputs for the last two terms in F.. Assuming that So, ,,....,,,,... Sn-1 have already been defined, we observe that the last two terms are new additions to F, when comparing it to F1 Therefore, all elements in F,, except the last two are fixed polynomial functions Wn, variables of 0, with a total degree no greater than n when varies in E S,- This is because S, is finer partition than Sn-1-
We denote Pæ, P=,.n- as the output of the k-th node the last term of Fx-1 in response to xy when 0 E S. The collection of polynomials
De, W, (Pæ S. (0)
1 h 1...,, N.)
can attain at most 2 22mm
distinct sign patterns when O S due to Lemma for 5n W, parts, each having the
W.
sufficiently large m. Therefore, we can divide into
2emm E W.
13

---

property that -n..... (0) does not change sign within the subregion. By performing this for all e Sn we obtain the desired partition S,, This division ensures that the required property is satisfied.
Additionally, since the input the last two terms in FF, is Pa 1,55 (0), and we have shown that the sign of this input will not change in each region of Sn, it follows that the output of the last two terms F,, is also a polynomial without breakpoints in each element of Sn. Therefore, the required property 2 is satisfied.
In the context of DNNs, the last layer is characterized by all terms containing the activation function To. Consequently, for any element of the partition Sz. when the vector of parameters varies within S, the h-th term in FL for h 21,2. ................................ L + 1} can be expressed as polynomial function of at most degree 1, which depends on at most W,. variables of 0. Hence, the required property is satisfied.
Due to property 3, we multiply all the terms in Fz and obtain term D&. Hence, the output of each term in DΦ is a polynomial function in IL+1 W; variables of 0 E S Sr, of total degree no more than 1+1. Therefore, for each S E Sr, we have ([sg((]( 0)), ..., sgn( (3rm 0))) S} s E1Et W;
2 2em(L + 1)/ E W;)
Then
ΣLH
L+1
2emnnN
Ei W;
2emmNN
E W.
K <2 Bem(L+11) +1/ Σ
Wi
II 2
II 2
-i=1
W;
Ei=1 W;
<2 (2em(L + ( + 1)N
(22)
20
where U = 1+1 En W, = O() N is the width of the network, and the last inequality is due to weighted AM-GM.. For the definition of the VC-dimension, we have
2edim( DO) < 2 (eVCdim(D&) + 2)(2+
(23)
U
Due to Lemma
2 we obtain that
VCdim(DD) < L ++++ ( + 2 2)] OON2 L log, N)
(24)
since U = (
Proof of Theurem 2
Denote DΦN == (n( y) ,,.,,) ((x) y, 1b E DΦ, (x, y) E RRd+1..
Based on the definition of VC-dimension and pseudo-dimension, we have that
Pdim(D0) - VCdim(DDww)
(25)
For the (Cdim(D@y)) it can be bounded by O(N log, L log, N). The proof is similar to that for the estimate of VCdim(Dø) as given in Theorem
O
We establish that Pdim(D4) < DCd,m)D@w), where D represents DNNs with N + 1 width
and L + 1 depth. This implies that Pdim DT) is upper bounded by C(N + 1) + 1) log, 1) logg(N 1) 64CN21,2 I,2 logg L. log, N. Therefore, we conclude that 64C > C.
7.2 Proof of Theorem 3
7.2.1
Propositions of Sobolev spaces and ReLU neural networks
The following two lemmas estimate the Sobolev norms and Sobolev semi-norms for the composition and product, which will be used in later proof.
Lemma 3 ([88 Corollary B.5l). Let d, m E N4 and Q C Rd and P2 C I both be open, bounded, and convex. Then for f E 11.00 (L,, IRT) and E w1.00 (Q2) with ran C. l2y, we have
l|g fl f((w).((a)) S Vdm Vdmmax (m())))))))))))))))))))))))) ol (02)) (
14

---

Lemma 4 (118 Corollary B.6]). Let d E N. and Ω C R.. Then for f.g E Wl (Ω), we have
(9f S ( + Ilfllz ( (m)l9lw):>00))
Then we collect and establish some propositions for ReLU neural networks.
Proposition 2 (128) Proposition 4.3]). Given any N, E N+ and 8 E 0, 3K for K
1 there exists O1-NN o with the width 4N + and depth 4L + such that
k k-1 K KK
Φ(x) k E
- 8. T k = 0, 1..,.... 1.
Proposition 3. 128 Proposition 4.4] Given any N, L, E N4 and E [0, 1. 0, 0,1,.- 1,.,.... 2..,,...2L$
there exists a σ NN & with the width 16s(N + 1) 1og2(8N) and depth (5L - 2) log (4L) such that
(o(1) E N 2 L 2$ for i 0,1, 2
0 5 ((x) S D
Proposition 4. For any L,
E N4 and a > O, there INN & with the width 15N and depth 2L such that (()la)>><(aaaa)) $ 12a² and
|,,(, =yllmr S N-2
(26)
Furthermore,
6(0, v) 0o(0.)) 0, y (-a,a). Oy
(27)
Proof. We first need to construct neural network approximate x2 on (-1,1). and the idea is
similar with [23] Lemma 3.2] and (28] Lemma 5.1]. The reason we do not use [23 Lemma 3.4] and
28 Lemma 4.2] directly is that constructing (xx; y) by translating neural network in W7, (0. 1]
will lose the proposition of (0..)) = 0. Here we need to define teeth functions T; on T. E [-1,
[2
a
Ti = {2(1
2
and
T. o for = 2,3,....
Define
T.(T)
22
According 23 Lemma 3.2] and 28 Lemma 5.1]. know &b is neural network with the
width 5N and depth 2L such that | W/ ((-1,) $ 2, [1x()) (( S - and (0) = 0.
By setting z at E (-a, for E (-1,1), 1), we define
(xx) a² 2
Note that x² = a² (²)) we have
[1)((x)) - 22Iwixx(-aa) = =0²
15 a
~
-(2)²
(I
S N-
and (0) 0, which will be used to prove Eq,
27
Then we can construct Φ(x, y) as
r + yl
[
o(x, y) = 2 1b
1
(28)
2
2
15

---

where (x)) is neural network with the width 15N and depth 2L such that ((=la)) S 12a² and
[| u) - -yllw
S 6a2N-4
(29)
For the last equation Eq. 27 due to o(z, y) in the proof can be read Eq. 28 with x0
-
Proposition 5. For any N, L, E N4
there exists dN-NN with the width 9(N + 1) s and depth 14s(s L such that | @él ((0.1))) $ 18 and
[ςδ(()) 2122 -x Iallwa - 10(s I) + +1) 7st,
(30)
Furthermore, for any i = 1, 2................. if r; 0, we will have
6(21, 22; .... 1t- 1, T++1: v.) aΦ(21, F2 2......................... ................................ Fz- 0. 2 2441, 21,1....,
0, i i j. (31)
Ox,
Proof. The proof of the first inequality Eq. (30) can be found in 23 Lemma 3.5]. The proof of
Eq. (31) can be obtained via induction. For s 2, based on Proposition we know there is a neural network d2 satisfied Eq. (3I..
Now assume that for any i S a there is a neural network di satisfied Eq. (31). On constructed
On (2 .2.... In) = @2(@n-1(11 x2, ... an- 1), (
(32)
which satisfies Eq. For = n, we have
30 Then on (11 T2, ..,
T2- Fi+1 Fn) 0 for any i
.,,,...,?
Φ( 22..... 0) Oz,
D0z - (2) 1
In 0) don (x1, 22, In-1) = 0. (33)
d0 00n-1(1i U2 ................................ In Fn-1)
0r,
by by the propecty of 42.
For < n and j < we have
6(11, ... T4-1, Ti+1, dx
002((nn (101,1101,100000000 x2, ........ 1, 3, 1it. ( (In))
0ihn ( 1., 0, 1i Fn 1)
0.
DΦn (II,..., O, 1i...... xn-1)
dx,
=0, via induction.
(34)
For i < n and j n, we have
<0 T2. ... Li- 0, 1.
Orn
ddz(On-11a B2.... 14-1, Hn In-1)..
do 0.
(35)
(x()))
dæn
=0, by property du.
Therefore, Eq. 31 is valid.
Proposition 6
23 Propositiion 3.6)). For any N, I,, E N4 and |ol| there d1-NN 6 with the width 9(N + 1) + + and depth 14x2 such that (1ollw.>>(... S 18 and
[[ő(x) xz 20 I 10s(N + 1
(36)
{ i=t and each ps is Proposition (139 Proposition 1]). Given a sequence of the neural network {ps
01-NN from R IR with the width N and depth Li, then EMd Pe is o -NN with the width N + 4
and depth Σ M
Li.
We present the proof of Proposition beloo.
16

---

Proof of Proposition 7
First, we construct 91 and by neural networks in [0, 1]. Note that [ -
L 2 (LL +1) We first construct a ONN the small set [0, [ [[2//]] easy to check there is neural network & with the width and one layer such
4K (a
(1))
8K
8K
8K
(37)
4K (x
8K
x
E
SK
8K
0,
Otherwise.
5
8K
3K
Figure 2: 4/1
Hence, we have network th with the width 4 [/vi/d and one layer such as
[N -1
(x) = Σ
+
K
Next, we construct v); for = 2,3,4 4 based on the symmetry and periodicity of g. 122 is the function
with period [NTa][Laaa 0, [
and each period hat function with gradient 1. th3 is
the function with period [zar_T 0, 2'// and each period hat function with gradient
[127d]
2 ((1,2/a [|,47]]
(1.2/1++1)
and each period is a hat function with gradient The schematic diagram in Fig. (The diagram is shown the case for [N1/d] and [L | + is even integer.).
d is the function with period
in 0,
[1:74]]
Note that die vis (x) the function with period [NVc]ua [0. 1] c Jo. (LL*))++1**
[2214] and
each period is hat function with gradient 1. Then function t the tha the (x) is obtained by
(1z\/d]+)) [2/44
repeating reflection 1 in 0.
which is the function we want.
Similar with wh, 1/2 is network with 4 /|d width and one layer. Due to Proposition 7 we know that thy and db is a network with 7 width and [/d + depth. Hence
((x) = 11 the o tha a (1((x)
(38)
a network with [[N1/d] width and 2 I + depth and 9i = xb (x st) and 9i =
d (a ).
Now we can construct 9m for m {1, 21 based on Proposition There is neural network épod with the width 9(N 1) d and depth 14d(d 1)nL such that || wo < 18 and
pp (x: - 2112 Fallyyi. ((0.1))) S 10(d 1)(N 1) 1)-rdl
17

---

127
2
12449
[na2]]
[nx77
1224
[1
+1
2((21
1)
(4 1)
[281]]
[1244]
Figure 3: th for i = 2,3,4
Then denote om (m)) : Pprod (Fmp (gmm Am...........................9.. 9m.) which is a neural network with the width smaller than (9 + dN + 1) + and depth smaller than 15d(d 1)mL. Furthermore, due to Lemma we have
(x) Im 9m (2))lllx <d p()p 21 ... Fdl 1. ((0.1)a)
+ dd ll x1 ... Iel (ollwi.. (2
=da - 1)(N + 1) 7ndl. (1 (1+4 (14
<50d (N + 1)
(39)
where the last inequality is due to
[N1/d]20 |, (N - 1) 3ddn..
N2 (N + 1)3da1.
12
1,2
S
I
2dn $ 1.
(N + 1) 1)adaI-2
In the final of this subsection, we establish three lemmas for {5 me {9m) me me (1,234 and 1ombme(1.2) defined Subsection 3.1 Lemma S. For (mmmmmm(1p)) (1,23 defined in Definition 5 we have
U
Pm = [0, 1)4.
m1.21
Proof. We prove this lemma via induction. is valid due to O1 U.2 lemma is true for d - 1, then
[0, 1]. Assume that the
U Pm = 00 1
U Pm x Uh +
U
Pmm x Zz
m1.22
m m
mE(1,2)d-1
(10, 1|=-1 1 x 2.) (10 02) = [0, 1]d
(40)
hence the case of d is valid, and we finish the proof of the lemma.
18

---

Lemma 6. {Im (m defined in Definition 6 satisfies:
(i): Eme(1,2 Im (x) for every x E [0.
(ii): supp Im 7 [0, 1 2m where 14m is defined in Definition
(ūi): For any m (m1,
m m2,.............................
ma) E {1,2]a and a (I1, (2,..22-. 2.1....... xd) E [0, 1m there
dgmg (z2) 0.
exists j such as Jmy (xz) = 0 and
dmg
Proof. (i) can be proved via induction Lemma S and we leave it to readers.
As for (ii) and (iii), without loss of generality, we show the proof for m. := (1, .......................... 1). For any
a E [0, (0mm there is zÿ E [0, (2 Then 9n (xzz) = 0 and Im. (a:) = [[ 91 (1z) = 0.
therefore supp Im. n [0, 1j 9m. Furthermore, dgm, (x,) for Ij E [0, 1] S2 due the definition of ya (Definition 6. then we finish this proof.
dæ,
The following lemma demonstrates that om defined in Proposition norm the entire space to 2m. Lemma 7. For any xxx) E w ((0, 1))), denote
1 can restrict the Sobolev
M =
then have
1 xxxx)| = (m))(()
[10m(x)) x(x) dm (0m (z)), ( (ww.))))1ll==01.)))))))))) = =l) (x)) x(xx) (2) wl
(41)
for any m E {1,2]d, where om (x) and 9. is defined in Proposition and Definition, and ΦM is from Proposition 4 (choosing a M the proposition).
Proof. For the first equality, we only need to show that
1m0m (a)) ((=))llw1.=<0001)/
0.
(42)
According the Proposition [ we have @m (z)) Opeoal (9m (Jmn)
Imggs- -angg----0 Im,)) and for any dgm, (my) 0 due Lemma
(I1, ,2, .d) E (0, 1)dd (0.. there my such Im, (xz) and
day
Based on Eq. 31 in Proposition 5 we have
@m((r) Johm (x) dr.
= O, x (0, (0,1)aM0 10mm
Furthermore,
Je (a:)
Dpprod (9m. Imas......
Ima) dgm, (x1z) dæy
O.
(43)
Sym;
Hence we have
d Σ [dm(x) - x(x)|+ +
Im (x)
x(x)]
= 0
(44)
0z,
for all E (0, 1)
Similarly, for the second equality in this lemma, we have
a (eo x(x))
10 (x)))
2z,
d Σ
a (0, x(x)]
0x(x)
dΦm (x)
]
(0,x())(()))
+
0x(x:
dx,
ddm(
dx,
=0, Q=1
(45)
19

---

for all x E (0, (0 based on
abm (0,1)
0. y (-M,M),
dy
and (d)( 02g
0. Hence finish our proof.
7.2.2
An approximation of functions in Sobolev spaces based on the Bramble-Hilbert Lemma
7 Lemma 4.3.8)
In this subsection, we establish {fk.m m1(2))) as mentioned in Subsection 3.1 which is presented Theorem [6 To prove this result, we build upon the work of [T8), which leverages the average Taylor polynomials and the Bramble-Hilbert Lemma to approximate functions in Sobolev spaces.
Before show Theorem 6 define subsets of 9m for simplicity notations.
For any m E {1,2]% we define
22, 1m, 52
3+ 42, - 2 1my $2
1m = 10, II
(46)
2K
4K
i= (11, .2, dd) E 10.1..., K]dd and is easy to check USE Im,t 9m
Theorem 6. Let K E N4 and n 2 2. Then for any E W ((0, 1)8) with |1 ((0)))==((()))))))) S and [1, there exist piece-wise polynomials function JK.m -1a Im (2)) on Qm (Definition 5) with the following properties:
If fK 1l (Rm) S C1 (n,nd))K(nr
| fK (m (Alm) S Ci dn,
(47)
Furthermore, 91. (m)) Pm + IR is a constant functiion with on each P E 1..,..., Kja. And
(ffam (x)) S C2(n, d)
(48)
for all Im. where Ci and C2 are constants independent with K.
This proof similar to that of [8. Lemma C.4.], but we provide detailed proof as follows for readability. Before the proof, we must introduce the partition of unity, average Taylor polynomials, and lemma
Definition 7 (The partition of unity). Let d, K N4, then
V [14 : i E f0, K}d}
with h4 : R&d + for all i (0, 1,.., KRd d is called the partition of unity [0, 1]d if satisfies
(i): 0 < ha(x)= < for every h4 E
(ii): Σn.ew h4 1 for every [0.
Definition 8. Let n 2 and f E Ww..0 ((0, 1)d), æn E 1)) and r > O such that for the ball B(xo) == ((xo)r.11 which is compact subset of ((0, 1)d). The corresponding Taylor polynomial of order of f averaged over B is defined for
(xx(
T (x:)b.
(49)
where
TTf(x)
Σ
aa f(y)(( - y)a
Ja|šn-1 a!
(1-(le-x0//1))
x 3D T x 3D S f,
(x())
0,
c -11-((le=aa//1}) dx.
Gr =
(50)
20

---

Lemma 8. Letn's 2 1 and E W (00, 1)"), 20 E Ω and r > O such that for the ball ( == (2o)) which a compact subset of ((0, 1) The corresponding Taylor polynomial of order n. of averaged over B can be read as
f())
= Σ cfa.t.
|a In-1
Furthermore,
l/,al - C2(n,, (fln)))llll (B)
(51)
where C2(n, d) - a.
Proof. Based
18
Lemma B.9.], f()) can be read
Q"
Σ
cfa
(52)
Sa/
where
1 (G + a)+ 934a / D
C/.a
Σ
(0)))()))bb
(53)
In+
for ap+a
(a++ a!j!
Note that
1/1 Da+ f( dy s =1// = Ifllw=
(54)
B
Then
lcf.al S C2(n, ()
(55)
where C2(nnd) -na+ alg
The proof of Theorem il based average Taylor polynomials and the Hamble-Hilbeet Lemma Lemma 4.3.8).
Definition 9, Let Q B E Rdd, Then Q is called shaped with respect to if conv ((x) UB& Q), for all Qt
Definition 10. Let Rdd be bounded, and define
R { {o r> >0: star-shaped with respect to By (wo)
there exists Do such that S2 is
Then define
diam(())
max = sup R
and call
7 max
the chunkiness parameter 0 R + Q.
Lemma (Bramble- Hilbert Lemma [7] Lemma 4.3.8J). Les E Rd be open and bounded, 2g E S2 and such that Q is the stared- shaped with respect to B = BrA (xn), and > 2 mmax Moreover, let n. E N4, S S oa and denote by y by the chunkiness parameter of Q. Then there is constant C(n, d, 7) > 0 such that for all f (
- Q" Ilwtirg) S C(n, d, "> fllwa for k: = 0, 0,1,...... 1....,n
where Q" denotes the Taylor polynomial of order of J averaged over B and h = diam
Proof of Theorem 6 Without loss of generalization, we prove the case for m = (1, 11.1..... ........) =: m..
Denote F. : W' ((0, 1)d) - W7.00 (Rd) an extension operator and set := F.f and CF
the norm of the extension operator.
21

---

Define Py. as the average Taylor polynomial Definition 8 in Bi.k = B sk-l- 1-1
(86+3)
i.e.
8K
/
PS
Tzf(2)b
de (y) dy.
(56)
BL,
Based on Lemma 8
Py. can be read
Psá
Σ lalsn-1
(57)
where
lo,,aal S C2(n.d).
(58)
The reason to define average Taylor polynomial on Bi, is to use the Bramble-Hillerrt Lemma on
88 + 3
3 3 4ig
Dm..t
B sR.
1
8K
II
K'
4K
Note that
1
1
3
diam (Sm.. 2Vd.
"mmax mm (mm_.)); (9mm.
4K
2
8K
max (mm.,.)
Therefore we can apply the Bramble-Hilbert Lemma and have
|lf Pr.llem (am..))) S (B, d)K-"
If Pf P/.allt.o CBи (n, (n-1)
(59)
where Cnu(n, d) ||| n231 Lo gd-12 (1-22) de
2 + +V4
Ce by following the proof of
Lemma 7 Lemma 4.3.8). Therefore,
II - P/iilws.>> (0m..s) d)
where C1 Ci(n, d) BCBB (n.
Now we construct partition of unity that we use in this theorem. First of all, given any integer K, define {ha)a from IR
I::
he(x) = [KK (1
(AK
8i 81+))) Mxx =
|xr >
(60)
8K
4 4 2/x].
< |x|
2
It is easy to check that JK is partition of unity of [0, 1] and h,(x) 1 for x E
[
3+4
Hence
4k
can define ha(a:) for (61,12,.... (2)
10.1, KJa and x (21, 22, ,
Rd.
ha(1)) II hi (xz),
(61)
J=1
and { [1g : i E {0 10,1,...,K]' is a partition of unity of [0, 1jd and h4(x)) = 1 for x E
m
d
Pm and i = (2..,,...., E 1...,..., KYd. K 4k
3441,
1=
Furthermore,
[|a(F - (8m. S I1 P).elle<(amm.)) S dn
(62)
and
hha(F - -....)/..wwwwppp ( s
S CBH(n, (mn-1
(63)
which is due h4 on Pm...-.
Then
[|4[ pr.))lli (Bm..)) S (n,
(n-1) ((n-))
22

---

Finally,
Σ
hiPsi
max K).
|1 - py.s)lll (Amm..)
tE.00II....KK KJd
12.00 (8mm)
I Cnnn, d) (- (n-1),
(64)
which is due KJjo Qm. and supp 14 O Amm 9m...t
Similarly,
haps,
_C((n,))K~*.
(65)
iE Kuj
Last of all,
sk. (x) =
Σ
huPpA =
E
E
1E,0,1,...Ky K3d
iE(0,
JalSn-1
Σ
al
(0,
Σ
ffa.m.
(66)
Sa-sn1
with 19 (x) & C2(n, d) for x E 9m. Note that If,am. (x) is step function from Um. R:
ff.amm. (x)) Cftia
(67)
for x E [[
i, 3+44; 1K
and = (i1, i2
ia) since h4(x)) = 0 for x E Om. AlI=
3+4
K
K
4K
and ha(ar) = for E I[
3+48
K 1K
7.2.3 Approximation of functions in W.,co with W1, norm by ReLU neural networks in the whole space except small set
Theorem 7. For any ʃ W'. ((0, 1)a) with I[ S 1, any N, E N4, and m d+1 1 (N + 1) log (8N)
(mi, m2,... ..., ma) E {1, there is neural network 4mm with the width 25m and depth 27n (L + 2) logg such that
(x= t/ (2:) (I)) (Qm) S Co d)N 2(n 2(--1/dd 2(n 2(n-1)/d
Il((=) ei (x)) (10)) (5m) I Co(n, doNN-)/N/N-- 2n/d 2n/d1-2n/d 2n/d
(68)
where Co is the constant independent with N,
Proof. Without loss of the generalization, we consider the case for m, (1, 1, (I.,,...,11 1). Due to
Theorem and setting K [ we have
|l fk.m. 11 (0m.) (n, (n, 2(n (C 2(n 1(nd
||ʃ f 1 (ftm.) 2 = (n,, 122/d
(69)
where fK.m. = Σ 2/alsn Sn- Isaam. x for x E 2m, Note that Jf.a,m, (x) constant
function for æ 11 K
3+4i; and (i,, (i.i,,)), da) E (0,1,.... K 1]d. The remaining
4k
part is to approximate fk.m. by neural networks.
The way to approximate I5.amm m. (a:) is similar with 23 Theorem 3.1). First of all, due to Proposition 2. there is neural network Φ1 (x) with the width 4N + 5 and depth 4L + 4 such that
b k+1
1
x(x)= = k, x E
k = 0, 1, ...., K 1.
(70)
K
K
4K
23

---

Note that we choose 5 =
1 3R 3K
1
S
in Proposition
Then define
Φ2(x)) = (x1)
Φ1 (x2)
Ø (1d)
K
K
K
For each p =0, 0.1.,.... 1..... Kd 1, there is bijection
(pp) [/, 72 nu] E f0,1,....
K 13ad
such that Dj=1 K p. Then define
7(p) + C2(nn, d)
m,
K
Ex.
E [0,1].
2C2(n, d)
where C2 d) is the bounded of Jf.am. m. defined in Theorem 6 Therefore, based on Proposition 3
there a neural network (x) with the width 16n(N + 1) loga (8N) and depth (5L + 2) loga
such that t0a (p) Ea.pl $ 2- I, 2n for p = 0, 1...... Kd 1. Denote
(x(x) 2C2(n, dj
Σ 3 x2 K
C2(nn
and obtain that
(ppp) Φa
[pp))
= 2C2(n, d)) - -ca.pl S 22C((n, L
K
m.
K
Then we obtain that
ll (Φ2(x)) am. (x) Ilwl. (0m.) =1 (#2(z)) -f.am. (x) (0m.)) <2C₂ d)N L-2n 2n
(71)
which is due dx (d2(x)) - Jm (x) a step function, and the first order weak derivative is in Pm..
Due to Proposition 6 there is neural network áz with the width 9(N + 1) + and depth
14n² I, such that [193.a ((.)((()))))))) 18 and
[ (a) x: I ( S 10n(N + +1) 1)-1L
(72)
Due to Proposition 4 there is neural network ee with the width 15(N + 1) and depth 4n + 1) such that ||o. (-C. I d2) and
- (all:))))--lllvxx_((...p S ((C2((n,)))(0) 1) 22((2+1)
(73)
where C3(n, d) max 18).
Now we define the neural network dmn (x) to approximate fk.m. (x)) Pm.
Vm. (x) =
Σ
( (z.
(74)
lalsn-1
24

---

The remaining question is to find the error E:
:
Σ
@4
fk.m (x)
aals-1
(0m.))
||04 (0. (x)]
(x)x g,
I..ammm
wi.
Ja|sn-1
(00100((0(x))) (z) -0l0
Sn|Sn-1
E1
( m..amm (ta)) (1)
1h-1
=
(2)00, - a, (x)) 1p.. (8m.a)
(75)
cx Kn-1
As for E,, due to Lemma 3 we have
E Σ 2Vd
f (02 haapa//........//../r.e./aa/aaaa |
v)
|a snlsn-1
max
2Vd 1)4((x,)) (164401)))- Ca xyllmo
la|sn-1
+ (/ 2n((+1)
jalsn-1
<C1(n, d)(N + 1
(76)
where Cn d) dn [Cs(n, d) 1] (C2(,,)))
As for E2, due to Lemma 4 we have
& <
Σ
2 (0222())(2))
J.a.m. (0)1lyx> (am.) ((aa(=)ll:==(mm... (Am.)
In
T22 2 22
(77)
The estimation of &g is similar with that of &g which is
Eg S Σ lg..a.m llwi (103, x w1
(Am.) (mm.)
< 10n (2(nnd))(N))) + +1)
(78)
Therefore, using the total error is
2n([+1) & N 2n (N + 1) Tpt < (N+1) (N+1)-2n((+))
E E + Eg + Eg < Cs(n, d)K 2n 222
2n
(79)
where Cs(n, d) Ca(n, d) + 72m Cz(n, d) + 10n d)n.
At last, finish the proof by estimating the network's width and depth, implementing v/m, (w)). From Eq. (74), we know that vmm (x:) consists the following subnetworks:
1. Φ3.a (x) with the width 9(N + 1) + and depth 14n² L.
25

---

2. (2(2) with the width 4N + 5 and depth 4L + 4.
3. &a with the width 16n( N 1) 1og2(8N) and depth (5T () log2(44.).
(2 y) with the width 15 + 1) and depth 4n(T. + 1).
Therefore (xx) is neural network with the width 25n (N + 1) logz (8N) and depth 27n² (L 2) log,( (4L).
Combining Eqs. 69 and 79). have that there neural network 1/m. with the width 25n 25m 3
logo (8N) and depth 27 L + 2) logg (4L) such that
[x m'm (z) wl. (1mm.) I Co(n, 22n 22nn-111
[x) 2/ (.)]l S Co(n, d)N L- 2n/dd
(80)
where Cs = C1 + Cs is the constant independent with L.
Similarly, construct neural network t'm with the width 25m d+ (N 1) log (8N) and depth 27 2) (4LL which can approximate f on 4m with same order of Eq. (80)
n
7.2.4 Proof of Theorem 3
Now can prove Theorem based on Theorem and Proposition 1
Proof of Theorem 3 Based on Theorem
there is a sequence of the neural network
(x)(()) (m))mmmm122 (1,23 such that
l] (z) ( (mm) Co(n, N)NN 2(n 2(n-))((11144) -- 1(n-
Ilf(x)) - t'm (m))))))lal) (=)))> S Co N N- -
2n/d
(81)
where Co = C. + C3 is the constant independent with N, L, and each t'm a neural network with the width 25n (N 1) (8NV and depth 27n (L + 2) (4L). According Proposition | there is a sequence of the neural network {ém (2) (1.,)))) (1,2)4 such that
Im (x) 9m (x) [w1. ((0,)))) S 50d (N + 1) 4dnL
where (9mm me (1,2g² is defined Definition 6 with Eme (1.24
a Im (x) and supp 9m 9m [(, 1]
Pm For each 2m. it is a neural network with the width smaller than (9 + dN + 1) + - 1 and depth smaller than 15d(d- 1)mL.
Due to Proposition there a neural network & with the width 15(N + 1) and depth 14n L such that | w1.. (-C, $ (2( and
[0(,,1) xy
1 <6(CT) + +1) 11-77(4+1)
(82)
where C, = C. + 50d +1.
Now define
d(x)= = Σ
Hlm (m)))
(83)
mE (1.2)))
Note that
R =1] ((x))]l1>>(00.))
Σ
Im f(x)) 6(x)
11.x0 ((0.1)
IIm f(x) - -mm(x) (m))
mE (1.24
(1,10
Σ
(0m(()) vm((x) ((0m(()) (z)),
(84)
mE(1.244
Wl.. (l..(((0)1)))
26

---

As for the first part,
Σ Im f(x)- - (m()) vm)
mE
(l..x((0.11))))
Σ 11am f(x) - (x)) 2m (2) (2)1
(1,22)
<
Σ
[1lgom - 6m (())) + ll(fm - -mm(x)) (=) ((0.))))
mE(122)
Σ
[[lcm- - (m)) ((0) l1(fm - (mm
=
(85)
where the last equality is due to Lemma Based on Lemma and 1//l111...0001))) S 1, we have
l1(mm (m(()) ((0.))) S (1 (m(2))lli S 50d (N + 1) 4dnL
(x))ll
(86)
And
Il(fm 1' (x:) &m (3) (2)]lw)..
< <ll(mm t'm (x)) ( /w (a,,) || L (ftm) + 11.m t' -mm()))) (mmm)
<Co(n, d),, 2(n 1 (1 50d3) Co(n, d)N -2n/d/ L 2n/d 54d [N2/d [12
SCr(n, d),, 2 2/
(87)
where the second inequality is due to
110m Il (amm) S ll (10mll>((a.1)))) I l19m [10m 11 //w (0m) ((0m) 11 [10mlllw..>000119))) I I1 I1 10mll:::: + m1 Im ((o,))
+ 110m Im (1011)))) S 1 + 50d
I $4[
50d
(88)
Therefore
Σ m
I9m ((x) (m)))) vm (2))
S (C,( d) + 50dd 2 -
11.00 ((0,)))
(89)
due to (N + 1) Adul < NN L-2n
For the second part, due Lemma 7 have
Σ
(m)( vm((x) ((0m(() V (x))
(1,21
Σ
(0m (m(()) (2).
2 (m) W (1.2)
me (1,2)
Σ
(0m(x) vm) 3(mm (20) (m
(90)
W1. (8m))
mL
Similarly with the estimation of 776.. we have that
| [0m(z)) Wm(2) - 66 v'm (x)) 11,00 (3mm)
<Ca(n, + +1)- < Cn N).- 2(n 1)/d //dd 1//-
(91)
27

---

Combining 89 and 191,, we have that there is a 01 -N & with the width (34 + d)2"n n (N
1) 1ogg (SN) and depth n2 logg (4L) such that
[I(()) o (()))lw1 S Co 2 L-2 2(n-1)/d
where Cg is the constant independent with N, L.
The method proposed in 22
23
39
38
37 may not be applied to prove Theorems These
works approximate the target function using deep neural network in the unit cube except for an arbitrarily small region S2, as per [36 Lemma 2.2]. Since || (at) can be bounded and
is independent of the size of 92, ||ʃ - + (()) can be well estimated across the entire space for E [o,+ For approximations measured the L (22) norm, [28] translates the deep neural network Ø, while [39] constructs different neural networks in the unit cube away from various negligible regions. Both methods aim to find neural networks { 1 that approximate the target function f well in different regions. They then observe that the middle value of {e: (a:) ) is close to (ax for all x² E S2 and construct the middle-value function using ReLU neural network. However, these methods may not generalized to prove the theorems presented this paper.
Neither of the methods previously proposed can be applied to the approximation measured in Sobolev space. the first method, (( depends on the length of Ω2ó, and the derivative is substantial in the negligible region, as shown in [36] Lemma 2.2]. Thus, || / (1)) will be excessively large. In the second method, median value functions can only identify the median values, not the median values of functions and their derivatives simultaneously. In this paper, we overcome this difficulty using a partition of unity. We construct a partition of unity of f2 and approximate them using ReLU DNNs denoted as { m For each om, its support set is the unit cube away from small region, and we can construct a deep neural network vim that approximates the target function f well on supp Φm- We then combine {Øm } me (1.2)4 and (1/m (1.22) obtain a deep neural network that can approximate the target function f well across the entire space. This approach resolves the issue of simultaneous approximation of both functions and their derivatives in Sobolev spaces.
7.3 Proofs of Corollaries and
7.3.1 Preliminaries
First, we list a few basic lemmas of 02 neural networks repeatedly applied in our main analysis.
Lemma 10 ((3 Lemma 3.7]). The following basic lemmas of a2 neural networks hold: (i) σi neural networks are 02 neural networks.
(ii) Any identity map in Rd can be realized exactly by o2 neural network with one hidden layer and
2d neurons.
(iil) f(x) = can be realized exactly by a a2 neural network with one hidden layer and two neurons.
(iv) f(x,y) = xy layer and four neurons.
can be realized exactly by a 02 neural network with one hidden
(v) Assume x x x "........................ x.
... sh for a E Nd. For any N, L E N+ such that NL + 2 Nj 2 |ax) there exists d2 neural network (xx) with the width 4N + 2d and depth L + [log2 N1 such that
x(x) x
for any x TR.d.
(vi) Assume P(x) -/=1 o5 for a Nd. For any N, L, N+ such that ab 2 J and (I. 2b blog, N) N 2 b maxx jayy,, there exists a 02 neural network d(x:)) with the width
4Na + 2d - and depth L such that
((x) = P(x) for any x E Idd.
Next, we define function which will be repeatly used in the proof of Corollary I in this section.
28

---

Definition 11. Define s(x) from R + [0, 10.1]6 as
2x²;
# E [0
2( - 1)2 + 1,
x E 21 x E [1.2] 22 51 x E 3
[1
1,
(())
(92)
-2(x - -2)2 +
2(x 3)
0,
Otherwise.
Figure 4: s(x) in R.
Definition 12. Given E N4, then we define two functions IR:
K
(1(x)= = Σ
(4Kx + 40), s2(x) = x 2K
(93)
1=0
Then for any m (m), m0,,,,,, ma)) E {1, we define
d 8m (x) = II
8my (Iz)
(94)
j=1
for any = (z1, x2, Iaa E Rd. Proposition 8. Given N, L.d d E N4 with NL + 2 loga NJ
> and L 2
[log2 N1, and setting
K [N1/d] [ {sm (x) me(22 defined in Definition 12 satisfies:
(i): I|sm (x) ( I 1, ||sm (x)))l:: & 8K and ||8m (2m()))ll) ((0.))) S 64K2 for
any E (1,2)4
(ii): {sm (a) m2 is a partition of the unity [0, 1]d with supp sm sm(x)) n [0, 1]d = 14m defined in Definition
For any m E (1,2]d there a 02 neural network Am (2r) with the width 16N 2d and depth 4L + 5 such as
Am (z)
II 1=1
8mg (xz) 8m (m)x)) x E [0, 1j
Proof. (i) and (ii) are proved by direct caleulation. The proof (iii) follows:
First, we architect s(x) by neural network. The is a an neural network g(x) with 3 the width and one layer such that:
x E
2 x
00
g(x)
=
2
E
1 2: +00
(95)
0,
Otherwise.
Based on (iii) in Lemma 10 g² (xx is d2 neural network with the width and two layers. Then by direct calculation, we notice that
1
s(x) 2x) 2-x + x) 2g" (2+ x) 2
(96)
29

---

which is d2 neural network with 12 the width and two layers. The g(z) defined as
LN
g(x)
Σ
(AKr 4i 4i-2) -/2
(97)
02 neural network with 12([N)/dJ) the width and two layers.
Similar with Lemma]] !
we know that
g 2/2 thy (x)
is a 02 neural network with 12([[v/d]) the width and 5 + [/L and
1
52(x)= 81 (x + 2K
1
$1 s1 9
x 8K
[0,1].
(98)
Based on (v) in Lemma 10 have there is d2 neural network Am(x)) with the width 16N + 2d and depth 4L + such as
Am (x) II 8m, (oz) 3m(x), [0,1]²
7.3.2 Proof of Corollaries 1 land] 2
The proof is comprised of three parts, which include Theorem 8 and followed by the combination of these results. Theorem to apply the Bramble-Hilben Lemma measured the norm of 22.00;
Theorem 8. Let K E N and n 2 2. Then for any f E W",,00 ((0, 1)9) with ((.1)) S and 21,2]d, there exist piece-wise polynomials function fkmm= Σ 11..a-19f.amm (x) Pm (Defimition)) 5) with the following properties:
If - fK mmmllwa.s (am))
(Am) 3 Ci(n, (ihn,d))-aa)) (n-
If fk.m momllwioo - (n, (n-1)
I1 ( S (i
(99)
Furthermore, (m))))(()) And
Pm + R. is constant function with on each Pm for E 10.
Kj4.
9f.am (x)) S C2(n, d)
(100)
for all x Im where C₁ and C2 are constants independent with K.
The proof is the same that of Theorem 6 Note that (fKmm (1,22) will be same in two theorems f E W7n.00 ((0, 1)d) in two theorem are same.
Theorem is to establish neural networks {Tm him))1 and each can approximate f well on Q.
Theorem 9. For any Wm..o ((0, 1)d) with [[/l==.><(0.11)))
1, any N. L. E N4 with N 20 NJ 2 n and L 2 [log, N1, and m = (m1, m2,.......... ma) E {1, 2]d there is a 02 neural network " with the width d+1 (N + d) (8Ng(8N) and depth 11 (T. 2) (4g. such that
[lf(x) 7m [2. Cn - 2(n 2( [lf(x)) 7/m (z) < Cio(n, d) - 2(x 11x11)// 2(n 1)/d
[lf(x) (0m))m))))>)000 Cio(n, d)N - 1 2n/d
2n/d
(101)
where C10 is the constant independent with N, L.
30

---

Proof. The proof is similar to that of Theorem 7 the difference is that and x can be architected precisely by d2 neural networks.
Without loss of the generalization, we consider the case for m. = 1,,1,.... 1). Due to Theorem and setting K [N [,
we have
Ilf fk.m. fimm.ll2...0m 11 Ci(n, (n - 2(
Ilf fk.m. 1lw 1 Ci ( (1 S - 2
IVS Sk.m. (0.111(x0mm) S Ci
Ci
2n/d
(102)
where fkm. = -Daassn-1 Js.amm (a) ) for x E Am. Note that Jf.a.m. (x) constant function for x E EI[ i 3+4;, and i ii........... ia) E (0, 10.1,.... K 13d The remaining
Kt
part is to approximate fKmm by neural networks.
The way approximate m. (œ) is same with Theorem and we have that
|1 (#2(2)) - Jm.am. (x) (w.. = 00 (#2(x)) - m,,am. (2) [/
= -10a (#2(2)) - Js,am. (2) (10m.) 22C₂(n, N 2n -2n
(103)
which is due to da (02(x)) - Jm. (x) is a step function, and the first order weak derivative is 0 Pm.
Due to (v) in Lemma 10 there a d2 neural network ( (x) with the width 4N + 2d and depth
L [log2 N] such that
s (a) x²" E Rdd there is d2 neural network de (x) with the width and depth 1 such that Φ6 v) = ry, x, y E R.
(104)
Due to (iv) in Lemma 10
(105)
Now we define the neural network Ym, (z) to approximate fk.m. (x) in Pm.
Y'a
(x)
Σ
Φ (# 05,
(106)
Jalsn-1
The remaining question is to find the error E:
:
de (o(0)()( (s,ax))) fk.m
12.00 (9mm))
Σ
1 (a((((())) 0s,a 9s.am, (x)x²" Il 1 ( (Am.)
al S
Σ
()=()=()))=
(x).m w2.2
al5n-1
Zn²
Σ
( - I..am. (x) (m))
<2n d+2 C2(, 20 2 222
(107)
At last, finish the proof by estimating the network's the width and depth, implementing Ym. (x). From Eq. (106), we know that 7m. (x) consists of the following subnetworks:
1. @ (z)) with the width 4N + 2d and depth L [logz N7.
(z) with the width 4N and depth 4L + 4.
3. de with the width 1 16n( N + 1) (8g,(8N and depth (5L + 2) log, (4L).
4. de (z, y) with the width and depth 1.
31

---

Therefore (()) is neural network with the width 28n (N + d) (8N) and depth 11m² (L 2) logz (L).
Combining Eqs. 102 and 107 we have that there is a neural network 7m, with the width 28nd+1(N) (N + d) log, (8N) and depth (1 + 2) logz(4L) (4L) such that
[x) 1'm. (a) (2 (mmm))))) (Am.) S Cio d)N 2(n-22(n2/)))--- 21/d 2(/=
2(m llf()) - t'm. (2))ll11.000 S Cno d)N -2 11/d - 2
[] t'm. (x) [z)]l (Rm.)) Cio(n, N 2n/d 2n/dd
(108)
where Ci0 = C - 2n is the constant independent with N, L.
Similarly, we can construct neural network Tm with the width 28n (N + d) l8gx(8N) and depth 1In2 + 2) logg which can approximate J' on Pm with same order of Eq. (108).
The last part to combine (AmJme(1.2)) and (mm)mm [0, 1] and obtain a 02 neural network to approximate f measured in the norm of W
Proof of Corollary ! Based on Theorem 9 there is sequence of the neural network
(7m(x) [ such that
fx 7' (2) [2. S Cio(n, -
2(n-2)) N 2(n 1)/d 2(n 1)/d
[l 7m (x) [1 S Cio(n, d)
[I)()) 7'm (2)) Cio 2
2n/4
(109)
where C1o is the constant independent with N, L. and each 7/n is neural network with the width 28n (N + d) log, (8N) and depth 11n² + 2) 1og,(4L) According to Proposition & there is a
sequence of the neural network {sm m=.,)) satisfies:
(i): mm (x) (=)01=((001)))) I 1, (3))
8K and |m (x) (am)allli. 64K for
any m E [1,2]*.
(ii): (#)(() (1,22) is partition of the unity [0, 1j with supp 8m (m: n [0. 1] = Ωm defined in Definition 5
For each 8m, is neural network with the width 16N + 2d and depth 4L + 5.
Due to (iv) in Lemma 10 there is d2 neural network d5(x)) with the width and depth 1 such that Φ6(x. ry, x, y E R.
(110)
Now we define
7xx)
Σ (e(sm())
(111)
(1,2,2)
Note that
R -=11](()-><(()))) - (==))ll===(0011))
Σ
|| [z) f(x))= - smm (
me [1,2d
= Σ
I1sm (x) f(x) sm (x) 7 (x)l
(112)
(1,2))
where the last equality is due to supp (m) n [0, 1]d = 9.
Then due chain rule, for each m (1,2)d, we have
Is (z)= f(x) sm (m) (x=) 22, (9..)
< mm (x) [1 [l 7m (x) 1 (8m)
|| sm (z) (lr.) [1f(x) - 7m (m) (1m)
+ mm (m>)) [[f(x) - Tm (Am))
+ ||sm (z) (z) 1f(xx) - 7mm 7m (x) [(mm
+ Illm (z) (.)))
[[(x) 7m
+ ||sm (2) 1lf (m))))) 1 (m0))
591C1o(n, - 22/d L 2//d
2(n
(113)
32

---

Hence
R v 2 Cio(n, d)N 2(m 2(n 2(n-2)/d 10 2(n 2)/d
At last, we finish the proof by estimating the network's width and depth, implementing (x)) From
Eq. (111), we know that (ax) consists of the following subnetworks:
1. 7m (2) with the width 28 (N + d) (8g)(8N) and depth 11n² + 2) logg (4L).
2. sm (2) with the width 16N + 2d and depth 4L + 5.
(I, y) with the width and depth 1.
Therefore (<x) is neural network with the width d (N + +d) (8g2(88) and depth 15n² 2) log, (4L).
Our method can easily extend to approximations measured by the norm of Wm..0, The primary difference in the proof lies in need to establish a differential {am ( which can be achieved by constructing architected 8m (a) as piece-wise m-degree polynomial functions. By extanding this approach,
obtain Corollary 2 using our method.
7.4 Proof of Theoren
Proof. The Theorem will be proved by contradiction. The idea of the proof is inspired by Ref.
28
Claim 1. There exist C1, C2, C3, Jo > and s, E N+ such that, for any f E Fn we have
inf l - fl (10.1))) S C2L-2(n 1//--) -- -2(nn-13/d-p $c#
(114)
for all NL 2 Jo. where
=
(ó ReLU FNNs o with the width < C.N log N and depth S CoLlog L).
The remaining question is to show Claim iis invalid.
Denote
DE = {vb : 1b D.b. क; .....,
Due to Theorem
we obtain
VCDim(D@) S C4N2L22og, L Loog N =: bu.
(115)
Now we will use Claim to estimate lower bound
b = [(NL) 2e jd
of VCDim DT). In other words, we will construct (v)(()) : (h)( e D E B) to seatter by points. B will be defined later.
First, fix = I,...,d, and there exists ÿ E O (0, 1)a such that 870 and ğ(x) 0 for
||>||2 1/3. And
find constant C3 0 such that = g/Cs Fn.d-
Denote M = [(NT) 3 z follows:
Divide [o, 1j into Md non-overlapping sub-cubes {Qo)o as
Qo = x [I1, ... xzl T E [0, x; E
0, 0, M M
; = 1,2, ... ad.
for any index vector = [0,, 02, ... 0z)² E [1,2, ... ,Mdd Denote the center of Qo by ao for all
{1, (1, dd Define
B {3 : is a map from (1,2, ... .M²" {-1,
33

---

For each / E B, we define, for any a E R
ha(x)) = Σ
M- (30)))()))
where g0(x)) = g (M (xc - 2o))
05(1,2,-,,M1
Due to |suppā())] I and [0))(())) S M - [gg|| 1, we obtain that
DD [=(()) S
for any |x] S Therefore, fa E Fn.d And it is easy check (D,hg hg B E B) scatters by
points since 20(0) and g(x) = 0 for | 2 1/3.
82;
Note that for any hg E Fa,d, there is a Φg E T such that Ca(NL) 2mn-1 -6 2 (Daha(ro)
D200( for any J3 S NL due Claim Denote J1 max There is constant
J2 such that M-*+1
Cs 2 (a(NT) 2(m-1) for J2 S NT. Define J == max [J1,
J2), J2) then for any
J NL, we have
[Dah((xoo)
M M-n+1 @g(mro)
M-n+1
Cs 2 Cs(NI)
-2n-1
-2 Diha(æro) - Di
Or;
(116)
MM D.Se (2x) and Didg (rr) have the same sign. Then (Di0g B B) shatters {xe 21,2, . M]a] since (D,hg B} shatters (wo E (1, M)3a as discussed above. Hence.
In other words, for any 8 E B and 0 E (1,2. ...
VCDim (10s 3 BB) 2 M bi
(117)
for N, I. E N with NL J.
By Eqs. 115 117 for any N, N with NL 2 J, have VCDim (fés BB)
s
VCDim D$) I b implying that
[(NL) jd S C4 L log, N
(118)
which is a contradiction for sufficiently large N, N. So we finish the proof of Theorem
Based on the proof of Theorem we can easily check that the estimation of VC-dimension of DNN derivatives (Theorem is nearly optimal and prove Corollary 3 Assume VCDim( < b, 0(N2~=L in Eq. 118) for >> 0, and bi must be larger than L(NL) Já according the construction in the proof of Theorem and Theorem Hence we still obtain a contradiction in Eq. (118). and the estimation in Theorem iis nearly optimal.
7.5 Proof of Theorem 5
7.5.1 Bounding generalization error by Rademacher complexity
Definition 13 (Rademacher complexity (3). Given sample set S (21, 22 22...., 2M} on a domain Z, and a class FF of real-valued functions defined the empirical Rademacher complexity of F in S is defined as
1
Rs(F) = ES
sup FEJ 1m1
o.f((z))
M
where EM (01, 00 distribution. i.e., P(o, +1) = P(a; = -1) = = for i= 112,..., M. For simplicity, if S (21, ,2, ,M1 an independent random variable set with the uniform distribution, denote
J are independent random variables drawn from the Rademacher
RM Rs).
The following lemma will be used bounded generalization enror by Rademacher complexities:
34

---

Lemma 11 (17), Proposition 4.11). Let F be set of functions. Then
1 M
Ex sup WEF
u(Tz) - u(() s (RM(F).
M
==1
where X == {I1, EM is an independent random variable set with the uniform distribution.
Now we can show that generalization error can be bounded by Rademacher complexities of two function sets.
Lemma 12. Let d, L,N, M E N., C2 E R4. For any f E ((0,0 with
Wl ((0.))) 1, set
② = {0: with the width S CiN log N and depth S C2L 110 110ll S B}
D$ = {vb sb D l.....d}.
(119)
We have
E(Rs( RD(()) 4(B + ()(dRM (T)) 0
sup
where E is expected responding to X, and X (x1,..., xMM is independent random variables set uniformly distributed on (0, 1)a.
Proof. For any 6(x; 0) D have
(()s(()) - (D)
M
a(f(x;) Øxx;; 0))
0(f(x) 6(x; 0)) Or.
2
dæ
M
Ory
(0.13
M
E
(f(x;) - <ba;;; 0))
1(f(x))
6(x;; 0))1 dar 0(f(x) - xxx 0)) dx J(0.)4 dz,
M
(00,3)4
1=1
1
M
a(f(x;;
p(ax;; 0))
1(B+1)
E
M
dzy
j=1
t=1
M
(B++))
Σ
(J(..) - 5(0;; /
(f(x) <(x;; 0)) dac
M
(0.1))
(D4) + R M ())
(120)
where the last inequality is due to Lemma
L
7.5.2 Bounding the Rademacher complexity and the proof of Theorem 5
In this subsection, we aim to estimate the Rademacher complexity using the covering number. We then estimate the covering number using the pseudo-dimension
Definition 14 (covering number (3). Let (V, ||=ll) be normed space, and + E V. {V1, V2...., Vn
an e-covering of if Q U Be,1 (V,). The covering number ((e, θ, ll is defined as
Wis, e II) min (n Be-covering over θ of size n).
Definition 15 (Uniform covering number (3). Suppose the F is class of functions from F to IR
Given n samples Zn (Z1,..... .......,,,)) )n) E X", define
Flz, -[(u(2))...... u(zn)) uE
The uniform covering number N, is defined as N(E,F,
max N (e,Flz.. lloc), Z,eX²
where N (E,Flz, z., |1- 11oo) denotes the e-covering number of F Flz, w.F. the Log
35

---

Then we use a lemma to estimate the Rademacher complexity using the covering number.
Lemma 13 (Dudley's ' theorem 3].. Let F be function class such that ser If S B. Then
the Rademacher complexity R. (F) satisfies that
12 Vn
B
R (F) inf
48
(o,
0SB5B
To bound the Rademacher complexity, we employ Lemma covering number. We estimate the uniform covering number by the pseudo-dimension based on the following lemma.
B which bounds it by the uniform
Lemma (3)), Let be a class of functions from X to [- B, J3B, B). For any e > O, we have
Pdim(FF
BenB (F)im(F)
((),
for n 2 Pdim(F).
The remaining problem is to bound Pdim ④) and Pdim(D0) Based on 4 Pdim(
O(L2N2 log, Logg N). For the Pdim (D)),
estimate it by Theorem
Now we can estimate generalization error based Lemma 12
Proof of Theorem 5 Let J max (Pdim Pdim( ()). Due to Lemma
14 and Theorem
for any M 2 J, we have
(DD) <48 +
12
V Vlog (x, DE M)
V M
Pdimi D+b)
12
B
2eMB (Pdim(D))
<48 +
log
de
VM
J
1/2
12B
Pdim(
B
2cMB (Pddm(DD)
<0 +
+ 12
log
de. (121)
VM
M
By the direct calculation for the integral, we have
B
2
2eMB B (Pdim(Dō)
log
de B log
ePdim (DT)
Pdim Pdiml(D@) De)) M
Then choosing 8 B
B. we have
Pdim (DD)
2eM Pdim DT)
R RM
28B
log
(122)
M
Therefore, due to Theorem there a constant C4 independent with L, N, M such as
(M s C. NT(log, Llog, N)
log M.
(123)
VM
R (3) can be estimate the similar way. Due to Lemma
12
we have that there is a constant
Cs Cs(B,, C1, C2) such that
L L log, N)
ERs(Op) (n(0p) + ERn(Os) - ERs(Os) S Cs
log M.
(124)
VM
36


Reviews:
[{"review_id": "av7sCTtoBC", "reviewer": "Reviewer_dSYn", "summary": "The main contribution of the paper are new VC dimension and pseudo-dimension bounds for derivatives of functions implemented by deep neural networks. The utility of these bounds is demonstrated by proving the tightness of approximation error bounds in the Sobolev norm for networks with ReLU and ReLU squared activations, and by giving an improved generalization bound in a similar setting.    ", "questions": "What are the important non-technical takeaways from this paper?", "limitations": "See above", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Contribution.** This is a good technical paper that improves state of the art in the theoretical studies of VC/pseudo-dimensions and approximation and generalization rates of DNNs. The focus of the paper is the setting where VC/pseudo-dimensions are estimated for model derivatives, and approximation/generalization is considered with respect to Sobolev norms. This setting is not so well-explored as the more common setting where the fitted functions are assumed to belong to a Sobolev space, but the error of fitting does not involve the derivatives. The main results claimed in the paper are new VC/pseudo-dimensions bounds. The other results are new approximation and generalization bounds. The VC/pseudo-dimension bounds naturally help to obtain the generalization bounds and show the tightness of approximation bounds. It appears that all the results established in the paper improve previous analogous results in terms of giving more accurate/tight rates. \n\n**Quality and clarity.** The paper is fairly well written. All the results are precisely stated, sketches of proofs are provided where appropriate (full proofs provided in the appendix), connections between the results are well-explained, previous work is duly mentioned.", "weaknesses": "I don't see any major issues in the paper, but my overall impression is that it is fairly technical and lacks significant new insights. Virtually all results in the paper rely very heavily on previous research, and most of them look like being assembled from ideas scattered across many previous publications. I find it hard to name new ideas that never appeared before. I would say that this paper is more suitable for a journal.\n\nI think that the claims of achievement in this paper are exaggerated. The main claim is connected with the new VC-dimension bound: \"obtaining such bounds for DNN derivatives is much more difficult\", \"DNN derivatives consist of a series of interdependent parts...rendering existing methods for estimating bounds inapplicable\". In fact, the bound for VC-dimension of derivatives given in Theorem 1 is very close to the bound for the original network function given in Theorem 7 of Bartlett et al (2019), and the proof of Theorem 1 is just a slight modification of the proof of Theorem 7 in Bartlett et al (2019). This is not surprising because the chain rule expression (13) for the derivatives of the network function is only slightly more complicated than the original function for the purpose of partitioning the parameter domain into piecewise polynomial components and estimating the degrees of the resulting polynomials, as required for the proof. The authors claim \"we propose a method to achieve nearly optimal estimations of the VC-dimension and pseudo-dimension of DNN derivatives\", but I don't see here any new method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's careful reading of our paper, as well as your positive feedback and helpful suggestions.\n\nThe problem we addressed is important and open since the nearly tight VC dimension bound of neural networks (not their derivatives) by Bartlett. Even though our analysis tools are not fundamentally new, we have addressed an open problem with wide applications in the theoretical analysis of deep neural networks. We hope that the reviewer understands that it may not be necessary to address an open problem with completely novel analysis tools. The main contributions of our research are establishing nearly optimal DNN structures in Sobolev spaces and deriving nearly optimal bounds for VC-dimension and pseudo-dimension. To the best of our knowledge, no existing work has achieved these results, despite the long-standing consideration of derivatives in DNN training, such as solving partial differential equations (PDEs) using DNNs. Our findings confirm the effectiveness of DNNs in Sobolev training and substantially improve approximation and generalization errors compared to methodologies described in the existing literature, such as those proposed by Duan et al. (2021), De Ryck and Mishra (2022), and Jiao et al. (2023). We believe that our results are of great importance and interest to the NeurIPS community. Presentation of our paper at the conference will enable the community to quickly access our findings and to use our results in their further analyses of DNN algorithms, ultimately leading to a broader impact. This aligns with the purpose of a conference paper on NeurIPS.\n  \nMoreover, to achieve our theory, there are several technical difficulties to be addressed with new ideas.\n\nFirstly, one particular difficulty arises when constructing ReLU-based DNNs in Theorem 1. In the work of Lu et al. [2021], the target functions are approximated in the trifling region, the entire domain except for a small subset, and techniques such as integration and shifting, employing a middle-value function are utilized to control the error in the small subset. However, when it comes to approximating functions in Sobolev spaces, these methods prove to be ineffective since the derivatives of DNNs tend to deteriorate in such small subset.\n\nSecondly, we agree that while there are similarities between our method and Bartlett et al. [2019] in proving the upper bound of VC-dimension for DNN derivatives, there are notable differences. Applying the chain rule necessitates considering the correlations between different parts of the DNNs, rather than treating them as independent components multiplied together. This correlation-based partitioning of parameter spaces is a specific and challenging aspect of our estimation process, setting it apart from previous approaches. The difficulties associated with this aspect also contribute to the suboptimality observed in the results of Duan et al. [2021].\n\nThirdly, our approach to proving the optimality of VC-dimension differs from Bartlett et al. [2019] (Theorem 3). The proof of optimality for DNN derivatives is not easily generalizable using their approach. Instead, we establish the optimality of VC-dimension estimation (Corollary 3) based on the DNN approximation results we derived within the Sobolev space (Theorem 3). Specifically, we demonstrate that if the degree of polynomials in the upper bounds of VC-dimension for DNN derivatives in Theorem 1 can be reduced, it becomes impossible to find DNNs that achieve the established approximation rate. This approach distinguishes it from Bartlett et al. [2019] (Theorem 3).\n\nWhile this paper primarily focuses on technical aspects, it also offers valuable non-technical insights.\n\t\t\n1. DNNs outperform traditional methods: According to Theorem 1 in our paper, DNNs with $O(N^2L\\log L(\\log N)^2)$ parameters can achieve an error rate of $O(N^{\\frac{-2(n-1)}{d}}L^{\\frac{-2(n-1)}{d}})$ when measured by the norm in $W^{1,\\infty}$, while approximating functions in $W^{n,\\infty}$ in Sobolev spaces. In comparison, traditional methods like finite elements require $O(N^2L^2)$ parameters to achieve the same approximation error. This shows that DNNs have a clear advantage over traditional methods in terms of approximation in Sobolev spaces, particularly in terms of the freedom of the depth parameter $L$. Notably, this result is not found in other papers that focus on DNN approximation in Sobolev spaces measured by Sobolev norms, such as Gühring et al. [2020] and Gühring and Raslan [2021], as their results are suboptimal.\n\n2. Replacing ReLU with squared ReLU: Although ReLU-based DNNs cannot approximate functions measured by $W^{m,\\infty}$ for $m \\geq 2$ due to their lack of smoothness, our paper suggests a solution by replacing some ReLU activations with squared ReLU activations. This modification allows for the approximation of functions measured by higher-order Sobolev norms. Furthermore, the number of squared ReLU activations required can be very few, as shown in the proof of Corollary 1.2.\n\n3. Generalization error and sample points: Based on Theorem 5, our findings indicate that learning target functions with loss functions defined by Sobolev norms does not require substantially more sample points compared to those defined by $L_2$-norms. The generalization error orders of these two types of loss functions are equivalent with respect to the width $N$ and depth $L$ of DNNs.\n\n4. Implement of solving PDEs by DNNs: Our findings serve as confirmation that DNNs are indeed capable of effectively solving partial differential equations (PDEs) within frameworks like Deep Ritz, Wasserstein GAN (WGAN), and Physics-Informed Neural Networks (PINN). Furthermore, our research contributes significant advancements by substantially improving the approximation and generalization errors presented in the methodologies in this field proposed by Duan et al. [2021], etc."}, {"review_id": "Ch2TFOaPBQ", "reviewer": "Reviewer_2REw", "summary": "The authors provide estimates on two measures of statistical complexity, the VC-dimension and the pseudo-dimension, of derivatives of deep neural networks. The estimate of the VC-dimension is shown to be optimal up to logarithmic factors. They also propose a constructive method for approximating functions in Sobolev spaces by deep neural networks. The VC-dimension bound is used to show that the obtained approximation rate is optimal as a function of the width and depth of the network. Finally, they prove a generalization bound in terms of Sobolev norm by leveraging the pseudo-dimension upper bound.", "questions": "+ Line 77: you claim that the estimate of the pseudo-dimension is nearly optimal, but I do not see a lower bound in the paper. Could you provide a lower-bound or at least an argument on how to obtain one, or otherwise change the phrasing of this sentence (and similar ones elsewhere in the paper)?\n+ Line 101: I don’t understand the \\leq sign. Shouldn’t it be an equal sign? Otherwise, I feel the argument of lines 184-187 breaks down, since \\sigma_2 networks include ReLU networks.\n+ Line 129: the dependence of the width on the dimension d is exponential. Is this expected? Do you think that you could get a matching dependence in the lower boud?\n+ Line 224 and Theorem 5: I think it would be clearer to upper bound your generalization error term by 2 sup_{\\theta} |\\Esp(R_S(\\theta)) - R_D(\\theta)|. Otherwise it is a bit confusing since, without further clarification, the expectation applies both to the estimator \\theta_S and to the random function R_S. Similarly, in the proof of Lemma 12, I don’t think that the proof is correct as it is if you apply it for \\theta_S, since \\theta_S depends on the random sample. However, it is correct if you write it for any (deterministic) \\theta, thereby getting the sup over \\theta as in the LHS of Lemma 11, which you can then apply to get the same upper bound that you get with your proof.\n", "limitations": "See weaknesses.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper is globally well-written and pleasant to read. It brings several new results regarding the statistical and approximation properties of deep neural networks in terms of Sobolev norms, which could be of broad use, in particular in the community of deep learning for PDEs. I like that most of the presented bounds have matching lower bounds. I have not checked the proofs in details, so I cannot provide evidence on their soundness, but the mathematical statements presented in the main paper are easy to understand and unambiguous.", "weaknesses": "I do not have any strong reservation, a few questions are list below. The only part of the paper that I found hard to follow is the proof of Theorem 1. I suggest that authors take advantage of the additional page to expand a bit on the proof. Perhaps a drawing would help?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We extend our heartfelt appreciation to the reviewer for your comprehensive and diligent review, invaluable feedback, positive remarks, and insightful summary. \n\nReviewer's comment: \"I do not have any strong reservation, a few questions are list below. The only part of the paper that I found hard to follow is the proof of Theorem 1. I suggest that authors take advantage of the additional page to expand a bit on the proof. Perhaps a drawing would help?\"\n\nResponse: We greatly appreciate your kind suggestions and insights. We agree that the proof of Theorem 1 in our paper is lengthy. We have found that providing a sketch of the proof can effectively convey the main ideas to a wider range of readers. The most challenging and extensive aspect lies in the refinements necessary to obtain the partitions of parameter spaces, which are crucial for our analysis. For this purpose, we have included a concise sketch of the proof in the main paper. This will allow readers to grasp the key concepts and logical flow without being overwhelmed by excessive details. We have moved the detailed proof of refinements required to obtain the partitions to the appendix, for those who desire a more thorough understanding. By adopting this approach, we hope to enhance the overall readability of our paper.\n\nReviewer's comment: \"Line 77: you claim that the estimate of the pseudo-dimension is nearly optimal, but I do not see a lower bound in the paper. Could you provide a lower-bound or at least an argument on how to obtain one, or otherwise change the phrasing of this sentence (and similar ones elsewhere in the paper)? \"\n\t\t\nResponse: We would like to express our sincere appreciation for your attentive review of our paper. We have included Corollary 4 for the lower bound of the pseudo-dimension, which demonstrates the near optimality of the pseudo-dimension estimate presented in Theorem 2.\n\t\nReviewer's comment: \"Line 101: I don’t understand the $\\leq$ sign. Shouldn’t it be an equal sign? Otherwise, I feel the argument of lines 184-187 breaks down, since $\\sigma_2$ networks include ReLU networks.\"\n\n Response:  The sign $\\leq$ is correct. We understand the concern regarding the presence of higher-order derivatives in DNNs that employ ReLU activation functions. While it is true that not all DNNs utilizing ReLU or the square of ReLU activation functions have higher-order derivatives, it is worth noting that some DNNs do have higher-order derivatives. For instance, the expression $\\sigma_2\\circ\\sigma_2\\circ (\\sigma_1(x)-\\sigma_1(-x))$ has higher-order derivatives.\n\nIn the proofs of Corollaries 1 and 2, we construct $\\sigma_2$ networks that include both ReLU and square of ReLU networks. These constructed networks are designed to approximate functions measured by $W^{m,\\infty}$ norms, which implies that they can effectively capture higher-order derivatives.\n\t\nReviewer's comment: \" Line 129: the dependence of the width on the dimension $d$ is exponential. Is this expected? Do you think that you could get a matching dependence in the lower bound? \"\n\t\nResponse: In this paper, we focus on the optimality of approximation rate with respect to width $N$ and depth $L$ of DNNs. The dimensionality $d$ is not the focus that we consider in our research. Addressing your question about mitigating the exponential dependence of width on dimensionality, we have observed that this arises from the utilization of methods like Taylor's expansion or average Taylor polynomials in our approximation techniques. It remains an open question for future research to explore alternative approaches to address the challenge of getting the dependence of $d$ in the lower bounds.\n\nReviewer's comment: \"Line 224 and Theorem 5: I think it would be clearer to upper bound your generalization error term by $2 \\sup_{\\theta} |E(R_S(\\theta)) - R_D(\\theta)|$. Otherwise it is a bit confusing since, without further clarification, the expectation applies both to the estimator $\\theta_S$ and to the random function $R_S$. Similarly, in the proof of Lemma 12, I don’t think that the proof is correct as it is if you apply it for $\\theta_S$, since $\\theta_S$ depends on the random sample. However, it is correct if you write it for any (deterministic) $\\theta$, thereby getting the sup over $\\theta$ as in the LHS of Lemma 11, which you can then apply to get the same upper bound that you get with your proof. \"\n\t\nResponse: Thank you for your feedback. Following the suggestion, we have revised Theorem 5 and Lemma 12 to ensure clarity and avoid confusion."}, {"review_id": "TmzZ8fDNTk", "reviewer": "Reviewer_MY91", "summary": "This paper facilitates the understandings of Sobolev training and performances of DNNs in Sobolev spaces by providing the near optimal VC-dimension and pseudo-dimension of DNN derivatives. ", "questions": "1.\tTo my knowledge, VC-dimension and Pseudo-dimension are essentially same notion. (Reference [4].) I am wondering why the results in Theorem 1 and Theorem 2 are surprising in a sense that they have the same bound. Is there any intuitive reason on why it is non-trivial to expect they should be same for the DNN derivatives?  \\\\\n2.\tWhat is the meaning of approximating functions in $W^{n, \\infty}([0,1]^{d})$ with Sobolev norm $W^{1,\\infty}([0,1]^{d})$? Why this is interesting?  \\\\\n3.\tHow do we know the bound is optimal? To my knowledge, we commonly refer that we have an optimal bound when we have the matching orders of lower bound and upper bounds. But the author only provides the upper bounds in the paper. \n", "limitations": "This work has no negative societal impact.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Technically, they improve the bounds on VC and pseudo-dimensions of DNN derivatives in reference [10]. ", "weaknesses": "Though I think the theoretical contributions of this paper is great, but in terms of readability of the paper, there are some rooms for the improvements. \\\\\nFirst, this paper assumes that the readers are very familiar with the notions of Sobolev training. In my opinion, authors should defer some technical proofs in the appendix, and introduce the notion briefly in the main paper, and motivate readers why the Sobolev training is interesting problem to consider. \\\\\nSecond, some notations should be introduced first, before being stated. I realized the Sobolev Spaces $W^{n,\\infty}([0,1]^{d})$ first appeared in line 59, then introduced in line 114, formally.\\\\\nThird, some sentences are repeated quite often. For instance, line numbers 125-127 are same with line numbers 167-169.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our gratitude to the reviewer for your thorough review and positive feedback. We would like to clarify that our contribution is not limited to improving the bounds on VC and pseudo-dimensions of DNN derivatives. Beyond that, our contributions also include: 1) establishes DNNs as effective approximators of functions in Sobolev spaces through the use of Sobolev norms, resulting in lower error rates compared to previous works. 2) demonstrate the optimality of our approach through the estimation of VC-dimension. 3) utilize pseudo-dimension to obtain the generalization error of Sobolev training in supervised learning of DNNs. All are novel results not found in other works.\n  \t\nReviewer's comment:\" Though I think the theoretical contributions of this paper is great, but in terms of readability of the paper, there are some rooms for the improvements. First, this paper assumes that the readers are very familiar with the notions of Sobolev training. In my opinion, authors should defer some technical proofs in the appendix, and introduce the notion briefly in the main paper, and motivate readers why the Sobolev training is interesting problem to consider. Second, some notations should be introduced first, before being stated. I realized the Sobolev Spaces $W^{n,\\infty}([0,1]^d)$ \n first appeared in line 59, then introduced in line 114, formally.Third, some sentences are repeated quite often. For instance, line numbers 125-127 are same with line numbers 167-169. \"\n \nResponse: Thank you for your valuable suggestions! Based on your input, we have moved the complete proofs of Theorems 1 and 2 in the appendix, while providing proof sketches in Section 5. Furthermore, we have enriched the introductions by including additional references and discussing the significance of Sobolev training. We have also added a befily review of a specific task focused on solving partial differential equations to provide a practical context for the application of Sobolev training.\n\nSecondly, we have included the definitions of Sobolev spaces in the introduction section to enhance readability. Finally, we have also removed the duplicated parts. Thanks for your help and suggestions again!\n\t\nReviewer's comment: \"To my knowledge, VC-dimension and Pseudo-dimension are essentially same notion. (Reference [4].) I am wondering why the results in Theorem 1 and Theorem 2 are surprising in a sense that they have the same bound. Is there any intuitive reason on why it is non-trivial to expect they should be same for the DNN derivatives?\"\n\t\nResponse:  Please note that the claim in the arXiv version of Bartlett et al. [2019], stating that the VC-dimension and pseudo-dimension of DNNs are the same, dose not always hold. The authors correct this claim in the published form in Journal of Machine Learning Research (See the reference of their paper in our reference list). Roughly speaking,  the pseudo-dimension can be bounded by the VC-dimension of a larger set. The most challenging aspect of our work revolved around proving the VC-dimension of DNN derivatives. The introduction of the pseudo-dimension was necessary because the VC-dimension alone is insufficient for obtaining a generalization error estimate. We rely on the notion of pseudo-dimension to achieve this.\n \nSecondly, we were not surprised to find that the order of the VC-dimension and pseudo-dimension are the same. What surprised us is the order of VC-dimension between DNNs and their derivatives are same, considering the differences in the complexity of their respective structures. \n\nReviewer's comment:\" What is the meaning of approximating functions in $W^{n,\\infty}$ with Sobolev norm $W^{1,\\infty}$? Why this is interesting? \"\n\t\nResponse: When utilizing ReLU-based DNNs to approximate functions in the Sobolev space $W^{n,\\infty}$, the goal is to capture both the magnitude and derivative of the functions.  This is the essence of approximating functions in $W^{n,\\infty}$ with the Sobolev norm $W^{1,\\infty}$. Although it is desired to consider approximating functions in $W^{n,\\infty}$ with Sobolev norms $W^{m,\\infty}$ for $m\\geq2$, one has to recognize that ReLU DNNs lack higher-order derivatives, making them impossible to approximate functions in Sobolev norms $W^{m,\\infty}$ with $m\\geq2$. As a result, when employing ReLU DNNs, the primary focus is on approximations measured within the $W^{1,\\infty}$ framework e.g. Gühring et al. [2020].\n\nThe consideration of approximating functions in $W^{n,\\infty}$ with the Sobolev norm $W^{1,\\infty}$ sufficiently explains the success of DNNs in Sobolev training, particularly when dealing with loss functions that only involve first-order derivatives of both the DNNs and the target functions, as mentioned in the introduction, such as solving second-order partial differential equations (PDEs) in a weak sense and penalizing function gradients in the loss functions to control the Lipschitz constant of DNNs. Therefore, this scenario is both valuable and interesting.\n\nReviewer's comment:\" How do we know the bound is optimal? To my knowledge, we commonly refer that we have an optimal bound when we have the matching orders of lower bound and upper bounds. But the author only provides the upper bounds in the paper. \"\n\t\nResponse: The paper's Corollaries 3 and 4 provide lower bounds for the VC-dimension and Pseudo-dimension, respectively. These lower bounds are proven to be on the order of $O(N^{2-\\epsilon}L^{2-\\epsilon})$ for any small $\\epsilon>0$. The upper bounds in Theorems 1 and 2 are $O(N^2L^2\\log_2 N\\log _2L$). This means that the paper's results are considered nearly optimal because the order of polynomials in the upper bounds cannot be further reduced without contradicting Corollaries 3 and 4. Note that there still exists a small gap between the upper bound and the lower bound, which is the meaning of nearly optimal,"}, {"review_id": "XoOlJwb50K", "reviewer": "Reviewer_vGRi", "summary": "The paper proposed a method to estimate the Vapnik-Chervonenkis (VC) dimension and pseudo-dimension of deep neural network (DNN) derivatives with the ReLU activation function, which have important applications such as characterizing the generalization error of machine learning methods and establishing the optimal approximation of DNNs in Sobolev spaces.\n\nThe authors provided theoretical analysis and proofs for their proposed method, which fills a gap in learning error estimations for many physics-informed machine learning models and applications, including solving partial differential equations, operator learning, network compression, and regularization.\n\nAnother contribution of the paper is the demonstration of how DNNs can be used to approximate functions in Sobolev spaces using ReLU activation functions in a deep feedforward neural network architecture, with a nearly-optimal approximation rate.\n\nOverall, the study provides a framework for analyzing and optimizing DNNs for different applications while taking into account mathematical concepts such as VC-dimension and pseudo-dimension.", "questions": "1. Pseudo dimension is a more general concept than VC dimension,  while the bounds in Theorem 1 and Theorem 2 seems similar to each other except two constants $\\hat{C}$ and $\\overline{C}$, is there any relationship between  $\\hat{C}$ and $\\overline{C}$ ?\n\n2. Are those results in this paper holds only for ReLU networks?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The topic of the paper is highly relevant to the field of deep learning and offers an interesting approach to estimate VC-dimension and pseudo-dimension of derivatives of deep neural networks.\n* The paper is well-written and clearly presents the mathematical language and definitions used in the study. The proofs provided are detailed and structured in a logical manner.\n* The paper presents two important theorems that provide a solution to the approximation rate problem of DNNs in Sobolev spaces and the degree of generalization error in loss functions involving derivatives of DNNs.\n* The proposed approach has the potential to be applied in different areas of physics-informed machine learning such as solving partial differential equations, operator learning, and generative models.", "weaknesses": "- Some aspects of the paper could be clearer and more thoroughly explained. The introduction, for instance, could better demonstrate the main contribution of the paper and provide a more detailed overview of the state-of-the-art and the limitations of existing research.\n\n- The section on references could be more comprehensive, covering more related studies and presenting a more thorough overview of the existing literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for your thorough and diligent review, helpful feedback, positive remarks, and insightful summary.\n\nReviewer's comment: \" Some aspects of the paper could be clearer and more thoroughly explained. The introduction, for instance, could better demonstrate the main contribution of the paper and provide a more detailed overview of the state-of-the-art and the limitations of existing research.\"\n\t\nResponse: Thanks for providing kindly suggestions. In the introduction (Page 2), we add a more comprehensive discussion of the state-of-the-art and the limitations of existing research on the VC-dimension and pseudo-dimension of DNNs. We observe that most existing research in this area does not consider the derivatives of DNNs, which are crucial in the error analysis of Sobolev training. Furthermore, we note that a recent study by Duan et al. [2021] analyzed the VC-dimension and pseudo-dimension of DNN derivatives, but their results were suboptimal due to a lack of consideration for the relationships between the multiplied terms in a DNN derivative. As a result, their findings cannot be used to determine the optimal approximation error of DNNs in Sobolev training, and may only provide a generalization error that is much larger than the actual error that may arise from Sobolev training. \n\t\nReviewer's comment: \" The section on references could be more comprehensive, covering more related studies and presenting a more thorough overview of the existing literature. \"\n\t\t\n\t\t\n\t\t\nResponse: We appreciate your feedback and have made additional revisions to the introduction and references. Specifically, we have added more references on Sobolev training and the estimation of VC-dimension and pseudo-dimension to the introduction and references sections. \n\t\n\n\nReviewer's comment: \" Pseudo-dimension is a more general concept than VC dimension, while the bounds in Theorem 1 and Theorem 2 seems similar to each other except two constants $\\bar{C}$ and $\\hat{C}$, is there any relationship between them?\"\n\nResponse: Yes. As you can see in the proof of Theorem 2, we establish that $$\\bar{C}(N+1)^2(L+1)^2\\log_2 (L+1)\\log_2 (N+1)\\le 64\\bar{C}N^2L^2\\log_2 L\\log_2 N.$$ Since the pseudo-dimension of derivatives of DNNs with $N$ width and $L$ depth can be controlled by the VC-dimension of derivatives of DNNs with $N+1$ width and $L+1$ depth. Therefore, we conclude that $64\\bar{C}\\ge\\hat{C}$. We add this discussion after the proof of Theorem 2 in appendix.\t\n\t\nReviewer's comment: \" Are those results in this paper holds only for ReLU networks?\"\n\t\t\nResponse: We do not only consider ReLU networks. In Corollaries 1 and 2, we present the approximation results of DNNs with ReLU and square of ReLU activation functions, respectively. Unlike piece-wise polynomial activation functions such as ReLU and square of ReLU, developing the method based on this paper for DNNs with other activation functions can be challenging. Especially, difficulties arise from not only building DNNs that can approximate functions in Sobolev spaces but also estimating the VC-dimension of these DNNs. This is an interesting question that requires further exploration, and we refer to it as an area for future research."}]

Author rebuttal:
We would like to express our gratitude for all the reviewers' valuable suggestions and careful reading. Based on your advice, we have made several improvements to our paper. Additionally, we have added an example for solving Partial Differential Equations by DNNs with Sobolev training in the introduction section, as well as a corollary discussing lower bounds of pseudo-dimension. We have provided further details in the attached file.

Meta-review: This paper presents novel theoretical results bounding the VC/pseudo-dimensions and approximation/generalization properties of derivatives of deep neural networks. The technical contributions improve upon prior work and fill an important gap in the theoretical deep learning literature.

The reviewers agree that the core theoretical results are solid and represent meaningful advances to the state of the art. While constructive feedback is offered to further strengthen the manuscript, the reviewers concur that the central contributions warrant acceptance.

In particular, the proofs of the main VC/dimension and approximation/generalization rate bounds are viewed as technically strong. These theoretical findings can enable progress in diverse applications including physics-informed deep learning.

I recommend accepting this paper based on its significant theoretical contributions. The authors should address the constructive feedback through revisions that expand the framing, provide more intuition, consolidate repetition, and further situate the work in the literature. These revisions will help broaden the impact of this theoretically grounded work.
Decision: Accept (poster)