Approximation and non-parametric estimation of functions over high-dimensional spheres via deep ReLU networks
Authors: Namjoon Suh
Tian-Yi Zhou
Xiaoming Huo
Venue: ICLR 2023 poster (2023)
Keywords: Approximation Theory
Non-parametric regression
Asymptotic
Deep ReLU Neural networks
High-dimensional sphere

Abstract: We develop a new approximation and estimation analysis of deep feed-forward neural networks (FNNs) with the Rectified Linear Unit (ReLU) activation. The functions of interests for the approximation and estimation are assumed to be from Sobolev spaces defined over the $d$-dimensional unit sphere with smoothness index $r>0$. In the regime where $r$ is in the constant order (i.e., $r=\mathcal{O}(1)$), it is shown that at most $d^d$ active parameters are required for getting $d^{-C}$ approximation rate for some constant $C>0$. In contrast, in the regime where the index $r$ grows in the order of $d$ (i.e., $r=\mathcal{O}(d)$) asymptotically, we prove the approximation error decays in the rate $d^{-d^{\beta}}$ with $0<\beta<1$ up to some constant factor independent of $d$. The required number of active parameters in the networks for the approximation increases polynomially in $d$ as $d\rightarrow{\infty}$. In addition to this, it is shown that bound on the excess risk has a $d^d$ factor, when $r=\mathcal{O}(1)$, whereas it has $d^{\mathcal{O}(1)}$ factor, when $r=\mathcal{O}(d)$. We emphasize our findings by making comparisons to the results on approximation and estimation errors of deep ReLU FNN when functions are from Sobolev spaces defined over $d$-dimensional cube. Here, we show that with the current state-of-the-art result, $d^{d}$ factor remain both in the approximation and estimation error, regardless of the order of $r$. 

Published as a conference paper at ICLR 2023
APPROXIMATION AND NON-PARAMETRIC ESTIMATION OF FUNCTIONS OVER HIGH-DIMENSIONAL SPHERES
VIA DEEP RELU NETWORKS
Namjoon Suh, Tian-Y Yi Zhou, Xiaoming Huo
H.Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology, Atlanta, GA, USA (namjsuh, tzhou306, hus.@gatech.ccomm
ABSTRACT
We develop new approximation and statistical estimation analysis of deep feed- forward neural networks (FNNs) with the Rectified Linear Unit (ReLU) activation. The functions of interests for the approximation and estimation are assumed to be from Sobolev spaces defined over the d-dimensional unit sphere with smoothness index > 0. In the regime where is of the constant order (i.e., is shown that at most d' active parameters are required for getting d d-C approxi- mation rate for some constant C O. In the regime where the index grows in ((d) asymptotically, we prove the approximation error
O())), it
the order of d (i.e., decays in the rate d with 0 < < 1 up to some constant factor independent of d. The required number of active parameters in the networks for the approx- imation increases polynomially in d d oc. It is also shown that bound the excess risk has d' factor, when ((1), whereas it has d()) factor, when r = (d). We emphasize our findings by making comparisons to the results on the approximation and estimation errors of deep ReLU FNN when functions are from Sobolev spaces defined over d-dimensional cube. In this case, we show that with the current sate-of-the-an result, dd factor remain both in the approximation and estimation errors, regardless of the order r.
INTRODUCTION
Neural networks have demonstrated tremendous success in the tasks of image classification (Krizhevsky al., 2012 Long et al., 2015). pattern recognition (Silver al.) 2016). natural lan- guage processing (Graves et al. 2013 Bahdanau et al., 2013 Young et al. 2018). etc. The datasets used in these real world applications frequently lie high- nigh-dimensional spaces Wainwright 2019).
In this paper, we try to understand the fundamental limits of neural networks in the high-dimensional regime through the lens of its approximation power and its generalization error.
Both approximation power and generalization error of neural network can be analyzed through specifying the target function's property such as its smoothness index r >> and its input space X. In particular, deep feed-forward neural networks (FNNs) with Rectified Linear Units (ReLU) have been extensively studied when they are used for approximating and estimating functions from general function class such Sobolev class defined on d-dimensional cube (i.c., X' := C²)) de- noted as (Cd) for 1 S < 00. However, in practice, signals on a spherical surface (i.e., X = 84-1 (x E Rdd |x||| 1)) rather than on Fuclidean spaces often arise in various fields, such as astrophysics (Starek et al. [2006] WWaux et al. 2005), computer vision (Brechbühler et al.) 1995), and medical imaging YY et al., (007).
Motivated by this, we focus our attention on the cases where deep ReLU FNNs are used for function approximators and estimators, when functions are assumed to be from the Sobolev spaces defined over dd that is f E (S*- Under this setting, our analysis focuses on how the input di- mension d explicitly affects the approximation and estimation rates of f W (S )). At the same time, we show how the scalability of deep ReLU FNNs grows in the high-dimensional regime. Here, the scalability is mainly measured through the three metrics: (1) the width denoted W.

---

Published as a conference paper at ICLR 2023
Theorem
Theorem 4.4
Function class
W (S
Wx (10, 1
Smoothness r
((d)
(1)
Vr > 0
Upper-bound N
(nnd)
(nd)
O((++r))
Estimation error rate
Odd
d' *5.3
Ō((d r)
Table 1: Here, C > 0 is an universal constant, Notation O(.) hide the logarithmic factor in n. Note
that the upper-hounds for N in Theorem 4.3 (i.e., (Md)) from Theorem 3.1 with choices M
3d
(2) the depth, denoted L, and (3) the number active parameters, denoted as N of the net- work, (Anthony & Bartleti 1999). It should be emphasized that we find there exists an interaction with smoothness index 0 and dimension whereas we cannot find one for the case when E W (C4). We further summarize our detailed findings in the following Subsection.
1.1 PAPER ROAD MAP AND CONTRIBUTIONS
we provide an approximation bound of deep ReLU FNN (i.e., î) for approximat- ing the target functions in Sobolev spaces defined over sphere (i.e., f W ())- Notably, in the bound, we track the explicit dependence on data dimension d allowing it tends to infinity. This tracking enables how the three components of network architecture, width (W), depth (L), and the number of active parameters (N), should change as d increases, for obtaining the good approximation eтrоr rate.
In Theorem 3.1
As Corollary of Theorem 3.1 we show how the order of function smoothness r can have the effect on the scale of network in terms of d. Specifically, when the function smoothness show that the constructed network, f, requires W = O(d)),
(()), we Od logz d) for 0 < < 1, and N = ( (dd+1) for obtaining d d1)) approximation error up to some constant factors independent with d. Furthermore, when
(d), show that only W Old)), L O(d log2 d), and at most N (dd) are required for obtaining the sharp approximation rate O(d d') for 0 a, 1. See Corollary 3.3 for the detailed statement of the result.
Our result implies that for approximating f W (Sd-1), the larger the smoothness index is, the narrower the width of the network should be enough, while the depth of the network can be fixed. Moreover, when r is in the same order as d, the network can avoid the curse of dimension- ality requiring only (dd²) number of active parameters. It is interesting to note that the function smoothness index can affect the design of the network, specifically on width, while it has little effect (dd) is restrictive in sense that it makes
on the design of depth. Admittedly, the condition the function space W (8d-1) small. Nonetheless, it contains some interesting examples: that is, reproducing kernel Hilbert spaces (RKHS) generated by O kernels such Gaussian kernels.
Additionally, to the best of our knowledge, this finding not observed in the current approximation theory of neural network literature when W (Cd) where Cdl denotes some d-dimensional cubes, and f is a deep ReLU FNN. Out of the long list of literature to be introduced shortly, we choose the result from SSchiidt-Hicbbe (2020) for the comparison as it also has the explicit dependence on in their approximation bound. From their result, can be seen that the curse cannot be avoided, even when = (d). The width of their constructed network is lower bounded by 2(r V ed) and the number of active parameters is upper-bounded by O(r + d)d). Note that the bounds on both components grow exponentially in d as increases. See Subsection for detailed comparisons.
We further make the comparisons between estimating functions f W (Theorems 4.3) versus ʃ E Wr (Cd) (Theorems 4.4 via deep ReLU FNNs under the non-parametric regression framework. Given n noisy samples, the two Theorems suggest the specific orders of W, L and N in terms of n, d and for which they give the tightest bound excess risk of respective function estimator from Proposition 4.2 When r = O(1), it is shown that the excess risk upper- upper-bounds bounds of
Interested readers find the intuitive technical reason for having the exponential dependence in d on width W and active parameters N in the Appendix
2

---

Published as a conference paper at ICLR 2023
both function estimators have d' in the constant factors. In contrast, when (d)), estimating functions f ( (S4-1) has at most dd(1) factor in the bound. whereas the bound for function estimator of f E W (Cd) has d'. See Table and Subsection 4.2 for detailed comparisons.
1.2 RELATED WORKS
In this Subsection, aid readers have more clear understanding on the contributions of our paper, we provide the list of relevant works with comparisons of how these works are different from ours.
Approximation of f E W (5"-1) via deep CNN. For the approximation theory of Wx (S8-1), we must refer readers Fang et al. (2020) and Feng et al. (2021). But in their works, the convolutional neural network (CNN) is used for the function approximator under fixed setting.
Approximation of f E W (C via deep ReLU FNN. Approximation theory of deep ReLU FNN for functions f W (C4) has lengthy history in the literature. Representatively, Mhaskar 1996) showed that f can be approximated uniformly within s-approximation accuracy with a 1-layer neural network of (cr-d/r) neurons and an infinitely differentiable activation function. Later, for deep y
ReLU networks, Yarotsky (2017) showed that the number of active parameters (N) in networks is bounded by O(E-d/" log (e)) and the depth has the order (log( He further proved that / lower-bounded by the order O(e which is backed up by the result in Vore et al. 1989). For f E Wy(C') with 1 S p I oo, Petersen & Voigtlaender (2018) showed that there exists a deep ReLU network with bounded and quantized weight parameters, with O( network size, and with e-independent depth for achieving the E-accuracy in the Lp norm. For approximating functions I E W (C4), SccmidttHHebber (2020) proved that network of size O(--//r) with bounded weight parameters achieves e-approximation error the Lox norm.
Function spaces with special structures. The result of Yarotsky (017) implies that deep ReLU
net cannot escape the curse of dimensionality for approximating f E Wx (C*). Many papers have demonstrated that the effects of dimension can be either avoided or lessened by considering function spaces different from Sobolev spaces, but defined over Cd. Just to name few, MMhssar et al. (2016) studied that function with a compositional structure with regularity can be approximated by neural network with O(e-2/1 neurons within accuracy. [Suzuki (2018) proved the deep ReLU network with O(e-1/r) neurons can avoid the curse for approximating functions in mixed smooth Besov spaces. Chen et al. (2019) showed the network size scales as (s--D/r) for approximating C" functions, when they are defined on a Riemannian manifold isometrically embedded in ERd with manifold dimension D with D < d. Montanelli & Du (2019) and Blanchard & Bennouna (2022) showed respectively the deep and shallow ReLU network break the curse for Korobov spaces.
Estimation rates of excess risk under non-parametric framework. Many researchers also have tried to tackle how the neural networks avoid the curse by considering specially designed function spaces under the non-parametric regression framework. We only provide an incomplete list of them. Such structures include additive ridge functions (Fang & Cheng 2023), composite function spaces with hierarchical structures (Schmidt-Hieber 2020; Han et al. 22022), mixed-Besov spaces (Suzuki 2018 Hölder spaces defined over a diven-iimeniionll manifold embedded in R2 (Chen et al, 2022). They all showed the function estimators with neural network architectures can lessen the curse by showing the excess risks of the estimators
bounded by O(n (+2=2(()r+D)),,, where denotes the size of a noisy dataset, and D' & d is an intrinsic dimension uniquely determined through the characteristics of function spaces, when they are compared with the minimax risk On (22//((2+))) (Donoho& & Johnstone 1998) for f E W&,C"
Comparisons. The aforementioned works mainly focused on the approximation and estimation of functions defined on Cd. not sd-1, for the fixed d. Moreover, the introduced papers on approxi- mation theory, except the work of efSchmidt-HHeber (2020), hide the dependence on d in the Big-O notation of N in e-accuracy, even for papers where they consider the function spaces with special structures. Thus, it is not clear how the d affects the approximation bound and the scale of the pro- vided network architecture. Introduced papers estimation rate for excess risk also follow the same philosophy with papers on approximation theory, as they work on the fixed d setting. In contrast, we work the Sd-1 input space, track the explicit dependence d in the error bound, and describe
3

---

Published as a conference paper at ICLR 2023
how d affects the scale of deep ReLU FNN as d - with its interactions with function smoothness r > O. Our paper focuses on tracking the dependence on d in the constant factor hidden in the Big- O notations both in approximation and estimation enror rates, rather than paying attentions to reducing the exponential dependence of with base & N or with base n in excess risk bound.
PRELIMINARY DEFINITIONS
In this Section, we provide the mathematical definitions of deep ReLUU FNN and Sobolev function spaces on unit sphere.
2.1 DEFINITION OF DEEP RELU NETWORK
For defining the deep ReLU network mathematically, we adopt the notation used in Schmidt--iebbe 2020). F (Vi....., Vr) R", let ov R + R' be the shifted ReLU (Rectified Linear Units) activation function as F. (1 yr) ,,)) = o ((y1 V......, yr v,) where a(x) = (az 0).
With this notation, the network architecture (L, p) consists of a positive integer L, called the number of hidden layers, and a width vector p == (Po..... PL+1) E N A deep ReLU network with architecture (L, p) considered in this work is then any function of the form
(1) where W. 1P--1XP weight matrix with Po d. PL+1 and v, R shift vector. Network functions are built by alternating matrix-vector multiplications with the action of the nonlinear activation function Ø.
f: S: +R. R. x x f(x) = WL W WL-10v Ov. Wix.
Let | lloo and lo be the number of nonzero entries of W; and v, in the jth hidden layer. The final form neural network we consider in this paper is given by
F(L.P.A) = {i of the form
W + lyslo 1 SN
(2)
==1
The main advantage of using this notation comes from its convenience for tracking the construction process of network f for approximating f E W (S--1). See Section D.2 in the Appendix. Now, we define the Sobolev spaces over the sphere in the next Subsection.
2.2 DEFINITION OF SOBOLEV SPACES OVER SPHERE
For S p S co, we denote (y( C,(S8-1, ,x)) as the C--function space de- fined with respect to the normalized Lebesgue measure px on Sd-1, with norm ||g|| = (Jsa-1
Let Hi be the space of homogeneous harmonic polynomials of total degree E 24 restricted on sd-1 Rd In Dai Xu (2013): Efthimiou & Frye 2014), its dimension for le E N is found be
Nkk d) = 2k 2 /k + +d3
(3)
k-
Note that (2(8d-1) is a Hilbert space with inner product (f.g) c2(0-11) := Ss--1 f(x)g(x)))x))))) (x) for f.g E C2( The spaces Hd. for & E Z4, of spherical harmonics are mutually orthogonal with respect to the inner product of (Sd--))).
Since the space of spherical polynomials is dense in L2(Sdt1), every I (2(8a-1) has spherical harmonic expansion f Ex (f) Ex ((k.d) fr. Yx, converging in the (2( norm. Hereafter, (Yx.) ((k.d) denotes an orthonormal basis of H.g. Fr.e is the SsL. f(x) (x)x(())xxx(s
Fourier coefficients of f given by Fr.e (n1)) and Proj (f) denotes the orthogonal projection of (2(St-1) onto Hg. which has an integral Zx
representation (f) (((k,d Yx,(()) Vx.y Sd-1
Vx Sd-1, where Zx(x,
4

---

Published as a conference paper at ICLR 2023
We know that Zx(X, y) is reproducing kernel of Hgg independent of the choice of &Y ((k.d)
8=1
and with Àg - (x. N4 ght ((x, y)), Vx,y S where gh is the Gegenbauer
Ao
polynomial of degree & with parameter A > 2 see for instance Dai & Xu (011)). Denote
= y), the exact expression of gh (u) is given in terms of the Gamma function by
(u) - (-1) T(k 1 e+ Ao) T(AG)el(k - 26)! (2u)*
(4)
The space of Hg of spherical harmonics can also be characterized as eigenfunction spaces of the Laplace-Beltran Beltramm operator A on Sd-1, Indeed, Ht = { (² Ag-. = =>xff
where A = k(k + 2) and (S denotes the space of all twice continuously differentiable functions on 5a-1. In fact, with the identity operator I, we may define the fractional power of Aa- 1 + I) of the operator -se--- + I) in a distributional sense for a E R: Projj (( A + Z)
+ )τ) "Proju (f). Now, we define the Sobolev space W, WF$$t11) to be the subspace of (8 for p 00, with the finite norm
f) f)
|| 1 +II
(-As0
r/2
|l 11/1111(0-11
) )
f
<
(S)
In this paper, we consider the case p do (i.e., I E WT. (S4-1)), which is essentially the Hölder space. The sphere $0-1 is smooth Riemannian manifold without boundary. Its nice Laplace- Beltrami operator (i.c.,Ass 1) acting as Hessian operator of functions on the sphere gives the natural definition of Sobolev spaces W ( (Sd-1) in (5): that is, the Sobolev space is collection of continuous functions defined on sphere gd-1 whose generalized (distributional) derivatives up to order r are essentially bounded. See Equations (16) Hesse (2006). (3.4) in Fang et al. (2020), (16) in Feng et al. (2021), (5.1.9) in Freeden et al. (1998) for more detailed treatments on W (S
Readers can also refer the definition of (C in the Appendix A when Cd [0, 1]d, for compar-
ison with W (8d-1) and later use in Subsection 3.1
3 APPROXIMATION ERROR
Now, we present our Theorem on approximating functions f E Wo via F(L. in
Theorem 3.1 < a < 1,m, WT. (S with
with S S do 1. For any function f O, there exists network
M N,M
E (d, 22.M,...... N.NM,...,22,MMD... 22NM,
(6)
with depth I, = (m + 4) [2N) and number of parameters N & M(2d + 404N (m + 3) +
2N + 4) + such that
| - il s C [Ifllw X
N
24 2
(2N + 1) 3d-4r:
max N-
dNN (log (1og) (2N
22mmm
(7)
VM
where C", is a constant dependent on 7,, and independent on d,r, N.M f.
The proof of Theorem 3.1 is lengthy and technical. We provide detailed proof ideas with technical remarks for the Lemmas and Proposition used for the proof of Theorem 3.1 in the Appendix D The detailed technical proofs of those Lemmas and Proposition for conciseness, we provide some important remarks on the Theorem and a simple proof sketch, which starts with a simple triangle inequality:
provided in the Appendix E Here,
s -11--L(0 LN + || - Ex 1x + 17
(8)
5

---

Published as a conference paper at ICLR 2023
Three error terms in correspond to the bounds on three terms of the right-hand side in the inequal- ity (8). We want emphasize that the constant C, > 0 in independent of d. Furthermore, track how the bound is explicitly dependent on allowing it to tend to infinity.
For first term, note that any E W (5 is approximated by weighted sum of Proje(f) (f) for 0 S k S 2N, denoted as L (f). The corresponding approximation error is small for large enough N and r. Here, importantly, we set the N [d for 0 < 1, that the input dimension d grows faster than N.
For the second term, notice that the definition of TaN (f') is involved with the integral over the sphere, and the key for approximating the function is to discretize this integral by M random samples y (yI,.... YMJ independently drawn from px. The discretized version of LN (f) is denoted as (f). As observed in the error bound, the higher degree N the LN has, the more sampled ameliorated as r increases. A
points M the approximation requires. However, the requirement similar effect can be observed in the constant factor in d. For the fixed smoothness index r, the higher the data dimension d is, the more the sampled point is required for good approximation, but the requirement is alleviated the smoothness index increases. If r increases up to order d, the factor decays exponentially fast as d + oc, eventually letting M 2 1 to be any integer. This phenomenon is further investigated in the Corollary 3.3
The last term corresponds to the error of the neural network f approximating a For any point x 5 the evaluated function value D (f) is simply a weighted average of Ev,r (xx y:)), for the sampled y (y1,..., YMM). Here, (x. y:)) is linear combination of g (xx, y.)) in ( for 0 S & S 2.V. Thus, it is the sum of univariate polynomials of degree up to 2N. We construct sub-networks approximating Év.-((x, y)) for each [M]. This explains the width of f is proportional to N N. The corresponding error bound is dependent on deN, where comes from the applications of Stirling's s formula on the coefficient factors in G. ((x, y.)). The er- & for 0 S S 2NV via neural networks. The larger the m is, the deeper the network becomes as (m). and the error gets smaller.
ror, loga (2.))) 22 2-mm, comes from approximating (x, );
3.1 COMPARISON WITH SCHMIDT-HIBBER 2020)
In this Subsection, compare the result from Theorem 3.1 with the result from Schmidt-Hieber 2020), where they consider the approximation of f E WT. (10,1)4) via deep ReLU FNN. The Theorem is stated follows:
Theorem 3.2 [Theorem 5 of Schmidt- Hieber [0200]] For any function f W ([0,1]9) 11t) and let
K3 be the radius of Hölder ball. Then, for any integers m 2 1 and 2 (r+1)) d (K + +1)e", there exists network
jH E W (L, [r]]N* ..... 6(d TrINN 1),
(9)
with depth L = 8 (m+ +1+ [ogg(d and the number of parameters NH S 141(1+d+
N N (m + 6). such that
r Fー
+
+ (N3
(10)
To avoid the confusion with the notations used in Theorem 3.1 eter that determines width of the network (i.e., "", to the total number parameters in the network (i.e,, AH), and to the network class (i.e., JH). It is interesting to note that the exponential growth of the network size in observed in the construction of FH whereas there exists a flexibility in F, dependent on the choice of M. Specifically, the width of the network in JHH is exponentially dependent on as H 2(rd V ) whereas the width of the network in F is dependent on two parameters N = o(d) and any integers M > 1. For the total number of network parameters, we have R = ((d + r)),, whereas N = (Md + Nmd).
we put the superscript H to a param-
Iff r (d)) the factor becomes ( | for 0 < 1. Here, the exponential decay term (L) derived from Sobolev embedding Lemma. See Proposition D.I.3 Appendix D

---

Published as a conference paper at ICLR 2023
Analogously, the bound on the approximation enror of f in (0) is dependent d exponentially, but this exponential dependence in d can be avoided in the error bound of f in 7 under two see-
narios: (1) r = (d) and any integer M 2 or (If) r -= (1) and = (d')). ). In the Corollary presented in the next Subsection, we further specify the two scenarios, and describe how the approx- imation error bound in each scenario converges to 0 in terms of d.
3.2 FAST APPROXIMATION ERROR IN TERMS OF d
Corollary 3.3 Ler < a. 3,y < with y > max B] and N E N with S & do + 1. For any f E W W 18 with r 0, we have:
(I) For 3d-2 C1 network
3d-2 with some constant C1 0 independent of there exists
j(a E (T, (d, G6N, 66N, 66N, ,N) with depth I O (d log2 d) and the number of active parameters N O ((duax(at))))) such that f f(n)
S SCa. 1lffllllllwlll
18a-1,d (s
d" where C² C, is constant depend-
ing only C1. 17, a, and
(II) For (1) and M = ( there exists a network
jun F(,, (d, 22,M, ...... 22NM,1).NN
with depth L = =0 (d log2 d) and the number of active parameters N = O (9 such that 1ff-i(mn D0 only on 9) ot 3 and y
S C² 3, flflllwllllwww isd-- (st where C² C,,,8,y is a constant depending
The detailed proof on Corollary 3.3 deferred in the Appendix E.6 The approximation error in scenario (I) decays at a rate d-d for 0 < B < 1, while the required number active parameters N at most (dd)). Here, the construction of network f(() is independent with the choice of M, and we simply choose M 3. In scenario (II), since = ((1 and 0 < a 1, the approximation error decays to 0 at d' d(1) rate, which can be slower than d'd' for close to 1. The width f(I)) grows exponentially in d requiring M Odd)). Interestingly, in both scenarios, the depth L has the same order as O (d" log, d) for 0 < 7 <.
Remark 3.4 As suggested by one of the reviewers, we further compare our results in Corollary 3.3 (I) with the CNN architecture with downsampling operation suggested in Fang et al. (2020) for Jiao
approximating f E (S and (II) with Lu al. (022 Jiao el al. | (022) where they consider
the problem of approximating I WT. (Ca) via deep ReI.U FNN. Due to the limited space, we defer the detailed remarks on the comparisons in the Appendix
STATISTICAL RISK BOUND
Let X' : SU-1 and y R be the measureable feature space and output space. We denote p joint probability measure on the product space 2 = X' x y, and let px be the marginal distribution of the feature space X. We assume that the noisy data set D {(x, y:) are generated from the non-parametric regression model
y: = (xx))
i= 1, 2,.
(11)
where the noise e; is assumed to be centered sub-gaussian random variable and [E(x)x)) = 0. Our goal is estimate the regression function fx(x) with the given noisy data set D. Specifically, is assumed that the regression function belongs to Sobolev space on d-dimensional sphere: that is fo W:. ( is easy to see regression function fo = Ely /x) is minimizer of the following population risk Ef) defined as:
E()) Exxxi~ (y (V-
7

---

Published as a conference paper at ICLR 2023
However, since the joint distribution p is unknown, cannot find fo directly, Instead, solve the following empirical risk minimization problem induced from the dataset D:
E (xx-) [(x)
In = arg min En(f)= = arg min SEF(L.P.M)
(12)
SEF(L.p.N)
Note that the function estimator is taken from the feedforward neural network hypothesis space F(L, deetined in (2). and we denote the empirical minimizer of (12) as fu. is assumed that ly S B almost everywhere and we have [x)[ < B. We project the output function f SSa-1 -
onto the interval |- B, B| by a projection operator
f(x),
if B B f(x) S B, if f() > B,
Txf(x)
B,
(13)
B,
if f(x) < -B
We consider the clipped estimator TBJu for recovering the regression function f.- Note that the clipped estimator has been widely used in statistical learning papers Suzuki (2018): |Fan & Cheng 2023
Oono & Suzuki 2019). The quality of TB is measured through the difference between two expected risks (i.e., excess risk) defined as E( (TBB.)) E(f).
4.1
BOUND ON EXCESS RISK
In this Subsection, we provide the upper-bound on the excess risk of the clipped estimator 13 (fx) with respect to the pseudo-dimension (i.e., Pd)m(F)) and the approximation error (i.e., || - -fl-oll soll,0) Before presenting the bound, the definition of Pdim(F) FF) is presented.
Definition 4.1 Denote by (Fi the eyeudo-dimensee which there exists (E1,...,&6, m..... ME) ) X2 x RR. such that for any (01,-.., ae) (0, there is some f E F satisfying
of F, which is the largest integer for
Vi: f(E)) To =1
For more comprehensive exploration Pdi can be found in references Anthony & Bartlen [1999; Bartlett et al. (2019). We provide the first theorem on the excess risk.
Proposition 4.2 Set 8 E (0, 1). Then, with probability least 6, we have
E(TBfA) Eff)) s CB... (Pdim(F) -log())
ff
+ llf - 5ol1be)
(14)
Vn
where CB...J an absolute constant dependent B, 8, independent on n, n,,r.6 d.
A detailed proof of Proposition 4.2 is deferred in the Appendix. The excess risk E (x
a random quantity over the estimator f/ and the statement the Theorem holds with probability at least 5. The failure probability 5 E (0, 1) is hidden in the constant CB.,, logarithmically, ie., log(}) 3). In the bound, it should be noted that there is a trade-off between the "approximation error" (i.e.. [ liffSplles term and the combinatorial "complexity measure" term of a neural network class F (i.e., Pdim(F) -lo(nn)/o); that is, the richer the network hypothesis space J becomes, the finer the approximation result we get. Nonetheless, the arbitrary increase in the hypothesis space F eventually leads to the increase of the bound in excess risk. In the following Subsection, will show how the specifications (i.e., the choices of (I, P.N)) of the network architecture affect the tension between these two terms.
4.2 CONVERGENCE RATE EXCESS RISK
Now we are ready to formally state bounds on the excess risks of T Fro when fo E W (Sd-1) (i.e., Theorem 4.3 and f, E W ((0, 1Jd) (i.c., Theorem 4.4). respectively.
'Hencforrth, we will use shorthand notation of F(I.p, as F. Dependence on (T., P..) should be implicitly understood.
8

---

Published as a conference paper at ICLR 2023
Theorem 4.3 Suppose fo E (5* with r 0. A network Fn from (6) with choices N In [nzafar] 1, M = [naaaar 2d 1, and m = [ sdtar log2(n)] yield the bound on the excess risk with
probability at least 8 as follows:
fM - ESTn
CBBmo, max 1, (3d + 4r)2 (log2(n) (n))),
6rd
(
6
$ NRN+ 20 2: d&w .uw.. arfina, (15)
Te
where Cn depends on B, 1), 8, f and independent on d,y r and n.
Theorem 4,4 Suppose Jp W ([0, 11 with > O. A network In from 2 with choices N
In In 1, and m = d+r log2(n)] yield the bound on the excess risk with probability at least 1 - 5 as follows:
d42r
E fm) - =spp
(16)
$ C...k max [[log (r))))))((((+++++++ r)* (logg(n))), (1 +0 + 22) d + g2r
2x
n
where CB.. depends B, n, 8, K and independent d, and
Both proofs are simple applications of Proposition 4.2 with results from Theorem 3.1 and 3.2 For both cases, PFi can be easily computed from Lemma H. in the Appendix. The parameters that deter- mine the network architectures, N, M, and N m in two Theorems are chosen in way that the bound in (4) is tight in terms of sample size n. Constant factors CB, and CB,,,.K are dependent 8 E (0, 1) log())). The bound in Theorem 4.3 Oa(n भनंक)) ), is sub-optima 4 in minimax sense for estimating functions fp E W where O₂ hides the constant factor in d. The extra 0. 0.5d factor in the denominator of exponent comes from the Sobolev embedding Lemma (Lemma D.1.3) and discretization Lemma (Lemma D.1.4). For the constant factor d, when r = (1), the exponential dependence on d can be observed. However, when = (d), the excess bound in [5) reduces {(TM [2)) (S(p) < CB.,, max {(log((n))* d 2
Detailed proofs on Theorems 4.3 and 4.4 are deferred in the Appendix F2 and F3
With choice of N T as d, co, the constant ddN becomes (1),, In contrast, in (T6) for estimating functions So E W ((0, 1] the rate n is minimax optimal, but we cannot observe the interactions between r and d as we observe in 15
From the technical point of view, the result in Theorem 4.3 should be compared with the results in the existing literature, i.e.. Selhmidt-Hieber (2020); Chen et al. (2022); Suzuki (2018) a sense that our result doesn't require the boundedness of the weight parameters in the network construction. The detailed readings of their proofs reveal that they require the bound on the uniform covering number of F and it can be bounded by the Lipschitzness of the network output with respect to the weight parameters. Naturally, for the discretizations of the parameter space, the bounded- ness assumption is required. In contrast, in our result, due from the Bartlett et al. (2019) (See Lemma H.I. bounding the complexity measure PJim(F) doesn't 't require the parameter bounded- ness assumption.
Remark 4.5
AN OPEN QUESTION
In this paper, we prove when r r= Odd) deep ReLU FNNs only require at most N' = Odd2) param- eters to get a sharp approximation rate. However, this condition seems restrictive, and needs further investigation whether it is necessary and sufficient condition to avoid the curse of dimensionality for approximating f E W (1d-1). To answer this question, it is essential to study the lower bound of A with a similar approximation error as stated in Theorem 3.] and see if has the matching or- der with the upper-bound we get in d. We conjecture obtaining this result is possible by combining the ideas of using VC-dimension of deep ReLU FNNs (Bartlett et al., 2019 Yarotsky (017)) and of constructing the packing set on the sphere through the spherical cap (Hesse (0066. while tracking the d d-dependency in the constant factor carefully. We leave this for future research.
"Since 1 C Cd, it seems obvious we should achieve minimax optimal rate. In this regard, we add further detailed technical remarks on the sub-optimality of excess risk in the Appendix B
9

---

Published as a conference paper at ICLR 2023
REFERENCES
Martin Anthony and Peter I. Bartlett. Neural network learning: Theoretical foundations volume 9.
Cambridge University Press, Cambridge, UK, 1999.
Dzmitry Bahdanau, Kyung Hyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In International Conference on Learning Representations, 2015.
Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1):285-2201, 2019.
Moise Blanchard and Mohammed Amine Bennouna. Shallow and deep networks are near-optimal approximators Korobov functions. International Conference on Learning Representations, 2022.
Ch Brechbühler, Guido Gerig, and Olaf Kübler. Parametrization of closed surfaces for 3-d shape description. Computer vision and image understanding, 61(2):154-170, 1995.
Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Efficient approximation of deep ReLU networks for functions low dimensional manifolds. Advances in neural information processing systems, 32, 2019.
Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Nonparametric regression on low- dimensional manifolds using deep relu networks: Function approximation and statistical recovery. Information and Inference: A Journal of the IMA, 11(4): 2022.
Feng Dai and Yuan Xu. Approximation theory and harmonic analysis on spheres and balls, vol- ume 23, Springer, 2013.
Ronald DeVore, Ralph Howard, and Charles Micchelli. Optimal nonlinear approximation. Manuscripta Mathematica, 63(4):469 478, 1989.
David I. Donoho and lain M Johnstone. Minimax estimation via wavelet shrinkage. The Annals of Statistics, 26(3):879-921, 1998.
Costas Efthimiou and Christopher Frye. Spherical harmonics in p dimensions. World Scientific, 2014.
Zhiying Fang and Guang Cheng. Optimal learning rates of deep convolutional neural networks: Additive ridge functions. Transactions on Machine Learning Research, 2023.
Zhiying Fang, Han Feng, Shuo Huang, and Ding-Xuan Zhou. Theory of deep convolutional neural networks II: Spherical analysis. Neural Networks, 131:154-162, 2020.
Han Feng, Shuo Huang, and Ding-Xuan Zhou. Generalization analysis of CNNs for classification on spheres. IEEE Transactions on Neural Networks and Learning Systems, 2021.
Willi Freeden, Theo Gervens, and Michael Schreiner. Constructive approximation on the sphere
with applications to geomathematics. Oxford University Press on Demand, 1998.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Discussion of: nonparamaett regression using deep neural networks with ReLU activation function".. The Annals of Statistics, 48(4):1898 -901-9998111------11111191111181 2020.
Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recur- rent neural networks. In 2013 IEEE international conference acoustics, speech and signal processing, pp. 6645-6649, IEEE, 2013.
László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk. A distribution-free theory of nonparametric regression, volume 1. Springer, 2002.
Zhi Han, Siquan Yu, Shao-Bo Lin, and Ding-Xu Xuan Zhou. Depth selection for deep ReLU nets in feature extraction and generalization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
10

---

Published as a conference paper at ICLR 2023
David Haussler. Decision theoretic generalizations of the PAC model for neural net and other learn- ing applications. The Mathematics of Generalization, pp- 37-116. CRC Press, 2018.
Kerstin Hesse. A lower bound for the worst-case cubature error spheres of arbitrary dimension. Numerische Mathematik, 103(3):413 2006.
Yuling Jiao, Guohao Shen, Yuanyuan Lin, and Jian Huang. Deep nonparametric regression on approximately low-dimensional manifolds. arXiv preprint arXiv:2104.0670 2021.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. Advances in neural information processing systems, 25, 2012.
Jonathan Long, Evan Shelhamer, and Trevor Darrell. Fully convolutional networks for semantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp.
2015.
Jianfeng Lu, Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation for smooth functions. SIAM Journal on Matematical Analysis, 5365):56555506, 2021.
Vitaly Maiorov and Joel Ratsaby. On the degree of approximation by manifolds of finite pseudo- dimension. Constructive approximation,, 15(2):291 -3000, 1999.
Hrushikesh Mhaskar, Qianli Liao, and Tomaso Poggio. Learning functions: when is deep better 2016.
than shallow. arXiv preprint
Hrushikesh N Mhaskar. Neural networks for optimal approximation of smooth and analytic func- tions. Neural computation, 8(1):164-177, 1996.
Hadrien Montanelli and Qiang Du New error bounds for deep ReLU networks using sparse grids. SIAM Journal on Mathematics of Data Science, 1(1):88-9)) 92, 2019.
Kenta Oono and Taiji Suzuki. Approximation and non-parametric estimation of resnet-type con- volutional neural networks. In International conference on machine learning, pp. 4922-4931. PMLR, 2019.
Philipp Petersen and Felix Voigtlaender. Optimal approximation of piecewise smooth functions using deep ReLU neural networks. Neural Networks, 108:296-330, 2018.
Johannes Schmidt-Hiee Hieber. Nonparametric regression using deep neural networks with ReL.U acti- vation function. The Annals of Statistics, 48(4):1875-1897, 2020.
Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation characterized by number of ncurons. arXiv preprint 1906:::9990055444 2021.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panncershelvam, and Marc Lanctot. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):48444555 2016.
Steve Smale and Ding-Xus Xuan Zhou. Learning theory estimates via integral operators and their ap-
proximations. Constructive approximation, 26(2):153-172, 2007.
J-L Starck, Yassir Moudden, Pierrick Abrial, and Mai Nguyen. Wavelets, ridgelets and curvelets on the sphere. Astronomy & Astrophysics, 446(3): 1 191-12044 2006.
Taiji Suzuki. Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality. In International Conference on Learning Rep- resentations, 2018.
Roman Vershynin.
High-dimenssonal probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Martin Wainwright. High--imensionn statistics: A non-asymptotic viewpoint, volume 48, Cam- bridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.

---

Published as a conference paper at ICLR 2023
Yves Wiaux, L Jacques, and Pierre Vandergheynst. Correspondence principle between spherical and euclidean wavelets. The Astrophysical Journal, 632(():15, 2005.
Dmitry Yarotsky. Error bounds for approximations with deep ReLU networks. Neural Networks, 94:103-114, 2017.
Tom Young. Devamanyu Hazarika, Soujanya Poria, and Erik Cambria. Recent trends in deep learn- ing based natural language processing, IEEE Computational Intelligence Magazine, 13(3):55-75, 2018.
Peng Yu, P Ellen Grant, Yuan Qi, Xiao Han, Florent Ségonne, Rudolph Pienaar, Evelina Busa, Jenni Pacheco, Nikos Makris, Randy L. Buckner, et al. Cortical surface shape analysis based on spherical wavelets. IEEE transactions on medical imaging, 26(4):582-557, 2007
Ding-X Xuan Zhou. Theory of deep convolutional neural networks: Downsampling, Neural Networks, 124:319-333 2020.
12

---

Published as a conference paper at ICLR 2023
A d' -DEEENDENT CONSTANT IN N FOR APPROXIMATING f W (10, 1)()
First, we define the function space W ((,, 1J on the d-dimensional unit cube. For r n where n E Ng and a E (0, 1], a function has Hölder smoothness index r all partial derivatives up to order exist and are bounded and the partial derivatives of order ball r--ölder functions with radius Q is then defined as
Hölder. Formally, the
W ([O, 119) { f: 10, 11 RR:
|0 f(x) -0 f0)()) 2
Σ Sn
Σ sup ax/ex
+
(0. m/y
x y y
where pz "Pt....p f for the multi-index notation, ar == (0i,,..,aaa
The fundamental ideas for approximating functions f E W (10, 11 in the existing literature rely on a local Taylor approximation technique. The technique discretizes d-dimensional input cube into a sub-cube set whose size is (K + 1) where (K + 1) is the grid size of each coordinate. For any x the input cube, the function f is approximated by using the closest 24 grid points to x via Taylor expansion of f up to the degree [r], where we denote the largest integer less than equal to >> 0 as [u]. Therefore, the total number of active parameters for the net is at least more than the total number of coefficients of partial derivatives 0 := ge eortaend network via local Taylor approximation
اااl a for |a] = |ai +... + laal < [r]-
This yields the lower bound on the active parameters as (K + 1)d (
B SUBOPTIMAL CONVERGENCE RATE OF EXCESS RISK FOR f E W (S
Since sa-1 C Cdd, in light of Whitney's extension theorem, it is obvious that the convergence rate ár
of excess risk for f E W (Sd-1) should achieve the minimax optimal rate n same as for estimating f W (Ca). However, from this perspective, it is not possible to track the explicit dependence on in prefactor of the rate.
From Proposition 4.2, we track this dependence with the combination of our own approximation result. First of all, order to achieve the minimax learning rate in n (e.g., sample size); that is, अ,क0, we need to achieve the optimal approximation rate, known as O(N-a), where A denotes the number of active parameters in the network. This can be easily checked in Schmidt-Hiehhe (2020)ss 's result.
But this cannot be achieved in our Theorem 3.1, the result of approximation theorem. The main reason arises from the employment of Sobolev embedding theorem (Proposition D.1.3) and of concentration inequality from (Smale & Zhou (2007) (Lemma 1.2.1) used for bound- ing the term (f) - I% (f)lloo Proposition D.1.3 specifies || (f) I% (f)l I Ca))LN(f) - lations [[ 5. (f)lll)) 1) S Ca,rlll/lww 1) (2N+1)
for some 8 (3d - 2)/4 and Lemma D.1.4 specifies the re- 3d 4r
In this process, there are some extra factors multiplied leading to the rate sub-optimal, reflected in the term (2N + +1 +1)" ""7" would be an interesting research direction, we can develop a nice mathematical framework eliminating this extra factor.
VM
C FURTHER COMPARISONS WITH EXISTING LITERATURE
C.I COMPARISONS OF COROLLARY 3.3. WITH THE CNN APPROXIMATOR FOR THE APPROXIMATION OF f E WT (8
We consider the case when the approximator is deep ReLU CNN followed by downsampling oper- ations and very few nully-connected layers. This exactly the same architecture considered in the paper Fang et al. (2020), and by applying result (Lemma D.1.4), we get the following theorem.
Theorem C.1. Let 2 < < d. < a < 1, and B, N, M E N with 1 S N < do 1. Let J > Md Md-1 Dj (2B + 33) JS)/dJ, and D2 [(d + /d) Then, for any function
13

---

Published as a conference paper at ICLR 2023
Schmidt-Hiehbe (Thm 5) O(Hlog V d)1)
Lu et (Thm 1.1.)
Jiao et al. (Corol. 3.1)
Depth
0(r2+0 d)
[[[[r] 1)2))
Width
O(d++ r +
O d3
O(([) + 1)33"aliity
Approx. Rate
0 (r 11))
(r 1)
o((r) + a1
Table 2: A summary of r and d dependences in the prefactors of constructed deep ReLU networks' depths, widths and approximation rates for approximating the functions f E W (C4) Schmidt- Hieber 2020); Lu et al. )0 Jiao et al. (202T).
W (84-1) with > 0, there exists network joNN D...Di.D..S with the number of parameters N I J(3S + 2) + M + 2B + 4 such that
|| jamml s C [flllw(sss) max N ( (oe) d dNN430 35-55-5--00 2d-4r-2
(2N + -d
N2 2NN
VM
B
S
(17)
where C is a constant dependent on n) a, and independent on d, r, N, M or
The only part we need to pay attention to is bounding the term | N.M (J)
jCNN I| and track the
explicit dependence on d in the bound, and its proof is deferred in Appendix
We consider the case r (d) and any integer M 2 this case, our result for deep ReLU
FNN shows that (dd-d) can be achieved for the approximation, with at most (d?) active param- eters. In light of the result from Zhou (2020), we also should expect the same results for CNN with downsampling operation.
In order to get an approximation rate O(d-d) for some 0 < 3 < 1, controlling the first two terms in (1.1) is the same as that of our proof in the Appendix E.6. We only need to pay attention the
last term. Since 1 < N < d + 1, for some 0 S a < 1, we have
2N No B 2dd fa / s 8 ddd +1 M/B
for some constant C' > independent with d > 0 and O. The rate d d is obtainable only when B = Odd). Then, the number of parameters N < J(3S + 2) + M + 2B + is bounded by O (dd). This is unsatisfactory result. However, firmly believe this result can be improved, and leave it as an open question for future work.
C.2 COMPARISONS OF COROLLARY 3.3. WITH THE RECENT APPROXIMATION RESULTS FOR W VVE(C") VIA DEEP RELU FNN
After the publication of Sichmidt-Hiebee (2200) series of works further studied the approximation and estimation of WT. (C") via deep ReLU FNNs. Specifically, Ghorbani al. (2020) pointed out that the additive function studied in Schmidt-Hieber (2020) has an exponential dependence in in the prefactor of the estimation error, requiring n. 2 d" sample sizes for good convergence rate. Later, [Shen et al.) (202T) and Lu et al. (2021) tracked the explicit dependence on d in the approximation error as well as in the architectural components, (i.e., width (W) and depth (L)), for approximating f CCCC) (i.e., Lipschitz continuous functions C4) and f W (Cd), respec- tively. Specifically, Lu et al. (202 improved the prefactor O(8 (r+1)d) when it is compared with (6 1)d) from Schmidt-Hieber
(2020) for the approximation error. Most recently, Jiao et al. 2021 further improved the prefactor O([[r +
for approximating f E W (Cd). In Table 2 comparisons of depths, widths, and approximation rates of the constructed deep ReLU
networks in Schmidt- Hccbiit-HHebberi (2020): Lu al. 2021); Jiao et al. (202T) are summarized.
2021 direct comparisons their can be challenging. However, it can be roughly checked that the result in Diao et al. (202T) doesn't escape the curse for all r > 0. Specifically, for r (l)) the constructed network has the exponential dependence in for its width. For the case r = (d), achieving the approximation rate (dd-d") d")) requires (dd') width in the suggested network.
Since A is not tracked in the works of Lu et al. 2022 Jiao et al.
results with results for the approximation of / WT (Sa
14

---

Published as a conference paper at ICLR 2023
D ROADMAPS FOR PROOF OF THEOREM 3.1
In this section of the Appendix, we provide the definitions of (f( and ( along with the overall picture for the proof of Theorem 3.1 Recall we have the following decomposition:
|| - - If - LN + (N((F) - L ( (O) + +
(18)
(II)
(I
In Subsection D.I, we provide the idea for bounding (I) and (II). In Subsection D.2, the construc- tion of neural network for approximating (f) is described.
this section, no proofs of
Propositions and Lemmas are included, but only key ideas for the proofs and technical comparisons with other literature are provided. All the detailed proofs of technical statements in this section are deferred in the Appendix C.1.
D.1 ERROR BOUNDS FOR (I) AND (II)
A function f (S is approximated by linear scheme LN defined follows.
Definition D.1.1 Given a C ool) function n with 17()) 1 for 0 & 1 and ny(t) = 0 for t 2 2. we define sequence of linear operator LN, N E N. (p(5t with 1 S s0
2N
k
Proje = 1S-.. f x s (19)
LN(f)(x) = Σnr
N
R=
where with λg
2-2
LNd is kernel given by
2
2N
k k
Ag goo
(x,(()) =
[-1-1,
(20)
AG
It can be found in Dai & Xu (013) (Chapter 4) that L is near best, achieving the order of best approximation for ( ").
Lemma D.1.2 (Lemmaa in Fang et al. (2020) For N E PAIspS x0, O, and E
(Sd) there holds
LN S C, -1. (
(21)
where Ci is constant depending only on the function n in defining T.N-
r/2 I)² is self-adjoint operator. For x E Sd-1, recalling the definition of Note that (- As + (f),), we have
Lx(f)(x) (filN,l( 1)) 1)
= -(- 5/, --) (x.a))= exal(xx.)1) L
I | Fr(y) Ex.r((xx,)))xx((()
(22)
Hereafter, we denote F, (-Age- +I) 1/2 and EN. ((x, (-Aga- -2)-1+ZZ~11/
1/2 2..///eNndl eN (v,a((x,))) :))-
By the fractional power of the operator (- Aga-i I) -r/2 in distributional sense, EN (.) is polynomial of degree at most 2N written as:
k k + t
(1) Σ (1+ XR)
1/2
1
(1), tetttet tE|-1,1]
(23)
AG
The fractional power of (-Aga-1 + I) caused by the regularity f E W (Sd-1) enables r- dependent error bound for discretizing L (f): the larger the regularity r becomes, the smaller the bound for approximation error gets.
15

---

Published as a conference paper at ICLR 2023
Following Fang et al. 2020), the key idea for constructing neural network that approximates LN (f) to discretize the integral form (22) by random samples y = (y1,..., .M) indepen-
dently drawn from px. We write the discretized version of (22 as
1 1 M
Σ (y.) (x,,((x)))),, Vx E
(24)
Before estimating the distance between IN (f) and π. 7. NNM(s)) we need Sobolev embedding prop- crty.
Proposition D.1.3 For 2 5, continuously embedded into C(S the space of continuous functions
oc, and s = 3d=2, the Sobolev space (o( is
functionss on s which implies
Il I co
|I 1151
E W
where co is an absolute constant independent of d, 8, and f.
Proposition D.1.3 is motivated from Eq.(14) in Hesse (2006). where they proved
|
C..d [If (1 E WD(( for 2 d-1 The constant obtained in Hesse (2006)
Ca,d (2) EA=0
N(k.d) 1/2 where wa is the surface of d-dimensional sphere. For large (x++ 33,
enough d, (1/wa)2/2 grows in the order of (((2)))) )d/t). Then, by choosing 3d-2, (1/wa) can be absorbed into the infinite sum making the constant Cs.a converge in an asymptotic regime of d. It should be noted that the threshold smoothness index (i.e., > 3dك2) is larger than that from Hesse (2006) (i.e., s - where they consider the fixed d. See Appendix EE.1 for the proof. Next. we state the discretization lemma which provides probabilistic bound on the difference LN( I% (f).
Lemma D.1A4 Let r < 3d-2 and 0 < a < 1. ISS W (S then for any M E N and 4
W 1 d" + 1, there exist y = {u1. ,2,,...,uh.. C Sa-1 such that
6. C" (Ga) $ llf l (8a-1) d 34-40-2
(2N + 1) 3d-4r
|LN(1) - a (D)
VM
where C" is a constant depending on a but independent of J, N, M, and d.
Lemma D.1.4 is motivated by Lemma in Fang et al. (2020). The main framework of the proof is based on the Sobolev embedding property in Proposition D. and the concentration inequality for random variables with values in Hilbert space. which can be found in Smale & Zhou (2007). For the application of the concentration inequality, the random variable {(y.) = Fy NNN.y (xx,
in 24 needs to be bounded in || (S4-1) norm for > the Lemma.
3d-2 See Appendix E.2 for the proof of
When compared with the technical proof of Lemma from Fang al. (2020), the most notable difference comes from tracking the explicit dependency on d in the constant factor. Specifically, under the fixed d setting, Fang al.] (2020) did not explicitly express how the constant Ca.r,d (see the statement in their Lemma) depends on d. However, in our paper, since the main focus is how the approximation error behaves under d - 30, we need to keep tracking how d explicitly affects the bound. The result of Proposition 4.1 in our paper serves important role in this tracking. Note that the constant ep is independent of 8, d, r,
the bound of Proposition 4.1, and we obtain the d/1 However, in Fang et al. (2000), they utilized the result from Hesse
bound decays at the rate ( (.6) (,6))/1 2006;; that is, || S CC,all (C.all//llw,rs---y--
d-1 (S*1)11) for 2 Here, note that the constant C..a 18 function of d. and since they work under the fixed setting, they did not pay much attention to the dependency. Of course, since are in asymptotic setting, to see behaviors of (K,, d) as d + oo, whereas Fang et al. (2020) just used a simple calculation N A d) S d.2 for some d' dependent on d.
the Stirling's 's formula
16

---

Published as a conference paper at ICLR 2023
D.2 CONSTRUCTION OF DEEP RELU NETWORKS: ERROR BOUND FOR (III)
In this section, several useful tools for the construction of neural network for approximating function "N.M N. (f) are introduced. Then, the full proof of our main theorem is presented.
The first key lemma is from Yarotsky 2017) wherein the neural network that approximates the quadratic function x² for E 00 constructed.
Lemma D.2.1 (Proposition 2 in Yarotsky (2017)) For any positive integer 2 1, there exists deep ReLU network
fm F(m, (1,5 .................... 5,1),
such that fm E [0, 1] and [m( - 2² < 2m-2mm2,for for all x E [0, 11.
The main idea of Lemma D.2.1 to approximate the quadratic function via fm(x) = x E (x(w) 2
Here, (x) is s-c s-compositions of sawtooth functions defined
g(x) 2x)x) 40 1/2) 20 - 1)-
Note that g(x) can be implemented by single layer ReLU network. Then, we can easily construct ReLU network fm. which belongs to F(m, 51. 1)).
Next lemma states that we can construct a neural network that can implement the multiplica- tion operator.
Lemma D.2.2 For any positive integer m 2 1, there exists a deep ReLU network
Multm E F(m + (.....)))..........)
such that Mult (z, y) E [0, 1] and
Mullm (2., 3) - xyyl S 2- 2m-1
for all x, E [0, 1]. Moreover, Multm (z,, 0) = Mult,, (0, v)
The key idea for constructing Mult,,, (z. 3) to invoke the identity zy 1 ((1 + y) (x 3) The first two hidden layers in the network are used to compute | E [0, 1] and -= E [0. 1] via
|x| (x) + (-x). Given the values | and = as inputs, f. in Lemma D.2.1 is used for approximating (x + 2 and {x y) in the identity. See Appendix E.3 for the detailed proof.
The final key ingredient is to construct a deep ReLU network that approximates univariate polyno- mial functions of degree N, that is x* for [0, 1].
Lemma D.2.3 For any positive integer 2 I, 2 2 and for P= [log([N)] there exists deep ReLU network
Poly E F(L, (1, (I, LIN, (1.1I,,....1,,2))...)
with the depth L = m (m+))) (N)1 11) and the number of parameters N 102N.(m++3 such that Poly!M) ()] (x) E [0, 112" and
Poly' (x) - 2²| 22.22-2 2m2-1 for all jE fl,...,,2"
for all x E [0,
n. Note that the network Poly (N) (x) := (Poly]. (x), Poly?
2 m (x)} with P = (N)] provides
approximations monomials xd of degree up to 2N for [0, at its final output.
The key idea for the construction is to employ tree structure; that is, the width the network at ((m+ (m 4) -))t hidden layer is doubled from that ((m (m 4) (j 1)) hidden
17

---

Published as a conference paper at ICLR 2023
layer for j {l,.... 1) as
(Poly (....... Polym 2 (z))
(in+1))(m++)(()))) 2' (x), Multi (I,, Poly (x)) fm (Poly 2' (x))
(Poly), (z),.... ................................ Polym
(25)
((m+1)+ 4)-53 layer
The first 2 input values in ((m + 1) + (m + 4) 1hth hidden layer is exactly copied from input values at the ((m + 1) (m + 4) (j 1))t hidden layer. The remaining 2/ input values in ((m+1))+ (m-++))))+))
hidden layer approximates monomials (2:2²'++
xx.' through f' and
Mult,, operations Lemmas ee2.1 and [.2.2] The approximation error can be obtained via proof
by induction. Readers can find the detailed proof in the Appendix E.4 with the exact descriptions on the construction of Poly
Finally, ready to state Proposition D.2.4 the construction of network f which approximates M
Proposition D.2.4 Let 0 < < 1,m, N, M E N with 1 S N S d= + 1. For any function E W (8t-1) with > O, define "N, (f) in 24 Then, there exists a network
F(L, (d, 22. 22 1),
with depth L = (m + 4) [log (2N) and number of parameters N & M(2d + 404N (m + 3) + 2N + 4) + such that
T (f) - i1 sC
: IIfllw 1y daN (log,(20)) (2N)) 2-mmm 2m
(26)
where C, is positive constant depending on y and a, but not on d, r, m, N, M S.
detailed proof for Proposition D.2.4 deferred in the Appendix E.5
Given the input data 1d-1, recall the definition of / (f) 24). The crux of the whole construction procedure of our network is to build the sub-network which approximates EN ((x, (xxy)) y:)) for each i [M.. The key observation is that ( y:)) is the weighted sum of univariate polynomials of degree up to 2N. Let u, = (x. With the properly defined constant ds (see its definition in the Appendix (E.)) EN.-((x,y.)) can be re-written as (w,) = 2N Since |u,] [0, 1). with the help of network constructed in Lemma D.2.3 with P 0ti /1/19. the sub-network that approximates EN.,(u;) is easily constructed. Recall this is enabled through the reproducing property of the kernel of H. for S K < 2N.
(2NN),
E PROOFS OF STATEMENTS IN APPENDIX B AND COROLLARY 3.3
E. PROOF OF PROPOSITION D.L.3
Proposition D.1.3 For 2 5, p S oc, and 2 3d-2, the Sobolev space (Sd is continuussly embedded into C(Sd-1), the space of continuous functions on Sd-1, which implies
11 S co
[I IIIllwyss 1y>
JE JEW
where 6o is an absolute constant independent ofr, d, 8, and f.
Proof. For (Sd- by Sobolev embedding Lemma (see Hesse 2006 Eq. 14, p. 420), the infinity norm can be bounded by the Sobolev norm as
Ilf < Ce.d || IIfll 1)*
(27)
18

---

Published as a conference paper at ICLR 2023
where the constant Ca.d is defined with its square as
N(k,d) d) + 22
C We
(28)
with wa - - Recalling (3. it is easy to see that by Stirling's formula, for large d.
((kk = (k + 1 (1 + +()). Also, we have
d
2
2 d
d +1
d
1 O (
r
r
2
(29)
2
2
2e
When
d-1 2
we have
d - 2
2-
1
d 2
d=1-2x
{ d 22 dt
28
+
Observe that d 2 5, we have thereby (28) is bounded as
d-2
1 12
d
Thus, when
2 3d-2 we have 2s + 1 - d 2 d/2 and
12.
1+ (1)
2V- 1
dvd Tp - (1+0
C2 V V 2
12
Then, there exists absolute constant co such that
6
C
c TE
PA 2 5.
This yields the claim.
E.2 PROOF OF LEMMA D.I.4
Lemma D.14 Let < r < 3d-2 I d + 1, there exist y (V1, (21.22....,.0 ... ,yM) C Sd such that
4 and 0 < a < 1. I E W: (SL-1), then for any M E N and
6 c" ( $ || 15 13 d ad
(2N + 3d-4n
|| - M (
VM
where C" > is constant depending on but independent of f. N, M, and d
Proof. We recall the following probability inequality for random variables with values in Hilbert space which can be found in Smale& & Zhou| (2007).
Lemma E.2.1 Let (H, || II) be a Hilbert space and & be a random variable on (Y, px) with values in H. Assume ||E|| S -M < co almost surely. Denote (E( [[[ Let {y:), MM be independent samples from Px. Then for any 0 < 8 < 1, we have with probability at least 1 - 5.
1 M
2M M
20 (E) log
Σ
((x))
B(()
(30)
M
M
Let us define the random variable & on (Sa-1 Pxx) with values in H given by
2N
1/2 k
E(v)
Fv)
Σ K=0
(1
Zu(
y E Sd-1
(31)
To bound the norm || [|E(v) llazz we set
3d-2 and recall the norm of WS given with
p 2 and for 1
2N Fr(())
[k(x)) wg(s" 1)
(1++x
30
(
k Zz (v:-)
(32)
Lo(S0 1)
19

---

Published as a conference paper at ICLR 2023
Recall X k<k + d - 2). Then, for 0 < k < 2N, d 2 3, we have k2 < <1+ A I dk2. We 0). Also note that 0 I ntt ((1/)) in the expression but independent of d. By using the identity (v. = NVkk, d) (see Corollary 1.2.7. in Dai & Xu 2013 ||E| wg
(:: for 1. [0. Employing Stirling's formula d! v2xd(1))
find (1 + Ax) 2 d= by s 3-22
for (K: d) yields (Kk d) I Cd for 0 < k v 2N and some constant C depending
be bounded
2N
2N (1+
1 N
Fr(y)2 Σ (1 AR) 2x)= 1/ k=
d)
Σ k=1
(1+
17² N(k,d)
N
S P.(()
(1 (1+C.
k 2 di
2N
S F.(1)) (1+C-
22(e-1)
while the term Dx= 12((--)) with r 20 0 can be bounded as
2N Σ 2((0-))
2N+ 2 dx S 2(x - r) + (2N + 1)2(5-1341
1
1=1
Combining this with the definitions of the norm |l ( we know that [KE())]l can be bounded as
lk(u)liw; C² (s - + 1))(
where C is constant depending on a but independent of s, f. N. and d. Thus the random variable & satisfies the condition |El|| S M < 30 in Lemma E.2.1 with M
C" "'Illlls (s*-1) + (2N + 1)( So by Lemma E.2. with 8 = & and o²(E) s M², we know from the positive measure of the sample set that there exists a of points y {wi 8d-1 such that
M
1 M
E(v.)
= =||-x(0) (B(E)
I (1)
6 C" [lfllws N (2N + 1)
(33)
VM
Since s 3d-2 combining the result from Proposition D.1.3 with yields
6 c" (+)
$ |15 Www 1 d 3d-4r-2
(2N 1) 38-4r
[LN(f) ig N
VM
where C" > 0 is constant depending a but independent of f. N, M, and d.
E.3 PROOF OF LEMMA D.2.2
Lemma D.2.2 For any positive integer m 1, there exists deep ReL.U network
Multi F(m + +3, (2, 10, 10, ..., 10,1));
such that Mult, (z, y) E [0, 1] and
Mult (x. y) xzyl < 2 2m-1
for all x, E [0, 1). Moreover, Mult, (2r, Muli,,, (0. v)
20

---

With the application of Published as a conference paper at ICLR 2023
Proof. Given imput (I, 2), the network Mult, (2. y) computes in the first hidden layer
{
( r + y
+
(-(())
(x, v)
2
By using the equality |a|| layer
(x) + + xx) for [0, 1]. the network computes in the second hidden
x +
}
(x, v) +
2
2
Note o (1 ( - E [0, 1]. and o
= +
o
(1
- We apply the
=
network f' on the two components respectively. This gives network of (m + 2) hidden layers with width vector (2, 10...... 10, 2) that computes
v) + o fm
x + y
)) 2
( (1=)
fm -リ y })}
(34)
The network Multm computes (34) in the (m + 3)th hidden layer. Since fm [0, 1]. (fm(z)) (x). In the output layer, the network value is computed as
Multm (v, v) = i' x +
I x- ) Jm
(35)
2
Since Fm is an increasing function in argument, Mult, (ar, v)
>
0, and since fm E [0, 1].
Mult,,, (x, 3) I 1. By identity, zy z follows:
-= and Lemma D.2.1 the error is computed as
x x ) ( x +
) fm
0(( - / )) ))(
[Mult (I, -zyl S fm
2 2-2m1
If either Or 0, by the definition of 35 we have Multm (x, 0) Mult,, (0, 0.
E.4 PROOF LEMMA D.2.3
Lemma D.2.3 For any positive integer m 2 1,N 2 2 and for p= [log( there exists deep ReLU network
Poly E F(L, (1, (1, (I,,,,, (1..
with the depth L = m 31=++(m++t)) (m))))(oog(()) 1) and the number of parameters N < 202NN (m+ such that Poly (x) E [0, _11" and
Polyin (x) x²| < 2-2-1 2m-1 for all jE (1, (1,...,,")
for all x E [0,
Proof. Let us describe the construction of the network Poly (N) Lemma D.2.1 in the (m + 1)th hidden layer, the network computes
(f(x))
with the width p = (1, .,........... 5,2). For approximating x the network Mult,, is applied on the pair (a(x), (f)()))) and for approximating x², the network f. is applied on the (f)().) Therefore, in the {(m + 1) + (m + 4 hidden layer, the network Poly computes
((t)) a (f. (Mult, (z. f' (x))) (fm(( (m)(t)))
(36)
21

---

Published as a conference paper at ICLR 2023
Note that each component in the hidden layer is in [0. 1] by Lemmas D.2.1 and D.2.2 This procedure continued until a following vector is in the final output layer.
Poly m (z). "oly
2" (x), Multm (z, "o (x)), (fm (fm(z))) e [o, 1je"
The resulting network is referred as Poly (N) and has m + (m + ()((l - 1) hidden layers. Recall P [log((N) By the construction procedure of the network, we can compute the upper bound of maximum width as,
[ogg(N)) + 10 (2 (2 + - 11 (00) S 11N,
(37)
where we use [lgg((] S (N)+ in the second inequality. Now, we need to count the number of active parameters in the network. For k E (1...., [log2 (N)1), we compute the upper bound on the total number of active parameters in-between following hidden layers:
Poly!: (x),........ Polym 2* (10)
Polyth (o (x),.... Poly 2*
Poly (z), Poly (x)
(38)
Think a network that takes the hidden layer in the left hand side of (38) as an input, and gives the hidden layer in the right hand side of (38) output. It is easy count the number of active parameters in input, hidden, and output layers, separately as follows:
Input layer
+ 21 (2t-1 = 24
Hidden layers
(m + 24 100 (m + 2) (2 1) + 25 (m + 2) = (m + 2) 2*-1 75).
Output layer
- 10- 10 12 + 1 11112-1-1-1
Since the k runs over {L,..., [log2(N))]] the total number of active parameters can be bounded as:
[Ng]
(m + 2
(m+))
101 201-2"-11
2h-1
-55) 75 + (14. (14. 114.24-1- -6)
[N))
[ogg(N)]
$ (m + 2) 101
2 14.
2
< 202N (m + 33.
The approximation error is proved via induction the number of iterated multiplications P [V)], For P = 1, that is = 2, we have
- fm( 5 2m
by Lemma D For the convenience of notation, denote z" := Poly (xr) for some positive integer assume a following holds
a. For P k
x - انن
< 3 33- 2 2 2-22-mm 2m-1 for j (1.1...., 2k
Then, for p= k. we want to prove
r .ه <
for j (1,...., 2*.
By the construction of neural network and induction assumption, for j E {1...., 2k-13, we have N Tol 3k-2 2 2-2m-1 < 3 2-2m 2-2m-1 For any j E (2k-1 1,...,2t},
24,, find any a,
(1...., 2 1- such that j = Latb__ Mult,n (z (3"5""] s at 5. 1 + 1aa 2thh Multm (5" 2t4)
Then, for E [0, 1].
< x" 2 - _² + I 10" -
-5 =11+ + 1iah 4b Mult (i",z") x²)]
3 2 2m - + zk- 2-2m- + 2 2 < 3h-1, 2 2m-1
By using the fact 13g < 2, can deduce - < p2 and conclude the proof.
22

---

Published as a conference paper at ICLR 2023
E.5 PROOF OF PROPOSITION D.2.4
Proposition D.2.4 Let 0 < < 1,m, N, M E N with 1 S N S d= + 1. For any function f W (8*-1) with > O, define D (f) in (24). Then, there exists a network
F( (d, M2,............................. 22 1),
with depth L = (m + 4)(log,)) (2N) and number of parameters N & M(2d + 404N (m + 3) + 2N + 4) + such that
( - sC,
f1_
-1ffllw -Ifllllwg d2N (1og, (2N)) 2m
(39)
where Cy is positive constant depending on y and a, but not on r, m, N, M f.
Proof. We adopt the shorthand notation denoting [n] = {1, ............. and [nlo == {0, ......n.......... n for
E N in the proof.
Given the input data x E 8d-1, recall the definition of M W (x) in 24 The crux of the whole construction procedure is build the sub-network which approximates (x,- y:) for each i E [M]. First, observe that, by and (23). (u,) can be written as:
2N
k N
k
+ Ag
r - E (o) el 20)! (2 k-2e
(u,)
Σ (1+
1
Σ
(-1)
(40)
k=0
t=
is the weighted sum of univariate polynomials of degree up to 2N. We define a constant Ce...ndd as
for i [M]. The key observation is that Eq. (40)
k + AO (-1)TT e+ 20)2
Ax) in
(41)
N
[(AG) 26)!
For i E (1...., M). set Ci,q as
EuENEA (- Ck..mnderd)) if u4 < and g odd, EEEDEA (cH...nde,rs))
ai.q
(42)
otherwise,
where for each {O...., 2NJ. the set Ag is given by A, = ((k,E) [2N]o [[4/]]o k 4). Then, (40) can be re-written as (N,r(u:) Eg= Qi.q 1
1. The Network Construction. Now, we are ready for the construction of f. Through Lemma D.1.4, we know that there exists y [yI.....NM] that satisfies the bound (D.1.4) Then, for each i E [M], we put y; E Sd-1 a weight vector that connects input x to the (2i thth and (hi)th nodes in the first hidden layer. Through this, f computes in its first hidden layer x + (().
the identity [z| = (xx) + +((=))) (x)) ...., (x.,,......x.))))))) of (x,) E [o. 1]2M Then, by for x E R. the network computes in its second hidden layer x x- (o(( ([le)),,..... ),....ar [uml)) E [0. where u4 = (x, E [-1,1] for E [M]. Since a((u]) = |us] E [0, Poly|2N; with P [logg(2N)] is applicable for each {lua))// and it generates Poly!. (Iu.) with 9 at most 4N. Set Bmax max,=1.....M Σ 04,4 Poly? (1 (lw,l) Using the definition of the constant dg.q. the network computes the (m 4) [og, (2N) th hid- 2N
Poly. (|u=)) )) + 2Bmx)...... a (E Pol.y (IuM 1) + 2Bmxx) RM den layer {o 2N
By the definition of Baax, it is easy to see each component in the hidden layer is positive. Set the weight of output layer as 1 F, (y Define C((u,)) : -g 0i, Poly (lus)) + 2 Bmax Then, given the data = [y....., }M). the network f computes its final output as f(x) = M F-(ys) ((x..))
1 EN Fr(y;) (C(I(x,))))) - 2Bmax) N
The Width and Number Active Parameters of f. By the construction of network f and the result of Lemma D.2.3 it is easy the maximum width of the network is 22N M. Now,
23

---

Published as a conference paper at ICLR 2023
work counting the number of active parameters in the network as
From Input to 2nd hidden layer
2Md + 2M.
From 2nd to ((m + 4) (2N)) - th hidden layer
404NM (m + 3).
From ((m + 4) [og, (2N) 1) hidden layer to output layer
(2N +1M M +1.
Summing up the total number yields the desired result.
3. Approximation Error Computation. remaining thing is to calculate the approximation error:
M
M
1% ( - - = sup xES
Fr (x())
EN,,
1
Σ
Fx(r))
((x,
M
M
1=1
Illlll (S4-1) ||Ex.r (ENN.))
(43)
Recall the definition of okig in (42). Using Stirling's s Formula, I(++1) 2 ()) O1+((())))
we observe the behavior of Gegenbauer coefficient in (4) where AG = A-2 > da +1
2 N, and find
2
that it can be bounded as C' Aa-e. E 22 d.
2 (LLdd), where C' 0 is a constant independent of
For & 10.1..... ,N,] combining the facts (1 + Ax) 1, n.) S d-2 yields
A+ Ao s for k - 2N 1
2(d + 1) with ÀG
2
Ae C, 2- d
(44)
where C, > 0 is constant dependent on a and 17. Recall (EN,,) ((x,,)) = Eg Oj.g
Poly% (x, 1) and note that En |ajaa Ex ElEd Cceendendd Then, we have
[|,,r L(N,,) S
sup
max |u2 Poly?, (w)
uE(0.1) (0......N)
k=U
2N C
(1 (1og2(2N))
S
2 2m
(dd)
k=0
1$1 D.2.3 and 44) in the second inequality. Using Σ
where we used the result from Lemma
===0 (2dj
2 in the last inequality yields the claim.
E.6 PROOF OF COROLLARY 3.3
Corollary 3.3 Let 0 < a. 3, with y > max and N e N with S s do + For any f E W (Sd-1) with r > 0, we have
3d-2 with some constant C1 0 independent of there exists (I) For 3d-2 - C1 r network
j(( F (L, (d, G6N, 66N, ... 66N, 16 ,N) with depth I O (d logz d) and the number of active parameters N O (d
such that [ f
j(n) f(n
s fl.fll,ylfflww (sa-1jd de where C² C),,, is constant depend-
ing only C1, B.y.
(II) For O(1) and M = (gdd2d)) there exists a network
jul) F(I, (d, 22N 22N 1).N)
with depth L 0 log, d) and the number of active parameters N = O (gdd#a) such that ||s f(1) only on 17 a. 3,7.
S C &ho.s,y,lll (se-iyd-a where C² Ch is a constant depending
00
24

---

Published as a conference paper at ICLR 2023
Proof. By the results of Theorem 3.1 for 1 I N S d 1, we have the following inequality on the approximation error
J 11e s s 1Illlll 1)x
6 N
N (2N + 11)
max
N
dd (Po()0((22))
(45)
VM
where C is constant dependent 7), and independent on d,r, N, M or f. We divide the proof into two cases.
(I) (d) and any integer M 2
For the first term in 45 since N = [d we know that N = Old = O(d-d) "") with any
0 < 3 < 1. This is due to the assumption that 3d-2 and d o(r).
C1 S r S 3d-2 which implies d = (rr)
For the second term in 45 since N = [d with a < 1, we know that it bounded by
(2N
3d-dr
6
d
3d 1r+4
(3da)
3d-4r
(46)
VM
M
As Ci rrs we know the term on the right hand side of 46 can be written as
G +0())30111) /VM To show that the bound is of order Old-d"), we multiply the bound by dd take the logarithm, and find that for any a, <
log ( ddd " 40(1)
d
S
log Te
+ (d" + d + O(1)) log(d) + -00
πe
as d + 0c. Hence, there exists constant Ca.3 > depending only on C1 a, such that
N 3d-
2N +
3d-4r
S Ca
M
for any fixed M E N. In our proof, we simply choose M = 3. For the third term in (45). take m [dr] with max(a, 3} < y then there exists a constant Ca,p, depending on a, B, such that
d (No))((2N)) 2m < 2d +2 2 + log)
2m < add 2 2m S Ca,
2-2m
where (2d + 2) & (4dg < 2 + +ogg(() is used in the first inequality, and the last inequal- ity follows from the same argument above, of multiplying with dd and taking the logarithm. Combining all the analyses above, we have
i 11_- S C, (sa-1dd
where C n..0. > 0 is a constant dependent on 17, a, 3, ?, and C₁.
Recall from Proposition D.2.4 f is network with depth L (m + +) [og, and number of parameters A < M (2dd + 404N (m + 3) + 2N + 4) + 1. By simply plugging-in m = [d7],
N = [d and M = 3, we have L = O(d (d)) and V = O (dmax(a+>.1)).
(II) r r= O(1) and M = O
For the first term in 45 since N [ we know that - O(d
For the second term in 45 since N = [d with O < a < 1, we know that it is bounded by
N 3d 1r
(2N 1) 34-4r
6 d 3d- 4r46
(3do)
3d-dr
6
d +0 !ddd
(47)
M
M
M
25

---

Published as a conference paper at ICLR 2023
Take M- d) multiply the bound 0 a < 1,
47 by dd take the logarithm, and find that for any
+ (d + + + O(1)) log(d) + -0, as d ++ 00. Hence, there exists constant Ca.B > 0 depending only on C1, a, B such that
log
dd do +0(1)
log 4
Te
N 2 (2N + +1) 4d
ne
I Ca,ed d" S Co
VM
for M = (d) For the third term in (45) take m = [d'] with maxfa, 3} < y < 1, then there exists constant 0,,0, depending a, 5,7 such that
dLN (log, (2N)) 32 2-2m < ddd +2 (2 logz (d) 2-2m ddd 2-2m 2m " Ca. d I Ca.a.ad
where log, (2d + 2) S log2 (4d") < 2 log2 is used in the first inequality, and the last inequal- ity follows from the same argument as above, of multiplying with dd and taking the logarithm. Combining all the analyses above, have
|
where O n.o,,r > 0 is constant dependent on 17, a, 3, 3,7, and C1.
Recall from Proposition D.2.4 f is network with depth parameters N & M(2d + 404N (m + 3) + 2N + 4) + 1. By simply plugging-in m = [d]],
(m + 4) [log (2N) and number of
N [ and M = O(9d we have = Od (d)) and = o (g'd"d).
F PROOFS OF PROPOSITION 4.2, THEOREM 4.3 AND THBOREM 4.4
F.1 PROOF OF PROPOSITION 4.2
Proposition 4.2 Set E (0, 1). Then, with probability at least 1- 6, we have
(TTBF)) - {fp) s CB... (Pdim(F) -log(n)
|lf f + 115- follse)
(48)
Vn
where Cn.8.f is an absolute constant dependent on B independent on r, d.
Proof. Since In is empirical risk minimizer in 112 have Ep(()) S Ep(l) for any fixed
E F and (T s (Fa). Then, we have following decomposition:
- = -()) (E En(())))
- (Eo(TTTN)-E(())) (E)(f) -
(Eo((TBB)) -
((ED(S) ((E)(f)-E (66()) -(00)(---0())--00---)-)-++)----- ((()))+((())))))))))) ((()) (8())))((()
E((.)))
((((TTT)) - - - Eo(fo))
(49)
+ +((E(()) -bo())))(()))----))))))))))))))) (E()) -(()))) + (((f)
Let Je: = (Tal Vʃ E F} and define two quantities:
Fr) {E()) {(T)) - (E)(J)
{n(so) -()))) - EfEJn,
Sy(n = (()) -(f)) YfEF.
Step 1: Control Fn). The following concentration incquality is needed for controlling the
term.
26

---

Published as a conference paper at ICLR 2023
Lemma F.1.1 [Theorem 11.4 of Györfi et al. [2002]] Assume lyl I B almost surety and B 1.
Let a, B > O and 0 1/2 F is of functions f Rd 1- B, B), then for any f E F,
we have
se(
E(f,))
BE
F, ,11 (l2)()) )
c² - s)mn
2 21-sup sup
exp
208
214 B)
D
Lemma F112 [Theorem 6 of Haussler 20188] Let > 0 and F be a set of functions f [- B, Bl. Then for any E (0, B), there holds
-
Pdim (F')
2eB
BeB log
M(s,F (I
(50)
Recall a classical relation between s-packing number and E-covering number that asserts
M(2e, F, -|,,,)),,))))))))))))))),))))))) S (e,,,, (I,, S M,s (I),,
(51)
for any E > 0. Combining (50), (5T). the facts log < z, Vo 0, and Pdim(FB) I Pdim(FF
(See Maiorov & Ratsaby (1999), page 297), have the upper- bound (Ne,, FB, (D))) as follows:
2eB
2eB
Pdim (Fn)
BeB
2Pdim
W(,,FB,ll (I))) 2
log
2
(52)
Then, taking 5/2 in Lemma F.I.1 using the upper-bound covering number in yields the lower bound for the confidence level in Lemma (FI.I) as follows:
(52
- sup.N
Fn, 1l -R.11-ILL.C)))
Qn
exp
40Bn
25
2 11-CB exp
2 Pdimmm)) log(n) 2568 B4
(53)
where Cn 0 is some absolute constants dependent on B. Choosing a in (53) such that
CB,5 Pdim (F) log(n)
π
with properly chosen CB.S 0 absolute constant dependent B and 8 yields the probability of following event is least 1 g.
PFim(FF)loo(n 1 E(TDff)) E((p)
(1, S CB.5*
(54)
n n
Step 2: Control F), Define random variable 1 on 2 X' x to be
</==) (u [(x)) (y fp(x))²
Since In(2)] < (3B + ) then In(2) E[n(2)]] 2(3B |lf lxc) It is also easy to x² < E n < (3B + [1f Il fa Then, by the one-side Bernstein's inequality (see
Lemma H.2 have
I S2(n, <E) 21 26)21-0x7 {
n
(Ilf 2(3B + 11fl 2 fp113- + +30)
Taking 5 exp
ne? 11 ( +3e)
AAA=22(33 11) |l f and
2(3
solving the quadratic equation with respect to yield the following inequalities with absolute
27

---

Published as a conference paper at ICLR 2023
constant C. 0:
Alog (3) + V A2 log (3) + 9MABII log (3)
3n
2.A 2Allg (3)
log (3)
+
AB
3n
|l. -
S CB...
Vn
where the first inequality, the facts Va + b S Va + vb for a, is used, and CB. is constant dependent on C, B and f. Then, with probability at least 2. we have
1f-
S2(n, S CB.
(55)
Vn
Step 3: Combining Everything, Note & {f) - {(f) = 1lf -fel S 11f - f Then, plug-
ging the (54) and (55) in (49) yiclds the claim.
F.2 PROOF OF THEOREM
Theorem 4.3 Suppose Jp E (84-11 with r > O. A network Jn from (6) with choices N 3d InsaF 1, M = [n 1, and m = [ Taafar (o))(n)] yield the bound on the excess risk with
probability at least 8 as follows:
E(TMMM) - E(P)
SCBmo, max
6 ( 2N+ { (3d + 4r)2 (n))*,,
6rd
aNN 213133
(56)
where C. depends on B, 8, f and independent on d, r and n.
Proof. Let 0 <a < 1,m, N, e N with N & do +1. Then, for fo E (Sd-1))). recall
from Theorem D.2.4 that there exists network
jE FL, (d, 22N 22N 22, 1),N)
(57)
with depth L (m + [og, [2N) and number of parameters A M(2d + 404N (m + 3) + 2N + 4) + such that the corresponding network's approximation error is bounded as:
rell_ - s C" ll flllw (Se-1)
|
(G) N+
3d-4r-2
(2N 1) 3d-4r
max N-r
dRN (2o()oo((2.)) 22-222 2m
(58)
M
where C constant dependent on 7) and independent on d, r, N, M and f. Since the network width is 22N M, the total number of units across the L-hidden layers (i.e., U1) of f is bounded as
4 < 22N (m + (2N))
If Nm = o(d), is easy to see N (Md). Recall from the result of Lemma H.1 the pseudo- dimension of function class F in 57 is bounded as follows: for some universal constants C 0:
Pdim(F) C 7mmMd [1og log (mMN[loog
(59)
28

---

Published as a conference paper at ICLR 2023
Plug the (58), (59 in 48
from Proposition 4.2
fm - (fp) & CB
mMd
log(n) [log2 (N) log (m.MN(log2(7)))
Bound for Pdimi FF) F))log(()//
N+ 3d-dr-2
(2N + 1) 3d-dr
max N
4
a2a (10g2(2N)) 2-mmm J/V1
M
Bound |5- /v2
max 2-2r [
2N sd-am-2 (2N 2d
N (20g)
Bound for ||f
(60)
where Cn... depends B, 7/, 8, and independent on d, r and n. Then, under the regime 1 < N < d + for some 0 < < 1, choices of m = | logy(n)), N
[n and
M = n IF
3d
make the fraction of the first term in (60) simple as follows:
2
2r (3d + 4r)2 (og2(1))
[log2(N) log (mMN[logs(A)))
3d + 4r (og2(n) log (l0g2(n) 3a14
3d + 4r (l)g2(n))?
Then, with the same choices of m, N, M as above, we obtain the bound on the excess risk as
Fa) E(Tr)
6rd (3d 4r)2
(n))* (-)) $ ggN+ go saN }
(
S CB max
1
This concludes the proof.
F.3 PROOF OF THEOREM 4.4
Theorem 4,4 Suppose fp E W (10,17)) with r > O. A network fn from 2 with choices N [nzdrr], 1, and m 242r logz(n)] yield the bound on the excess risk with probability at least
1 - 8 as follows:
{(TMfA) E(fo)
(61)
CBR.KKK max {
[loggld+ (r (logg(n))² 21+ 2 + +
where CB. depends on B, v, 5, K and independent d, and n.
Proof. From Theorem of "Schmidt-Hieher (2020), for any function S, E C7((0, 1]d, K) and any integers m 2 and N 11d (K I)e", there exists a network
i F(, (d [r]],. 6(d 1).N
(62)
with depth L= + (m + 5) + (o v)]) and the number of parameters A < 141(1 d + 3m + 6), such that
<2K + + dl + i 1 10 1/
m &
N-.
(63)
29

---

Published as a conference paper at ICLR 2023
Then, similarly with the proof in Theorem 4.3 of F in 62 can bounded as
by the result of Lemma H.1 the pseudo douudd-iimensinn
Pdim(F) = C. Nmd [dg ((d [r]]m (d
(64)
for some universal constants C > 0.
Plug the (63 and 64
(88) from Proposition 4.2 Then, we obtain the bound on the excess risk as
follows:
E fm) Efr) S CB,,K
N
log(n) (d + r) (r) ((d + [r]]mN [log2 (d V r)])
n
Bound for Pdim( -o)log()//
+ (11 + de +,2 33 (00555/// ///nn
Bound for [8-1oll../v
(11 d + N22 2m + -
(65)
Bound for f-
where CB,s.K depends B, 8, K and independent d,r and Note that use (a + b)2 s
2a + 25 for all a, b E IR for getting the bound on f - fp We choose the N = [n म and
2rta (ng2(1)] Then, fraction of the first term in (65) can be bounded m
d loga (n) naata log2(d < loga ((d + [2))
log (d (d+ [r])
2r +
Then, we obtain the bound on the excess risk as
(TM ((e)
$ CBB.o.KK max
[loga((d (r))))))()))))(++++)))))))) (log,(n))² (1 r2 + +d))362 32r Faa
This concludes the proof.
G PROOF OF APPROXIMATION RESULT FOR CNN: FANG ET AL. (2020)
Theorem C.1. Let 2 < $ d 1, and B, N, M E N with 1 < N < d' + 1. Let > Md-11 Dj (2B + (d JS)/d), and D: [[d JS)/d). Then, for any function S-1
WT (8d11) with > 0, there exists network JCNN H...D,,D..S with the number of parameters
N & J(3S + 2) + + 2B + 4 such that
1 fcNN|
< " IIflll max { N-r,
G d
3d 4
(2N +
3d dr
22N
N
M
B (66)
where Ca is a constant dependent on n, a, and independent on d, r, N, M or f.
Proof. By the inequality (5.9) in the paper Fang et al. (2020), have
Ix ( jCNN]] < [1Illls IKE - L.(EN.))ll(11..)
(67)
30

---

Published as a conference paper at ICLR 2023
where (E(,N, (t) is univariate function for t E [-1, defined in Lemma in Fang al. 2020 Now, we work on controlling llSN,r (((tNn))lcc--..))
|| (((EN)))le)-1111 S (w,,,, 1/B)
2
- --
B
8N2
(KN.rlloi-2n)
B
8N2
k
k=1
N2
2N
J2N
k=1
8CaN²
LN
r
B
1-1
In the first inequality, we Lemma in Fang al. (2020), where w(E,,r 1/B) is modulus continuity of En.r given by
w(EN,r 1/B)
sup {IEN,-(V) EN + 1) + 1d51/B
In the second inequality, we use definition of modulus continuity EN.-. the third equality, since EN,, is an algebraic polynomial of degree at most 2N, by Markov's inequality, have |I I (2N))11EN=-lle--L.. In the fourth inequality, we have the bound 2N
(EN.11lc1-1.11 k= k""((k d) by Corollary 1.2.7 of Dai & Xu 2013). Employing Stirling's formula d! 22 L) (1 ((I/d) in (K, d) yields (Nk, d) s C. for 0 < S 2N and some constant C. depending on a but independent d. In the last inequality, we used the following inequality:
k 1+
2N
Σ k- <1+
Σ
x Jd
x T
dx
S
r
Now, combine result from Lemma D.1.2 and Lemma D.1.4, and conclude the bound in (66).
H USEFUL LEMMAS
Lemma H.1 [Theorem 6 of Bartlet et al. (2019) Consider the function class F computed by feed-forward neural network architecture with N parameters and U computation units arranged across L layers. Suppose that all non non-outpul units have peecewise-polynone with p pieces and degrees no more than and the output unit has the identity function as its activation function. Then the VC-dimension and pseudo-dimensn dimension of class F is upper bounded by
activation functions
[F) Pdim((F) S C. CLNNoog U) + (ooNoo
with some universal constants 0.
Lemma H.2 [Theorem 2.8.4 of Vershynin (018)) Let be a random variable on a probability
space Z with mean E(n) μ. variance o² (1) o², and satisfying (n(2)= E(n) < B,, for almost
z E Z. Then, for any E > 0,
n
n
P
Σ (2.)) p u<e 21 exp
2 + Bys
31


Reviews:
[{"review_id": "PlrCu1jSZ-", "reviewer": "Reviewer_JPQC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors study the approximation of functions using neural networks with ReLU activations. They showed that, for the functions defined on some Sobolev spaces over the d-dimensional unit, there exists a fast approximation error rate of $d^{-d^\\beta}$ by some neural networks, which is very sharp. Also, the construction of the suggested neural networks is given.", "summary_of_the_review": "In summary, I think the contribution of this paper is enough and this paper is suitable for ICLR, as explained above.", "strength_and_weaknesses": "The main results in this paper will certainly help us have a better understating of the approximation of deep neural networks from a theoretical way. The techniques in this paper may be extended to more general architectures.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "H3S8Rm_z-UJ", "reviewer": "Reviewer_52e1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper concerns the approximation power of ReLU FNNs for Sobolev (or actually Hölder) smooth functions defined on spheres. This paper constructs ReLU FNNs with certain architectures to obtain their approximation results. The main idea is to leverage approximation capability of the homogeneous harmonic polynomials on spheres. The obtained results are mainly compared with those in Schmidt-Hieber (2020), which nevertheless concerns the ReLU FNN approximation on functions defined on $d$-cubes. By comparison, it is claimed that their approximation results can alleviate the dependence of network size (number of total parameters) on dimension $d$ to achieve similar approximation error bounds in Schmidt-Hieber (2020). In addition, the paper has also discussed on the approximation results when the smoothness of the target function $r$ varies w.r.t $d$.", "summary_of_the_review": "In general, the paper is well organized with a clear presentation. This paper concerns the approximation power of ReLU FNNs for Hölder smooth functions defined on spheres. This paper constructs ReLU FNNs with certain architectures to obtain their approximation results, while a large part of the proof follows that of Fang et al. (2020). The most notable difference between Fang et al. (2020) and this paper is that this paper track the explicit dependence of the constant factor on $d$. Besides, several major questions raised in “Weakness” part need to be addressed.", "strength_and_weaknesses": "Strength:\n1.In general, the paper is well organized with a clear presentation.\n2.The paper derived new approximate results for Sobolev functions defined on spheres in the sense of tracking the explicit dependency on $d$ in the constant factor compared to existing ones. \n3.The paper talked about the results when the smoothness $r$ varies with respect to dimension $d$.\n\nWeakness\n1.The obtained estimation error rate does not achieve the expected optimal minimax rate.  Regarding to the comparison in Table 1, it looks a bit weird for me since sphere $\\mathcal{S}^{d-1}$ is a subset of the cube $[0,1]^d$, but the estimation rate on a subset \nIs even slower. Is there a way to fix it? Or is there a reasonable explanation?\n\n2.Regarding to the main result in Theorem 3.1, the approximation error has basically dependence $d^{N+d} \\times N^{d}/\\sqrt{M}$. This result seems also cursed by $d$ in numerator, otherwise one has to set a very large $M$, e.g. $M=d^d$ to get a good approximation accuracy. Please explain more on this.\n\n3.The condition $r=O(d)$ is restrictive. The author may explain more on this condition, especially it’s better to give an example on in what scenarios the condition $r=O(d)$ holds. In addition, I wonder if the condition $r=O(d)$ can be plugged in other existing results, e.g., Schmidt-Hieber (2020) to have a comparison with the obtained results in these $d, r$ varying cases. If it’s not possible, please also explain why $r=O(d)$ can not directly be plugged in other results.\n\n4.The comparison can be fairer since Schmidt-Hieber (2020) focus on the approximation on hyper-cubes instead of sphere. The authors can compare their results with Fang et al. (2020) and Feng et al. (2021) since a large part of the proof follows that of Fang et al. (2020). The most notable difference between Fang et al. (2020) and this paper is that this paper track the explicit dependence of the constant factor on $d$. In addition, though Fang et al. (2020) and Feng et al. (2021) considered CNN approximations, Zhou, D.X. (2020). has shown that any CNN can be equivalently computed by a FNN with parameters at most 8 times larger than that of CNN. In light of this, the author should compare their results with Fang et al. (2020) and Feng et al. (2021).\n\n5.Within the studies of ReLU FNN approximation, the author can also compare with more recent results which have already improved the results in Schmidt-Hieber (2020). For example, Shen, Yang, and Zhang. (2020) and Lu, Shen, Yang, and Zhang. (2021) have already demonstrated the clear dependence on dimension $d$ for ReLU approximation results. In line with these works, Jiao, Shen, Lin and Huang (2021) has also shown the explicit dependence of ReLU approximation results on $d$ as well as obtained polynomial dependence results.\n\nMinor comment:\n1.For reference, the issues about the dependence on dimension $d$ was also discussed in Ghorbani et al. (2020).\n2.The obtained approximation results are for Sobolev function space $W^r_\\infty$, which is actually Hölder function space. This is also mentioned in Appendix A.\n\nReference\n\nSCHMIDT-HIEBER, J. (2020). Nonparametric regression using deep neural networks with ReLU activation function(with discussion). Ann. Statist. 48 1875–1897.\n\nDing-Xuan Zhou. Theory of deep convolutional neural networks: Downsampling. Neural Networks,\n124:319–327, 2020.\n\nSHEN, Z., YANG, H. and ZHANG, S. (2020). Deep network approximation characterized by number of neurons.\nCommun. Comput. Phys. 28 1768–1811.\n\nLU, J., SHEN, Z., YANG, H. and ZHANG, S. (2021). Deep network approximation for smooth functions. SIAM\nJournal on Mathematical Analysis 53 5465–5506.\n\nJiao, Y., Shen, G., Lin, Y., & Huang, J. (2021). Deep nonparametric regression on approximately low-dimensional manifolds. arXiv preprint arXiv:2104.06708.\n\nGHORBANI, B., MEI, S., MISIAKIEWICZ, T. and MONTANARI, A. (2020). Discussion of: “Nonparametric regression using deep neural networks with ReLU activation function”. Ann. Statist. 48 1898–1901.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "6iHc-_FECFj", "reviewer": "Reviewer_JVzW", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper investigates the theoretical properties of deep feed-forward neural networks (FNN) with ReLU activation function when the target function belongs to a Sobolev space defined over the $d$-dimensional unit sphere with smoothness index $r>0$. The bounds for both approximation error and excess risk are derived for two different regimes as $d\\rightarrow\\infty$, which explicitly depend on the data dimension $d$ as follows\n\n1. In the regime where $r=O(1)$: at most $d^d$ active parameters to get the approximation rate of $d^{-C}$ with $C>0$ being a constant; Moreover, the excess risk bound has a $d^d$ factor\n\n2. In the regime where $r=O(d)$: at most $d^2$ active parameters to get the approximation rate of $d^{-d^{\\beta}}$ with $0<\\beta<1$; Moreover, the excess risk bound has a $d^{O(1)}$ factor\n\nThe authors make comparisons to the case where the input space is d-dimensional cubes and highlight the novelty of their results.", "summary_of_the_review": "The paper presents novel results on how the approximation rate (excess risk) of deep ReLU FNN depends on the data dimension when the input space is a high-dimensional sphere, which provides new insights into the approximation analysis of deep neural networks and will be of great interest to the community of deep learning theory. The intuition is clearly explained and the theorems are technically sound.", "strength_and_weaknesses": "$\\textbf{Strength}$\n\n1. To my best knowledge this is a novel contribution that broadens the understanding of deep ReLU FNN for approximating Sobolev functions defined on the high-dimensional sphere ($d\\rightarrow\\infty$), a topic of great interest to the ICLR community\n\n2. The paper explicitly describes the dependence of the approximation error and excess risk on the data dimension $d$, which shows that the curse of dimensionality may be avoided when $r=O(d)$.\n\n3. Excess risk bounds are derived through the lens of pseudo-dimension, which removes the boundedness requirement of the weight parameters in the literature, e.g., Schmidt-Hieber (2020).\n\n4. A different phenomenon is observed compared to the case for $d$-dimensional cubes, which is interesting and novel.\n\n$\\textbf{Concerns}$\n\n1. Can the results or analysis be extended to other neural networks, e.g. convolutional neural networks?\n\n2. Will it make any difference if we consider the regime $r=O(d^\\alpha)$ for some $0<\\alpha<1$?\n\nMinor typos:\n\n1. In Table 1, 4th row & 3rd column, should $O(d^2)$ be $O(d^d)$?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster