Optimal Convergence Rates of Deep Convolutional Neural Networks: Additive Ridge Functions
Authors: Zhiying Fang
Guang Cheng
Venue: Accepted by TMLR ()

Abstract: Convolutional neural networks have shown impressive abilities in many applications, especially those related to the classification tasks. However, for the regression problem, the abilities of convolutional structures have not been fully understood, and further investigation is needed. In this paper, we consider the mean squared error analysis for deep convolutional neural networks. We show that, for additive ridge functions, convolutional neural networks followed by one fully connected layer with ReLU activation functions can reach optimal mini-max rates (up to a log factor). The input dimension only appears  in the constant of convergence rates. This work shows the statistical optimality of convolutional neural networks and may shed light on why convolutional neural networks are able to behave well for high dimensional input.

Published in Transactions on Machine Learning Research (01/2023)
Optimal Convergence Rates of Deep Convolutional Neural Networks: Additive Ridge Functions
Zhiying Fang
fangzkkyjng@@spp..ee..cr
Institute of Applied Mathematics
Shenchen Polylechnic*
School of Data Science
Chinese University of Hong Kong, Shenzhen
Guang Cheng
guangcheng@stat. ucla. edu
Department of Stalistics University of California, Los Angeles
Reviewed on OpenReview: https: openreview. net/ forum? id= Q==XXmV7BBBFF
Abstract
Convolutional neural networks have shown impressive abilitics in many applications, es- pecially those related to the classification tasks. However, for the regression problem, the abilities convolutional structures have not been fully understood, and further investigation needed. In this paper, we consider the mcan squared error analysis for deep convolutional neural networks. We show that, for additive ridge functions, convolutional neural networks followed by fully connected layer with ReLU activation functions can reach optimal mini-max rates (up to log factor). The input dimension only appears in the constant of convergence rates. This work shows the statistical optimality of convolutional neural net- works and may shed light on why convolutional neural networks are able to behave well for high dimensional input.
1 Introduction
Deep learning, based on deep neural networks structures and claborate optimization techniques, has achieved great successes and empirically outperformed classical machine learning methods such as kernel methods many applications in areas of science and technology (Kingma & Ba 2014 Le al. [001]] LeCun al. 2015
Schmidhuber 2015). Espocially, convolutional neural networks were considcred to be the most powerful tool
for various tasks such image classification (Goodfellow et al.
2016
speech recognition (Hinton et al.
2006) and sequence analysis in bio-informatics (Alipanahi et al.
2015
Zhou & Troyanskaya, 2015 before
the appearance of the Transformer structures (Vaswani et al.
2017
Dosovitskiy et al. 2020). However,
compared with significant achievements and developments in practical applications, theoretical insurances
are left behind.
Recently, many researchers in various fields have done great works trying to explain the mysteries of convo- lutional neural networks (d' As'osi et al. 2019 Neyshabur 2020), and most of the existing works focus on the approximation properties of convolutional structures. For vector inputs, universality result for convolu- tional neural networks is first established in Zhou (2020b). Afterwards, Zhou (2020a) further illustrates that deep convolutional neural networks are at least as good as fully connected neural networks in the sense that any output fully connected neural network can be reconstructed by a deep convolutional neural network with the same order of free parameters. spaces on the unit sphere or taking an additive ridge form can be approximated by deep convolutional neural networks with optimal rates. For square matrix inputs, authors in Petersen & Voigtlaender (2020) prove
also shown Fang et al. (2020) that functions Sobolev

---

Published in Transactions on Machine Learning Research (01/2023)
that if the target function is translation equivariant, then convolutional structures are equivalent to fully connected ones in terms of approximation rates with periodic convolution. Recently, He et al. (2021) derives a decomposition theorem for large convolutional kernels and enables convolutional networks to duplicate one hidden layer neural networks by deep convolutional nets including structures of ResNet and MgNet.
For approximation ability of fully connected neural networks, Yarotsky (2017) establishes upper and lower bounds of the complexity of deep ReLU networks when approximating functions in Sobolev spaces. Petersen & Voigtlaender (2018) also derives optimal approximation ability for piccewise smooth functions with fixed layer ReLU networks. For functions in Besov spaces, approximation results are presented in (Suzuki (0018) Compared with numerous works concerning mean squared error analysis of fully connected neural networks (Suzuki 2018 Imaizumi & Fukumizu 2019 Schmidt- Hieber et al.) 2020), only very few papers attempt to understand the convolutional structures from a statistical learning perspective. With the same spirit in ZZhu (2020a), authors in Oono & Suzuki (2019) show that any block-sparse fully connected neural network with M blocks can be realized by a ResNet-type convolutional neural network with fixed-sizod channels and filters by adding ((M) parameters. Consequently, if a function class can be approximaled by block sparse fully connected nets with optimal rates, then it can also be achieved by ResNet-type convolutional nets. Authors prove that ResNet-type convolutional neural networks can reach optimal convergence rates for functions in Barron and Hölder classes by first transforming a fully connected net to a block sparse type, then to ResNet-type convolutional nets. Authors in Mao et al. (2021) first establish approximation results for deep convolutional neural networks with one fully connected layer when the target function takes a composite form as f Q with a feature polynomial Q and univariate function f. Two groups of convolutional structures are applied to approximate functions Q and consecutively. Then mean squared error rates are derived for the function class f Q. Analysis shows that the estimation error decreases to minimum the network depth increases to optimal value, and then increases as the depth becomes larger. According to the mini- max lower bound derived in our paper, the rate is sub-optimal. Universal consistency of pure convolutional structures is recently presented by Lin et al. (2021) in the framework of empirical risk minimization.
Compared with previous works on mean squared error analysis of deep convolutional neural networks, we show that functions possessing inherent structures &-2 x in an additive form can be directly learned by deep convolutional networks. Formally, we consider mean squared error analysis for deep ReLU convolutional neural networks in the estimation of additive ridge functions. The function class takes the form of
m
Σ SelEs
where for each i, Si satisfies some regularity conditions, & can be considered as a projection vector and is the inner product in Rd. This function class is also known as the additive index models (Yuan 2011 in statistics and related to the projection pursuit regression introduced by Fricdman & Stuctzle (1981p. It
has been shown in Diacouis & Shahshahani (1984) that this function class can be used to approximate any square-integrable function to arbitrary precision. A precise definition will be presented Section 3.
For additive ridge functions, various invostigations have been done including convergence rates, identifiability iterative estimation in Chen [191]] : Chiou & Müller (2004); Ruan & Yuan 2010); Yuan 2011 Bach (0117).
Also, with a similar structure to the function class above, minimax convergence rates have been presented in
Klusowski & Barron (2016 2017) when all the fi are sine functions or Hermite polynomials. However, none of these works presents mini-max lower rate for this type of functions when f, possess different regularities. Though optimal convergence rates are achieved Ruan & Yuan (2010) by traditional reproducing kernels with regularized least squares scheme, shortcomings of this mothod are quite obvious when comparing to neural networks. For example, to achieve optimal convergence rates, the best regularization parameter is usually related to the regularity of the target function which is practically unknown and is often decided by cross validation. However, convolutional neural networks are more automatic in the sense that the function smoothness is not required when implementing the algorithm. Also, the smoothing spline algorithm is applied in a backfitting manner, whereas the convolutional neural network is more generic.
We show that deep convolutional neural networks followed by one fully connected layer are able to achieve the mini-max optimal convergence rates for additive ridge functions by a careful analysis of the covering number of deep convolutional structures. The additive index m would affect the depth of our networks in linear
2

---

Published in Transactions on Machine Learning Research (01/2023)
way which indicates the importance of depth of neural networks when the target function is complicated. The inherent structures I can represent different localized features of input when &s are sparse. The input dimension only appears in the constant of the final convergence rate.
In summary, the contributions of our work are as follows:
We conduct in-depth covering number analysis for deep convolutional neural nelworks presented in Fang et al. (2020). Thanks to the simple structure and few free parameters of convolutional neural networks, wc derive small complexity of this hypothesis space.
We present mini-max lower bound for additive ridge functions. As direct consequence, the lower bound also applics when & z is generalized to any polynomial function ((r). We show that for these two types of functions, lower rates are dimension independent.
By combining the approximation result in Fang al. (2020) and our covering number analysis, show that deep ReLU convolutional neural networks followed by one fully connected layer reach optimal convergence rates for the regression problem for additive ridge functions and the input dimension only appears in the constant of the upper bound.
2 Problem setting
We first give brief introduction to the structure of convolutional neural networks considered in this work. For a sequence w = (wx) supported in 1, ,}} and another one x = (It) supported in {1,2, ,), the convolution of these two sequences given by
(w r); = Σ
wi b = Σ
wi TR,
i E,
KEZ
k=
which is supported in {1. D S}.
By applying this convolutional operation, we know that the matrix in each layer of convolutional neural networks should be of the form
WD
0
0
0
W1
160
0
0
Ws
Wp
WFg
W1
100
THP
(1)
WS
W1
w0
Wg
00
0
0
with TH E (D++8)xD For input x = (I1, F2, ... xz)) E Rdd, a deep convolutional neural network with J hidden layers (10); Rdd + Rd, and widths {d, d, 5(1) can be defined ileratively by ((()))) = x and
1x) = o (T() 1(1-1) 1) (x) 865)
j = 1, I.....J
if we denote TÚ) = (1) with D = dj-1 and S s(6) for j = 1, ... J. Throughout this paper, we take identical filter length (6) S N which implics {d, d + jS} and take the activation function as the ReLU,
a (ω) max (0,z),
E R.
3

---

Published in Transactions on Machine Learning Research (01/2023)
Since the sums of the rows in the middle of the Toeplitz type matrix (1) are equal, we impose restriction for the bias vectors (b01))=1 of the convolutional layers
(0) S+1 ...
(i)
j I......,J.
(2)
S
After the last convolutional layer, we add one fully connected layer h(++)) with restricted matrix F(J+1) and a bias vector 6(++1), Precisely, we have
(x) = ( - -b(++1)
For the fully connected layer, we take G 112N+++++ for = 1,..., m, i 1,...... 2N + 3 and 0 otherwise. We let 12N+3 = (I,1,..., 1)" E 12, Specifically, the matrix in the last layer takes the form of
(J+1)
12N+3
0 O2N+3
O2N +3
O2N+3
O 12N+3
O2N+3
F(J+)=
(3)
O O2N43
O O2N43
12N+3
where F(J+)) E ((2N++)mx((-JS)) for some positive integer E which can be considered as the order of the number of free parameters in the network.
further demonstrate abilities of convolutional structures. The hypothesis space induced by our network is given by
We restrict the full matrix to take a simple form 43
: H.B.S.N = {c. (J+1)
(x)
B. s 2( + 1)BY, Icel S <NB].
(4)
and F(++)) takes the form 3 with || & 1. Here B is a constant depending on the target function space and the filter size S that will be given explicitly Lemma 3.4
2.1 Statistical learning framework
Now we formulate regression problems in the setting of statistical learning theory.
Let X' be the unit ball in Rd, that is, X' = {o ||~||| S 1, E Rd) and y C R. In the non-parametric regression model, we observe iid. vectors I; E X' and n responses y: E R from the model
yi = fr (zt) + Ets
n,
where the noise variables 6 are assumed to satisfy E (G/x:)) and common to assume standard normal distribution for the noise variables. Our goal is recover the function f from the sample (I)))
In statistical learning theory, the regression framework is described by some unknown probability measure on the set 2 = X' x V. The target is to learn the regression function fz(x) given by
fo(x) = f udd(yla),, x E
-1,
where p(y(z) denotes the conditional distribution of at point induced by It is easy to see that these two settings are equivalent by letting
f(())=
For any measurable function, we define the L prediction error as
E( = / (f(x) -
4

---

Published in Transactions on Machine Learning Research (01/2023)
and clearly we know that fp(2) is the minimizer of it among all measurable functions. We assume that the sample D = ((r u)))== is drawn from the unknown probability measure p. Let Px be the marginal distribution of on X' and (12xx11-11) l1-llxxxxxx be the space of px square-integrable functions on X. For any J E 12 by simple calculation we know that
8(f) - E(fo) -
Since the distribution p is unknown, we can not find fo directly. We thus use
fD.H arg min {f()), JEH
(5)
to approximate fo where H is our hypothesis space and ED(f) is defined to be the empirical risk induced by the sample given by
ED(l) == > (((x))))1+ y²)²
The aim of mean squared error analysis to derive convergence rate of I Jollox We assume that lol S M almost everywhere and we have [v((x)] s M. We project the output function f X - IR onto the
interval [-M, M)] by a projection operator
f(x), M,
if M f(x) M, if f(x) > M, if f(z) M,
TMf(x)=
M,
and we consider JMJH our estimator to fa(a). This type of clipping operator has been widely used in various statistical learning papers such as Suzuki (0118;; Oono & Suzuki (2019) Mao et al. 2021
2.2 Additive ridge functions
Additive ridge functions take the following form as
m f(x) - Σ 5=1
go(Es- x),
(6)
where m considered as a fixed constant. For each j. 95(:) : R + R a univariate function and & x represents the inner product R& with Ey E Rd and ||&,|| is boundod by some constant E. Since this constant E would only affect our results in linear way, for simplicity of the proof, we take = 1. Specifically, we require that ||& || < 1 and we take 9, WS ([),, the space of Lipschitz-a functions on [-1, 1] with the semi-norm kw being the Lipschitz constant. We let G = maxj=1,-- m 11 As mentioned before, (6) is also known as additive index models (Yuan) 2011) and related the the projection pursuit regression Friedman & Stuetzze 1981). In particular, when
d and (C,,..., ,.) is permutation matrix, this function class reduces to the additive model (Hastie & Tibshirani 2017) and it reduces to single index model
Duan & Li 1991
Hardle el al. 1993 Ichimura 1993 when 1. More precisely, we consider the function
space
Om.a.GL
m
--((x) Σ gy(E, :::::::: :9 E W2 ([-1,1)), j=1
(7)
0 < ||& < 1, || s G, < L},
and we assume that the target function fp is in the set O

---

Published in Transactions on Machine Learning Research (01/2023)
3
Main results
3.1 Covering number analysis of deep convolutional neural networks
The mean squared error analysis relies on the approximation abilitics and the covering number of the hy- pothesis space. Before presenting the covering mumber analysis for the hypothesis space H. (4), we would need to first state Theorem Fang et al. (2020) which presents the approximation error to functions the space (7) by deep convolutional neural networks.
Theorem 3.1. Let N, d 2 3,
d, J= 3-1 and N N. If θ then there crists deep neural network consisting of J layers of CNNs with filters of length S and bias vectors satisfying P followed by one fully connected layer h(J+1) with width m(2N + 3) and connection matrir F(J+1) defined as such that for some coefficient vector c E 23)(2N43) there holds
m2
| ((+1)) (122).1(110 1(1+1)
Σ
1g N-a
The total number of free parameters N in the network can be bounded as
'dd - 1 + m(2N + +)..
N S (3S 2)
S-1
Remark 3.2. In this convolutional neural nelwork, each lager only contains one filler and padding is not con- sidered. If we use maultiple convolutional filters, then the torget function con be more complicated. As a simple eatension of the additive ridge functions, we can take the target function the form of >f g: gi{Ei. Ci.s xx) if we consider filters each layer. In this paper, the convolutional layers are used to learn the features Ej x and the last fully connected layer is used to approzimate functions Dj- Thus, the some approcimation rate also be achieved for this type of function by two two-layer fully connected networks with the same order of numbers of free puramelers.
To calculate the covering number of our target space, we first need Cauchy bound for polynomials and Victas Formula to bound the infinity norm of filters in each layer. Proofs will be given in supplementary materials. Lemma 3.3. If {Wz) is real sequence supported {0. .O..... K} with WK =1, then all the compler roots of its symbol (2) ΣØ Wyz are bounded by 1 1+ max K-1 [Wyl. the Cauchy Bound of W. If we factorize W into polynomials of degree at most S, then all the coefficients of these factor polynomials are bounded by 2 (1 + ma. K-1 ( [W)1)*
By applying the previous lemma, we are able to bound the magnitude of filters in each layer.
Lemma 3.4. Let 2 < S < d. For the deep convolutional neural networks constructed in this paper with J convolutional layers and fully connected layer satisfying Theorem 3.7 there exists constant B Bg.s.G depending on &, S and G such that || I
B,
-, J1, and |[ S 1, ||c(++D)l S NB,
where B is given by B ==max max 28 (1+ |1+1 )* 4G
S
(5m))
After bounding the filters, we can bound bias vectors and output functions in each layer. Lemma 3.5. Let 2 S S < For the deep convolutional neural networks constructed in this paper with J convolutional layers and fully connected layer satisfying Theorem 3.1 we have for j j= 1, J + that ||00|| 22S + 1) BY' and
|n00 < + 12)$ + +)BB
(8)
After bounding all the filters, bias vectors and output functions in each layer, we can derive a bound for ( as stated in the lemma below. The covering number / (n, H)
covering number of our hypothesis space H. of subset H. of C(X) is defined for r) > 0 to be the smallest integer I such that H contained in the union of I balls in C(X) of radius n, The notation of covering number can also be extended N (n) H, +) where denote some specific metric. C(X') denotes the space of continuous functions on X.

---

Published in Transactions on Machine Learning Research (01/2023)
Lemma 3.6. For N E N and H given in with two constants Cs.dmm.B and S,d.m,. depending S, d, m. B, there holds
1 + B.d.m, Nog Cs.dm. BN log 8
log. (o, H)
for any 0 < 1.
Constants Cs.a.m and C m, depend on m, S and at most in a cubic way. Since we treat m, S and d as fixed constants in our sctting, the covering number affected by N lincar way which the order of free parameters in the last layer. The above lemma shows that the hypothesis space H has a relatively small covering number. Consequently, we able to derive optimal convergence rates for convolutional neural networks.
3.2 Oracle inequality for empirical risk minimization
With the bound of the covering number of the hypothesis space, able to prove the oracle inequality which leads to the estimation error bound combining with approximation error. The following theorem presents the oracle inequality for empirical risk minimizers based on covering number estimates.
Theorem 3.7. Suppose that ly| s M almost everywhere and there erist constants C1, C2 > 0 and some real numbers n,, n2 > 0, such that
log (o, (6) S Cini log + C2nz logn2, n2, 4A >
(9)
Then for any H and 8 > 0, we have
IMMDD foll2x 28+2 ffll
holds
with
probability
at
least
1 - exp (Cnn log 16M
C2nz log
3n8
512M
3nd
exp
16(3M+
(6 14 1
1,l13
+6)
3.3
Mean squared error
By applying Theorem 3.1 and Theorem 3.7 we can obtain our main result on the upper bound of mean squared error.
Thcorem 3.8. Let 2 < S d and H. θ be defined as and 7
If fyll < M almost everywhere
and fp E 9, then for E N, we have
IITMIDNN follox] s C Caax N- N N
n
where the constant C = C......a..B is independent of the sample size and the N. In particular, if we choose = n 1420 then we can get
E ITMNDD -foll Cn log n.
22.
Remark 3.9. The assumption of lyv S M excludes the case of Gaussian noise and can be avoided by applying the oracle inequality Lemma 4 in Schmiddt llieer et al. [202d). However, the above mentioned Lemma requires that the output functions of the neural network model are bounded by some constant F. This constant F is usuolly related to the model complerity and thus may affect convergence rate if stated explicitly.
Proof of Theorem 3.8 We know from Theorem
that there exists some h E H such that || 1h-Spllpa S 9 W We further know that || S M Ca By applying
3.1
|| Th--f,h follog < CCa N where Cam = >E Theorem 3.7 we have
E (FMSDD)) 3 (fp) 2 2
11 +6,

---

Published in Transactions on Machine Learning Research (01/2023)
holds
with
probability
at least
1
exp ( log 16M + C2N
Sne 512M2
exp
Co. (602 m N -220)))
where C1 D, and C2 C S.d.m
If we let.
2 6C am N=2a
then we have
8 (TMfDHH) ( (fp) S 2e,
hold with probability at least 8M
3n exp [CaN log
512M"
exp
32(1M+Ca ) where C3
(Cr log 30% 2aC1 + C2).
We further let
1 log
3n
then we have
8 (TMfD,H) - (fp) 2e,
holds with probability least exp
--
3nd T024M7
exp
3nd
By taking
32(1M +C.
C4 = max
1202 a.m
2048
M² 3
64
(4M + Co.m)²
and 7 22, have
8 (fe) S 1- {
nē (-ca)
PP
for any ē C1 max N 20 Noog N s. Then by letting å 2exp {
nē
we know that
Co
N log N
N log 2
& (TMSDAH) - (fp) S Cg max
n
holds with probability at least 1-
Now we apply EEE - -o PPt
di with E (TMSD.)) E
II Sollpx - We have
- follpx]] < (' 1dt +
poc
-nn
2C4 < 3T,
E
2 eex
dt < T
J
C₁
with T' C4 max { 22 NloR
This finishes the proof with the constant Cs., independent of n
N given by
Css.,m.Ma.BB maxx 1202 a.m:
2048
64 M²Cs,
(4M + Camm))
where C3 (Cr log
SM 30
2aC + CC2, Ci C S,d.m. and C2 s,
3.4 Lower bound for additive ridge functions
In this subsection, we will present the mini-max lower rate for estimating additive ridge functions. We let M(p, @) be the class of all Borel measures p on X' x y such that fp E O. This class M(p, Q) is related to the set of distributions p where data ye drawn from and θ representing the set of target functions. Now we state mini-max lower bound for the class M(p O).
8

---

Published in Transactions on Machine Learning Research (01/2023)
Theorem 3.10. Assume m 2 1, G>> 0 and M 4mG. Let fa(x) be the output of any learning algorithm based on the sample (Tt 1/i ]= then we have
E (l(((()) so(0))
inf sup (cM(n.9)
2 Cm,
L2x
where the constant G only depends on m and G. For more discussion about this constant, please refer the proof of Theorem 3.9 in Appendix.
Since { ..a is essentially polynomial of n, we can obtain a mini-max lower bound for the function in the type of f Q as a direct consequence, where Q(r) can be any polynomial of z. Formally, we define
o' : a, G)
= [f(x)) Σ 93 (Q(x)) E W ([-1,1]),
(10)
0 < |kyll| - 1, ll - &G,lloslws, $ L))
where (xx) denote any polynomial of x.
Corollary 3.11. Assume 1, G 0 and M 2 4mG. Let fa( be the output of any learning algorithm based on the sample {z,, Volm=1 then we have
inf sup
B (1)) f fc(0)
20 2 Cm, 20+1
fn pEM(p.
12x
where the conslanl Cm,G only depends on m and G.
Combining this lower bound with the upper bound in the last section, we know that deep convolutional neural networks followed by one fully connected layer can reach optimal convergence rates for additive ridge functions up log factor. In other words, for estimating fo O, other methods could achieve better rale than the estimator by deep convolutional neural nelworks. Furthermore, due to the special form of ridge functions, we can observe that this rate is dimension independent. Thanks to the simple structure of convolutional ncural networks, we are able to derive small complexity bound and reach this rate with the input dimension appearing in the constant.
4 Conclusion and discussion
In this paper, we consider the regression problem in statistical learning theory by using deep convolutional neural networks. By careful analysis of covering number of deep convolutional neural networks, we show that for additive ridge functions, deep convolutional neural networks followed by one fully connected layer can reach optimal convergence rates (up log factor). With the simple structure and few free parameters of convolutional neural networks, we obtain suitable complexity bound for the hypothesis space and are able to achieve this dimension independent convergence rate with the input dimension appearing in the constant, which shows the superiority of convolutional structure.
In the future we would like to address in what situation convolutional neural networks outperform usual fully connected neural networks concerning approximation abilities. Or can derive optimal approximation rate for larger function classes when considering convolutional neural networks. Convolutional structures have been widely applied to various types of neural networks and have performed outstandingly in the classification problems. However, only few papers consider classification problems from statistical perspective by using fully connected neural nerkorks (Hu et al. 2020 Kim el. al. 2021 Bos & Schnidd-Hieber (022)). Also, there is currently no paper that directly approximates a specific function class (such as Sobolev space) through a twro-dinensional convolutional neural network which is critical for the analysis of statistical learning theory. It would be significant we can theoretically show the superiority of convolutional structures when considering classification problems with two dimensional convolution in the future.

---

Published in Transactions on Machine Learning Research (01/2023)
Acknowledgements
The authors would like to thank the referees for their encouraging comments and constructive suggestions. The first author is supported by the National Natural Science Foundation of China [NSFC-72150002] The second author is supported by the Office of Naval Research [ONR. N00014-22-1-2690) and National Science Foundation [NSF SCALE MoDL (2134209)).
References
Babak Alipanahi, Andrew Delong, Matthew T Weirauch, and Brendan J Frey. Predicting the sequence specificities of dna-and rna-binding proteins by deep learning. Nature biotechnologg, 33(8)8831 838, 2015.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, :8(1):629 681, 2017.
Thijs Bos and Johannes Schmidt-Hieber Convergence rates of deep relu networks for multiclass classification. Xiviv preprinl ar Xiv:22 00969, 2021.
Hung Chen. Estimation of a projection-pune pursuit type regression model. The Annals of Statistics, pp. 142-157, 1991.
Jeng-Min Chiou and Hans-Georg Müller. and variance functions. Scandinavian journal of statistics, (3):3667-338, 2004.
regression with multiple indices and smooth link
Felipe Cucker and Ding Xuan Zhou. Learning theory: on approzimation theory vieupoint, volume 24. Cambridge University Press, 2007.
Stéphane d' A'scoli,, Levent Sagun, Giulio Biroli, and Joan Bruna. Finding the needle in the haystack with convolutions: on the benefits of architectural bias. Advances in Newral Information Processing Systems, 32, 2019.
Persi Diaconis and Mchrdad Shahshahani. On nonlinear functions of linear combinations. SIAM Journal Scienlific and Slalislical Compuling, 5(1):175-11) 1984.
Alexey Dosovitskiy, Lueas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Un- terthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, al. An image is worth 16x16 words:
Transformers for image recognition scale. arXiv preprint XrXiv:2010. 1 11929, 2020.
Naihua Duan and Ker-Chau Li. Slicing regression: link-free regression method. The Annals of Statistics. pp. 505-530, 1991.
Zhiying Fang, Han Feng, Shuo Huang, and Ding-Xual Xuan Zhou. Theory of deep convolutional neural networks ii: Spherical analysis. Neural Networks, 131:154-162, 2020.
Jerome H Friedman and Werner Stuetzle. Projection pursuit regression. Journal of the American statistical Association, 76(376):817-823, 1981.
lan Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT press Cambridge, 2016.
Wolfgang Hardle, Peter Hall, and Hidehiko Ichimura. Optimal smoothing in single-index models. The annals of Statistics, pp. 157-178, 1993.
Trevor J Hastie and Robert J Tibshirani. Generalized additive models. Routledge, 2017.
Juncai He, Lin Li, and Jinchao Xu. Approximation properties of deep relu cnns. arXiv preprint arXiv:2109.000 000000000........111100100000.00 2021.
Geoffrey E Hinton, Simon Osindero, and Yeo- Thy- Teh. A fast learning algorithm for deep belief nets. Neural computation, 1277-1555, 2006.
10

---

Published in Transactions on Machine Learning Research (01/2023)
Tianyang Hu, Zuofeng Shang, and Guang Cheng. Sharp rate of convergence for deep neural network classifiers under the teacher-student setting. orviv preprint ar orXiv22001006992 2020.
Hidehiko Ichimura. Semiparametric least squares (sls) and weighted sls estimation of single-index models.
Journal of econometrics, 58(12))77 1993.
Masaaki Imaizumi and Kenji Fukumizu. Deep neural networks learn non-smooth functions effectively. In The 22nd international conference on artificial intelligence and statistics, pp. 869-878. PMLR, 2019.
Yongdai Kim, Ilsang Ohn, and Dongha Kim. Fast convergence rates of deep neural networks for classification.
Neural Networks, 138:179 197, 2021.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv:1422. 6980, 2014.
ar preprint
Jason M Klusowski and Andrew R Barron. Risk bounds for high sigh-dimensional ridge function combinations including neural networks. arXi preprint 167.:440,. 2016.
Jason M Klusowski and Andrew R. Barron. Minimax lower bounds for ridge combinations including neural nets. In 2017 IEEE International Symposium on Information Theory (ISIT), pp. 1376-1380. IEEE, 2017.
Quoe V Le, Jiquan Ngiam, Adam Coates, Ahbik Lahiri, Bobby Prochnow, and Andrew Y Ng. On optimiza- tion methods for deep learning. In ICML, 2011.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521((553))433 444, 2015.
Shao-Bo Lin, Kaidong Wang, Yao Wang, and Ding-Xuan Zhou. Universal consistency of deep convolutional neural networks. areee preprint orXiv:2106. 12498, 2021.
Tong Mao, Zhongjie Shi, and Ding-Xuan Zhou. Theory of deep convolutional neural networks ii:: Approxi- mating radial functions. Neural Networks, 2021.
Bchnam Neyshabur. Towards learning convolutions from scratch. Advances in Neural Information Processing Systems, 33:8078-8088 2020.
Kenla Oono and Taiji Suzuki. Approximation and non-parametric estimation of resnet-lype convolutional netral networks. In International Conference Machine Learning, pp. 4922 29311. PMLR, 2019.
Philipp Petersen and Felix Voigtlaender. Optimal approximation of piecewise smooth functions using deep relu neural networks. Newral Networks, 108:296 330, 2018.
Philipp Petersen and Felix Voigtlaender. Equivalence of approximation by convolutional neural networks and fully-connected networks. Proceedings of the American Mathematical Society, 148(4):1567 1581, 2020.
Lingyan Ruan and Ming Yuan. Dimension reduction and parameter estimation for additive index models. Statistics and its Interface, 3(4):493-44) 499,, 2010.
Jürgen Schmidhuber. Deep learning in neural networks: An overview. Newral networks, 61:85 117, 2015.
Johannes Schmidt-Hieber et al. Nonparametric regression using deep neural networks with relu activation function. Annals of Statistics, 48(4))1875-1897, 2020.
Taiji Suzuki. Adaptivity of deep relu network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality. arXiv preprint arXim:1810.0801 2018.
Alexandre B Tsybakov. Introduction to nonperumetric estimation. Springer Science & Business Media, 2008
Ashish Vaswani, Noam Shazoer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
11

---

Published in Transactions on Machine Learning Research (01/2023)
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94:103- 114,
2017.
Ming Yuan. On the identifiability of additive index models. Statistion Sinica, pp. 1901-1911, 2011.
Ding-Xuai Xuan Zhou. Theory of deep convolutional neural networks: Downsampling. Nearal Networks, 124: 319 327, 2020a.
Ding-X Xuan Zhou. Universality of deep convolutional neural networks. Applied and computational harmonic analysis, 48(2):787-77M) 2020b.
Buan Zhou and Kurt Jetter. Approximation with polynomial kernels and svm classifiers. Advances in Computational Mathematics, 25(1):323-2 344, 2006.
Jian Zhou and Olga G Troyanskaya. Predicting effects of noncoding variants with deep learning based sequence model. Nature methods, 12(10))931-934, 2015.
A Appendix: Proof of Main Results
Proof of Theorem 3.1
Proof of Theorem 3.1
The proof of this theorem is a combination of proofs of Lemma 3 and Theorem
Fang et al. 2000 with minor modification. For the completeness of our following results, we present the proof here.
For m N and , }m} with 0 < ||6l12 2 I 1, we take W to be sequence supported in {0, md - 1} given by (G-1)a++a-1) = (6,); where E f1..... ,m} and i E {1,... d}. By Lemma A.2 with M = md - 1, there exists sequence of filters w (w6)] convolutional factorization W = =(() w 1=1 supported in ....... S} with J 2 s satisfying the *.... (( * w!)) Here for j = p + 1....,J.. J, we have taken w to be the delta sequence dg given by (60) = and (6n) = =0 for E Z \ (0). By Lemma A.3
we know
that
TU)TU-D... ... ((11) = (W:=+) JS,K l.... E R(d++5)xd
where TD) is the Toeplitz matrix with filter w for j = 1, 1.2.....JJ
Now construct bias vectors for convolutional layers. We denote ||m|||
E00 -k=-oo /wx/-
We take ((1)
- (I,, 1a, and
300 | (o(e)) 1,) TU)) T (TP. mo(o) 1) Idz-
(11)
for =2,... 2,... .J. The bias vectors satisfy 6--1 =... = -s Observe that ||0]|o S for X. Denote
|| max 112lloo jj =,.,..,, 1,..., 4 for a vector of functions h X + Reg We know that for h X - R4-1
T
$ ( |1bl
Hence the components of (x) satisfy
(11) kd
k= 1.....,,m m, = (Ex, + B(J)
where B() IT [ |||-
For the last fully connected layer, we have
(J+1) ((F((+)))())))))) ((1+11),
12

---

Published in Transactions on Machine Learning Research (01/2023)
with the full matrix F(J+1) stated in 3 The bias vector in the last layer is given by (J+1)
(12222+33) B())+ +h
for = l,...,, m, 1,.... 2N + 3 where t = {tı < .... < 12N+3) is given in Lemma A.1 Then the fully-
connected layer N(++1) (1) E Ik (3((2++3) of the deep network
(J+1) (-1)22443 (15),) 14), for isismmi
(12)
We choose the coefficient vector c Rm(2N+3) by means the linear operator LN
17 as
{ (1)
2N+3
NLN ((0((1)))22>>
j 1,...
Then by the identity
18
have
2N+3
(x)+))xx)
N Σ Σ
(o) D(2N+3343) (15),2) t,)
m
La (gg) ((5)
Combining this with the additive ridge form 6 of f and Lemma A.1 we know that for x X,
[F(x) - --ht))-)
Σ 91 (1E,, x)) Σ Le (0s) (()),)))
10g - Lo(e))ll(-1.1
$
gg gslwa Wo N=
1=1
Then the desired error bound is verified.
Proof of Lemma 3.4
Proof of Lemma 3.4 Since 0 |6 - there exists some l E {1,.... df such that (Em); * 0 and (Em); 0 for any i < 1. Then we know that the soquence W constructed in the proof of Thcorem 3.1 is supported [(m) W, then W satisfies the
in (0. 1} with Wmd-1 = (E.... ) + 0. Now we set a sequence W'
condition in Lemma 3.3 with K md
By Lemma 3.3 all the complex roots of W are located in the and the filters {w(0) } constructed in our networks
disk of radius 1+ max 0... mnd1 [Em]] < 1+ [5m)]
satisfying Lemma A.2 can be bounded
8
< 25
1+
j -= 1.
(Em))
For the matrix F(J+1), we have | from the construction in the proof of Theorem
< 1.
For the vector in the hypothesis space, know that
0c
3.1 we have ||c]loo < 4NG. Then we can take B as
28 (1+
(5m) )
B = max
4G
13

---

Published in Transactions on Machine Learning Research (01/2023)
Proof of Lemma 3.5
Proof of Lemma 3.5 The bias vectors {b6))
j=1 of CNNNs are chosen in the proof of Theorem 3.1 as 6(1)
- -||uo(11|, dd and clearly have |6600|
S (S 1)B I (S + 1) B. For j 2, J have 86))
[TP=] p=1 || 15 - (Ty- ||
1 d Thus, we know that
(66)
2 ((S + +1)11111111111 |
+ ((S 1)B) - 2(15 + 1)BY.
For b(J+1) constructed Theorem 3.1 clearly we have [b(+1)| 00 2 + +1)B)* B)¹ = 1) By
If w, in each layer and F, satisty the restrictions in 1 then by Lipschitz condition of ReLU and the special form of Toeplitz matrix T, we have
S S + 1)B
ho D (x)
+ +
for 1,... J. Combining this with ||((0)
Im. S 1, can obtain by induction
(m) S (2j ()(((+++++)))))) 1)B))
It can be checked easily that the above inequality holds when j J + 1 by the special form of p(J+1).
Proof of Lemma 3.6
Proof of Lemma 3.0 If à (x) is another function from the hypothesis space H induced by
w, b, [(J+1) è satisfying the restrictions in 14 and
(w00) w6) S <.. 10000 - BB601 S
||c - a s 6, p(J+1) - fo(+t)) 50.
00
then by the Lipschitz property of ReLU, we have
(100 A00 $ /T ( (z) -bw) (rr ( 866) 00 0
< | (1(i-1)(z) - 110-1) (x)) + (TTWL) - - 8 (x)) +
for j 1,... , J. Combining the above equation with and the special form of the Toeplitz matrix
Tw/l) - Tiol)) -Tw (t) -065) we know that
|10 - -R00 ||_ S + (1$ (1++1)B[n6--1 -10-- {
+ +SS + 1)8(2) - 1)((S + 1)B)'++
Further by induction and (0) - -2(0) 0, we have
[n0) R000
(( 1)BY',
(2 + 1)BB88 j= j=
14

---

Published in Transactions on Machine Learning Research (01/2023)
For the last fully connected layer and know that
1 (1+1) (
- (0)
- -P
| (z) - (0)
- h (x) 11. +
()B)) + 5(2J + 1)((5 + 1)B) +
15)((5+1)B)b
Finally for the output function, we have
c. h(+11) - è. A
- < (()t)))))))) + |c- (c- (x))))))(x))
<(2N 3)mN 1)B) (2N 3)mo(2J 3)S( + 1)
<6(J² + 4)m + (N) 1)B)
Since J md
S md - I, for the output function, we have
8 8-1
c- h(++)) - 8- -i-ttt < ((S
8.
Then, by taking an ô-net for each of w(t), 663, and p()+1), we know that the covering number of the hypothesis space H with radius & E (0, 1] can be bounded as
N (8HH) -
2B
(8+1)J
-
(2(S 1)BY
25+1
(2 1)B 3+1 m(2++3)
8
8
2N
m12N-3
2
m(2N+33
(S+
(5+1))++1(25++++3mm
2m (35+)) (18
Cs
(n + 1)B) 3mdCs,...m
8
where Cs.d. 5mm²d 2d + 2m) + (md - 1)(mds + md + + Os.a. = 20ssd,m + 5m. Thus we have
log {Nr (8.41) S Cs..m.BNN log [1]
C'Amm log[N},
where C
B 3mdC's.d, log (153md(S + 1)B) C's.,m
Proof of Theorem 3.7
Proof of Theorem 3.7 Since fDH is the empirical minimizer from 2.1 we have ED (fr.)) S. Ep (h) for any h E H and Ep (TMfDM) ED (fD.)). Then we derive
& (TMMDAX) - E (f,) =E E (TMfDH)) - En (TMfNH))
+Ep (TM (T.))H))))))))))))))))))) - En (h)
+ED (h) (h) + (h) - E {sp) SE (TMMfD, - Ep (MMf EED (h) (N) ( - E E(T).
15

---

Published in Transactions on Machine Learning Research (01/2023)
For simplicity, denote
D (H)) E (1) ((,)) = 11 follxx
Si H)) {En (h)) - -E)( 11 (h) - (sp)),
and
S2 (n, H) = (TM..D..) (f,)) - (TM..N)))) ED (f))
Thus we have
8 (TMIDHH) -Ep) D (H) + Si (1, H) S2 (n. H).
Now we define the random variable on Z to be
7(2) (y h(z))² - (y- - fo(x))
and (n) is the variance. Then can be easily derived that In(2)] S (3M + ||bl ) 1 (n)l S
2 (3M + |
2 and (2)))) I E (17) < (3M + [1 D (H)). Then we can apply Lemma A.4 to get
n 2
PIS (n. H) < < 2 1 exp
exxp
(3M + 11 1 (D + 23)
Now we consider a function set.
9 g:= {== (TM -x)) -((()) y)² : SEH).
and for any fixed f E g, there exists an E H such that f(z) = (#Mf(x) y)² - (fp(x) -)) Then we know that E (f) [TM Sollex px and 1 Σ (z:) = En (TM En (Jp) It can be easily derived that
[f(=) < 8M² [f== - E (f) < 16M and E (f²) < 1.M (f). Then we can apply Lemma A.5 to G with
B'= == 16M to get
& ( (S,) (ED (TM ED (So)) SVV.
sup SEN
(13)
(E(TM]) {Jpp) +
holds with probability at least 1 - (c,9,, L (X x x))) exp { {- 512M²
3nc }. Since for any fi, f2 H, we have
f - < 4M (1))) f2(x))
Thus, IM covering of H provides covering of g for any e 0 which implies that
(e, (8 x v)) S N
H. 1 (x))
4M
Combining this with 9 we have
I (X ))) exp { Cmm log
4M
C2n2 lo
c
This together with
13
implies that
1
Sa (n, H) s 2 (E (E(TSD. 8 E(p)) +
holds with confidence at least 1 - exp { [Cimi log 1M + C2n2 log n2
3ne T28
}. Combing all these inequalities,
we have
E (TMSNHH) - (Sp) S 2D (H) + 4c,
holds
with
probability
at
least 1
exp { CCin log 4M + C2ng log n2 128 ]
Sne
exp
We finish the proof by letting = 4e.
2 (3M+IIA (D(N+
16

---

Published in Transactions on Machine Learning Research (01/2023)
Proof of Theorem 3.10
First, we associate a probability measure Ps E Mip, Q pair (n, f) where y is measure on X and E O. We assume that f upper and lower bounded by constants Ti and T2. Now we define probability measure Pf by
Proof of Theorem 3. 3.
T f()) dōr(y) + T T- f(x) dõ (v() dp(x),
dpy(x. v)
(14)
27
2T
where T 4mG and dôr denotes the Dirac delta with unit mass at T. It can be verified that Py is probability measure on X' x y with being the marginal distribution px and f the regression function. Moreover, M 2 4mG ensures ly/ S M almost surely. Hence for any f θ, E O),
Now we would apply Theorem 2.7 in [sybakov 2008 to prove our conclusion. states that if for some N 2 1 and k > 0, fo. ff θ are such that
Ilf:
f, 15llig
on for all 0 Osi<js
1 Σ N KL
(p)) (1))
1 log
N 1=
then there exists a positive constant Ce.ri. such that
12
inf sup E (x)) ( In p
2 CR,T
2a
(15)
L2x
Now we construct a finite sequence fo.... SN. in the space O First, we let function K L2R n Lip a (R) be supported on [-2 2 11 with Lipschitz constant L and | S G. Clearly this function exists. We partition the set [-1, 1] into N, lc, interval (An,)) with equivalent length 2 centers fux N. N.
and C,
2304m
| + 1. Now we define function
157
Vun (I) = [0)==Kk (= - m.)). for le 1,... Nn. Na
It is clear that the (x) are Lipschitz-a functions with Lipschitz constant -لا L for 0 < a 1 for k = I,.... Nn and Il (x) S G. From the definition above, we can also see that for u, # uj, Uu. (x) and via (x) have different supports. Now we consider the set of all binary sequences of length Nn.
Ω = {w = (Wi, ... ,,,.,,),))) wi E (0, = {0, N)
and define functions (x) as
N, Wath (I:).
(x) = Σ
1=1
Now we are going show that (w) Lipschitz-a function with Lipschitz constant L and ()) G for any w. The sup-norm can be check easily by noticing that this is summation on different. supports and wol < 1. Now are going to check the Lipchitz constant. If 20, y An,i, then have
(x)) (v)) |Wa
(v)l & To 1x yl
17

---

Published in Transactions on Machine Learning Research (01/2023)
If x E Ans and y An, for i # and we let I and y be the boundary points of An, and An, between z and y, then we have,
lxw(x) - (w)1
= Wi:th (I) - wythu (v)
S (x)) + |//u, (v)
Mer (a) -//,, (+)
M/, (v)
Muyy (T)
22
L (|x x1"
+
17
1
=2
+
. +
57
<L
2
<L -/
where we have applied Jensen's inequality. Then (x) is Lipschitz-a function with Lipschitz constant L. Since for any E θ it can be written in the form of E gi z) with 9i W [=[,111]. Now we simply take m = 1. & = [1. 0. ... 0] and (z()) ow Then we denote fa(z) (w()) where 21 is the first component of E R and clearly we know that su E.
For any uk, we have |/ 112 urا | We use Ham(w, = EE I (wx * w/) denote the Hamming distance between the binary sequences w and w' We know that
2
I Sw 11 = Ham(w,
NA --1+ ||
By the Varshamor-Gilbee bound (Lemma 2.9 in Tsybakov 2008 we conclude that there exists subset W Ω of cardinality [W] 2 2 f such that Ham(w, w²) 2 N. for all w, E W, w'. Then have
11 1l 2
N N' 20 | for ws w W,w + w.
Further, we know that
Ilfw - fwr 1223x मम, for w. W,w w'
by taking tr || The above inequality verifies the condition 1 in Theorem 2.7 in Tsybakov h2088.
For simplicity, we use fi to denote fat. Now we consider the KT-divergence KI. (ps,) By the euation 14h, we have dp u) = g(ø, y)dp,, (I, y) with
T + sign(y)f(()) T + sign(y))s(tr
sign(y)(f: fj).
g( u)
1+
T +iignyy)ss
Then we know that
KL (p.lPs))
/ T' + +((())
In 1 f((z)
2T
T+ fz(2)
x
T - -f(z))
f((x)-f((e
In
1+
dp((z)
2T
T Tz)
f((x)) f5(x)
(T+
T T-(((x)
T T- fz())) dx(x)
X 2T
T T fz())
I1.f - 11
1572
Since KL (0%10%))
<
1 n [| - S, Sullig we have
18

---

Published in Transactions on Machine Learning Research (01/2023)
KL (p7l0%,)
16n
Ilf - f5l1
1572 n
16T
2
nHam(w, w²)
||
157
N22+2a
2304T1
n Ñr
|K|
157
N1+2a
72
By
2304m 157
| 1, we know that
log W
KL (0%,00%,
72
9
Then two conditions of inequality
13 are satisfied by taking [W] = N. Then we have
inf sup B El(fx(0) fp(()) In PEM(p.)
CR, m2 S0TT
L2x
The proof can be applied directly Corollary 3.11 by noticing that 21 is polynomial of input x. For simplicity, ||| be chosen to be 1. We know that Ti and 72 actually upper and lower bounds of simply take = and 72 TOO Since k is a
marginal density of 2ı, the first component of 2, thus constant depending on m and G, the constant Cu. essentially depends on m and G.
This finishes the proof.
Auxiliary Lemmas
Lemma A.1. Fang et al. [-1 No 1+1+ N
(0200) N
Given an integer N, let t = [ the uniform mesh on Construct a linear operator L, on C[-1, 1] by
with 1
2N+2
[(()(u== = Σ ((4)).H)) /El-1.1),&CC(11,,
where 8, E CCR), == 2,... 2N 2, given by
8,(1) N(a (u 4--1) 20 (u 4:) a (u (441)).
(16)
Then for g E C[, [4. [|ol|c[-1.] and
[TT+(g) glcc--1.11 2w (g. 1/N),
where w(g.p) p) is the modulus of continuity of given by
w(g. sup {lg(v) + - |
For the convenience of counting free parameter numbers, we introduce a linear operator LN : R2++1 R2N+3 given for Ç (N+) R2N+1 by
for i = 1,
G 2(2,
for 2,
(Cx(()),
G-11 2Ç C1+1,
for 3 < <i5 2N + 1,
(17)
(2N+1 2C2N+2
for i = 2N - 2,
C2N+2:
for 2N + 3.
19

---

Published in Transactions on Machine Learning Research (01/2023)
An important property of the operator LN is to express the approximation operator Lt C[-1, in terms of for (-
1=) 2N+3
2N+3
L(f) = N Σ (EN (1F(W))))2) (4), Vf 1=1
(18)
Lemma A.2. Zhou 2020b) Let S 523 and W (Wi) be sequence supported in {0, ,M with
M O. Then there erists a finite sequence of filters {wlr} j=1 each supported , ,S} with p S 3 such that the following convolutional factorization holds true
W = wiP) * w(p-1) 1) .... w * w()).
Lemma A.3.
Zhou 2020b)
Let {w(
lk=1 be a set of sequences supported in {0, 1,, Then
S}..
p())...p(2)T (1))T(1) T(J.)) = ( (R(+Jssxd
(19)
is Toeplitz matria associated with the filter W w(l) w12) w(t) supported in 10,1,... ,S}.
Lemma A.4. Cucker & Zhou [2007]] Let be rundom variable probabilily space Z with mean E(n) ,,, variance o² (n) = o², and satisfying (m(2) E()) I Bn for almost E 2. Then for any > 0,
IP
n(2)) = 2 21
exp exp {
mE
2
B,cc)
Lemma A.5.
Zhou & Jetter
[2006)] Let G be set of continuous functions Z such that for some B' > 0,
き> 0, f - (f)
< B' almost surely and E (f2) I 2B (f) for all f f G. Then for any > 0,
E (f)
(X)) 1 Em { vc SN(G,,
P
sup jeg
2c + 2B' 3
V (f)+c
20


Reviews:
[{"review_id": "ihdZzt99Cs", "reviewer": "Reviewer_eRfE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I finds this result interesting. But I am also interested in more potential extensions to the result, specifically on the following aspects: (Of course, may not necessary for the current paper)\n\nThe training: this paper studies the properties of the minimizer of empirical loss. Surely this is standard practice in statistical learning theories. However, for neural networks it is hard to guarantee that the minimizer can be found. How do the authors comment on the optimization issue? Is it still possible to derive similar bounds when optimization is taken into consideration, even just for very simple networks?\n\nThe input shape: Convolutional neural networks are usually applied on two-dimensional arrays (images). Can the analysis be extended to image inputs?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the learning ability of convolutional neural networks followed by one fully connected layer and shows a minimax rate for learning ridge functions using the minimizer of the empirical loss function. To achieve the result, the authors base the analysis on an existing approximation result, made careful estimate to the magnitude of the filtered, and derived a bound for the cover number.\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have no required changes for the authors. It will be great if the authors can make some discussion on the two questions I listed above.", "broader_impact_concerns": "I have no concerns on the broader impact of this paper. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6Sj7iNzn7r", "reviewer": "Reviewer_aznz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\nThe authors combine different ingredients to derive the results.\n1. The covering number is derived using standard tools on this topic. A concentration-type inequality is then proven (Thm3.6) which will be a key factor in the main results.\n2.  The authors then opportunely use exiting results on the approximation rates in the case of an additive ridge function and well-defined hypothesis class that consists of stacked convolutional layers followed by a fully-connected layer.\n3. Using standard regression analysis, the authors derive an upper bound on the mean squared error (Thm3.7) and a mini-max lower rate (Thm3.9).\n4. In addition to these technical contributions, the paper is well written and easy to follow. The proofs are concise and rigorous.\n\n### Weaknesses\n\nI have a few questions regarding the main results.\n\n1. **Is it really a CNN analysis?** The hypothesis class consists of neural networks constructed with multiple convolutional layers followed with a fully-connected layer. I have read the proofs in Fang et al. (2020) and it seems that the only time the convolutional structure was used is to approximate a linear function of type $\\xi \\cdot x$ (see e.g. Lemma 5 in Fang et al. (2020)). This works in this case because the target function has the special additive ridge form which. Hence, is this result really leveraging the Convolutional structure? Another thing that got my attention is the dependence of the approximation rate in Thm3.1 (Thm2 in Fang et al.) on the number of parameters in the model. Achieving zero approximation rate requires only $N$ to go to infinity, which is exaclty the number of parameters in $c$ (a.k.a the output layer, right after the fully-connected one). The convolutional layers can have a fixed number of parameters and we still achieve a perfect match. As such, it seems that the role of convolutions here is just to replicate the linear operations of type $\\xi \\cdot x$ which is readily available if we just use a linear layer. \n    \n2. **What happens if we were to replace CNN with Fully-Connected?** could the authors provide some insights on how things will change if we consider a simple hypothesis class consisting of a single hidden layer fully connected neural networks? I assume the same approximation rates (if not better) should be achieved when the target function is a ridge additive function. \n    \n3. **What happens with multiple filters?** The hypothesis class used to obtain the results consists of convolutional layers with single filters. In practice, a convolutional layer usually have multiple filters, and the output of the layer is just a sum over the convolution operations with the different filters. Could you provide some insights on how the results would change if the hypothesis class incorporates multi-filters convolutional layers?\n    \n    \n4. **What happens with padding?** The hypothesis class consists of a bit weird convolutional networks. The network width grows with depth, and the network is kind of triangular. This is because no padding is considered to preserve the dimensionality of the layers. What happens if, say, we consider circular padding? or just trim the first $S$ rows and the last $S$ rows from the matrix $T^w$?\n    \n    ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the regression properties of a certain form of convolutional neural networks where the target function is an additive ridge function. It provides new theoretical results on the mean squared error. The contributions are as follow:\n\n1. Leveraging existing approximation results in the case of a regression problem with additive ridge target function, the authors obtain an upperbound on the mean squared error by carefully bounding the covering number of the hypothesis class.\n    \n2. A mini-max lower rate is also obtained with this framework.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Overall, there is nothing to criticise about the theoretical correctness of this paper and I think it fits in the scope of TMLR. However, I would like to see a comprehensive discussion/answer to my questions above, as I believe it would clarify better the contributions.\n\n**Other minor changes**: there are multiple claims that I found either inaccurate or wrong:\n\n- In the introduction, the authors claim that `convolutional neural networks are considered as the state-of-the-art  for various tasks such image classification'. While this was true for a long time, it is no longer the case as now Vision Transformers beat ConvNets in many (almost all) standard image tasks.\n        \n- In the problem setting section, the authors claim that \"For convolutional networks, the number of parameters can be decreased dramatically\" because of the weight-sharing property. This is not true in general since in practice, convolutional layers are defined with multiple filters, and with a large number of filters, the convnet can exceed the fully-connected network in the number of parameters. I would not use this as a selling point for the theoretical analysis of ConvNets.\n\n- Other minor issues: I would not use the expression \"extraordinary abilities\", something like \"impressive abilities\" is better. Same for \"delicate covering...\", I suggest \"in-depth analysis ...\". \"The target of mean squared\" $\\to$ \"The aim/goal of mean squared\".", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "W4EZdC6EFh", "reviewer": "Reviewer_ckgW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n\nThe paper considers an interesting problem and is very well written. The developed covering number bounds and excess risk bounds are very interesting to understand the behavior of DCNNs. In particular, the derived bounds are dimension-independent with the input dimension appearing only in the constant.The proofs are easy to follow and seem to be correct except minor issues which can be easily addressed.\n\n**Weakness**\n\nIn the proof of Lemma 3.5 on covering numbers, the authors show\n\n\\begin{align*}\nN(\\hat{\\delta}, H) &\\leq c(1/\\delta)^{(S+1)J}\\prod_{j=1}^J(1/\\delta)^{2S+1}(1/\\delta)^{m(2N+3)}(1/\\delta)^{m(2N+3)}(1/\\delta)^{m(2N+3)}\\\\\\\\\n& \\leq (1/\\delta)^{(S+1)J+2^{-1}(J^2+J)(2S+1)+m(2N+3)(J+3)},\n\\end{align*}\nwhere $c$ is independent of $\\delta$. However, according to the first inequality, the second inequality should be \n$$\nN(\\hat{\\delta}, H) \\leq  (1/\\delta)^{(S+1)J+(2S+1)J+3m(2N+3)}.\n$$\nI would suggest the authors check this computation.\n\nIn the definition of covering number, it has two arguments. However, in the proof of Thm 3.6, it has three arguments.\n\n**Minor comments**\n\n- Lemma 3.5: it seems that $C''_\\{S,dm\\}$ should be $C''_\\{S,d,m,B\\}$\n\n- Section 3.4: \"is drawn from and\"\n\n- Below eq (15): $|||K||_\\infty$ should be $||K||_\\infty$\n\n- page 18: \"is a constant depends on\" should be \"is a constant depending on\"\n\n- Eq (19): the last period should be removed\n\n- Proof of Thm 3.9: \"is an measure\" should be \"is a measure\"\n\n- In the proof of Thm 3.6: the meaning of $\\sigma^2$ is not given.\n\n- In the proof of Thm 3.6: the authors use the notation $E[\\xi]$. In Thm 3.7, the authors use the notation $\\mathbb{E}$. The authors should use a consistent notation for the expectation operator.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the learning ability of deep convolutional neural networks (DCNNs). In more details, the paper considers hypothesis of the form $c\\cdot h^{(J+1)}(x)$, where $c$ is a weight vector and $h^{(J+1)}(x)$ is the output of a DCNN followed by a fully-connected layer. The paper shows that by putting appropriate constraints on the vector $c$ and the weights in DCNNs, the functions of the form $c\\cdot h^{(J+1)}(x)$ can achieve minimax optimal rates (up to log factors) for learning additive ridge functions. This result is derived by computing the covering numbers of the spaces of DCNNs and concentration inequalities to derive estimation error bounds. These estimation error bounds are further combined with the existing approximation error bounds. Matching lower bounds are also presented.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like the authors to address the issues on the computation of covering numbers. I would also request the changes on the typos.", "broader_impact_concerns": "There are no broader impact concerns since this submission is of theoretical nature.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: During the discussion period, the questions and concerns raised by the reviewers are well addressed by the authors. Overall, the reviewers are all positive about the technical contribution and the results obtained.   All the reviewers have recommended its acceptance.    
Decision: Accept (poster)